Express the $\gamma_{2}^{\epsilon}$ SemiDefinite program in a form that is acceptable by SDPT3

Question

I'm trying to express the following semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$,

\begin{align} &\gamma_{2}^{\epsilon}(A):= \min\,t\\ &\text{subject to} \left( \begin{array}{ccc} W_1 & B \\ B^T & W_2 \\ \end{array} \right)\succcurlyeq 0,\, \operatorname{diag}(W_1)\leq t,\, \operatorname{diag}(W_2)\leq t,\\ &\forall (i,j) \in \{1,...,m\} \times \{1,...,n\}: -\epsilon\leq A_{ij}-B_{ij},\, A_{ij}-B_{ij} \geq \epsilon. \end{align}

where $B \in R^{m \times n} ,\, W_1 \in R^{m \times m}$, $W_1 \in R^{n \times n}$ and $t \in R$ are the decision variables, in a form that is acceptable by the semidefinite-quadratic-linear program solver SDPT3. I know that the first thing I should do is to convert it to the standard SDP form. I tried to do it, but I got stuck on how to model the objective function. Any help on modelling this program in an SDPT3-acceptable form would be much appreciated.

Answer 1

In order to do this, you'll need to convert inequalities to equality constraints by introducing slack variables and then add these slack variables to your matrix variable as an additional LP block.

Let

$ X=\left[ \begin{array}{ccc} W_{1} & B & 0 \\ B^{T} & W_{2} & 0 \\ 0 & 0 & \mbox{diag}(v) \\ \end{array} \right] $

where

$ v=\left[ \begin{array}{c} s_{1} \\ s_{2} \\ \vdots \\ s_{p} \\ t \\ \end{array} \right] $

In SDPT3, your $X$ matrix will be a block diagonal matrix with an $m+n$ by $m+n$ symmetric positive semidefinite block for $W_{1}$, $W_{2}$, $B$, and $B^{T}$, and a diagonal (or LP variable) block $v$ of length $2mn+3$ for the slack variables and $t$.

It's easy to express the objective $\min t$ as the minimum of the trace of $CX$, where $C$ is a matrix with a 1 in the lower right corner and all other entries 0.

Your constraints will then be

$X \succeq 0$

$\mbox{diag}(W_{1})+v_{1} - v_{p+1} = 0$

$\mbox{diag}(W_{2})+v_{2} - v_{p+1} = 0$

$A_{i,j}-B_{i,j} - v_{2+i+(j-1)m} = -\epsilon $ for $i=1, 2, \ldots, m$, $j=1, 2, \ldots, n$.

$A_{i,j}-B_{i,j} + v_{2+mn+i+(j-1)m} = \epsilon $ for $i=1, 2, \ldots, m$, $j=1, 2, \ldots, n$.

Each of these linear equality constraints can be easily written as a linear equality constraint involving entries in $X$.