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.
