An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners

Zhaosong Lu (zhaosongisye.gatech.edu)
Renato Monteiro (monteiroisye.gatech.edu)
Jerome O'Neal (jonealisye.gatech.edu)

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 \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{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 \cite{ONE04} is that, instead of using the maximum weight basis (MWB) preconditioner in the above 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 above 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.

Keywords: Convex quadratic programming, iterative linear solver, primal-dual path-following methods, interior-point methods, hybrid augmented normal equation, inexact search directions, polynomial convergence

Category 1: Linear, Cone and Semidefinite Programming

Citation: Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205, June 2005

Download: [PDF]

Entry Submitted: 06/29/2005
Entry Accepted: 06/29/2005
Entry Last Modified: 06/29/2005

Modify/Update this entry