New Active-Set Methods for Optimization and Complementarity Problems

用于优化和互补问题的新活动集方法

• 批准号: 1217153
• 负责人: Daniel Robinson
• 金额: $ 21万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217153&HistoricalAwards=false
• 关键词: New; Active; Set; Methods; Optimization

The principal investigator and his student consider the design, analysis, implementation, and validation of a new class of active-set algorithms for solving large-scale optimization and complementarity problems. In the first part of the project they introduce a new class of rapidly adapting active-set methods in the context of solving large-scale convex quadratic problems. These algorithms benefit if a good initial guess is available and allow for rapid updates to the active-set, which are essential for handling large-scale problems. Consequently, this algorithm not only solves stand-alone quadratic programs, but may allow other methods, e.g., sequential quadratic programming methods, to handle problems that are larger than is currently possible. In the second part of the proposal, they introduce the concept of an acceleration phase, which improves upon existing subspace phases. Subspace phases have been used with great success to enhance basic algorithms for solving various complementarity, variational inequality, quadratic, and nonlinear problems, as well as applications in machine learning and compressed sensing. This success, however, has masked a prevailing weakness: all iterates generated must remain in the subspace. An acceleration phase has the added flexibility of selectively enlarging the subspace, when deemed necessary. In the final part of the project, they consider a new fast and robust active-set algorithm for solving complementarity problems. Efficiency and reliability are acquired by (i) utilizing a special property of the Newton-like direction that holds in this setting to formulate an improved search procedure; and (ii) suggesting a simple framework that allows for acceleration phases to be incorporated naturally.The new active-set framework, convergence results, and freely available software will have a large sphere of influence by aiding in solving challenging problems arising in the design of large complex systems. In particular, they will serve as useful tools for the future design and development of new highly-efficient algorithms for solving large-scale real-world problems related to energy transmission, trajectory optimization, optimal control, contact problems in computational mechanics, regularized machine learning problems, and various equilibrium problems associated with traffic flow, optimal design, and the pricing of energy. For example, their work will help answer questions such as "How can we plan for energy transmission infrastructure that accounts for uncertainties such as the location and type of future energy generation, technology, policy, and economic development?" The improved optimization tools provided by the principal investigator and his student will aid regulators and regional transmission organizations to develop more robust investment plans that may save the consumers millions of dollars every year.

主要研究者和他的学生考虑设计，分析，实现和验证一类新的有效集算法，用于解决大规模优化和互补问题。 在该项目的第一部分，他们介绍了一类新的快速适应有效集方法的背景下，解决大规模凸二次问题。这些算法的好处，如果一个好的初始猜测是可用的，并允许快速更新的活动集，这是必不可少的处理大规模的问题。 因此，该算法不仅解决了独立的二次规划，而且可以允许其他方法，例如，序列二次规划方法，以处理问题，是比目前可能的。 在提案的第二部分中，他们引入了加速阶段的概念，该阶段改进了现有的子空间阶段。 子空间相位已被成功地用于增强解决各种互补、变分不等式、二次和非线性问题的基本算法，以及在机器学习和压缩传感中的应用。 然而，这种成功掩盖了一个普遍存在的弱点：所有生成的迭代都必须保持在子空间中。 加速阶段具有额外的灵活性，可以在认为必要时选择性地扩大子空间。 在项目的最后一部分，他们考虑了一个新的快速和强大的有效集算法来解决互补问题。 效率和可靠性是通过（i）利用在这种设置下保持的类牛顿方向的特殊性质来制定改进的搜索过程;以及（ii）提出了一个简单的框架，该框架允许加速阶段被自然地并入。新的活动集框架，收敛结果，而免费提供的软件将通过帮助解决大型复杂系统设计中出现的挑战性问题而具有很大的影响范围。 特别是，它们将成为未来设计和开发新的高效算法的有用工具，用于解决与能量传输，轨迹优化，最优控制，计算力学中的接触问题，正则化机器学习问题以及与交通流，最优设计和能源定价相关的各种平衡问题有关的大规模现实问题。 例如，他们的工作将有助于回答这样的问题，如“我们如何规划能源传输基础设施，考虑到不确定性，如未来能源发电的位置和类型，技术，政策和经济发展？“首席研究员和他的学生提供的改进的优化工具将帮助监管机构和区域输电组织制定更稳健的投资计划，每年可为消费者节省数百万美元。