1
$\begingroup$

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a differentiable function of which we want to find a minimum. One general approach is iterative descent:

  1. Choose $x_0 \in \mathbb{R}^n$ arbitrarily
  2. $x_{k+1} = x_k + \alpha_k \cdot d_k$ with the step length $\alpha_k \in (0, 1]$, commonly called learning rate in machine learning and $\alpha_k = 0.01$ is a very common choice. $d_k = - D_k \nabla f(x_k)$ is the direction of the descent. The most common choice is $D_k = I \in \mathbb{R}^{n \times n}$ which results in steepest descent ("gradient descent").

I've heard that Newtons method can be expressed in the same way by correct choice of $D_k$.

According to the German Wikipedia (Permalink),

$$D_k = J(x_k) \text{ with } J(\mathbf{x}):= \left(\frac{\partial f_i}{\partial x_j}\right) =\begin{pmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \ldots & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \ldots & \frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \ldots & \frac{\partial f_n}{\partial x_n}\end{pmatrix}$$

However, according to the English Wikipedia article Newton's method in optimization:

$$D_k = [H f(x_k)]^{-1} \text{ with } H f(x) = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}$$

I see three possibilities now:

  1. I did get something wrong. Either the Jacobian matrix or the hessian matrix is wrong.
  2. Either the English or the German Wiki article is wrong.
  3. Both are equivalent.

Which one is it? Could you please clarify?

$\endgroup$

1 Answer 1

2
$\begingroup$

The two articles both consider the Newton method, but the english one for optimization (for finding $f'(x) = 0$) and the german one for finding a zero $f(x)=0$. So for the "english" case we just apply the "german" newton method to the derivative in order to find a zero of the derivative instead of the function itself. Therefore we there need the second derivative (hessian matrix) and apply it to the gradient (first derivative).

The english WP article you linked is Newton's method in optimization while there is also Newton's Method.

So generally Newton's Method refers to the algorithm for finding zeros of a function.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .