0
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ That's not L1 minimization, Alec. $\endgroup$ – Dirk Jan 9 at 5:28
2
$\begingroup$

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

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