On the complexity analysis of a Mehrotra-type primal–dual feasible algorithm for semidefinite optimization

References

• Alizadeh , F. 1991 . Combinatorial optimization with interior-point methods and semi-definite matrices , Minneapolis, MN : Computer Science Department, University of Minnesota . Ph.D. thesis
   Google Scholar
• Alizadeh , F. 1995 . Interior point methods in semidefinite programming with applications to combinatorial optimization . SIAM J. Optim. , 5 : 13 – 51 .
   Web of Science ®Google Scholar
• Alizadeh , F. , Haeberly , J. A. and Overton , M. 1998 . Primal–dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results . SIAM J. Optim. , 8 : 746 – 768 .
   Web of Science ®Google Scholar
• Boyd , S. 1994 . Linear Matrix Inequalities in System and Control Theory , Philadelphia, PA : SIAM .
   Google Scholar
• de Klerk , E. 2002 . Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications , Dordrecht, , The Netherlands : Kluwer Academic Publishers .
   Google Scholar
• de Klerk , E. , Roos , C. and Terlaky , T. 1997 . Initialization in semidefinite programming via a self-dual, skew-symmetric embedding . OR Lett. , 20 : 213 – 221 .
   Google Scholar
• Helmberg , C. 1996 . An interior-point method for semidefinite programming . SIAM J. Optim. , 6 : 342 – 361 .
   Web of Science ®Google Scholar
• Horn , R. A. and Johnson , C. R. 1990 . Matrix Analysis , New York : Cambridge University Press .
   Google Scholar
• Jarre , F. 1993 . An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices . SIAM J. Control Optim. , 31 : 1360 – 1377 .
   Web of Science ®Google Scholar
• Kojima , M. , Shida , M. and Shindoh , S. 1998 . Local convergence of predictor–corrector infeasible-interior-point algorithms for SDPs and SDLCPs . Math. Program. , 80 : 129 – 160 .
   Web of Science ®Google Scholar
• Kojima , M. , Shindoh , S. and Hara , S. 1997 . Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices . SIAM J. Optim. , 7 : 86 – 125 .
   Web of Science ®Google Scholar
• Luo , Z.-Q. , Sturm , J. F. and Zhang , S. 1998 . Superlinear convergence of a symmetric primal–dual path-following algorithm for semidefinite programming . SIAM J. Optim. , 8 : 59 – 81 .
   Web of Science ®Google Scholar
• Merhrotra , S. 1992 . On the implementation of a (primal–dual) interior point method . SIAM J. Optim. , 2 : 575 – 601 .
   Google Scholar
• Mizuno , S. , Todd , M. J. and Ye , Y. 1993 . On adaptive step primal–dual interior-point algorithms for linear programming . Math. Oper. Res. , 18 : 945 – 981 .
   Google Scholar
• Monteiro , R. D.C. 1997 . Primal–dual path-following algorithms for semidefinite programming . SIAM J. Optim. , 7 : 663 – 678 .
   Web of Science ®Google Scholar
• Monteiro , R. D.C. and Zhang , Y. 1998 . A unified analysis for a class of long-step primal–dual path-following interior-point algorithms for semidefinie programming . Math. Program. , 81 : 281 – 299 .
   Web of Science ®Google Scholar
• Nesterov , Y. E. and Nemirovsky , A. S. 1994 . Interior Point Methods in Convex Programming: Theory and Applications , Philadelphia, PA : SIAM .
   Google Scholar
• Nesterov , Y. E. and Todd , M. J. 1997 . Self-scaled barriers and interior-point methods for convex programming . Math. Oper. Res. , 22 : 1 – 42 .
   Web of Science ®Google Scholar
• Nesterov , Y. E. and Todd , M. J. 1998 . Primal–dual interior-point methods for self-scaled cones . SIAM J. Optim. , 8 : 324 – 364 .
   Web of Science ®Google Scholar
• Potra , F. A. and Sheng , R. 1998 . A superlinearly convergent primal–dual infeasible-interior-point algorithm for semidefinite programming . SIAM J. Optim. , 8 : 1007 – 1028 .
   Web of Science ®Google Scholar
• Roos , C. , Terlaky , T. and Vial , J.-Ph. 2006 . Interior Point Methods for Linear Optimization , 2 , Boston : Springer Science .
   Google Scholar
• Salahi , M. , Peng , J. and Terlaky , T. 2007 . On Mehrotra-type predictor–corrector algorithms . SIAM J. Optim. , 18 : 1377 – 1397 .
   Web of Science ®Google Scholar
• Sheng , R. , Potra , F. A. and Ji , J. 1996 . “ On a general class of interior-point algorithms for semidefinite programming with polynomial complexity and superlinear convergence ” . Vol. 89 , Iowa City, IA : Department of Mathematics, The University of Iowa . Report. Comput. Math.
   Google Scholar
• Sturm , J. F. 1999 . Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones . Optim. Methods Softw. , 11–12 : 625 – 653 .
   Web of Science ®Google Scholar
• Sturm , J. F. and Zhang , S. 1998 . On the long-step path-following method for semidefinite programming . Oper. Res. Lett. , 22 : 145 – 150 .
   Google Scholar
• Sturm , J. F. and Zhang , S. 1999 . Symmetric primal–dual path-following algorithms for semidefinite programming . Appl. Numer. Math. , 29 : 301 – 315 .
   Web of Science ®Google Scholar
• Toh , K. C. , Todd , M. J. and Tütüncü , R. H. 1999 . SDPT3-A Matlab software package for semidefinite programming . Optim. Methods Softw. , 11 : 545 – 581 .
   Web of Science ®Google Scholar
• Vandenberghe , L. and Boyd , S. 1995 . A primal–dual potential reduction method for problems involving matrix inequalities . Math. Program. , 69 : 205 – 236 .
   Web of Science ®Google Scholar
• Ye , Y. 1990 . A class of projective transformations for linear programming . SIAM J. Comput. , 19 : 457 – 466 .
   Web of Science ®Google Scholar
• Zhang , Y. 1998 . On extending some primal–dual interior-point algorithms from linear programming to semidefinite programming . SIAM J. Optim. , 8 : 365 – 386 .
   Web of Science ®Google Scholar