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.