SEMIDEFINITE PROGRAMMING

In semidefinite programming, one minimizes a linear function subject t o the constraint that an affine combination of symmetric matrices is p ositive semidefinite. Such a constraint is nonlinear and nonsmooth, bu t convex, so semidefinite programs are convex optimization problems. S emidefinite programming unifies several standard problems (e.g., linea r and quadratic programming) and finds many applications in engineerin g and combinatorial optimization. Although semidefinite programs are m uch more general than linear programs, they are not much harder to sol ve. Most interior-point methods for linear programming have been gener alized to semidefinite programs. As in linear programming, these metho ds have polynomial worst-case complexity and perform very well in prac tice. This paper gives a survey of the theory and applications of semi definite programs and an introduction to primal-dual interior-point me thods for their solution.