Global convergence in trust region algorithm

Question

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!

Answer 1

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).