Collaborative Research: Investigation and Development of Active Set Prediction Techniques for Nonlinear Optimization

这项拨款提供资金支持大规模非线性优化的新算法的开发，该算法基于快速估计活动不等式约束。许多重要的非线性优化方法寻求确定哪些不等式约束在解处成立等式，从而将问题简化为等式约束问题。随着不等式约束数量的增加，使用二次规划的标准方法变得太慢了。因此，需要以更有效的方式预测正确的活动约束。本项目中开发的活动集识别技术将基于线性规划子问题的解决方案，并允许活动约束集的估计一次被许多约束改变。新的通用非线性优化算法将利用这些活动集识别技术得到发展。该项目将开发这些算法的软件实现，以及涵盖这些算法的活动集识别的一般理论。如果成功，所提出的研究将允许解决更大的非线性优化模型（特别是具有许多不等式约束的问题），而不是目前使用活动集方法解决的问题。这些更强大的算法可以应用于以前难以处理的模型，如医学成像、分类、信号处理、化学过程控制、电力系统管理、集成电路设计和金融等领域。此外，与内部点方法相比，这样的主动集方法在利用热启动方面更有效。这将有利于快速求解混合整数非线性规划分支定界法中的子问题。作为该项目的一部分，活动集识别的理论框架将为探索未来基于活动集的算法的发展提供基础。

This grant provides funding to support the development of novel algorithms for large-scale nonlinear optimization that are based on fast estimation of active inequality constraints. Many important methods for nonlinear optimization seek to determine which inequality constraints hold as equalities at the solution, so that the problem can be simplified to an equality constrained problem. As the number of inequality constraints grows, the standard approaches, which use quadratic programming, become too slow. Thus one needs to predict the correct active constraints in a more efficient way. The active-set identification techniques developed in this project will be based on the solution of linear programming subproblems and will allow the estimate of the active constraint set to change by many constraints at a time. New general purpose nonlinear optimization algorithms will be developed using these active-set identification techniques. This project will develop software implementations of these algorithms, as well as a general theory of active-set identification that covers these algorithms.If successful, the proposed research will allow for the solution of significantly larger nonlinear optimization models (particularly problems with many inequality constraints) than can currently be solved using active-set methods. These more powerful algorithms may be applied to previously intractable models arising in areas such as medical imaging, classification, signal processing, chemical process control, power systems management, integrated circuit design and finance. In addition, active set approaches like this will be more effective at making use of a warm start compared with interior point methods. This will be beneficial for quickly solving subproblems that arise in branch and bound methods for mixed integer nonlinear programming. The theoretical framework for active-set identification developed as part of this project will provide a basis for exploring the development of future active-set based algorithms.