Optimization Online


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

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

  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