0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Maybe you can show this function is convex. It looks like a sum of convex functions. A local minimum of a convex function is a global minimum. $\endgroup$ – AnonymousCoward Jul 2 '17 at 16:01
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much, that was beautiful! $\endgroup$ – Eren Jul 3 '17 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.