12.3 Semidefinite Optimization

Semidefinite optimization is an extension of conic quadratic optimization (see Section 12.2) 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].

12.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 Section 12.2.1), 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.

12.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 Section 12.1.2).

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

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