New Active-Set Methods for Optimization and Complementarity Problems

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

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.