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::t M = new Model("sdo1"); auto _M = finally([&]() { M->dispose(); });


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::t X  = M->variable("X", Domain::inPSDCone(3));
Variable::t 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

// Constraints
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.
#include <iostream>
#include "fusion.h"

using namespace mosek::fusion;
using namespace monty;

int main(int argc, char ** argv)
{
Model::t M = new Model("sdo1"); auto _M = finally([&]() { M->dispose(); });

// Setting up the variables
Variable::t X  = M->variable("X", Domain::inPSDCone(3));
Variable::t x  = M->variable("x", Domain::inQCone(3));

// Setting up the constant coefficient matrices
Matrix::t C  = Matrix::dense ( new_array_ptr<double, 2>({{2., 1., 0.}, {1., 2., 1.}, {0., 1., 2.}}));
Matrix::t A1 = Matrix::eye(3);
Matrix::t A2 = Matrix::ones(3, 3);

// Objective

// Constraints