Aller au boulot

Newton's Method

Given a twice differentiable function $f:\mathbb{R}\to \mathbb{R}$, solve the optimization problem

$$\underset{x\in \mathbb{R}}{\min }f(x).$$

Consider the second-order Taylor expansion of $f$ around $x_k$

$$f(x_k+t)\approx f(x_k)+f^{\prime }(x_k)t+\frac{1}{2}{f}^{\prime \prime }(x_k)t^2.$$

Setting the derivative to zero,

$$0=\frac{\mathrm{d}}{\mathrm{d}t}\left(f(x_k)+f^{\prime }(x_k)t+\frac{1}{2}{f}^{\prime \prime }(x_k)t^2\right)=f^{\prime }(x_k)+f^{\prime \prime }(x_k)t,$$

the minimum is achieved for

$$t=-\frac{f^{\prime }(x_k)}{f^{\prime \prime }(x_k)},$$

then

$$x_{k+1}=x_k+t=x_k-\frac{f^{\prime }(x_k)}{f^{\prime \prime }(x_k)}.$$