Active-Set and Interior Algorithms for Non-Linear Optimization

西北大学的非线性优化的活动集和内部方法本研究项目的目标是提高非线性优化算法的能力。首先，提出并分析了一种新的活动集算法，克服了传统序列二次规划方法的一些局限性。新算法属于EQP方法的范畴，它将活动集辨识和阶跃计算过程解耦。该算法首先求解线性规划（LP）来提供最优活动集的猜测，然后求解等式约束二次规划（EQP）来尝试实现最优性。新算法的一个关键特征是使用了两个信任区域（一个用于LP阶段，一个用于EQP阶段），它们的行为是准独立的。第二个项目研究了非线性内部方法——大规模优化的另一种主要方法。如何设计一种在实际应用中有效且具有全局收敛性保证的障碍参数控制方法，是目前最困难的算法问题之一。所提出的方法在每次迭代中通过最小化某些“质量函数”来选择屏障参数。计算校正步骤的新策略允许更长的步骤，即使在初始点选择不当的情况下。将开发一种全球化程序，使其尽可能少地干扰屏障参数的自适应选择。作为该项目的一部分开发的软件将有利于优化算法的众多应用领域。在电路仿真、计算化学、金融、基于pde的优化、流量均衡等许多领域都会出现大型优化问题。本项目开发的新算法将大大扩展非线性优化方法的范围和适用性，并将刺激大规模优化发挥关键作用的领域的未来研究。

ABSTRACT0514772Jorge NocedalNorthwestern UniversityActive-Set and Interior Methods for Nonlinear OptimizationThe goal of this research project is to advance the capabilities of algorithms for nonlinear optimization. First, it develops and analyzes a new active-set algorithm that overcomes some of the limitations of traditional sequential quadratic programming (SQP) methods. The new algorithm falls under the category of EQP methods, which decouple the active-set identification and step computation procedures. The algorithm solves a linear program (LP) to provide a guess of the optimal active set, and then solves an equality constrained quadratic program (EQP) to attempt to achieve optimality. A key feature of the new algorithm is the use of two trust regions (one for the LP phase and one for the EQP phase that act quasi-independently.The second project investigates nonlinear interior methods -- the other leading approach for large-scale optimization. Research focuses on one of the most difficult algorithmic questions: how to design aprocedure for controlling the barrier parameter that is effective in practice and is supported by global convergence guarantees. The proposed procedure selects the barrier parameter at every iterationbyminimizing certain "quality functions". New strategies for computing corrector steps allow for longer steps even when the initial point is poorly chosen. A globalization procedure that interferes with adaptive choices of the barrier parameter as little as possible will be developed.The software developed as part of this project will be beneficial in the numerous areas of application of optimization algorithms. Large optimization problems arise in circuit simulation, computational chemistry, finance, PDE-based optimization, traffic equilibrium, and many other areas. The new algorithms developedin this project will significantly expand the range and applicability of nonlinear optimization methods, and will stimulate future research in areas were large-scale optimization plays a crucial role.