Handbook of Linear Algebra, 2nd Edition

Chapter 69

Semidefinite Programming

Henry Wolkowicz

University of Waterloo

69.1 Introduction

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

$\begin{array}{cc}(\text{SDP})& \begin{array}{ccc}p*=& \min & \text{tr CX}\\ \text{subject to}& TX=b\\ X\underset{\_}{\succ }0,\end{array}\end{array}$

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 ...