  


An Iterative SolverBased Infeasible PrimalDual PathFollowing Algorithm for Convex QP
Zhaosong Lu (zhaosongisye.gatech.edu) Abstract: In this paper we develop an interiorpoint primaldual longstep pathfollowing 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 primaldual 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 primaldual search direction satisfying all equations of the primaldual Newton system. We propose a way to compute an inexact primaldual 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 303320205 USA, May 2004. Download: [Postscript][PDF] Entry Submitted: 05/04/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  