6
$\begingroup$

I was reading about TR methods and there are some terms, which are confusing for me.

It says, method is globaly convergent. What does it really mean? Converges to global minima, or converges for sure to local minima, if there is any?

thanks for clarification!

$\endgroup$
7
$\begingroup$

Standard terminology in nonlinear (i.e., derivative-based) optimization is that "global convergence" means "convergence to a stationary point no matter where you start from" (where the limit may in fact depend on the starting point). This is in contrast to local convergence, which requires that you start sufficiently close to a stationary point; if your initial point is too far away, the method need not converge at all. This is famously the case for Newton's method, which on the other hand (for nice enough functions) converges quadratically (i.e., much faster than steepest descent). Much of nonlinear optimization is concerned with trying to get rid of this requirement of a good enough initial guess (also called "globalization", of which trust region methods are one approach) without destroying the fast convergence.

The reason is that if you are using algorithms (only) based on derivatives,

  1. it is impossible to distinguish local from global minimizers (since derivatives only carry local information), and
  2. as soon as you hit a stationary point, the derivative by definition vanishes and hence the algorithm must terminate.

(Another reason for the terminology is that for a large class of practically relevant problems (convex problems), any stationary point is in fact a (global!) minimizer.)

In contrast, global optimization is concerned with actually computing global minimizers (for which, TANSTAAFL, there is much less convergence theory).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ And "convergence to a stationary point" isn't quite the same as "convergence to a local minimum", since you might somehow converge to a saddle point or local maximum. $\endgroup$ – Brian Borchers Aug 2 '16 at 2:38

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.