In calculus, Newton's method (also called Newton–Raphson) is an iterative method for finding the roots of a differentiable function f {\displaystyle f} , which are solutions to the equation f ( x ) = 0 {\displaystyle f(x)=0} . However, to optimize a twice-differentiable f {\displaystyle f} , our goal is to find the roots of f ′ {\displaystyle f'} . We can therefore use Newton's method on its derivative f ′ {\displaystyle f'} to find solutions to f ′ ( x ) = 0 {\displaystyle f'(x)=0} , also known as the critical points of f {\displaystyle f} . These solutions may be minima, maxima, or saddle points; see section "Several variables" in Critical point (mathematics) and also section "Geometric interpretation" in this article. This is relevant in optimization, which aims to find (global) minima of the function f {\displaystyle f} .
Newton's method The central problem of optimization is minimization of functions. Let us first consider the case of univariate functions, i.e., functions of a single real variable. We will later consider the more general and more practically useful multivariate case. Given a twice differentiable function f : R → R {\displaystyle f:\mathbb {R} \to \mathbb {R} } , we seek to solve the optimization problem
min x ∈ R f ( x ) . {\displaystyle \min _{x\in \mathbb {R} }f(x).}
Newton's method attempts to solve this problem by constructing a sequence { x k } {\displaystyle \{x_{k}\}} from an initial guess (starting point) x 0 ∈ R {\displaystyle x_{0}\in \mathbb {R} } that converges towards a minimizer x ∗ {\displaystyle x_{*}} of f {\displaystyle f} by using a sequence of second-order Taylor approximations of f {\displaystyle f} around the iterates. The second-order Taylor expansion of f around x k {\displaystyle x_{k}} is
f ( x k + t ) ≈ f ( x k ) + f ′ ( x k ) t + 1 2 f ″ ( x k ) t 2 . {\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}
The next iterate x k + 1 {\displaystyle x_{k+1}} is defined so as to minimize this quadratic approximation in t {\displaystyle t} , and setting x k + 1 = x k + t {\displaystyle x_{k+1}=x_{k}+t} . If the second derivative is positive, the quadratic approximation is a convex function of t {\displaystyle t} , and its minimum can be found by setting the derivative to zero. Since
0 = d d t ( f ( x k ) + f ′ ( x k ) t + 1 2 f ″ ( x k ) t 2 ) = f ′ ( x k ) + f ″ ( x k ) t , {\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}
the minimum is achieved for
… excerpt ends here. Continue reading the full article.
