Optimization Online


An Active-Set Quadratic Programming Method Based On Sequential Hot-Starts

Travis C Johnson(traviscj***at***traviscj.com)
Christian Kirches(christian.kirches***at***iwr.uni-heidelberg.de)
Andreas Wächter(andreas.waechter***at***northwestern.edu)

Abstract: 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 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 preconditioners. 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. The results 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.

Keywords: nonlinear programming, quadratic programming, active set, hot starts, iterative linear solver, preconditioner, sequential quadratic programming, nonlinear model predictive control

Category 1: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 10/16/2013
Entry Accepted: 10/16/2013
Entry Last Modified: 10/16/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society