## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 287-310 |

Number of pages | 24 |

Journal | SIAM Journal on Optimization |

Volume | 17 |

Issue number | 1 |

DOIs | |

State | Published - 2007 |

Externally published | Yes |

## Keywords

- Augmented normal equation
- Convex quadratic programming
- Inexact search directions
- Interior-point methods
- Iterative linear solver
- Maximum weight basis pre-conditioner
- Polynomial convergence
- Primal-dual path-following methods