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.

  • 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 Aug 12 '14 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 Aug 12 '14 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 Aug 13 '14 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.