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.