Interior-point Algorithms - Complexity Issues and Practical Concerns

本计画的目标是发展并分析求解大规模线性规划（LP）、二次规划（QP）、线性互补问题（LCP）的内点算法。本研究是先前工作的延续，其动机是希望解决有关内点算法的几个理论和实践问题：(1)算法终止：开发有效的终止技术，将近似最优解“净化”为（精确）最优解，并提高一类优化问题的复杂性结果。(2)平均复杂度：分析内点算法求解随机问题的复杂度，并概率论地解释内点算法优秀的实用行为。(3)渐近收敛：开发和分析超线性收敛的内点算法，改进算法的全局和渐近复杂度结果。(4)分解与列生成：开发各种分解与列生成方案，利用内点算法求解大规模实际问题。该项目将加强NSF先前研究的一些成果，并探索分析和改进内点算法的新技术和工具。它还将包括开发计算机程序，以解决生产调度和资源分配中出现的应用问题。

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.