Newton's Method for Optimization

  • Thread starter brydustin
  • Start date
  • #1
205
0
Just curious if Newton's method in high dimensions should always quickly converge to a min/max or saddle point. I can't seem to get the value of my gradient below 12-16; so, its not "diverging" but its not converging either. I want to avoid saddle points so I'm using Fletcher-Reeves method, but I figure if I test it with Newton-Raphson then it should at least converge to a saddle point quickly, right? (assuming my initial starting point is "good" in some sense).

thanks all
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
964
could you please given an example? What is the function for which you cannot get the value of the gradient below 12-16?

Even in one dimension it is possible to get a function and intitial value where you just alternate between two x-values- but just a slight change in initial value will correct that.
 
  • #3
AlephZero
Science Advisor
Homework Helper
6,994
293
The basic problem for any multivariable optimisation algorithm is the fact that (unlike the 1-D case) the optimum is usually at the bottom of a "curved valley" in N dimensions. Any method that only looks at the local gradient at a point tends to follow the steepest gradient, and the route to the optimum tends to be many short steps that "bounce off the sides" of the valley rather than "following the curve" along the bottom. A classic example of this for 2 variables (where it is fairly easy to draw pictures to see what is happening) is "Rosenbrock's banana function" (see Google).

To do multi-variable optimization efficiently, you usually need to know a lot about the function you are trying to optimize.
 

Related Threads on Newton's Method for Optimization

  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
933
  • Last Post
Replies
2
Views
2K
Replies
2
Views
647
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
11
Views
865
  • Last Post
Replies
15
Views
12K
  • Last Post
Replies
2
Views
2K
Top