An active-set method for quadra tic programming based on sequential hot-starts

Travis C. Johnson, Christian Kirches, Andreas Wächter

Research output: Contribution to journalArticle

4 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)967-994
Number of pages28
JournalSIAM Journal on Optimization
Volume25
Issue number2
DOIs
StatePublished - Jan 1 2015

Keywords

  • Active set
  • Hot-starts
  • Iterative linear solver
  • Nonlinear model predictive control
  • Nonlinear programming
  • Preconditioner
  • Quadratic programming
  • Sequential quadratic programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'An active-set method for quadra tic programming based on sequential hot-starts'. Together they form a unique fingerprint.

  • Cite this