zbMATH — the first resource for mathematics

Semidefinite programming. (English) Zbl 0845.65023
In semidefinite programming, one minimizes 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 semidefinite programs are convex optimization problems. Semidefinite programming unifies several standard problems (e.g. linear quadratic programming) and finds many applications in engineering and combinatorial optimization.
Although semidefinite programs are much more general than linear programs, they are not much harder to solve. 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.

90C22 Semidefinite programming
90C51 Interior-point methods
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
65K05 Numerical mathematical programming methods
90C27 Combinatorial optimization
90C25 Convex programming
Full Text: DOI