Show that the critical point of this function is a global minimum (geometric median)

Question

I am given the following function for $a^1, a^2, .... , a^n \in \mathbb{R}^n$:

$$f: \mathbb{R}^n \rightarrow \mathbb{R},\, f(x) = \sum_{i=1}^k\left|x-a^{i}\right|_{2}^2$$ where the subscript 2 denotes the euclidean norm.

---

What am I asked to show is that:

1. $f$ has only one critical point $\overline{x}$ (this critical point is the geometric median)
2. That $\overline{x}$ is a global minimum

---

I am stuck with the second part. Here is what I've got so far:

By definition $\overline{x}$ is a critical point if $$\nabla f(\bar{x}) = 0$$

Computing the gradient of $f$:

$$\nabla f(x) = kx - \sum_{i=1}^k a^{i} $$

Setting this equal to zero and solving for $x$:

$$kx - \sum_{i=1}^k a^{i} = 0 \Longrightarrow x = \frac{\sum_{i=1}^k a^{i} }{k} $$

This is the only critical point one can find.

For the second part, I know that $f(\overline{x})$ is a global minimum if $f(x) \geq f(\bar{x})$ for all $x\in \mathbb{R}^n$.

The Hessian Matrix will be a matrix with $k's$ on the diagonal and every other matrix element zero and with $k \in \mathbb{N}$ this means, the Hessian is positive definite which atleast shows that the critical point I have found is a local minimum.

However, being the only local minimum doesn't imply it is the global minimum so how can I show that this critical point is in fact the global minimum?

Answer 1

If $$\bar{x}=\frac1k\sum_{i=1}^k a^i$$ Then $$\eqalign{f(x)&=\sum_{i=1}|x-\bar{x}+\bar{x}-a_i|^2\cr &=\sum_{i=1}\left(|x-\bar{x}|^2+2\langle x-\bar{x},\bar{x}-a_i \rangle+|\bar{x}-a_i|^2\right)\cr &=n|x-\bar{x}|^2+\sum_{i=1}|\bar{x}-a_i|^2+2 \langle x-\bar{x},\underbrace{\sum_{i=1}^k(\bar{x}-a_i) }_0\rangle\cr &=n|x-\bar{x}|^2+\sum_{i=1}|\bar{x}-a_i|^2\cr &=n|x-\bar{x}|^2+ f(\bar{x}) }$$ Thus $ f(x) \ge f(\bar{x})$ with equality if and only if $x=\bar{x}$.