3
$\begingroup$

Is there any clear classification between different iterative methods?

What is the difference between Newton-type and Newton-like iterative methods?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ I agree with @Paul, but it might enhance this question substantially if you linked to some context where each was used. $\endgroup$ – Bill Barth Feb 6 '14 at 15:21
  • $\begingroup$ Is there a full list of all iterative methods for nonlinear optimization/nonlinear system solving with classification? especially with those iterative methods which are Newton-type or Newton-like... $\endgroup$ – LCFactorization Feb 6 '14 at 15:27
  • $\begingroup$ @LCFactorization: Methods are more commonly classified by the kind of problem you're solving as well as the methods used to solve it, e.g. convexity, differentiability, constraints (or lack thereof), etc... What kind of problem are you working on? $\endgroup$ – Paul♦ Feb 6 '14 at 15:36
  • $\begingroup$ Currently I am trying to solve a unconstrained nonlinear least square problem, which is only three-variate case. Efficiency should dominate so I prefer iterative methods. In a book ISBN 0-89871-360-9, I noticed they classify Newton-type and Gauss-Newton-type as different methods. So I want to make sure whether Newton-type can be used to cover all these.. or Newton-like would be more suitable $\endgroup$ – LCFactorization Feb 8 '14 at 14:00
4
$\begingroup$

They're equivalent. Both imply some variation of the root-finding method by linearization.

Improve this answer
$\endgroup$
  • $\begingroup$ Does that mean iterative methods other than fixed point iteration are all Newton type? e.g. Newton-Raphson, quasi Newton, Gauss-Newton, Levenberg-Marquardt, and their other variants with globalizing strategies (line search and trust region)? $\endgroup$ – LCFactorization Feb 6 '14 at 15:25
  • 1
    $\begingroup$ The methods you mention address different kinds of problems, e.g. least squares, optimization, and root finding. But they are all variations of the newton method. $\endgroup$ – Paul♦ Feb 6 '14 at 15:28
  • 1
    $\begingroup$ You're welcome. I do want to mention one more key point. Not all non-linear solver/optimization methods are Newton methods. Newton methods all use linearization using analytical or approximate gradients of the objectve function. There is another class of iterative methods which do not use derivative information at all. These are called 'Gradient-Free' methods. $\endgroup$ – Paul♦ Feb 6 '14 at 17:24
  • 1
    $\begingroup$ You would probably be very interested in this list of optimization methods $\endgroup$ – Paul♦ Feb 6 '14 at 17:33
6
$\begingroup$

A few specific examples:

Quasi-Newton methods avoid computing second derivatives by using an approximation to the Hessian which is updated at each iteration by a low rank (rank one or rank two) update. This makes factoring the Hessian (or equivalently keeping the inverse in product form) easy to do computationally. There are also limited memory Quasi-Newton methods that keep track of only the most recent rank one updates.

The Gauss-Newton method for minimization of sums of squares takes advantage of the sum of squares structure of the problem to get an approximation to the Hessian that only involves first derivatives (the second order term is dropped.)

The Levenberg-Marquardt method is a particular approach to stabilizing the Gauss-Newton iteration by regularizing the linear system that is solved in each iteration (either by adding a regularizing term in the equations or by using a trust region method.)

Improve this answer
$\endgroup$
  • $\begingroup$ @Paul @BrianBochers I noticed that in a book Numerical methods for least square problems(1996 by the Society for Industrial and Applied Mathematics, ISBN:0-89871-360-9), they classify Newton-type and Gauss-Newton-type as different iterative methods (Chapter 9) $\endgroup$ – LCFactorization Feb 8 '14 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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