- #1

mathmari

Gold Member

MHB

- 5,049

- 7

Let $a_1, a_2, \ldots , a_k\in \mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow \mathbb{R}$ defined by $\displaystyle{f(x)=\sum_{j=1}^k\|x-a_j\|^2}$ with the euclidean norm $\|\cdot \|$.

Show that f has an uniquely defined global minimum and calculate it. I have done the following:

\begin{equation*}f(x)=\sum_{j=1}^k\|x-a_j\|^2=\sum_{j=1}^k\sum_{i=1}^n(x_i-a_j)^2\end{equation*} The partial derivative in respect to $x_m$ is \begin{align*} f_{x_m}&=\sum_{j=1}^k2(x_m-a_j)=\sum_{j=1}^k2x_m-\sum_{j=1}^ka_j=2x_m\sum_{j=1}^k1-\sum_{j=1}^ka_j=2x_mk-\sum_{j=1}^ka_j\\ & =2kx_m-\sum_{j=1}^ka_j\end{align*}

The gradient is \begin{equation*}\text{grad}(f)=\begin{pmatrix}f_{x_1} \\ f_{x_2} \\ f_{x_3} \\ \vdots \\ f_{x_{n-1}} \\ f_{x_n}\end{pmatrix}=\begin{pmatrix}2kx_1-\displaystyle{\sum_{j=1}^ka_j}\\ 2kx_2-\displaystyle{\sum_{j=1}^ka_j} \\ 2kx_3-\displaystyle{\sum_{j=1}^ka_j} \\ \vdots \\ 2kx_{n-1}-\displaystyle{\sum_{j=1}^ka_j} \\ 2kx_n-\displaystyle{\sum_{j=1}^ka_j}\end{pmatrix}=2k\begin{pmatrix}x_1\\ x_2 \\ x_3 \\ \vdots \\ x_{n-1} \\ x_n\end{pmatrix}-\displaystyle{\sum_{j=1}^ka_j}\begin{pmatrix}1\\ 1 \\ 1 \\ \vdots \\ 1 \\ 1\end{pmatrix}=2kx-\displaystyle{\sum_{j=1}^ka_j}\begin{pmatrix}1\\ 1 \\ 1 \\ \vdots \\ 1 \\ 1\end{pmatrix}\end{equation*}

We get the critical point if we set the gradient equal to $0$: \begin{equation*}2kx-\displaystyle{\sum_{j=1}^ka_j}\begin{pmatrix}1\\ 1 \\ 1 \\ \vdots \\ 1 \\ 1\end{pmatrix}=\begin{pmatrix}0\\ 0 \\ 0 \\ \vdots \\ 0 \\ 0\end{pmatrix} \Rightarrow 2kx=\displaystyle{\sum_{j=1}^ka_j}\begin{pmatrix}1\\ 1 \\ 1 \\ \vdots \\ 1 \\ 1\end{pmatrix}\Rightarrow x=\left (\frac{1}{2k}\cdot \displaystyle{\sum_{j=1}^ka_j}\right )\cdot \begin{pmatrix}1\\ 1 \\ 1 \\ \vdots \\ 1 \\ 1\end{pmatrix}\end{equation*}

So, we have an extremum at $\left (\frac{1}{2k}\cdot \displaystyle{\sum_{j=1}^ka_j}\right )\cdot \begin{pmatrix}1\\ 1 \\ 1 \\ \vdots \\ 1 \\ 1\end{pmatrix}$.

The partial derivatives of second order are

\begin{align*}&f_{x_mx_m}=\frac{\partial}{\partial{x_m}}\left (2kx_m-\sum_{j=1}^ka_j\right )=2k \\ &f_{x_mx_{\ell}}=\frac{\partial}{\partial{x_{\ell}}}\left (2kx_m-\sum_{j=1}^ka_j\right )=0\end{align*}

So the Hessian-Matrix is:

\begin{equation*}H_f(x)=\begin{pmatrix}2k & 0 & 0 & \ldots & 0 & 0 \\ 0 & 2k & 0 & \ldots & 0 & 0 \\ 0 & 0 & 2k & \ldots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \ldots & 0 &2k & 0\\ 0 & 0 & \ldots & 0 & 0 &2k\end{pmatrix}\end{equation*}

Since we have a diagonal matrix, we get the eigenvalue from the diagonal: $\lambda=2k>0$.

Since $2k$ is positive, it follows that at the critical point we have a local minimum. Is everything correct? How can we show that this is a global minimum?

By uniquely defined is it mean that we have just one minimum?

(Wondering)