F has an uniquely defined global minimum

[mathmari]

Hey!

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)

 

[I like Serena]

Hey!

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*}

Hey mathmari!

Shouldn't that be:
\begin{equation*}f(x)=\sum_{j=1}^k\|x-a_j\|^2=\sum_{j=1}^k\sum_{i=1}^n(x_i-a_{j;i})^2\end{equation*}
(Thinking)

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*}

That also applies here, and wasn't a factor 2 dropped?
That is, shouldn't it be:
\begin{align*} f_{x_m}&=\sum_{j=1}^k2(x_m-a_{j;m})=\sum_{j=1}^k2x_m-2\sum_{j=1}^ka_{j;m}=2x_m\sum_{j=1}^k1-2\sum_{j=1}^ka_{j;m}=2x_mk-2\sum_{j=1}^ka_{j;m}\\ & =2kx_m-2\sum_{j=1}^ka_{j;m}\end{align*}
(Thinking)

 

[mathmari]

Shouldn't that be:
\begin{equation*}f(x)=\sum_{j=1}^k\|x-a_j\|^2=\sum_{j=1}^k\sum_{i=1}^n(x_i-a_{j;i})^2\end{equation*}
(Thinking)
That also applies here, and wasn't a factor 2 dropped?
That is, shouldn't it be:
\begin{align*} f_{x_m}&=\sum_{j=1}^k2(x_m-a_{j;m})=\sum_{j=1}^k2x_m-2\sum_{j=1}^ka_{j;m}=2x_m\sum_{j=1}^k1-2\sum_{j=1}^ka_{j;m}=2x_mk-2\sum_{j=1}^ka_{j;m}\\ & =2kx_m-2\sum_{j=1}^ka_{j;m}\end{align*}
(Thinking)

Oh yes, you're right! (Tmi) The gradient is then equal to \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{2\sum_{j=1}^ka_{j;1}}\\ 2kx_2-\displaystyle{2\sum_{j=1}^ka_{j;2}} \\ 2kx_3-\displaystyle{2\sum_{j=1}^ka_{j;3}} \\ \vdots \\ 2kx_{n-1}-\displaystyle{2\sum_{j=1}^ka_{j;(n-1)}} \\ 2kx_n-\displaystyle{2\sum_{j=1}^ka_{j;n}}\end{pmatrix}=2k\begin{pmatrix}x_1\\ x_2 \\ x_3 \\ \vdots \\ x_{n-1} \\ x_n\end{pmatrix}-2\begin{pmatrix}\displaystyle{\sum_{j=1}^ka_{j;1}}\\ \displaystyle{\sum_{j=1}^ka_{j;2}} \\ \displaystyle{\sum_{j=1}^ka_{j;3}} \\ \vdots \\ \displaystyle{\sum_{j=1}^ka_{j;(n-1)}} \\ \displaystyle{\sum_{j=1}^ka_{j;n}}\end{pmatrix}=2kx-2\displaystyle{\sum_{j=1}^ka_{j}}\end{equation*}

For the ccritical point we set the gradient equal to $0$: \begin{equation*}2kx-2\displaystyle{\sum_{j=1}^ka_{j}}=\mathbf{0} \Rightarrow 2kx=2\displaystyle{\sum_{j=1}^ka_{j}}\Rightarrow x=\frac{1}{k}\displaystyle{\sum_{j=1}^ka_{j}}\end{equation*}

So, we have an extremum at $\frac{1}{k}\displaystyle{\sum_{j=1}^ka_{j}}$.

The partial derivatives of second order are:
\begin{align*}&f_{x_mx_m}=\frac{\partial}{\partial{x_m}}\left (2kx_m-2\sum_{j=1}^ka_{j;m}\right )=2k \\ &f_{x_mx_{\ell}}=\frac{\partial}{\partial{x_{\ell}}}\left (2kx_m-2\sum_{j=1}^ka_{j;m}\right )=0\end{align*}

The Hessian matrix is equal to
\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*}

The only eigenvalue is $\lambda=2k>0$. So, it follows that at the critical point we have a local minimum.
Is now everything correct so far? (Wondering)

 

[I like Serena]

Is now everything correct so far? (Wondering)

Yep. All correct now. (Happy)

 

[mathmari]

Yep. All correct now. (Happy)

Great! (Happy)

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

How can we show that the local minimum that we found is a global minimum?

(Wondering)

 

[I like Serena]

Great! (Happy)

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

