7.3 Semidefinite Optimization

Semidefinite optimization is a generalization of conic quadratic optimization, allowing the use of matrix variables belonging to the convex cone of positive semidefinite matrices

\[\PSD^r = \left\lbrace X \in \Symm^r: z^T X z \geq 0, \quad \forall z \in \real^r \right\rbrace,\]

where \(\Symm^r\) is the set of \(r \times r\) real-valued symmetric matrices.

MOSEK can solve semidefinite optimization problems of the form

\[\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 \(A,B\in \real^{m\times n}\) we have

\[\left\langle A,B \right\rangle := \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} A_{ij} B_{ij}.\]

In Fusion the user can enter the linear expressions in a more convenient way, without having to cast the problem exactly in the above form.

7.3.1 Example SDO1

We consider the simple optimization problem with semidefinite and conic quadratic constraints:

(1)\[\begin{split}\begin{array} {llcc} \mbox{minimize} & \left\langle \left[ \begin{array} {ccc} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{array} \right], \barX \right\rangle + x_0 & & \\ \mbox{subject to} & \left\langle \left[ \begin{array} {ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right], \barX \right\rangle + x_0 & = & 1, \\ & \left\langle \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right], \barX \right\rangle + x_1 + x_2 & = & 1/2, \\ & x_0 \geq \sqrt{{x_1}^2 + {x_2}^2}, & \barX \succeq 0, & \end{array}\end{split}\]

The problem description contains a 3-dimensional symmetric semidefinite variable which can be written explicitly as:

\[\begin{split}\barX = \left[ \begin{array} {ccc} \barX_{00} & \barX_{10} & \barX_{20} \\ \barX_{10} & \barX_{11} & \barX_{21} \\ \barX_{20} & \barX_{21} & \barX_{22} \end{array} \right] \in \PSD^3,\end{split}\]

and a conic quadratic variable \((x_0, x_1, x_2) \in \Q^3\). The objective is to minimize

\[2(\barX_{00} + \barX_{10} + \barX_{11} + \barX_{21} + \barX_{22}) + x_0,\]

subject to the two linear constraints

\[\begin{split}\begin{array}{ccc} \barX_{00} + \barX_{11} + \barX_{22} + x_0 & = & 1, \\ \barX_{00} + \barX_{11} + \barX_{22} + 2(\barX_{10} + \barX_{20} + \barX_{21}) + x_1 + x_2 & = & 1/2. \end{array}\end{split}\]

Our implementation in Fusion begins with creating a new model:

    Model M  = new Model("sdo1");

We create a symmetric semidefinite variable \(\barX\) and another variable representing \(x\). For simplicity we immediately declare that \(x\) belongs to a quadratic cone

      Variable X  = M.variable("X", Domain.inPSDCone(3));
      Variable x  = M.variable("x", Domain.inQCone(3));

In this elementary example we are going to create an explicit matrix representation of the problem

\[\begin{split}\barC =\left[ \begin{array}{ccc} 2 & 1 & 0 \\ 1 & 2 & 1\\ 0 & 1 & 2\end{array}\right],\ \barA_1 =\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0\\ 0 & 0 & 1\end{array}\right],\ \barA_2 =\left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1\\ 1 & 1 & 1\end{array}\right].\end{split}\]

and use it in the model via the dot product operation \(\langle\cdot,\cdot\rangle\) which applies to matrices as well as to vectors. This way we create each of the linear constraints and the objective as one expression.

      // Objective
      M.objective(ObjectiveSense.Minimize, Expr.add(Expr.dot(C, X), x.index(0)));

      // Constraints
      M.constraint("c1", Expr.add(Expr.dot(A1, X), x.index(0)), Domain.equalsTo(1.0));
      M.constraint("c2", Expr.add(Expr.dot(A2, X), Expr.sum(x.slice(1, 3))), Domain.equalsTo(0.5));

Now it remains to solve the problem with Model.solve.

Listing 5 Fusion implementation of problem (1). Click here to download.
package com.mosek.fusion.examples;
import mosek.fusion.*;

public class sdo1 {
  public static void main(String[] args) throws SolutionError {
    Model M  = new Model("sdo1");
    try {
      // Setting up the variables
      Variable X  = M.variable("X", Domain.inPSDCone(3));
      Variable x  = M.variable("x", Domain.inQCone(3));

      // Setting up constant coefficient matrices
      Matrix C  = Matrix.dense ( new double[][] {{2., 1., 0.}, {1., 2., 1.}, {0., 1., 2.}} );
      Matrix A1 = Matrix.eye(3);
      Matrix A2 = Matrix.ones(3,3);

      // Objective
      M.objective(ObjectiveSense.Minimize, Expr.add(Expr.dot(C, X), x.index(0)));

      // Constraints
      M.constraint("c1", Expr.add(Expr.dot(A1, X), x.index(0)), Domain.equalsTo(1.0));
      M.constraint("c2", Expr.add(Expr.dot(A2, X), Expr.sum(x.slice(1, 3))), Domain.equalsTo(0.5));

      M.solve();

      System.out.println(java.util.Arrays.toString( X.level() ));
      System.out.println(java.util.Arrays.toString( x.level() ));
    } finally {
      M.dispose();
    }
  }
}