3
$\begingroup$

Given the two strictly convex (unique solution) optimization problems as:

$$Problem\:1:\min_{X} f(X)+\|X\|_{F}^2 \hspace{2cm}Problem \:2:\min_{X}f(X)+n\|X\|_2^2$$

where $X\in\mathbf{S}_{++}^{n}$ (being positive definite), $f(X)$ is strictly convex, $\|\cdot\|_{F}$ is the frobenius norm, and $\|\cdot\|_2$ is the spectral norm. Let $X_1$ and $X_2$ denote the solutions to problem 1 and 2, respectively.

Question: Prove that $f(X_1)\leq f(X_2)$ (or please provide a counterexample if you believe that this does not always hold). I highly appreciate any help or suggestions. Thanks.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ An idea: define $$X_t=\text{argmin} f(X)+t ||X||_F^2+(1-t)n||X||_2^2.$$ and then try to prove that $t \mapsto f(X_t)$ is monoton. However I dont know if this works or not. $\endgroup$
    – user35593
    Commented Aug 12, 2014 at 15:39
  • 1
    $\begingroup$ other ansatz: As $f$ is convex there is Matrix $A$ and $c>0$ s.t. $$f(X) \geq f(X_1)+\langle A, X-X_1 \rangle + c \|X-X_1\|_F^2$$ where $\langle A,B \rangle:=trace(A^TB)$. Note that $\|A\|_F^2=\langle A,A \rangle$ and hence $$f(X)+\|X\|_F^2=f(X_1)+\|X_1\|_F^2+\langle A+2X_1,X-X_1\rangle+(1+c) \|X-X_1\|_F^2$$ and by the minimality of $X_1$ we get $A=-2X_1$. Now to prove that $f(X_2)\geq f(X_1)$ it would suffice by the first inequ. that $$\langle 2X_1,X_1-X_2\rangle+\|X-X_1\|_F^2\geq 0.$$ For this it would suffice to prove that $$\langle 2X_1,X_1-X_2\rangle\geq 0.$$ $\endgroup$
    – user35593
    Commented Aug 12, 2014 at 16:17
  • $\begingroup$ Nice ways to tackle this problem. The second route looked more promising, but doing similar steps to the ones you described, now with the spectral norm involved, and finding another inequality seems challenging. $\endgroup$
    – borntotry83
    Commented Aug 13, 2014 at 2:38

0

Reset to default

You must log in to answer this question.