University of Waterloo
Semidefinite programming (SDP) refers to optimization problems where variables X in the objective function or constraints can be symmetric matrices restricted to the cone of positive semidefinite matrices. (We restrict ourselves to real symmetric matrices, Sn, since the vast majority of applications are for the real case. The complex case requires using the complex inner-product space.) An example of a simple linear SDP is
where T : Sn → ℝm. The details are given in the definitions in Section 69.2; the SDP relaxation of the Max-Cut problem is given in Example 1 in this section. The linear SDP is a generalization of ...