Mathematical Sciences: Interior Point Methods for Linear andNonlinear Programming

9305760 POTRA研究了线性规划、二次规划、线性互补问题和几类非线性规划问题的内点算法的计算复杂性和超线性收敛问题。同时考虑了具有可行起点和不可行起点的问题。为了更好地刻画具有良好实际性能的算法，尽可能地用概率复杂性结果来补充最坏情况下的计算复杂性结果。这项研究的目的是为了更好地了解内点方法的实际性能，并最终开发出具有更高数值效率的新的内点算法。内点法的出现使数学规划领域发生了革命性的变化。在理论方面，内点方法已经被用来证明一些重要的优化问题具有多项式的复杂性，这意味着即使在涉及大量变量的情况下，这类问题在计算上也是容易处理的。在实践方面，内点方法已经在几个非常有效的代码中实现，能够解决用经典方法无法解决的经济、科学和技术中出现的大规模问题。本建议的目的是将内点方法推广到新的问题类，并从确定性和概率的角度系统地研究它们的性质。这项研究的成功完成将有助于内点方法理论的新进展，并对高效实用算法的设计产生积极影响。

9305760 Potra The investigator studies the computational complexity and superlinear convergence of interior point algorithms for linear programming, quadratic programming, linear complementarity problems, and some classes of nonlinear programming problems. Both problems with feasible and infeasible starting points are considered. In order to better characterize algorithms with good practical performance, worst case computational aomplexity results are complemented, whenever possible, by probabilistic complexity results. The goal of this study is to better understand practical performance of interior point methods and eventually to develop new interior point algorithms with superior numerical efficiency. The advent of interior point methods has revolutionized the field of mathematical programming. On the theoretical side, interior point methods have been used to prove that some important classes of optimization problems have polynomial complexity, which means that such problems are computationally tractable even when a large number of variables are involved. On the practical side, interior point methods have been implemented in several very efficient codes capable of solving large scale problems arising in economics, science, and technology that cannot be solved with classical methods. The purpose of the present proposal is to extend interior point methods to new classes of problems and to investigate their properties in a systematic way both from a deterministic and a probabilistic point of view. Successful completion of the research will contribute to new advances in the theory of interior point methods with a positive impact on the design of efficient practical algorithms.