Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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
1  
"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
1  
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
1  
@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
1  
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

1 Answer 1

up vote 0 down vote accepted

It's not easy to find a global minimum of a general function. Many functions have lots of local minima and in principle the algorithm would need to check all of them to find the local a global minimum. This is for example a central problem in Neural Networks learning algorithms. I'm not expert on this, but I guess the algorithm is interesting because it is simple, it works for a relatively general class of functions, and it is fast.

share|improve this answer
    
Yes, but when it finds a strict minimum, it stops. So, how does it find all local minima, so that we can compare them? Because if we run it again, we might get the same local minimum as in the first run and so on. How do we know that we have determined all local minima? –  Chris Jul 18 '12 at 16:21
1  
@Chris "How do we know that we have determined all local minima?" - you don't. Functions will lie through their teeth if you give them half a chance. Without some way of ensuring 'honesty' - e.g. bounds on function values or derivatives - you literally cannot control the behavior of the function anywhere that you haven't explicitly looked at it. This is a big part of the reason why global results are so hard. –  Steven Stadnicki Jul 18 '12 at 16:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.