Trust region

Trust region is a mathematical optimization term, first coined by Celis, Dennis and Tapia at Rice University.

Essentially the algorithm approximates only a certain region (the so-called trust region) of the objective function with a model function (often a quadratic) as opposed to the entire function as with the Newton-Raphson optimisation algorithm. When an adequate model of the objective function is found within the trust region then the region is expanded. Conversely, if the approximation is poor then the region is contracted.

Trust region methods are also known as restricted step methods.

The evaluation method is to observe the ratio of expected improvement from the quadratic approximation with the actual improvement observed in the objective function. Simple thresholding of the ratio is used as the criteria for expansion and contraction.

Trust region methods are in some sense dual to line search methods: trust region methods first choose a step size (the size of the trust region) and then a step direction while line search methods first choose a step direction and then a step size.

References

* Celis, M., J. E. Dennis, and R. A. Tapia. "A trust region strategy for nonlinear equality constrained optimization", in "Numerical Optimization 1994" (P. Boggs, R. Byrd and R. Schnabel, eds)", Philadelphia: SIAM, 1985, pp. 71-82.
* Byrd, R. H, R. B. Schnabel, and G. A. Schultz. "A trust region algorithm for nonlinearly constrained optimization", SIAM J. Numer. Anal., 24 (1987), pp. 1152-1170.

External links

* [http://www.mathworks.com/access/helpdesk/help/toolbox/optim/ug/f3137.html Matlab: Trust-Region Methods for Nonlinear Minimization]