How can we show that the local minimum that we found is a global minimum?

(Wondering)

Yes. Since there is only 1 critical point, there is only 1 internal local extremum, which is a local minimum.
It is a global minimum if there is no lower minimum on the boundary, or, as in this case, the value of $f$ is greater than the minimum as $x\to\infty$.
What happens to $f$ if $x\to\infty$? (Wondering)

 

[mathmari]

Yes. Since there is only 1 critical point, there is only 1 internal local extremum, which is a local minimum.
It is a global minimum if there is no lower minimum on the boundary, or, as in this case, the value of $f$ is greater than the minimum as $x\to\infty$.
What happens to $f$ if $x\to\infty$? (Wondering)

Ah ok!

Does $f$ tend to infinity if $x$ goes to infinity? (Wondering)

 

[I like Serena]

Ah ok!

Does $f$ tend to infinity if $x$ goes to infinity?

Yes. Can you tell why? (Wondering)

 

[mathmari]

Yes. Can you tell why? (Wondering)

The function must tend to $+\infty$ so that we can tell that the loca minimum that we found is also a global one, or not?

We have that $$f(x)=\sum_{j=1}^k\|x-a_j\|^2$$ If $\|x\|\to \infty$ then $\|x-a_j\|\to \infty$ and so the whole right side tends to $+\infty$ because of the square, or not? (Wondering)

 

[I like Serena]

The function must tend to $+\infty$ so that we can tell that the loca minimum that we found is also a global one, or not?

We have that $$f(x)=\sum_{j=1}^k\|x-a_j\|^2$$ If $\|x\|\to \infty$ then $\|x-a_j\|\to \infty$ and so the whole right side tends to $+\infty$ because of the square, or not? (Wondering)

Yep. All correct. (Nod)

 

[mathmari]

Yep. All correct. (Nod)

Great! (Yes) The minimum of the function is therefore equal to \begin{equation*}f\left (\frac{1}{k}\sum_{j=1}^ka_{j}\right )=\sum_{j=1}^k\left \|\frac{1}{k}\sum_{j=1}^ka_{j}-a_j\right \|^2\end{equation*} Can we simplify this expression further? I am a bit confused with the two $a_j$'s. Only the first one is in the inner sum, isn't it? But both are in the outer sum? (Wondering)

 

[I like Serena]

Great! (Yes) The minimum of the function is therefore equal to \begin{equation*}f\left (\frac{1}{k}\sum_{j=1}^ka_{j}\right )=\sum_{j=1}^k\left \|\frac{1}{k}\sum_{j=1}^ka_{j}-a_j\right \|^2\end{equation*} Can we simplify this expression further? I am a bit confused with the two $a_j$'s. Only the first one is in the inner sum, isn't it? But both are in the outer sum? (Wondering)

Indeed. Let's use a different index variable before substituting, say $\ell$.
Then we get:
\begin{equation*}f\left (\frac{1}{k}\sum_{\ell=1}^ka_{\ell}\right )
=\sum_{j=1}^k\left \|\frac{1}{k}\sum_{\ell=1}^ka_{\ell}-a_j\right \|^2
=\sum_{j=1}^k\left \|\sum_{\ell=1}^k \left(\frac{1}{k}a_{\ell}-\delta_{j\ell}a_j\right)\right \|^2
=\sum_{j=1}^k\left \|\sum_{\ell=1}^k \left(\frac{1}{k}-\delta_{j\ell}\right)a_j\right \|^2
\end{equation*}
where $\delta_{ij}$ is the Kronecker delta, don't we? (Wondering)

 

[mathmari]

Indeed. Let's use a different index variable before substituting, say $\ell$.
Then we get:
\begin{equation*}f\left (\frac{1}{k}\sum_{\ell=1}^ka_{\ell}\right )
=\sum_{j=1}^k\left \|\frac{1}{k}\sum_{\ell=1}^ka_{\ell}-a_j\right \|^2
=\sum_{j=1}^k\left \|\sum_{\ell=1}^k \left(\frac{1}{k}a_{\ell}-\delta_{j\ell}a_j\right)\right \|^2
=\sum_{j=1}^k\left \|\sum_{\ell=1}^k \left(\frac{1}{k}-\delta_{j\ell}\right)a_j\right \|^2
\end{equation*}
where $\delta_{ij}$ is the Kronecker delta, don't we? (Wondering)

Ah ok! Thank you! (Mmm)