Trust-Region solvers: performance and applications in geosciences

The Trust-Region (TR) algorithms are relatively new iterative algorithms for solving nonlinear optimization problems. High efficiency of the TR methods was demonstrated in a number of recent publications. They have the global convergence and local super-convergence, which differ them from the line search methods, commonly used for solving Inverse Problems. The TR techniques are used in a number of well-known SW libraries such as IMSL, TAO, GALAHAD, LANCELOT, etc. the TR solvers were implemented in FORTRAN. Let us explain the main difference of the TR methods from the classical Newton ones. Assume we have a current guess of the solution for the optimization problem. An approximate model can be constructed near to the current point. Solution of the approximate model can be taken as the next iteration point. The classical line search algorithms also solve approximate models to obtain the search directions. However, in the TR algorithms, the approximation model is only "trusted" in the region near to the current iteration. This seems reasonable, because for general nonlinear functions, the local approximate models (such as linear and quadratic approximations) can only fit the original function locally. The region that the approximate model is trusted is called "trust region". The trust region is adjusted from iteration to iteration, i.e. if computations indicate the approximation model fit the original problem quite well, the TR can be enlarged. Otherwise when the approximation works not good enough the trust region will be reduced.