# Finding the global minimum of $f(\mathbf{x})=\|(1-x_1,x_1-x_2,x_2-x_3,\ldots,x_{n-1}-x_n,x_n-2)\|_2^2$

I am self-learning optimization algorithms. A certain assignment problem is as follows:

Show that the $$n$$-dimensional function

$$f(\mathbf{x})=\|(1-x_1,x_1-x_2,x_2-x_3,\ldots,x_{n-1}-x_n,x_n-2)\|_2^2$$

has exactly one stationary point which is a global minimum. Compute this minimum.

I would like someone to verify my optimal solution; does the math checkout?

Solution.

We have,

\begin{align*} f(\mathbf{x})= (1-x_1)^2+(x_1-x_2)^2+\ldots+(x_{n-1}-x_{n})^2 + (x_n-2)^2 \end{align*}

The partial derivatives of $$f$$ are as follows:

\begin{align*} f_{x_1}(\mathbf{x}) &= 2(1-x_1)(-1)+2(x_1-x_2) = -2 + 4x_1 - 2x_2\\ f_{x_2}(\mathbf{x}) &= 2(x_1-x_2)(-1)+2(x_2-x_3) = -2x_1 + 4x_2 -2x_3 \\ f_{x_3}(\mathbf{x}) &= 2(x_2-x_3)(-1)+2(x_3-x_4) = -2x_2 + 4x_3 -2x_4 \\ \vdots\\ f_{x_{n-1}}(\mathbf{x}) &= 2(x_{n-2}-x_{n-1})(-1)+2(x_{n-1}-x_n) = -2x_{n-2} + 4x_{n-1} -2x_n \\ f_{x_n}(\mathbf{x}) &= 2(x_{n-1}-x_n)(-1)+2(x_n-2) = -2x_{n-1} + 4x_n -4 \end{align*}

The critical points of $$f$$ are given by,

$$\nabla f(\mathbf{x}) = 0$$

Therefore, we have the system of equations:

\begin{align*} \begin{bmatrix} 4 &-2 & 0 & 0 & 0 & \ldots & 0 & 0 & 0\\ -2& 4 &-2 & 0 & 0 & \ldots & 0 & 0 & 0\\ 0 &-2 & 4 &-2 & 0 & \ldots & 0 & 0 & 0\\ 0 & 0 &-2 & 4 &-2 & \ldots & 0 & 0 & 0\\ 0 & 0 & 0 &-2 & 4 & \ldots & 0 & 0 & 0\\ 0 & 0 & 0 & 0 &-2 & \ldots & 0 & 0 & 0\\ \vdots\\ 0 & 0 & 0 & 0 & 0 & \ldots &-2 & 4 &-2\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 &-2 & 4 \end{bmatrix}\begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ \vdots\\ x_{n-1}\\ x_n \end{bmatrix}=\begin{bmatrix} 2\\ 0\\ 0\\ 0\\ 0\\ 0\\ \vdots\\ 0\\ 4 \end{bmatrix} \end{align*}

These are $$n$$ equations in $$n$$ unknowns. This tridiagonal system has a unique solution vector $$\mathbf{x}$$. Applying Gaussian elimination to the augmented matrix $$[A \quad b]$$, by hand, we have:

\begin{align*} \begin{bmatrix} 4 &-2 & 0 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ -2& 4 &-2 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 &-2 & 4 &-2 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 &-2 & 4 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 &-2 & 4 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 & 0 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ \vdots & & & & & & & & &\bigm| & \vdots\\ 0 & 0 & 0 & 0 & 0 & \ldots &-2 & 4 &-2 &\bigm| & 0\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 &-2 & 4 &\bigm| & 4\\ \end{bmatrix} \end{align*}

Applying \begin{align*} \{R_2 \rightarrow 2R_2 + R_1\} \end{align*}

\begin{align*} \begin{bmatrix} 4 &-2 & 0 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 6 &-4 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 &-2 & 4 &-2 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 &-2 & 4 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 &-2 & 4 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 & 0 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ \vdots & & & & & & & & &\bigm| & \vdots\\ 0 & 0 & 0 & 0 & 0 & \ldots &-2 & 4 &-2 &\bigm| & 0\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 &-2 & 4 &\bigm| & 4\\ \end{bmatrix} \end{align*}

Applying \begin{align*} \{R_3 \rightarrow 3R_3 + R_2\} \end{align*}

\begin{align*} \begin{bmatrix} 4 &-2 & 0 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 6 &-4 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 8 &-6 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 &-2 & 4 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 &-2 & 4 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 & 0 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ \vdots & & & & & & & & &\bigm| & \vdots\\ 0 & 0 & 0 & 0 & 0 & \ldots &-2 & 4 &-2 &\bigm| & 0\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 &-2 & 4 &\bigm| & 4\\ \end{bmatrix} \end{align*}

Applying \begin{align*} \{R_4 \rightarrow 4R_4 + R_3\} \end{align*}

\begin{align*} \begin{bmatrix} 4 &-2 & 0 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 6 &-4 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 8 &-6 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 0 &10 &-8 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 0 &-2 & 4 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ 0 & 0 & 0 & 0 &-2 & \ldots & 0 & 0 & 0 &\bigm| & 0\\ \vdots & & & & & & & & &\bigm| & \vdots\\ 0 & 0 & 0 & 0 & 0 & \ldots &-2 & 4 &-2 &\bigm| & 0\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 &-2 & 4 &\bigm| & 4\\ \end{bmatrix} \end{align*}

Continuing in this fashion, we obtain after $$\{R_n\rightarrow n R_n + R_{n-1}\}$$,

