4
$\begingroup$

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}

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ – Kuifje May 9 at 10:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Kuifje May 9 at 17:10
  • $\begingroup$ @Kuifje - wolframalpha.com/input/… $\endgroup$ – Quasar May 9 at 17:16
5
$\begingroup$

Cross-posting.


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: \begin{equation} m(a_1^2 +a_2^2+\dots+a_m^2) \ge (a_1+a_2+\dots+a_m)^2, \end{equation} 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$.


P/s: The following solution is only for your reference, I do not recommend it.

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.

$\endgroup$
1
  • 2
    $\begingroup$ If anyone is wondering (like I did) where the inequality $\begin{equation} m(a_1^2 +a_2^2+\dots+a_m^2) \ge (a_1+a_2+\dots+a_m)^2, \end{equation}$ comes from, it comes from applying Cauchy-Schwarz to the vectors $$(1 \ 1 \cdots \ 1)$$ and $$(a_1 \ a_2 \ \cdots \ a_m)$$. $\endgroup$ – user56202 May 19 at 17:13

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.