The goal of this project is to develop and analyze interior- point algorithms for solving large-scale linear programs (LP), quadratic programs (QP), linear complementarity problems (LCP). This research is a continuation of previous work and is motivated by the desire to resolve several theoretical and practical issues concerning interior-point algorithms: (1) Algorithm Termination: to develop efficient termination techniques to "purify" an approximate optimal solution to an (exact) optimal solution, and to improve the complexity result for a class of optimization problems. (2) Average Complexity: to analyze the complexity of interior-point algorithms for solving random problems, and to probabilisticly explain the excellent practical behavior of interior-point algorithms. (3) Asymptotic Convergence: to develop and analyze superlinearly convergent interior-point algorithms, and to improve the algorithms' global and asymptotic complexity results. (4) Decomposition and Column Generation: to develop various decomposition and column generation schemes for solving large-scale practical problems using interior-point algorithms. This project will strengthen some of the results from prior NSF research and explore new techniques and tools for analyzing and improving interior-point algorithms. It will also include developing computer routines for solving application problems arisen in production scheduling and resource allocation.
