AN ACTIVE-SET METHOD FOR QUADRATIC PROGRAMMING BASED ON SEQUENTIAL HOT-STARTS

作者：Johnson Travis C^*; Kirches Christian; Waechter Andreas

来源：SIAM Journal on Optimization, 2015, 25(2): 967-994.

DOI：10.1137/130940384

• nonlinear programming
• quadratic programming
• active set
• hot-starts
• iterative linear solver
• preconditioner
• sequential quadratic programming
• nonlinear model predictive control

A new method for solving sequences of quadratic programs (QPs) is presented. For each new QP in the sequence, the method utilizes hot-starts that employ information computed by an active-set QP solver during the solution of the first QP. This avoids the computation and factorization of the full constraint and Hessian matrices for all but the first problem in the sequence. The proposed algorithm can be seen as an extension of the iterative refinement procedure for linear systems to QP problems, coupled with the application of an accelerated linear solver method that employs hot-started QP solves as a preconditioner. Local convergence results are presented. The practical performance of the proposed method is demonstrated on a sequence of QPs arising in nonlinear model predictive control and during the solution of a set of randomly generated nonlinear optimization problems using sequential quadratic programming. In these experiments, the method proves to be fairly reliable, despite the lack of global convergence guarantees. The results also show a significant reduction in the computation time for large problems with dense constraint matrices, as well as in the number of matrix-vector products.

• 出版日期2015
• 单位西北大学