Semidefinite Programming

Henry Wolkowicz

ABSTRACT

Semidefinite programming is an extension of linear programming where (some of) the vector variables are replaced by matrix variables and (some of) the nonnegativity elementwise constraints are replaced by positive semidefiniteness constraints. These are convex problems that can be solved efficiently by interior-point methods. They arise in many applications, for example, in combinatorial optimizations, matrix completion problems, stability of differential systems, and, more generally, as the dual of Lagrangian relaxations of quadratic models of numerically hard problems.