ORIE 6327 Spring 2012

Semidefinite Programming References

  • Some useful references. I have hard copy or e-copies of most of these: contact me by e-mail if you're interested.
    There are links to online versions of Math. Progg. or SIOPT which should work if your domain is Cornell.

  • \bibitem{int:Alizadeh5}
    F.~Alizadeh.
    \newblock Interior point methods in semidefinite programming with applications to combinatorial optimization.
    \newblock {\em SIAM Journal on Optimization}, 5:13--51, 1995.
    Online here

  • \bibitem{int:Alizadeh7}
    F.~Alizadeh, J.~A.~Haeberly, and M.~Overton.
    \newblock Complementarity and nondegeneracy in semidefinite programming.
    \newblock {\em Mathematical Programming}, 77:111--128, 1997.
    Online here

  • \bibitem{int:Alizadeh6}
    F.~Alizadeh, J.~A.~Haeberly, and M.~Overton.
    \newblock Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results.
    \newblock {\em SIAM Journal on Optimization}, 8:746--768, 1998.
    Online here

  • \bibitem{int:Anjos1}
    M.~Anjos.
    \newblock Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems.
    \newblock {\em Journal on Satisfiability, Boolean Modeling and Computation}, 1:1--47, 2005.
    Online here

  • \bibitem{AnjosLasserre}
    M.~Anjos and J.~Lasserre, eds.
    \newblock Handbook on Semidefinite, Conic and Polynomial Optimization.
    \newblock Springer, 2012.
    Online here

  • \bibitem{BachocVallentin}
    C.~Bachoc and F.~Vallentin.
    \newblock New upper bounds for kissing numbers from semidefinite programming.
    \newblock {\em J. Amer. Math. Soc.}, 21:909--924, 2008.
    Online here

  • \bibitem{int:Bellman1}
    R.~Bellman and K.~Fan.
    \newblock On systems of linear inequalities in Hermitian matrix variables.
    \newblock In {\em Proceedings of Symposia in Pure Mathematics}, 7, AMS, Providence, 1963.

  • \bibitem{int:BenTal5}
    A.~{Ben--Tal} and A.~S. Nemirovskii.
    \newblock Robust convex optimization.
    \newblock {\em Mathematics of Operations Research}, 23:769--805, 1998.
    Online here.

  • \bibitem{int:Benson2}
    S.~J. Benson and Y.~Ye.
    \newblock DSDP5: Software for Semidefinite Programming.
    \newblock Working paper, Argonne National Laboratories Preprint ANL/MCS-P1289-0905.
    paper

  • \bibitem{int:Benson1}
    S.~J. Benson, Y.~Ye, and X.~Zhang.
    \newblock Solving large-scale sparse semidefinite programs for combinatorial optimization.
    \newblock {\em SIAM Journal on Optimization}, 10:443-461, 2000.
    Online here

  • \bibitem{int:Burer3}
    S.~Burer and R.~D.~C. Monteiro.
    \newblock A nonlinear programming algorithm for solving
    semidefinite programs via low-rank factorization.
    \newblock {\em Mathematical Programming}, 95:329--357, 2003.
    pdf

  • S. Burer, R.D.C. Monteiro and Y. Zhang:
    "Interior-Point Algorithms for Semidefinite Programming
    Based on A Nonlinear Programming Formulation",
    Computational Optimization and Applications 22 (2002) 49-79.
    pdf

  • J.-F. Cai, E.J. Candes and Z. Shen.
    "A singular value thresholding algorithm for matrix completion",
    SIAM J. on Optimization 20(4), 1956-1982, 2008.
    pdf.

  • \bibitem{int:Fujisawa1}
    K.~Fujisawa, M.~Kojima, and K.~Nakata.
    \newblock Exploiting sparsity in primal-dual interior-point methods for semidefinite programming.
    \newblock {\em Mathematical Programming}, 79:235--253, 1997.
    Online here

  • \bibitem{int:Fukuda1}
    M.~Fukuda, M.~Kojima, K.~Murota, and K.~Nakata.
    \newblock Exploiting sparsity in semidefinite programming via matrix completion I: general framework.
    \newblock {\em SIAM Journal on Optimization}, 11:647--674, 2001.
    Online here

  • \bibitem{GaertnerMatousek}
    B.~Gaertner and J.~Matousek.
    \newblock Approximation Algorithms and Semidefinite Programming.
    \newblock Springer, 2012.
    Online here

  • \bibitem{int:Goemans1}
    M.~X. Goemans.
    \newblock Semidefinite programming in combinatorial optimization.
    \newblock {\em Mathematical Programming}, 79:143--161, 1997.
    Online here

  • \bibitem{int:Helmberg3}
    C.~Helmberg and F.~Rendl.
    \newblock A spectral bundle method for semidefinite programming.
    \newblock {\em SIAM Journal on Optimization}, 10:673--696, 2000.
    pdf

  • \bibitem{int:Helmberg1}
    C.~Helmberg, F.~Rendl, R.~J. Vanderbei, and H.~Wolkowicz.
    \newblock An interior-point method for semidefinite programming.
    \newblock {\em SIAM Journal on Optimization}, 6:342--361, 1996.
    Online here

  • \bibitem{int:Kleinberg1}
    J.~Kleinberg and M.~X. Goemans.
    \newblock The Lovasz theta function and a semidefinite programming relaxation of vertex cover.
    \newblock {\em SIAM Journal on Discrete Mathematics}, 11:196--204, 1998.
    Online here

  • \bibitem{int:Kojima31}
    M.~Kojima, M.~Shida, and S.~Shindoh.
    \newblock Search directions in the {SDP} and the monotone {SDLCP}: generalization and inexact computation.
    \newblock {\em Mathematical Programming}, 85:51--80, 1999.
    Online here

  • \bibitem{int:Kojima28}
    M.~Kojima, S.~Shindoh, and S.~Hara.
    \newblock Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices.
    \newblock {\em SIAM Journal on Optimization}, 7:86--125, 1997.
    Online here


    \bibitem{Lasserre}
    J.~B. Lasserre.
    \newblock Global optimization with polynomials and the problem of moments.
    \newblock {\em SIAM J.\ Optim.}, 11:796--817, 2001.
    Online here

  • \bibitem{int:Laurent1}
    M.~Laurent, S.~Poljak, and F.~Rendl.
    \newblock Connections between semidefinite relaxations of the max-cut and stable set problems.
    \newblock {\em Mathematical Programming}, 77:225--246, 1997.
    Online here

  • \bibitem{int:Lewis3}
    A.~S. Lewis and M.~L. Overton.
    \newblock Eigenvalue optimization.
    \newblock {\em Acta Numerica} 1996, pp.\ 149--160.
    Online here.

  • \bibitem{int:ZLuo3}
    Z.-Q.~Luo, J.~F. Sturm, and S.~Zhang.
    \newblock Duality and self-duality for conic convex programming.
    \newblock Technical Report, Erasmus University Rotterdam, The Netherlands, March 1996.

  • J. Malick.
    "A dual approach to semidefinite least-squares problems."
    SIAM J. Matrix Anal. Appl. 26:272--284, 2004.
    pdf

  • J. Malick, J. Povh, F. Rendl and A. Wiegele.
    "Regularization methods for semidefinite programming."
    SIAM J. Optim. 20:336--356, 2009.
    pdf

  • \bibitem{int:Monteiro20}
    R.~D.~C. Monteiro.
    \newblock Primal-dual path-following algorithms for semidefinite programming.
    \newblock {\em SIAM Journal on Optimization}, 7:663--678, 1997.
    Online here

  • \bibitem{int:Monteiro26}
    R.~D.~C. Monteiro.
    \newblock Polynomial convergence of primal-dual algorithms for semidefinite programming based on the {M}onteiro and {Z}hang family of directions.
    \newblock {\em SIAM Journal on Optimization}, 8:797--812, 1998.
    Online here

  • \bibitem{int:Monteiro34}
    R.~D.~C. Monteiro.
    \newblock First- and second-order methods for semidefinite programming.
    \newblock {\em Mathematical Programming}, 97:209--244, 2003.
    Online here

  • \bibitem{int:Monteiro24}
    R.~D.~C. Monteiro and Y.~Zhang.
    \newblock A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming.
    \newblock {\em Mathematical Programming}, 81:281--299, 1998.
    Online here

  • \bibitem{int:Nakata1}
    K.~Nakata, K.~Fujisawa, M.~Fukuda, M.~Kojima, and K.~Murota.
    \newblock Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results.
    \newblock {\em Mathematical Programming}, 95:303--327, 2003.
    Online here

  • \bibitem{int:Nesterov15}
    Yu.~E. Nesterov.
    \newblock Semidefinite relaxation and nonconvex quadratic optimization.
    \newblock {\em Optimization Methods and Software}, 9:141--160, 1998.

  • \bibitem{int:Nesterov7}
    Yu.~E. Nesterov and A.~S. Nemirovskii.
    \newblock Conic formulation of a convex programming problem and duality.
    \newblock {\em Optimization Methods and Software}, 1(2):95--115, 1992.

  • \bibitem{int:Nesterov5}
    Yu.~E. Nesterov and A.~S. Nemirovskii.
    \newblock {\em Interior Point Polynomial Methods in Convex Programming\ :\ Theory and Algorithms}.
    \newblock SIAM Publications. SIAM, Philadelphia, USA, 1994.
    Online here.

  • \bibitem{int:Nesterov10}
    Yu.~E. Nesterov and M.~J. Todd.
    \newblock Self-scaled barriers and interior-point methods for convex programming.
    \newblock {\em Mathematics of Operations Research}, 22:1--42, 1997.
    paper

  • \bibitem{int:Nesterov12}
    Yu.~E. Nesterov and M.~J. Todd.
    \newblock Primal-dual interior-point methods for self-scaled cones.
    \newblock {\em SIAM Journal on Optimization}, 8:324--364, 1998.
    Online here

  • \bibitem{int:Overton1}
    M.~L. Overton and H.~Wolkowicz.
    \newblock Semidefinite Programming.
    \newblock {\em Mathematical Programming}, 77:105--109, 1997.
    Online here


    \bibitem{Parrilo}
    P.~A. Parrilo.
    \newblock Semidefinite programming relaxations for semialgebraic problems.
    \newblock {\em Mathematical Programming}, 96:293--320, 2003.
    Online here

  • \bibitem{int:Pataki3}
    G.~Pataki.
    \newblock Bad semidefinite programs: they all look the same. paper

  • \bibitem{int:Ramana2}
    M.~V. Ramana, L.~Tun{\c c}el, and H.~Wolkowicz.
    \newblock Strong duality for semidefinite programming.
    \newblock {\em SIAM Journal on Optimization}, 7:641--662, 1997.
    Online here

  • \bibitem{int:Shapiro1}
    A.~Shapiro.
    \newblock First and second order analysis of nonlinear semidefinite programs.
    \newblock {\em Mathematical Programming}, 77:301--320, 1997.
    Online here

  • \bibitem{int:Shida1}
    M.~Shida, S.~Shindoh, and M.~Kojima.
    \newblock Existence and uniqueness of search directions in interior-point algorithms for the {SDP} and the monotone {SDLCP}.
    \newblock {\em SIAM Journal on Optimization}, 8:387--396, 1998.
    Online here

  • \bibitem{int:Todd34}
    M.~J. Todd, K.-C. Toh and R.H. T\"{u}t\"{u}nc\"{u}.
    \newblock On the Nesterov-Todd direction in semidefinite programming.
    \newblock {\em SIAM Journal on Optimization}, 8:769--796, 1998.
    Online here

  • \bibitem{int:Toh1}
    K.-C. Toh, M.~J. Todd and R.~H. T\"{u}t\"{u}nc\"{u}.
    \newblock SDPT3 - a MATLAB software package for semidefinite programming, Version 1.3.
    \newblock {\em Optimization Methods and Software}, 11:545--581, 1999.

  • \bibitem{int:Vandenberghe2}
    L.~Vandenberghe and S.~Boyd.
    \newblock Semidefinite programming.
    \newblock {\em SIAM Review}, 38(1):49--95, 1996.
    Online here

  • \bibitem{int:Wolkowicz3}
    H.~Wolkowicz, R.~Saigal, and L. Vandenberghe (eds.).
    \newblock {\it Handbook on Semidefinite Programming}, Kluwer Academic Publishers, Boston-Dordrecht-London, 2000.
    Online here.

  • X. Yuan.
    "Alternating direction method of multipliers for covariance selection models,"
    to appear in the Journal of Scientific Computing;
    pdf

  • \bibitem{int:Zhang18}
    Y.~Zhang.
    \newblock On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming.
    \newblock {\em SIAM Journal on Optimization}, 8:365--386, 1998. paper
    Online here