Active-Set and Interior Algorithms for Non-Linear Optimization

点击翻译按钮获取中文摘要

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.