16.3 Semidefinite Optimization

Semidefinite optimization is an extension of conic quadratic optimization (see Sec. 16.2 (Conic Quadratic Optimization)) allowing positive semidefinite matrix variables to be used in addition to the usual scalar variables. A semidefinite optimization problem can be written as

(1)\[\begin{split}\begin{array} {lccccll} \mbox{minimize} & & & \sum_{j=0}^{n-1} c_j x_j + \sum_{j=0}^{p-1}\left\langle \barC_j, \barX_j \right\rangle + c^f & & &\\ \mbox{subject to} & l_i^c & \leq & \sum_{j=0}^{n-1} a_{ij} x_j + \sum_{j=0}^{p-1}\left\langle\barA_{ij}, \barX_j \right\rangle & \leq & u_i^c, & i = 0, \ldots, m-1\\ & l_j^x & \leq & x_j & \leq & u_j^x, & j = 0, \ldots, n-1\\ & & & x \in \K, \barX_j \in \PSD^{r_j}, & & & j = 0, \ldots, p-1 \end{array}\end{split}\]

where the problem has \(p\) symmetric positive semidefinite variables \(\barX_j\in \PSD^{r_j}\) of dimension \(r_j\) with symmetric coefficient matrices \(\barC_j\in \Symm^{r_j}\) and \(\barA_{i,j}\in \Symm^{r_j}\). We use standard notation for the matrix inner product, i.e., for \(U,V\in \real^{m\times n}\) we have

\[\left\langle U,V \right\rangle := \sum_{i=0}^{m-1}\sum_{j=0}^{n-1} U_{ij} V_{ij}.\]

With semidefinite optimization we can model a wide range of problems as demonstrated in [MOSEKApS12].

16.3.1 Duality for Semidefinite Optimization

The dual problem corresponding to the semidefinite optimization problem (1) is given by

(2)\[\begin{split}\begin{array} {llc} \mbox{maximize} & (l^c)^T s_l^c - (u^c)^T s_u^c + (l^x)^T s_l^x - (u^x)^T s_u^x + c^f & \\ \mbox{subject to} & & \\ & c - A^T y + s_u^x - s_l^x = s_n^x , & \\ & \barC_j - \sum_{i=0}^{m} y_i \barA_{ij} = \overline{S}_j, & j=0,\ldots,p-1 \\ & s_l^c - s_u^c = y, & \\ & s_l^c,s_u^c,s_l^x,s_u^x \geq 0, & \\ & s_{n}^x \in \K^*, \quad \overline{S}_j \in \PSD^{r_j}, & j=0,\ldots,p-1 \end{array}\end{split}\]

where \(A\in \real^{m\times n}\), \(A_{ij}=a_{ij}\), which is similar to the dual problem for conic quadratic optimization (see Sec. 16.2.1 (Duality for Conic Quadratic Optimization)), except for the addition of dual constraints

\[\left(\barC_j - \sum_{i=0}^m y_i \barA_{ij} \right) \in \PSD^{r_j}.\]

Note that the dual of the dual problem is identical to the original primal problem.

16.3.2 Infeasibility for Semidefinite Optimization

In case MOSEK finds a problem to be infeasible it reports a certificate of the infeasibility. This works exactly as for linear problems (see Sec. 16.1.2 (Infeasibility for Linear Optimization)).

16.3.2.1 Primal Infeasible Problems

If the problem (1) is infeasible, MOSEK will report a certificate of primal infeasibility: The dual solution reported is a certificate of infeasibility, and the primal solution is undefined.

A certificate of primal infeasibility is a feasible solution to the problem

\[\begin{split}\begin{array}{llc} \mbox{maximize} & (l^c)^T s_l^c - (u^c)^T s_u^c + (l^x)^T s_l^x - (u^x)^T s_u^x &\\ \mbox{subject to} & &\\ & A^T y + s_l^x - s_u^x + s_{n}^x = 0, &\\ & \sum_{i=0}^{m-1}y_i \barA_{ij} + \overline{S}_j = 0, & j=0,\ldots,p-1\\ & -y + s_l^c - s_u^c = 0, &\\ & s_l^c,s_u^c,s_l^x,s_u^x \geq 0, &\\ & s_n^x \in \K^*, \quad \overline{S}_j \in \PSD^{r_j}, & j=0,\ldots,p-1 \end{array}\end{split}\]

such that the objective value is strictly positive.

16.3.2.2 Dual Infeasible Problems

If the problem (2) is infeasible, MOSEK will report a certificate of dual infeasibility: The primal solution reported is the certificate of infeasibility, and the dual solution is undefined.

A certificate of dual infeasibility is a feasible solution to the problem

\[\begin{split}\begin{array}{lccccll} \mbox{minimize} & & & \sum_{j=0}^{n-1}c_j x_j + \sum_{j=0}^{p-1} \left\langle\barC_j,\barX_j \right\rangle & & & \\ \mbox{subject to} & \hat{l}^c_i & \leq & \sum_{j=1}^n a_{ij} x_j + \sum_{j=0}^{p-1}\left\langle\barA_{ij}, \barX_j \right\rangle & \leq & \hat{u}^c_i, & i=0,\ldots,m-1\\ & \hat{l}^x & \leq & x & \leq & \hat{u}^x, & \\ & & & x \in \K, \quad \barX_j \in \PSD^{r_j}, & & & j=0,\ldots,p-1 \end{array}\end{split}\]

where

\[\begin{split}\hat{l}_i^c = \left\lbrace \begin{array} {ll} 0 & \mbox{if } l_i^c >; -\infty ,\\ -\infty & \mbox{otherwise}, \end{array} \right. \quad \mbox{and} \quad \hat{u}_i^c := \left\lbrace \begin{array} {ll} 0 & \mbox{if } u_i^c <; \infty ,\\ \infty & \mbox{otherwise}, \end{array} \right.\end{split}\]

and

\[\begin{split}\hat{l}_j^x = \left\lbrace \begin{array}{ll} 0 & \mbox{if } l_j^x >; -\infty ,\\ -\infty & \mbox{otherwise}, \end{array} \right. \quad \mbox{and} \quad \hat{u}_j^x := \left\lbrace \begin{array} {ll} 0 & \mbox{if } u_j^x <; \infty ,\\ \infty & \mbox{otherwise}, \end{array} \right.\end{split}\]

such that the objective value is strictly negative.