0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You should clarify what your variables and constants are. Is $\epsilon$ a given scalar? Are A and B given real $n$ by $n$ matrices (or possibly $m$ by $n$)? Are the variables $W_{1}$, $W_{2}$ (matrices of what size?), and $t$ (scalar?) $\endgroup$ – Brian Borchers Feb 23 '16 at 18:23
  • $\begingroup$ @BrianBorchers I edited my question and added some explanations on these. $\epsilon$ is a positive scalar, $A,\,B$ are real $m \times n$ matrices and the matrices $W_1,\,W_2$ along with the (positive, as a value of a norm) scalar $t$ are the decision variables. $\endgroup$ – Kapoios Feb 23 '16 at 18:33
  • 1
    $\begingroup$ You could do the spiel described by Brian Borchers , which answers your question. Or to make life simpler, you could use CVX or YALMIP, which let you specify your model in a natural form, and take care of the conversion to/from the form and format needed by SDPT3 or another solver. $\endgroup$ – Mark L. Stone Feb 23 '16 at 23:50
  • $\begingroup$ @MarkL.Stone CVX was my first choice, but, unfortunately, it proved itself not scalable. As I need to work with large matrices ($n>200$), I should feed an SDP solver with the problem data in standard SDP form. $\endgroup$ – Kapoios Feb 24 '16 at 10:04
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.