A robust algorithm for semidefinite programming

References

• Alizadeh , F. , Haeberly , J.-P. A. and Overton , M. L. 1997 . Complementarity and nondegeneracy in semidefinite programming . Math. Program. , 77 : 111 – 128 .
   Web of Science ®Google Scholar
• Borchers , B. 1999 . CSDP, a C library for semidefinite programming . Optim. Methods Softw. , 11/12 ( 1–4 ) : 613 – 623 . Available at projects.coin-or.org/Csdp
   Web of Science ®Google Scholar
• de Klerk , E. , Peng , J. , Roos , C. and Terlaky , T. 2001 . A scaled Gauss–Newton primal–dual search direction for semidefinite optimization . SIAM J. Optim , 11 ( 4 ) : 870 – 888 . (online)
   Web of Science ®Google Scholar
• Dennis Jr , J. E. and Schnabel , R. B. 1996 . “ Numerical methods for unconstrained optimization and nonlinear equations ” . In Classics in Applied Mathematics , Vol. 16 , Philadelphia , PA : Society for Industrial and Applied Mathematics (SIAM) . (corrected reprint of the 1983 original)
   Google Scholar
• Dennis Jr , J. E. and Wolkowicz , H. 1993 . Sizing and least-change secant methods . SIAM J. Numer. Anal , 30 ( 5 ) : 1291 – 1314 .
   Web of Science ®Google Scholar
• Fong , D. C.-L. and Saunders , M. A. 2010 . “ LSMR: An iterative algorithm for sparse least-squares problems ” . Systems Optimization Laboratory, Stanford University . Report SOL 2010-2
   Google Scholar
• Gonzalez-Lima , M. , Wei , H. and Wolkowicz , H. 2009 . A stable primal–dual approach for linear programming under nondegeneracy assumptions . Comput. Optim. Appl. , 44 ( 2 ) : 213 – 247 .
   Web of Science ®Google Scholar
• Gruber , G. and Rendl , F. 2002 . Computational experience with ill-posed problems in semidefinite programming . Comput. Optim. Appl. , 21 ( 2 ) : 201 – 212 .
   Web of Science ®Google Scholar
• Helmberg , C. , Rendl , F. , Vanderbei , R. J. and Wolkowicz , H. 1996 . An interior-point method for semidefinite programming . SIAM J. Optim. , 6 ( 2 ) : 342 – 361 .
   Web of Science ®Google Scholar
• Knuth , D. E. 1994 . The sandwich theorem . Electron. J. Combin. , 1 : 48
   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 ( 1 ) : 86 – 125 .
   Web of Science ®Google Scholar
• Kruk , S. and Wolkowicz , H. 2003 . Convergence of a short-step primal–dual algorithm based on the Gauss–Newton direction . J. Appl. Math. , 2003 ( 10 ) : 517 – 534 .
   Google Scholar
• Kruk , S. , Muramatsu , M. , Rendl , F. , Vanderbei , R. J. and Wolkowicz , H. 2001 . The Gauss–Newton direction in semidefinite programming . Optim. Methods Softw. , 15 ( 1 ) : 1 – 28 .
   Web of Science ®Google Scholar
• Laurent , M. and Rendl , F. 2005 . “ Semidefinite programming and integer programming ” . In Handbook on Discrete Optimization , Edited by: Aardal , K. , Nemhauser , G. and Weismantel , R. Amsterdam , , Netherlands : Elsevier B.V .
   Google Scholar
• Lovász , L. 1979 . On the Shannon capacity of a graph . IEEE Trans. Inform. Theory , 25 ( 1 ) : 1 – 7 .
   Web of Science ®Google Scholar
• Malick , J. , Povh , J. , Rendl , F. and Wiegele , A. 2009 . Regularization methods for semidefinite programming . SIAM J. Optim , 20 ( 1 ) : 336 – 356 .
   Web of Science ®Google Scholar
• Mangasarian , O. L. 1969 . Nonlinear Programming , New York : McGraw-Hill .
   Google Scholar
• Mittelmann , H. D. 2003 . An independent benchmarking of SDP and SOCP solvers . Math. Program , 95 ( 2, Series B ) : 407 – 430 .
   Web of Science ®Google Scholar
• Monteiro , R. D.C. 1997 . Primal–dual path-following algorithms for semidefinite programming . SIAM J. Optim , 7 ( 3 ) : 663 – 678 .
   Web of Science ®Google Scholar
• Monteiro , R. D.C. and Todd , M. J. 2000 . “ Path-following methods ” . In Handbook of Semidefinite Programming , 267 – 306 . Boston , MA : Kluwer Academic Publication .
   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 ) : 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
• Paige , C. C. and Saunders , M. A. 1982 . LSQR: An algorithm for sparse linear equations and sparse least squares . ACM Trans. Math. Software , 8 ( 1 ) : 43 – 71 .
   Web of Science ®Google Scholar
• Todd , M. J. 1999 . A study of search directions in primal–dual interior-point methods for semidefinite programming . Optim. Methods Softw. , 11&12 : 1 – 46 .
   Web of Science ®Google Scholar
• Wei , H. and Wolkowicz , H. 2010 . Generating and solving hard instances in semidefinite programming . Math. Program. , 125 ( 1 ) : 31 – 45 .
   Web of Science ®Google Scholar
• Wolkowicz , H. 2004 . Solving semidefinite programs using preconditioned conjugate gradients . Optim. Methods Softw. , 19 ( 6 ) : 653 – 672 .
   Web of Science ®Google Scholar