Newton’s method updates design points (solutions) as follows: As \(H\) is a symmetric matrix, the Hessian is simply \(H\) and \(\nabla f(\vec x_k) = H\vec x_k\). Thus, Newton’s update looks like:\[\vec x_{k+1}=\vec x_k-H^{-1}(H\vec{x}_k)\] This implies,
\[\vec x_{k+1}=\vec x_k-\vec x_k=\vec 0\] Hence \[\vec x_1=\vec 0\] and the search finishes in one step because the following ones would not yield any change.
Gradient Descent update rule is as follows for unnormalized case: \[\vec x_{k+1}=\vec x_k-\alpha \nabla f(\vec x_k)\] and subtituting \(\nabla f(\vec x_k)=H\vec x_k\) yields: \[\vec x_{k+1}=\vec x_k-H\vec x_k=[I-\alpha H]\vec x_k\]
Let’s try first to set \(\alpha=1\). This will reveal itself for being a bad choice. In this case, the first iterates yield: \[\vec x_1=\begin{bmatrix}
1\\
1
\end{bmatrix}
-
\begin{bmatrix}1& 0\\
0& 1000\\
\end{bmatrix}
\begin{bmatrix}
1\\
1
\end{bmatrix}
=
\begin{bmatrix}
1\\
-999
\end{bmatrix}\] \[\vec x_2=\begin{bmatrix}
0\\
-999
\end{bmatrix}
-
\begin{bmatrix}1& 0\\
0& 1000\\
\end{bmatrix}
\begin{bmatrix}
0\\
-999
\end{bmatrix}
=
\begin{bmatrix}
0\\
998111
\end{bmatrix}\] \[\vec x_3=\begin{bmatrix}
0\\
998001
\end{bmatrix}
-
\begin{bmatrix}1& 0\\
0& 1000\\
\end{bmatrix}
\begin{bmatrix}
0\\
998001
\end{bmatrix}
=
\begin{bmatrix}
0\\
-997002999
\end{bmatrix}\] The gradient descent method diverges.
Let’s backtrack and analyse the update rule more generally. We have: \[\vec x_{k+1}=\vec x_k-H\vec x_k=[I-\alpha H]\vec x_k\].
We can regard this as a stochastic process where the state \(\vec x_k\) is updated by multiplying with a matrix \(I-\alpha H\). In particular, it is a Markov process of first order where the new state depends only on the current state and not on all the previous states. The theory to analyse the convergence of these processes is an application of Linear Algebra that is also behind the pagerank algorithm, see for example this class from AI511. The convergence of this process depends on the spectral radius of the matrix \(I-\alpha H\). In particular, for convergence we require that all eigenvalues of \(I-\alpha H\) have magnitude less than 1.
Recursing on the update rule we get: \[\vec x_{k}=[I-\alpha H]^k\vec x_0\] Now using our specific \(H\) matrix, we get:
\[\vec x_{k}=\begin{bmatrix}1-\alpha& 0\\ 0& 1-1000\alpha\\ \end{bmatrix}^k\vec
x_0\]
It is easy to see that: \[\vec x_{k}=\begin{bmatrix}(1-\alpha)^k& 0\\ 0&
(1-1000\alpha)^k\\ \end{bmatrix}\vec x_0\] To have convergence (ie, \(\vec
x_{k+1}=x_{k}\)), we require \(\alpha\) to satisfy the following equations: \(\lvert
1-\alpha \rvert < 1\) and \(\lvert 1-1000 \alpha\rvert < 1\). Solving these we get that choosing \(0<\alpha<2/1000\) ensures GD converges to the minimizer. However, note that it does not converge as fast as Newton’s method.
Conjugate gradient \[\vec x_{k+1}=\vec x_k+\alpha_k\vec d_k \qquad \vec d_k=-\vec r_k+\beta_k \vec d_{k-1}\] \[\vec r_k=\nabla f(\vec x_k)=H\vec x_k
\qquad
\beta_k=\frac{\vec r_k^TH\vec d_{k-1}}{\vec d_{k-1}^TH\vec d_{k-1}}
\qquad
\alpha_k=-\frac{\vec r_k\vec d_k}{\vec d_k^TH\vec d_k}\] \[\vec x_1=\vec x_0+\alpha_0\vec d_0\] We choose the first search direction \(\vec d_0\) to be the steepest descent direction at the initial point \(\vec x_0\). Hence, \(\vec d_0=-\nabla
f(\vec x_0)=-H\vec x_0\) and \[\alpha_0=-\frac{(H\vec x_0)^T(-H\vec x_0)}{(-H\vec x_0)^TH(-H\vec x_0)}= \frac{1 + 10^6}{1 + 10^9}\approxeq 0.001\] The first iteration then yields: \[\vec x_1=\vec x_0-\alpha_0\vec d_0=\begin{bmatrix}1\\1\end{bmatrix}-0.001\begin{bmatrix}1\\1000\end{bmatrix} =\begin{bmatrix}0.999\\0\end{bmatrix}\] The second iteration: \[\vec x_2=\vec x_1+\alpha_1\vec d_1\] Setting \(r_1=H\vec x_1\): \[\beta_1=\frac{\vec r_1^TH\vec d_0}{\vec d_0^TH\vec d_0}= \frac{(H\vec x_1)^TH(H\vec d_0)}{\vec d_0^TH\vec d_0}=...\] \[\vec d_1=-\vec r_1+\beta_1\vec d_0=...\] \[\alpha_1=-\frac{(H\vec x_1)^T\vec d_0}{\vec d_0^TH\vec d_0}=...\] \[\vec x_2\approx\begin{bmatrix}0\\0
\end{bmatrix}\] The matrix \(H\) has eigenvalues 1 and 1000 that are both positive, hence the matrix is positive definite (and hence symmetric). In this case, the conjugate gradient method needs \(n\) iterations to find the local optimum. So \(\vec x_2\) should be the optimal solution.
The function: \[f (\vec x) = (x_1 +1)^2 +(x_2 +3)^2 +4 = x_1^2+x_2^2+2x_1+6x_2+9+4+1\] Can be obtained by \[f(\vec x)=1/2\vec x^TA\vec x+\vec b^T\vec x+c\] where \(\vec x=[x_1, x_2]^T\), \(\vec b=[2, 6]\), \(c=14\) and \[A=\begin{bmatrix}
2&0\\0&2
\end{bmatrix}\] The matrix \(A\) is positive definite since its eigenvalues are positive. Hence, this is a quadratic function where the Netwon’s method finds the optimal solution in one iteration.
\[\nabla f(\vec x)=[2(x_1+1),2(x_2+3)]\] \[H=\begin{bmatrix}2 &0\\ 0& 2\end{bmatrix}\] \[\vec x_1=\vec x_0-H^{-1}{\nabla (\vec x_0)}=
\begin{bmatrix}
0\\0
\end{bmatrix}
-
\begin{bmatrix}
2&0\\
0&2
\end{bmatrix}^{-1}
\begin{bmatrix}
2\\6
\end{bmatrix}
=
\begin{bmatrix}
-1\\-3
\end{bmatrix}\]
