Semidefinite Programming

L. Vandenberghe and S. Boyd SIAM Review, 38(1): 49-95, March 1996. An earlier version, with the name Positive Definite Programming, appeared in Mathematical Programming, State of the Art, J. Birge and K. Murty, editors, pp.276-308, 1994. In semidefinite programming we minimize a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so positive definite programs are convex optimization problems. Semidefinite programming unifies several standard problems (eg, linear and quadratic programming) and finds many applications in engineering. Although semidefinite programs are much more general than linear programs, they are just as easy to solve. Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity, and perform very well in practice. This paper gives a survey of the theory and applications of semidefinite programs, and an introduction to primal-dual interior-point methods for their solution. programming unifies several standard problems (eg, linear and quadratic programming) and finds many applications in engineering. Although semidefinite programs are much more general than linear programs, they are just as easy to solve. Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity, and perform very well in practice. This paper gives a survey of the theory and applications of semidefinite programs, and an introduction to primal-dual interior-point methods for their solution.