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

合作研究：非线性优化活动集预测技术的研究与发展

• 批准号: 0728190
• 负责人: Richard Byrd
• 金额: $ 23.93万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-15 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728190&HistoricalAwards=false
• 关键词: Collaborative; Research; Investigation; Development; Active

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.

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