convex for two variables

Question

Suppose we have the following optimization problem: $$\min_{X,Y}~L=\min_{X,Y}~\|A-XY\|_2^2,$$ where $X\in R^{m\times n}$, $Y\in R^{n\times p}$ and $A\in R^{m\times p}$. Could someone give me some hints on how to determine the convexity of the formulation of $L$. Thanks and best regards.

Answer 1

The function $L(X,Y)=\|A-XY\|_2^2$ is not convex. To construct a counterexample, let's perform the SVD of $A=U\Sigma V^T$ and notice that $$ L(X,Y)=\|A-XY\|_2^2=\|U^T(A-XY)V\|_2^2=\|\Sigma-\underbrace{U^TX}_{\tilde X}\underbrace{YV}_{\tilde Y}\|_2^2=\tilde L(\tilde X,\tilde Y). $$ Since the relations $X\leftrightarrow\tilde X$, $Y\leftrightarrow\tilde Y$ are linear, the convexity of $L$ is equivalent to that of $\tilde L$.

Now take $$ \tilde X=\left[\matrix{x & 0\\0 & 0}\right],\quad \tilde Y=\left[\matrix{-y & 0\\0 & 0}\right],\qquad x,y\ge 0. $$ Then $$ \tilde L(\tilde X,\tilde Y)=\left\|\left[\matrix{\sigma_1+xy & &\\&\sigma_2 &\\&&\ddots}\right]\right\|_2^2= (\sigma_1+xy)^2=f(x,y). $$ The function $f(x,y)$ is not convex for $x,y\ge 0$ because its Hessian is indefinite there: $$ \nabla f(x,y)=2(\sigma_1+xy)\left[\matrix{y\\x}\right],\qquad \nabla^2 f(x,y)=2\left[\matrix{y^2 & \sigma_1+2xy\\\sigma_1+2xy & x^2}\right] $$ and $$ \det\nabla^2 f(x,y)=4[x^2y^2-(\sigma_1+2xy)^2]=-4(\sigma_1+3xy)(\sigma_1+xy)<0,\quad x,y\ge 0. $$ Thus $\tilde L$, and hence $L$, is not convex.