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

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

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 the standard form of a semidefinite program (see e.g. this wiki article).

I used slack variables as a first step to make up a trace contraint from the linear inequalities in the constraints. The hard step - on which I need some help - is to convert the objective function in the standard form $trace(CX)$.

  • $\begingroup$ Hint: set up a block matrix variable X in which t is a 1x1 block on the diagonal. $\endgroup$ – Brian Borchers Aug 19 '18 at 16:27

Your Answer

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

Browse other questions tagged or ask your own question.