An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners

Zhaosong Lu, Renato D.C. Monteiro, Jerome W. O'Neal

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors' previous paper [Z. Lu, R.D.C. Monteiro, and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17(1) (2006), pp. 287-310], we propose a new linear system, which we refer to as the hybrid augmented normal equation (HANE), to determine the primal-dual search directions. Since the iterative linear solver can only generate an approximate solution to the HANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a recipe to compute an inexact primal-dual search direction, based on a suitable approximate solution to the HANE. The second difference between this paper and [Z. Lu, R.D.C. Monteiro, and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17(1)(2006), pp. 287-310] is that, instead of using the maximum weight basis (MWB) preconditioner in the aforesaid recipe for constructing the inexact search direction, this paper proposes the use of any member of a whole class of preconditioners, of which the MWB preconditioner is just a special case. The proposed recipe allows us to: (i) establish a polynomial bound on the number of iterations performed by our path-following algorithm and (ii) establish a uniform bound, depending on the quality of the preconditioner, on the number of iterations performed by the iterative solver.

Original languageEnglish (US)
Pages (from-to)123-143
Number of pages21
JournalOptimization Methods and Software
Volume24
Issue number1
DOIs
StatePublished - Feb 2009
Externally publishedYes

Bibliographical note

Funding Information:
Z. Lu was partially supported by SFU Presidential Grant and NSERC Discovery Grant. R.D.C. Monteiro was partially supported by NSF Grants CCR-0203113 and CCF-0430644 and CCF-0808863 and ONR Grants N00014-05-1-0183 and N00014-08-1-0033. J.W. O’Neal was supported in part by the NDSEG Fellowship Program sponsored by the Department of Defense.

Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

Keywords

  • Convex quadratic programming
  • Hybrid augmented normal equation
  • Inexact search directions
  • Interior-point methods
  • Iterative linear solver
  • Polynomial convergence
  • Primal-dual path-following methods

Fingerprint Dive into the research topics of 'An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners'. Together they form a unique fingerprint.

Cite this