Editing Newton's method in optimization (section)

==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 <math> f:\mathbb{R}\to \mathbb{R}</math>, we seek to solve the optimization problem
:<math> \min_{x\in \mathbb{R}} f(x) .</math>

Newton's method attempts to solve this problem by constructing a [[sequence]] <math>\{x_k\}</math> from an initial guess (starting point) <math>x_0\in \mathbb{R}</math> that converges towards a minimizer <math>x_*</math> of <math>f</math> by using a sequence of second-order Taylor approximations of <math>f</math> around the iterates. The second-order [[Taylor expansion]]  of {{math|''f''}} around <math>x_k</math> is

:<math>f(x_k + t) \approx  f(x_k) + f'(x_k) t + \frac{1}{2} f''(x_k) t^2.</math>

The next iterate <math>x_{k+1}</math> is defined so as to minimize this quadratic approximation in  <math>t</math>, and setting <math>x_{k+1}=x_k + t</math>. If the second derivative is positive, the quadratic approximation is a convex function of <math>t</math>, and its minimum can be found by setting the derivative to zero. Since

:<math>\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, </math>
the minimum is achieved for
:<math> t = -\frac{f'(x_k)}{f''(x_k)} .</math>
Putting everything together, Newton's method performs the iteration
:<math> x_{k+1} = x_k + t = x_k - \frac{f'(x_k)}{f''(x_k)}. </math>