Unique solution of convex problem

187 Views Asked by At

Let's define for fixed $x\in R^n$ and $c\in R$ the function $F(y)=\|x-cy\|_2^2$. It is not diffucult to prove that $F$ is strictly convex, i.e, for $t\in(0,1)$ $F(ty_1+(1-t)y_2) < tF(y_1)+(1-t)F(y_2)$. So the problem $$\min_{y\in\Omega}F(y)$$ has unique solution provided that $\Omega$ is convex. What if I define $\Omega=\{y:\|y\|_2=1\}$? Clearly $\Omega$ is not convex, but if I find the minimum using lagrange multipliers I find the same solution as if $\Omega=\{y:\|y\|_2\leq 1\}$, which is a convex set.

The concrete question is this: can I guarantee a unique solution of the minimization problem when $\Omega=\{y:\|y\|_2=1\}$?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $c=0$, then this will make $F$ a constant function.

Hence, there is no uniqueness of solution.

Alternatively, let $x=0$, then $F(y)=|c|\|y\|_2^2=|c|$, again, every solution is optimal.

If $x \ne 0$ and $c \ne 0$, then we have over the circle,

$$\min \|x-cy\|^2 = x^Tx-2cx^Ty+1=(x^Tx+1)-2cx^Ty$$

which is affine with some of the coefficients non-zero, hence it is unique.