Find $\min(x^Tx+a||x-c||_2), a>0, x \in \mathbb{R}^n$

Question

Find $\min(x^Tx+a\|x-c\|_2), a>0, x \in \mathbb{R}^n$

My attempt:

Expression is convex, so I think that it will attain minimum at the point where gradient is zero.

I calculated $\nabla = 2x^T- a(x-c)^T/\|x-c\|_2 = 0$

After that I got stuck and don't know how to solve this equation.

Answer 1

If $x\ne c$, then the derivative of your function for $x\ne c$ is $$ \nabla f = 2x + a\frac{x-c}{\|x-c\|_2}. $$ The equation $\nabla f(x)=0$ implies that $x$ and $x-c$ are linearly dependent, which implies that $x$ is a multiple of $c$, $x = s c$. The equation $\nabla f(sc)=0$ is equivalent to $$ 2s + a \frac{s-1}{|s-1|\cdot \|c\|}=0, \ s\ne 0. $$ In case $s>1$ this means $s=-\frac a{2\|c\|}<0$, which is a contradiction. In case $s<1$, we get $s=\frac a{2\|c\|}$. Hence the point $x=\frac a{2\|c\|} c$ is stationary hence optimal if $a<2\|c\|$.

If $a\ge2\|c\|$ then no point of differentiability of $f$ is optimal. However, $f$ has compact level sets, hence it has a global minimum, which has to sit in the point of non-differentiability $x=c$.

The point $c$ is not optimal if $a<2\|c\|$, since then all points between $c$ and $\frac a{2\|c\|}c$ have to be optimal due to convexity, which is not the case.

This shows that the global minimum of $f$ is given by $$ x = \min\left(\frac a{2\|c\|},1\right)c. $$

Answer 2

From the gradient you get $||x|| = 0.5a$ (since $(x-c)/||x-c||$ has length 1). To get an idea what $x$ should be, look at the objective value: $0.25a^2 +a ||x-c||_2$. This is minimized when $x$ is as close to $c$ as possible, so $x=0.5a c/||c||$ probably works. Daw shows that indeed the gradient is $0$ in the case as long as $a<2||c||$.