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

摘要

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.