7.5 Semidefinite Optimization¶
Semidefinite optimization is a generalization of conic optimization, allowing the use of matrix variables belonging to the convex cone of positive semidefinite matrices
where \(\Symm^r\) is the set of \(r \times r\) real-valued symmetric matrices.
MOSEK can solve semidefinite optimization problems of the form
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
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.
We demonstrate the setup of semidefinite variables and the matrices \(\barC\), \(\barA\) on the following examples:
Sec. 7.5.1 (Example SDO1): A problem with one semidefinite variable and linear and conic constraints.
Sec. 7.5.2 (Example SDO2): A problem with two semidefinite variables with a linear constraint and bound.
Sec. 7.5.3 (Example SDO3): Shows how to efficiently set up many semidefinite variables of the same dimension.
7.5.1 Example SDO1¶
We consider the simple optimization problem with semidefinite and conic quadratic constraints:
The problem description contains a 3-dimensional symmetric semidefinite variable which can be written explicitly as:
and a conic quadratic variable \((x_0, x_1, x_2) \in \Q^3\). The objective is to minimize
subject to the two linear constraints
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
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
.
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();
}
}
}
7.5.2 Example SDO2¶
We now demonstrate how to define more than one semidefinite variable using the following problem with two matrix variables and two types of constraints:
In our example \(\dim(\barX_1)=3\), \(\dim(\barX_2)=4\), \(b=23\), \(k=-3\) and
are constant symmetric matrices.
Note that this problem does not contain any scalar variables, but they could be added in the same fashion as in Sec. 7.5.1 (Example SDO1).
The code representing the above problem is shown below.
public class sdo2 {
public static void main(String[] args) throws SolutionError {
// Sample data in sparse, symmetric triplet format
int[] C1_k = {0, 2};
int[] C1_l = {0, 2};
double[] C1_v = {1, 6};
int[] A1_k = {0, 2, 0, 2};
int[] A1_l = {0, 0, 2, 2};
double[] A1_v = {1, 1, 1, 2};
int[] C2_k = {0, 1, 0, 1, 2};
int[] C2_l = {0, 0, 1, 1, 2};
double[] C2_v = {1, -3, -3, 2, 1};
int[] A2_k = {1, 0, 1, 3};
int[] A2_l = {0, 1, 1, 3};
double[] A2_v = {1, 1, -1, -3};
double b = 23;
double k = -3;
// Convert input data into Fusion sparse matrices
Matrix C1 = Matrix.sparse(3, 3, C1_k, C1_l, C1_v);
Matrix C2 = Matrix.sparse(4, 4, C2_k, C2_l, C2_v);
Matrix A1 = Matrix.sparse(3, 3, A1_k, A1_l, A1_v);
Matrix A2 = Matrix.sparse(4, 4, A2_k, A2_l, A2_v);
Model M = new Model("sdo2");
try {
// Two semidefinite variables
Variable X1 = M.variable(Domain.inPSDCone(3));
Variable X2 = M.variable(Domain.inPSDCone(4));
// Objective
M.objective(ObjectiveSense.Minimize, Expr.add(Expr.dot(C1,X1), Expr.dot(C2,X2)));
// Equality constraint
M.constraint(Expr.add(Expr.dot(A1,X1), Expr.dot(A2,X2)), Domain.equalsTo(b));
// Inequality constraint
M.constraint(X2.index(new int[] {0,1}), Domain.lessThan(k));
// Solve
M.setLogHandler(new java.io.PrintWriter(System.out));
M.solve();
// Print solution
System.out.println("Solution (vectorized):");
System.out.println(java.util.Arrays.toString( X1.level() ));
System.out.println(java.util.Arrays.toString( X2.level() ));
} finally {
M.dispose();
}
}
}
7.5.3 Example SDO3¶
Here we demonstrate how to use the facilities provided in Fusion to set up a model with many semidefinite variables of the same dimension more efficiently than via looping. We consider a problem with \(n\) semidefinite variables of dimension \(d\) and \(k\) constraints:
with symmetric data matrices \(A_{ij}\).
The key construction is:
Variable X = M.variable(Domain.inPSDCone(d, n));
It creates \(n\) symmetric, semidefinite matrix variables of dimension \(d\) arranged in a single variable object X
of shape \((n,d,d)\). Individual matrix variables can be accessed as slices from \((i,0,0)\) to \((i+1,d,d)\) (reshaped into shape \((d,d)\) if necessary). It is also possible to operate on the full variable X
when constructing expressions that involve entries of all the semidefinite matrices in a natural way. The source code example illustrates both these approaches.
public class sdo3 {
// A helper method computing a semidefinite slice of a 3-dim variable
public static Variable slice(Variable X, int d, int j) {
return
X.slice(new int[] {j,0,0}, new int[] {j+1,d,d})
.reshape(new int[] {d,d});
}
public static void main(String[] args) throws SolutionError {
// Sample input data
int n = 100;
int d = 4;
int k = 3;
double[] b = {9,10,11};
double[][][] A = new double[n*k][d][d];
for(int i=0; i<n*k; i++)
for(int s1=0; s1<d; s1++)
for(int s2=0; s2<=s1; s2++)
A[i][s1][s2] = A[i][s2][s1] = Math.random();
// Create a model with n semidefinite variables od dimension d x d
Model M = new Model("sdo3");
try {
Variable X = M.variable(Domain.inPSDCone(d, n));
// Pick indexes of diagonal entries for the objective
int[][] alldiag = new int[d*n][3];
for(int j=0; j<n; j++) for(int s=0; s<d; s++) {
alldiag[j*d+s][0] = j;
alldiag[j*d+s][1] = alldiag[j*d+s][2] = s;
}
M.objective(ObjectiveSense.Minimize, Expr.sum( X.pick(alldiag) ));
// Each constraint is a sum of inner products
// Each semidefinite variable is a slice of X
for(int i=0; i< k; i++) {
Expression[] addlist = new Expression[n];
for(int j=0; j<n; j++)
addlist[j] = Expr.dot(A[i*n+j], slice(X, d, j));
M.constraint(Expr.add(addlist), Domain.greaterThan(b[i]));
}
// Solve
M.setLogHandler(new java.io.PrintWriter(System.out)); // Add logging
M.writeTask("sdo3.ptf"); // Save problem in readable format
M.solve();
// Get results. Each variable is a slice of X
System.out.println("Contributing variables:");
for(int j=0; j<n; j++) {
double[] Xj = slice(X, d, j).level();
double maxval = 0;
for(int s=0; s<d*d; s++) maxval = Math.max(maxval, Xj[s]);
if (maxval > 1e-6) {
System.out.println("X" + j + "=");
for(int s1=0; s1<d; s1++) {
for(int s2=0; s2<d; s2++)
System.out.print(Xj[s1*d+s1] + " ");
System.out.println();
}
}
}
}
finally {
M.dispose();
}
}
}