An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming

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

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

In this paper we develop a long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. We propose a new linear system, which we refer to as the augmented normal equation (ANE), to determine the primal-dual search directions. Since the condition number of the ANE coefficient matrix may become large for degenerate CQP problems, we use a maximum weight basis preconditioner introduced in [A. R. L. Oliveira and D. C. Sorensen, Linear Algebra Appl., 394 (2005), pp. 1-24; M. G. C. Resende and G. Veiga, SIAM J. Optim., 3 (1993), pp. 516-537; P. Vaida, Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners, Tech. report, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, 1990] to precondition this matrix. Using a result obtained in [R. D. C. Monteiro, J. W. O'Neal, and T. Tsuchiya, SIAM J. Optim., 15 (2004), pp. 96-100], we establish a uniform bound, depending only on the CQP data, for the number of iterations needed by the iterative linear solver to obtain a sufficiently accurate solution to the ANE. Since the iterative linear solver can generate only an approximate solution to the ANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a way to compute an inexact primal-dual search direction so that the equation corresponding to the primal residual is satisfied exactly, while the one corresponding to the dual residual contains a manageable error which allows us to establish a polynomial bound on the number of iterations of our method.

Original languageEnglish (US)
Pages (from-to)287-310
Number of pages24
JournalSIAM Journal on Optimization
Volume17
Issue number1
DOIs
StatePublished - Feb 26 2007
Externally publishedYes

Keywords

  • Augmented normal equation
  • Convex quadratic programming
  • Inexact search directions
  • Interior-point methods
  • Iterative linear solver
  • Maximum weight basis pre-conditioner
  • Polynomial convergence
  • Primal-dual path-following methods

Fingerprint Dive into the research topics of 'An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming'. Together they form a unique fingerprint.

  • Cite this