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:

      using (Model M  = new Model("sdo1"))

We create a symmetric semidefinite variable \(\barX\) and another variable representing \(x\). For simplicity we immediately declare that :math;`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 7.3 Fusion implementation of model (?). Click here to download.
using System;
using mosek.fusion;

namespace mosek.fusion.example
{
  public class sdo1
  {
    public static void Main(string[] args)
    {
      using (Model M  = new Model("sdo1"))
      {
        // 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();

        Console.WriteLine("[{0}]", (new Utils.StringBuffer()).A(X.Level()).ToString());
        Console.WriteLine("[{0}]", (new Utils.StringBuffer()).A(x.Level()).ToString());
      }
    }
  }
}