12.3 Semidefinite Optimization

Semidefinite optimization is an extension of conic optimization (see Sec. 12.2 (Conic Optimization)) allowing positive semidefinite matrix variables to be used in addition to the usual scalar variables. All the other parts of the input are defined exactly as in Sec. 12.2 (Conic Optimization), and the discussion from that section applies verbatim to all properties of problems with semidefinite variables. We only briefly indicate how the corresponding formulae should be modified with semidefinite terms.

A semidefinite optimization problem can be written as

(12.17)\[\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}.\]

As always we write \(A=(a_{i,j})\) for the linear coefficient matrix.

Duality

The definition of the dual problem (12.9) becomes:

(12.18)\[\begin{split}\begin{array} {lcl} \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} &\\ & A^T y + s_l^x - s_u^x + s_n^x = c & \\ & -y + s_l^c - s_u^c = 0, &\\ & \barC_j - \sum_{i=0}^{m-1} y_i \barA_{ij} = \barS_j, & j=0,\ldots,p-1 \\ & s_l^c,s_u^c,s_l^x ,s_u^x \geq 0, & \\ & s_n^x \in \K^*, & \\ & \barS_j \in \PSD^{r_j}, & j=0,\ldots,p-1. \end{array}\end{split}\]

The duality gap (12.10) is computed as:

(12.19)\[\begin{split}\begin{array}{l} c^T x^* + c^f - \left\lbrace (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 \right\rbrace\\ = \sum_{i=0}^{m-1} \left[ (s_l^c)_i^* ( (x_i^c)^*-l_i^c) + (s_u^c)_i^* (u_i^c-(x_i^c)^*) \right] \\ + \sum_{j=0}^{n-1} \left[ (s_l^x)_j^* (x_j-l_j^x) +(s_u^x)_j^* (u_j^x-x_j^*) \right] + \sum_{j=0}^{n-1}(s_n^x)_j^*x_j^* + \sum_{j=0}^{p-1} \langle \barX_j,\barS_j\rangle\geq 0. \end{array}\end{split}\]

Complementarity conditions (12.11) include the additional relation:

(12.20)\[ \langle \barX_j,\barS_j\rangle = 0 \quad j=0,\ldots,p-1.\]

Infeasibility

A certificate of primal infeasibility (12.12) is now a feasible solution to:

(12.21)\[\begin{split}\begin{array}{lcl} \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, & \\ & -y + s_l^c - s_u^c = 0, & \\ & \sum_{i=0}^{m-1} y_i \barA_{ij} + \barS_j = 0, & j=0,\ldots,p-1\\ & s_l^c,s_u^c,s_l^x,s_u^x \geq 0, & \\ & s_n^x\in \K^*, & \\ & \barS_j\in\PSD^{r_j}, & j=0,\ldots,p-1. \end{array}\end{split}\]

such that the objective value is strictly positive.

Similarly, a dual infeasibility certificate (12.13) is a feasible solution to

(12.22)\[\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}_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 & \hat{u}_i^c, & i = 0, \ldots, m-1\\ & \hat{l}_j^x & \leq & x_j & \leq & \hat{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 modified bounds are as in (12.14) and (12.15) and the objective value is strictly negative.