\begin{align*} \begin{bmatrix} 4 &-2 & 0 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 6 &-4 & 0 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 8 &-6 & 0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 0 &10 &-8 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 0 &0 & 12 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ 0 & 0 & 0 & 0 &0 & \ldots & 0 & 0 & 0 &\bigm| & 2\\ \vdots & & & & & & & & &\bigm| & \vdots\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 & 2n &-2(n-1) &\bigm| & 2\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 &0 & 2n+2 &\bigm| & 4n+2 \end{bmatrix} \end{align*}

By back-substitution, \begin{align} (2n+2)x_n &= 4n+2\\ x_n &= \frac{2n+1}{n+1} \tag{1} \end{align}

Substituting the value of $$x_n$$ in $$2n x_{n-1} -2(n-1)x_n = 2$$, we have: \begin{align} 2n x_{n-1} &= 2 + 2(n-1)x_n\\ x_{n-1} &= \frac{1}{n}\left[1 + (n-1)x_n\right]\\ &= \frac{1}{n}\left[1 + (n-1)\frac{2n+1}{n+1}\right]\\ &= \frac{1}{n}\left[\frac{(n+1)+(n-1)(2n+1)}{n+1}\right]\\ &= \frac{1}{n}\left[\frac{(n+1)+n(2n+1)-(2n+1)}{n+1}\right]\\ &= \frac{1}{n}\left[\frac{n + 1 + 2n^2 + n - 2n - 1}{n+1}\right]\\ &= \frac{1}{n}\left[\frac{2n^2}{n+1}\right]\\ &= \frac{2n}{n+1} \tag{2} \end{align}

As the recurrence relationship stays the same for $$n \in \{1,2,3,4,\ldots,n-1\}$$, we have: \begin{align*} x_{n-1} &= \frac{2n}{n+1}\\ x_{n-2} &= \frac{2n-1}{n+1}\\ x_{n-3} &= \frac{2n-2}{n+1}\\ \vdots\\ x_3 &= \frac{n+4}{n+1}\\ x_2 &= \frac{n+3}{n+1}\\ x_1 &= \frac{n+2}{n+1} \end{align*}

Now, the Hessian of $$f$$, $$Hf(\mathbf{x})$$ is the same tridiagonal matrix $$A$$ as above. If we find the sequence of determinants $$\det(B_k)$$, where $$B_k$$ is a $$k \times k$$ sub-matrix of $$A$$ in the upper-left corner, we see that $$\det(B_1) = 4, \det(B_2) = 8, \det(B_3) = 16, \ldots, \det(B_n)=2^{n+1}$$. Consequently, the critical point $$\mathbf{x}$$ is a global minima.

The minimum value of $$f$$ is given by,

\begin{align} \min \{f(\mathbf{x}):\mathbf{x}\in \mathbf{R}^n \} &=\left(1-\frac{n+2}{n+1}\right)^2 + \left(\frac{1}{n+1}\right)^2 + \ldots + \left(\frac{2n+1}{n+1}-2\right)^2\\ &= \frac{(n+1)}{(n+1)^2}\\ &= \frac{1}{n+1} \end{align}

• Note that since $f$ is convex (as a sum of quadratic terms), you don't even have to check the Hessian, the stationary point is the unique global minimum. – Kuifje May 9 at 10:34
• I haven't thoroughly checked your math, but if you take $n=1$, you have $f(x)=(1-x)^2+(2-x)^2$ which indeed has global minimum in $x=\frac{n+2}{n+1}=\frac{3}{2}$, with value $f^*=\frac{1}{n+1}=\frac{1}{2}$. It doesn't prove that you are right, but its a good sign. – Kuifje May 9 at 17:10
• @Kuifje - wolframalpha.com/input/… – Quasar May 9 at 17:16

The math looks good but why starting with $$\nabla f(x) = 0$$ instead of $$\frac{1}{2}\nabla f(x) = 0$$? You should have noticed that the factor $$2$$ was everywhere and could be simplified.
For the curious readers who wonder whether there exists a simpler solution to this simple problem: the answer is yes. It suffices to notice that the sum of the elements of $$f(x)$$ is a constant ($$-1$$) and apply the following inequality: $$$$m(a_1^2 +a_2^2+\dots+a_m^2) \ge (a_1+a_2+\dots+a_m)^2,$$$$ with equality occurs if and only if $$a_1=a_2=\dots=a_m$$. More concretely one should use the form $$(a_0^2 +a_1^2+\dots+a_n^2) \ge \frac{1}{n+1} (a_0+a_1+\dots+a_n)^2,$$ where the $$a_i$$ are the $$n+1$$ elements of $$f(x)$$. The minimum is attained at $$a_0=a_2=\dots=a_n=\frac{S}{n+1}$$ where $$S=-1$$ is the sum of all elements, which yields immediately $$x_1=\frac{n+2}{n+1}$$ and consequently all the other $$x_i$$.
Applying the inequality $$z^2\ge - \frac{2z}{n+1} - \frac{1}{(n+1)^2}$$ (which is true because it is equivalent to $$\left(z + \frac{1}{n+1}\right)^2\ge 0$$) to each of the elements of $$f(x)$$ (i.e., replacing $$z$$ by those elements), and summing up the obtained $$n+1$$ inequalities, we obtain immediately the results.
• If anyone is wondering (like I did) where the inequality $$$m(a_1^2 +a_2^2+\dots+a_m^2) \ge (a_1+a_2+\dots+a_m)^2,$$$ comes from, it comes from applying Cauchy-Schwarz to the vectors $$(1 \ 1 \cdots \ 1)$$ and $$(a_1 \ a_2 \ \cdots \ a_m)$$. – user56202 May 19 at 17:13