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