Efficient formulation of an SDP involving L1 norm

Question

I am trying to reformulate the following problem to be solved efficiently (by MOSEK) $$ \min_{X} \text{Tr}(CX)+\lambda\sum_{i,j}|x_{i,j}| \\ \text{s.t.} \quad ||X||_F\le1 \quad \text{and} \quad X\ge 0 \text{,} $$ where Tr() is the trace, $C \in \mathcal{S}^{n\times n}$ a real symmetric matrix, $X \in \mathcal{S}_{+}^{n\times n}$, the unknown positive-semidefinite (PSD) matrix, $\lambda$ the regularization parameter, and $x_{i,j}$ the $(i,j)^{th}$ entry of $X$.

I have two formulations: one obtained by myself and one obtained via YALMIP. The one obtained by YALMIP is solved more efficiently, and I'd like to know how that specific conversion is done. Below I present both formulations.

For simplicity in presentation, my formulation below does not show $x_{i,j}=x_{j,i}$, but this is incorporated in actual implementation. My simple formulation is $$ \min_{X} \text{Tr}(CX)+\lambda\sum_{i,j}t_{i,j} \\ \text{s.t.}\quad -t_{i,j}+x_{i,j}<0 \\ -t_{i,j}-x_{i,j}<0 \\ ||X||_F\le 1 \\ X\ge 0 \text{,} \\ $$ which involves $n(n+1)$ inequalities, a quadratic cone, a PSD cone, and $n(n+1)$ variables. (I hope I have these numbers right.)

YALMIP produces the following problem for MOSEK (using export.m), which I assume is equivalent up to some simple conversion because its solution is not the solution for the original problem. Because my understanding of this formulation is limited, I will use $n=2$ as a specific example. $$ \min_{X} t \\ \text{s.t.}\quad t\ge \sqrt{y_{10}^2+y_{11}^2+y_{12}^2} \\ y_{10}=c_{1,1}+y_1-y_2-x_{1,1} \\ y_{11}=\sqrt{2}\,c_{1,2}+\frac{1}{\sqrt{2}}(y_3-y_4+y_5-y_6)-\sqrt{2}\,x_{1,2} \\ y_{12}=c_{2,2}+y_7-y_8-x_{2,2} \\ y_{i}+y_{i+1}=\lambda \quad \text{for}\quad i=1,3,5,7 \\ y_i\ge 0 \quad \text{for}\quad i=1,2,...,8 \\ X\ge 0 \text{,} $$ which involves a quadratic cone, a PSD cone, about $n(n+1)$ equalities, $n(n+1)$ inequalities, and $3\times n(n+1)/2$ variables.

YALMIP problem is solved much more efficiently. It seems like it tries to complete a square, and implement $\lambda|x_k|$ by $(y_i-y_{i+1})x_k$. Any insight on how the YALMIP problem is formulated will be very helpful. Thank you.

Answer 1

YALMIP derives the model you do (except adding a dummy variable leading to $||X||_F\leq z, z\leq 1$ and adding some redundant constraints). However, YALMIP works in the dual space, i.e., $X$ is parameterized by variables, so to understand the model, it only makes sense to it interpret it as such.

For instance, if you look at the data in representing the dual $\max b^Ty \text{ subject to }C-A^Ty \succeq 0$ for your case

C = [7 2;2 19];
X = sdpvar(2);
obj = trace(C*X) +  sum(sum(abs(X)))
Constraint = [norm(X,'fro') <= 1, X>=0]
M = export(Constraint,obj,sdpsettings('solver','sedumi'));
M.b'
-7    -4   -19    -1    -1    -1    -1     0

The problem has three variables defining $X$, 4 variables to model the absolute values $t_{ij}$ (that's a performance bug, should be three, redundancy due to symmetry is missed) and one variable to represent the Frobenius norm. You see directly how these enter the objective through $b$. Studying $A$ and $C$ reveals that it is exactly the model you expect (9 linear inequalities to describe the 4 absolute values and the upper bound on the norm, involving YALMIPs dummy variable, an SOCP, and an SDP). Your confusion is most likely caused by the fact that you are trying to match the data to the primal representation of an SDP, $\min CX \text{ subject to } Ax=b,X\succeq 0$ thus giving a non-intuitive model.