4
$\begingroup$

There is a famous problem here; however, this is not I want to ask (about proximal operator).

Suppose I have an easy optimization problem:

$$\min_Q \|Q-Q_N\|_F$$

where $\|\cdot\|_F$ is the Frobenius norm: $\|X\|_F = (\operatorname{tr}(X^TX))^{\frac{1}{2}}$.

We know we can consider the following:

$$\mathcal{A}(Q,t) = \begin{bmatrix}I & Q-Q_N\\ (Q-Q_N)^T & tI \end{bmatrix}\succeq 0$$

By Schur complement we have the following $$tI-(Q-Q_N)^T(Q-Q_N)\succeq 0$$

If $Q\in \mathbb{R}$, the above becomes $$t-\|Q-Q_N\|^2\geq 0 \Rightarrow t\geq \|Q-Q_N\|^2 \geq 0$$ So the original problem is equivalent to \begin{align} &\min_{t,Q} & &t \\ & s.t. & & \|Q-Q_N\|^2 \geq 0 \end{align} or
\begin{align} &\min_{t,Q} & &t \\ & s.t. & & \mathcal{A}(t,Q)\succeq 0 \end{align} The second formulation is a SDP

My question is: if $Q\in \mathbb{R}^{n\times n}$ how to obtain the above convex optimization problem (minimize over $t$) with $\|\cdot\|^2$ replaced by $\|\cdot\|_F^2$

Is there any method except the vectorization of matrices?

$\endgroup$
6
$\begingroup$

Are you asking for the problem

$$\text{minimize trace(X) subj. to . } \begin{bmatrix}I & Q-Q_N\\ (Q-Q_N)^T & X \end{bmatrix}\succeq 0$$

which minimizes the Frobenius norm of $Q-Q_N$?

$\endgroup$
  • $\begingroup$ So now variables in your optimization is "$X$ and $Q$" and obviously, it is a SDP. Right? $\endgroup$ – sleeve chen Mar 13 '17 at 19:57
  • $\begingroup$ Yes, that is correct $\endgroup$ – Johan Löfberg Mar 14 '17 at 18:03
  • $\begingroup$ Can you do something similar for every Schatten p-norm? $\endgroup$ – Noel Mar 4 at 20:27
  • $\begingroup$ If you mean $(\sum |a_{ij}|_p)^{1/p}$, that's SOCP-representable for rational $p$, but way too complicated for a simple comment. Alternatively, it can be directly represented using the power cone $\endgroup$ – Johan Löfberg Mar 5 at 6:53
  • $\begingroup$ I have created a question for this: math.stackexchange.com/questions/3140803/… $\endgroup$ – Noel Mar 9 at 4:56

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.