Optimization Online


An Iterative Solver-Based Infeasible Primal-Dual Path-Following Algorithm for Convex QP

Zhaosong Lu (zhaosong***at***isye.gatech.edu)
Renato Monteiro (monteiro***at***isye.gatech.edu)
Jerome O'Neal (joneal***at***isye.gatech.edu)

Abstract: In this paper we develop an interior-point primal-dual long-step path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of an iterative (linear system) solver. We propose a new linear system, which we refer to as the \emph{augmented normal equation} (ANE), to determine the primal-dual search directions. Since the condition number of the matrix associated with the ANE may become large for degenerate CQP problems, we use a maximum weight basis preconditioner introduced by Resende and Veiga to better condition this matrix. Using a result obtained by Monteiro, O'Neal, and Tsuchiya, we establish a uniform bound, depending only on CQP data, on the number of iterations required for the iterative solver to obtain a sufficiently accurate solution to the ANE. Since the iterative solver can only generate 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 Newton 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.

Keywords: Convex quadratic programming, iterative solver, inexact search directions, polynomial convergence.

Category 1: Linear, Cone and Semidefinite Programming (Other )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, May 2004.

Download: [Postscript][PDF]

Entry Submitted: 05/04/2004
Entry Accepted: 05/04/2004
Entry Last Modified: 05/04/2004

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 Programming Society