# Newton's method

I'm trying to understand how the Newton's method in optimization works.

This is the algorithm:

$S_0)$ Choose $x_{0}\in \mathbb{R}^{n},\rho>0,\ p>2,\ \beta\in(0,1), \displaystyle \sigma\in\left(0,\frac{1}{2}\right),\ \varepsilon\geq 0$, set $k =0$

$S_1)$ If $\Vert\nabla f(x_{k})\Vert\leq\varepsilon \ \ \$ STOP

$S_2)$ determine $d_{k}$ with $D^{2}f(x_{k})d_{k}=-\nabla f(x_{k})$ if $d_{k}$ cannot be calculated or the condition

$$\nabla f(x_{k})^{T}d_{k}\leq-p\Vert d_{k}\Vert^{p}$$

is violated, set $d_{k}=-\nabla f(x_{k})$

$S_3)$ determine $t_{k}\in\{\beta^{j}:j=0,1,2,\ \ldots\}$ maximal with $$f(x_{k}+t_{k}d_{k})<f(x_{k})+t_{k}\sigma\nabla f(x_{k})^{T}d_{k}$$

$S_4)$ Set $x_{k+1}=x_{k}+t_{k}d_{k},\ k:=k +1$, go to $S_1)$.

My question:

As I understand, the algorithm presented in my first post generates a sequence xk which converges to a strict local minimum of the twice differentiable function $f$. Why is this algorithm so interesting, if it can't even find the global minimum of the given function?

Thank you very much for your time!

-
For 2: certainly, since this is an optimization, you want to look for the $x_k$ which makes your gradient zero, or nearly so. That's what that condition is all about. – J. M. Jul 12 '12 at 23:52
"Is this the reference you would suggest as being the easiest introduction into numerical optimization?" - Dennis/Schnabel requires you to have some familiarity with the calculus of several variables (you are, after all, going to be dealing with gradients and Hessians); if your background there is good, you shouldn't have any trouble reading it. – J. M. Jul 12 '12 at 23:54
For 5: It can happen that the Hessian of a function at a point is computationally singular for some functions at some points. In that case (thus also answering 4), you do what is called steepest descent, going in the direction where the gradient is pointing. – J. M. Jul 12 '12 at 23:58
@Chris: There are good answers to all your questions, but maybe you need to start at a more basic level. For example, you ask why go in the direction $-\nabla f(x_{k})$. This is because, generally, a descent is desirable; but it is a very basic aspect of optimization. There is little point in elaborating the subtleties if you haven't yet mastered the basics. – copper.hat Jul 13 '12 at 0:41
The basic concepts behind Newton's method (and variants) is that it is trying to find the zero of some function. The method is straightforward to understand graphically with a function $f:\mathbb{R} \to \mathbb{R}$. Wikipedia has a fair description (the picture is essential). One issue with the basic Newton's method is it just 'tries' to find a zero of the gradient, regardless of whether the zero corresponds to a min. or max. The above algorithm incorporates a number of devices to ensure that the iterates are strictly decreasing in value away from a stationary point, to address this issue. – copper.hat Jul 13 '12 at 0:45