Convex Optimization - Minimizing the Frobenius Norm of a Matrix with Linear Inequality Constraint of its Vectorization

I have the following optimization problem:

Minimize $\|X\|_F$ subject to $Ax\le b$

Where $X$ is a matrix in $\mathbb{R}_{n\times n}$ of variables, $x$ is the $n^2$ vector of those variables and $A\in \mathbb{R}_{n^2\times n^2},b\in\mathbb{R}^{n^2}$, and $\|\cdot\|_F$ is the Frobenius norm $\|X\|_F = \sqrt{\text{tr}(AA^T)}$.

If I understand correctly, this is a convex optimization problem and can be solved with convex optimization tools, but my search did not find an explicit treatment of the subject and I believe I'm missing obvious tricks.

What is the standard way of solving this problem using convex optimization? Are there any transformations which makes this, e.g. a semidefinite linear programming problem? A quadratic programming problem? etc.

• There is no constraint that $X$ be positive semi definite, right? The Frobenius norm of $X$ is simply the two norm of $x$. – Brian Borchers May 21 '18 at 15:35
• How large is $n$? How much memory does $A$ take up? – littleO May 21 '18 at 16:39

Minimizing $${\left\| X \right\|}_{F}$$ is equivalent of minimizing $${\left\| X \right\|}_{F}^{2}$$ which is equivalent of minimizing $${\left\| x \right\|}_{2}^{2}$$ where $$x = \operatorname{vec} \left( X \right)$$, namely the Vectorization Operator applied on $$X$$.

Now you can write your problem as:

\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| C x - d \right\|}_{2}^{2} \\ \text{subject to} \quad & A x \leq b \end{align*}

Where $$C = I$$ and $$d = \boldsymbol{0}$$.

Now all you need is to utilize Linear Least Squares solver which supports Linear Inequality constraints.

• That's not L1 minimization, Alec. – Dirk Jan 9 at 5:28

Since $\|X\|_F=\|x\|_2$, this is most naturally formulated as a second-order conic problem (SOCP).