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}{lccccl} \mbox{minimize} & & & c^T x+ \langle \barC,\barX\rangle + c^f & & \\ \mbox{subject to} & l^c & \leq & A x + \langle \barA,\barX\rangle & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \\ & & & Fx+\langle \barF,\barX\rangle +g & \in & \D, \\ & & & \barX_j & \in & \PSD^{r_j}, j=1,\ldots,s \end{array}\end{split}\]

where

  • \(m\) is the number of constraints.

  • \(n\) is the number of decision variables.

  • \(x \in \real^n\) is a vector of decision variables.

  • \(c \in \real^n\) is the linear part of the objective function.

  • \(c^f\in \real\) is a constant term in the objective

  • \(A \in \real^{m \times n}\) is the constraint matrix.

  • \(l^c \in \real^m\) is the lower limit on the activity for the constraints.

  • \(u^c \in \real^m\) is the upper limit on the activity for the constraints.

  • \(l^x \in \real^n\) is the lower limit on the activity for the variables.

  • \(u^x \in \real^n\) is the upper limit on the activity for the variables.

  • \(F \in \real^{k \times n}\) is the affine conic constraint matrix.,

  • \(g \in \real^{k}\) is the affine conic constraint constant term vector.,

  • \(\D\) is a Cartesian product of conic domains, namely \(\D = \D_1 \times \cdots \times \D_p\), where \(p\) is the number of individual affine conic constraints (ACCs), and each domain is one from Sec. 15.8 (Supported domains).

is the same as in Sec. 12.2 (Conic Optimization) and moreover:

  • there are \(s\) symmetric positive semidefinite variables, the \(j\)-th of which is \(\barX_j\in \PSD^{r_j}\) of dimension \(r_j\),

  • \(\barC = (\barC_j)_{j=1,\ldots,s}\) is a collection of symmetric coefficient matrices in the objective, with \(\barC_j\in \Symm^{r_j}\), and we interpret the notation \(\langle \barC,\barX\rangle\) as a shorthand for

    \[\langle \barC,\barX\rangle := \sum_{j=1}^{s}\langle \barC_j,\barX_j\rangle.\]

  • \(\barA = (\barA_{ij})_{i=1,\ldots,m,j=1,\ldots,s}\) is a collection of symmetric coefficient matrices in the constraints, with \(\barA_{ij}\in \Symm^{r_j}\), and we interpret the notation \(\langle \barA,\barX\rangle\) as a shorthand for the vector

    \[\langle \barA,\barX\rangle := \left(\sum_{j=1}^{s}\langle \barA_{ij},\barX_j\rangle\right)_{i=1,\ldots,m}.\]

  • \(\barF = (\barF_{ij})_{i=1,\ldots,k,j=1,\ldots,s}\) is a collection of symmetric coefficient matrices in the affine conic constraints, with \(\barF_{ij}\in \Symm^{r_j}\), and we interpret the notation \(\langle \barF,\barX\rangle\) as a shorthand for the vector

    \[\langle \barF,\barX\rangle := \left(\sum_{j=1}^{s}\langle \barF_{ij},\barX_j\rangle\right)_{i=1,\ldots,k}.\]

In each case the matrix inner product between symmetric matrices of the same dimension \(r\) is defined as

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

To summarize, above the formulation extends that from Sec. 12.2 (Conic Optimization) by the possibility of including semidefinite terms in the objective, constraints and affine conic constraints.

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 - g^T\dot{y} + c^f &\\ \mbox{subject to} &\\ & A^T y + s_l^x - s_u^x + F^T \dot{y} = c, & \\ & -y + s_l^c - s_u^c = 0, &\\ & \barC_j-\sum_{i=1}^m y_i\barA_{ij}-\sum_{i=1}^k \dot{y}_i\barF_{ij} = S_j, & j=1,\ldots,s, \\ & s_l^c,s_u^c,s_l^x ,s_u^x \geq 0, & \\ & \dot{y} \in \D^*, & \\ & \barS_j \in \PSD^{r_j}, & j=1,\ldots,s. \end{array}\end{split}\]

Complementarity conditions (12.11) include the additional relation:

(12.19)\[ \langle \barX_j,\barS_j\rangle = 0 \quad j=1,\ldots,s.\]

Infeasibility

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

(12.20)\[\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 - g^T\dot{y} &\\ \mbox{subject to} &\\ & A^T y + s_l^x - s_u^x + F^T \dot{y} = 0, & \\ & -y + s_l^c - s_u^c = 0, &\\ & -\sum_{i=1}^m y_i\barA_{ij}-\sum_{i=1}^k \dot{y}_i\barF_{ij} = S_j, & j=1,\ldots,s, \\ & s_l^c,s_u^c,s_l^x ,s_u^x \geq 0, & \\ & \dot{y} \in \D^*, & \\ & \barS_j \in \PSD^{r_j}, & j=1,\ldots,s. \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.21)\[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+ \langle \barC,\barX\rangle & & \\ \mbox{subject to} & \hat{l}^c & \leq & A x + \langle \barA,\barX\rangle & \leq & \hat{u}^c, \\ & \hat{l}^x & \leq & x & \leq & \hat{u}^x, \\ & & & Fx+\langle \barF,\barX\rangle & \in & \D, \\ & & & \barX_j & \in & \PSD^{r_j}, j=1,\ldots,s \end{array}\end{split}\]

where the modified bounds are as in (12.14) and (12.15) and the objective value is strictly negative.