An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners

References

• Anstreicher , K. M. 1999 . Linear programming in O(n3L/ln n) operations . SIAM J. Optim. , 9 ( 4 ) : 803 – 812 .
   Web of Science ®Google Scholar
• Baryamureeba , V. and Steihaug , T. On the convergence of an inexact primal-dual interior point method for linear programming . J. Optim. Theory Appl. , to appear
   Google Scholar
• Baryamureeba , V. , Steihaug , T. and Zhang , Y. 1999 . “ Properties of a class of preconditioners for weighted least squares problems ” . In Tech. Rep , Vol. 16 , Department of Computational and Applied Mathematics, Rice University .
   Google Scholar
• Bergamaschi , L. , Gondzio , J. and Zilli , G. 2004 . Preconditioning indefinite systems in interior point methods for optimization . Comput. Optim. Appl. , 28 ( 2 ) : 149 – 171 .
   Google Scholar
• Freund , R. W. , Jarre , F. and Mizuno , S. 1999 . Convergence of a class of inexact interior-point algorithms for linear programs . Math. Oper. Res. , 24 ( 1 ) : 50 – 71 .
   Google Scholar
• Gonzaga , C. C. 1989 . “ An algorithm for solving linear programming problems in O(n3L) operations ” . In Progress in Mathematical Programming: Interior-Point and Related Methods 1 – 28 . ch. 1
   Google Scholar
• Greenbaum , A. 1997 . Iterative Methods for Solving Linear Systems . SIAM ,
   Google Scholar
• Karmarkar , N. 1984 . A new polynomial-time algorithm for linear programming . Combinatorica , 4 : 373 – 395 .
   Web of Science ®Google Scholar
• Kelley , C. T. 1995 . Iterative Methods for Linear and Nonlinear Equations . SIAM ,
   Google Scholar
• Kojima , M. , Megiddo , N. and Mizuno , S. 1993 . A primal-dual infeasible-interior-point algorithm for linear programming . Math. Program , 61 ( 3 ) : 263 – 280 .
   Google Scholar
• Kojima , M. , Mizuno , S. and Yoshise , A. 1989 . A polyonimal-time algorithm for a class of linear complementarity problems, . Math. Program , 44 ( 1 ) : 1 – 26 .
   Google Scholar
• Kojima , M. , Mizuno , S. and Yoshise , A. 1989 . “ A primal-dual interior point algorithm for linear programming ” . In Progress in Mathematical Programming: Interior-Point and Related Methods 29 – 47 . ch. 2
   Google Scholar
• Korzak , J. 2000 . Convergence analysis of inexact infeasible-interior-point algorithms for solving linear programming problems . SIAM J. Optim. , 11 ( 1 ) : 133 – 148 .
   Google Scholar
• Kovacevic-Vujcic , V. V. and Asic , M. D. 1999 . Stabilization of interior-point methods for linear programming . Comput. Optim. Appl. , 14 : 331 – 346 .
   Web of Science ®Google Scholar
• Lu , Z. , Monteiro , R. D.C. and O'Neal , J. W. 2006 . An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming . SIAM J. Optim. , 17 ( 1 ) : 287 – 310 .
   Google Scholar
• Luenberger , D. G. 1984 . Linear and Nonlinear Programming , Addison-Wesley .
   Google Scholar
• Mizuno , S. and Jarre , F. 1999 . Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation, . Math. Program , 84 : 357 – 373 .
   Google Scholar
• Monteiro , R. D.C. and Adler , I. 1989 . Interior path-following primal-dual algorithms, part I: linear programming . Math. Program , 44 : 27 – 41 .
   Web of Science ®Google Scholar
• Monteiro , R. D.C. , O'Neal , J. W. and Nemirovski , A. S. 2004 . A new conjugate gradient algorithm incorporating adaptive ellipsoid preconditioning , Georgia Institute of Technology . Tech. Rep
   Google Scholar
• Monteiro , R. D.C. , O'Neal , J. W. and Tsuchiya , T. 2004 . Uniform boundedness of a preconditioned normal matrix used in interior point methods . SIAM J. Optim. , 15 ( 1 ) : 96 – 100 .
   Google Scholar
• Nesterov , Y. and Nemirovskii , A. 1995 . Interior-Point Polynomial Algorithms in Convex Programming . SIAM ,
   Google Scholar
• Oliveira , A. R.L. and Sorensen , D. C. 1997 . “ Computational experience with a preconditioner for interior point methods for linear programming ” . Department of Computational and Applied Mathematics, Rice University . Tech. Rep. 28
   Google Scholar
• Portugal , L. F. , Resende , M. G.C. , Veiga , G. and Judice , J. J. 2000 . A truncated primal-infeasible dual feasible network interior point method . Networks , 35 : 91 – 108 .
   Google Scholar
• Renegar , J. 1996 . Condition numbers, the barrier method, and the conjugate-gradient method . SIAM J. Optim. , 6 : 879 – 912 .
   Web of Science ®Google Scholar
• Resende , M. G.C. and Veiga , G. 1993 . An implementation of the dual affine scaling algorithm for minimum cost flow on bipartite uncapacitated networks . SIAM J. Optim. , 3 : 516 – 537 .
   Google Scholar
• Toh , K. C. , Tütüncü , R. H. and Todd , M. J. 2005 . “ Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems ” . Cornell University . Tech. Rep
   Google Scholar
• P.M. Vaidya, Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners,Tech. Rep., a talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis
   Google Scholar
• Zhang , Y. 1994 . On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem . SIAM J. Optim. , 4 ( 1 ) : 208 – 227 .
   Google Scholar
• Zhou , G. and Toh , K.-C. 2004 . Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming . Math. Program , 99 : 261 – 282 .
   Web of Science ®Google Scholar