Skip to main content
MathOverflow

Return to Question

improved the way of asking the question
Source Link
borntotry83
borntotry83
  • 53
  • 6

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

Although an intuitively simple result due to the fact that $\|X\|_{F}^2\leq n\|X\|_2^2$, the ''nonlinear'' increase of the penalization may make the proof(or please provide a counterexample if you believe that this does not so easyalways hold). I highly appreciate any help or suggestions. Thanks.

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

Although an intuitively simple result due to the fact that $\|X\|_{F}^2\leq n\|X\|_2^2$, the ''nonlinear'' increase of the penalization may make the proof not so easy. I highly appreciate any help or suggestions. Thanks.

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.

Source Link
borntotry83
borntotry83
  • 53
  • 6

On increasing the penalty term in convex optimization with regularization

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

Although an intuitively simple result due to the fact that $\|X\|_{F}^2\leq n\|X\|_2^2$, the ''nonlinear'' increase of the penalization may make the proof not so easy. I highly appreciate any help or suggestions. Thanks.