Active-Set and Interior Algorithms for Non-Linear Optimization

非线性优化的活动集和内部算法

• 批准号: 0514772
• 负责人: Jorge Nocedal
• 金额: $ 25万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514772&HistoricalAwards=false
• 关键词: Active; Set; Interior; Algorithms; Non

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.

西北大学非线性优化的有效集和内部方法本研究项目的目标是提高非线性优化算法的能力。首先，它开发和分析了一种新的有效集算法，克服了传统的序列二次规划（SQP）方法的一些局限性。新算法福尔斯EQP方法的范畴，它解耦了有效集识别和步长计算过程。该算法求解线性规划（LP）提供一个猜测的最佳活动集，然后求解等式约束二次规划（EQP），试图实现最优性。新算法的一个关键特征是使用两个信赖域（一个用于LP阶段，一个用于EQP阶段，它们准独立地起作用。第二个项目研究非线性内部方法-大规模优化的另一种主要方法。研究集中在一个最困难的算法问题：如何设计一个程序，用于控制的障碍参数，是有效的，在实践中，并支持全局收敛保证。该方法通过最小化某些“质量函数”在每次迭代中选择障碍参数。计算校正步长的新策略允许更长的步长，即使初始点选择不当。一个全球化的程序，干扰自适应选择的障碍参数尽可能少的将被开发。作为这个项目的一部分，开发的软件将是有益的优化算法的应用在众多领域。 大型优化问题出现在电路仿真、计算化学、金融、基于偏微分方程的优化、流量平衡和许多其他领域。本项目所开发的新算法将大大扩展非线性优化方法的应用范围和适用性，并将在未来的激励研究领域中起到至关重要的作用.