Trust region

In mathematical optimization, a trust region is the subset of the region of the objective function that is approximated using a model function (often a quadratic). If 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.

The fit is evaluated by comparing the ratio of expected improvement from the model approximation with the actual improvement observed in the objective function. Simple thresholding of the ratio is used as the criterion for expansion and contraction—a model function is "trusted" only in the region where it provides a reasonable approximation.

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.

The general idea behind trust region methods is known by many names; the earliest use of the term seems to be by Sorensen (1982).^[1] A popular textbook by Fletcher (1980) calls these algorithms restricted-step methods.^[2] Additionally, in an early foundational work on the method, Goldfeld, Quandt, and Trotter (1966) refer to it as quadratic hill-climbing.^[3]

Example

Conceptually, in the Levenberg–Marquardt algorithm, the objective function is iteratively approximated by a quadratic surface, then using a linear solver, the estimate is updated. This alone may not converge nicely if the initial guess is too far from the optimum. For this reason, the algorithm instead restricts each step, preventing it from stepping "too far". It operationalizes "too far" as follows. Rather than solving ${\displaystyle A\,\Delta x=b}$ for ${\displaystyle \Delta x}$, it solves ${\displaystyle {\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b}$, where ${\displaystyle \operatorname {diag} (A)}$ is the diagonal matrix with the same diagonal as A, and λ is a parameter that controls the trust-region size. Geometrically, this adds a paraboloid centered at ${\displaystyle \Delta x=0}$ to the quadratic form, resulting in a smaller step.

The trick is to change the trust-region size (λ). At each iteration, the damped quadratic fit predicts a certain reduction in the cost function, ${\displaystyle \Delta f_{\text{pred}}}$, which we would expect to be a smaller reduction than the true reduction. Given ${\displaystyle \Delta x}$, we can evaluate

${\displaystyle \Delta f_{\text{actual}}=f(x)-f(x+\Delta x).}$

By looking at the ratio ${\displaystyle \Delta f_{\text{pred}}/\Delta f_{\text{actual}}}$, we can adjust the trust-region size. In general, we expect ${\displaystyle \Delta f_{\text{pred}}}$ to be a bit smaller than ${\displaystyle \Delta f_{\text{actual}}}$, and so the ratio would be between, say, 0.25 and 0.5. If the ratio is more than 0.5, then we are damping the step too much, so expand the trust region (decrease λ) and iterate. If the ratio is smaller than 0.25, then the true function is diverging "too much" from the trust-region approximation, so shrink the trust region (increase λ) and try again.

References

• Dennis, J. E. Jr.; Schnabel, Robert B. (1983). "Globally Convergent Modifications of Newton's Method". Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9.
• Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint "Trust-Region Methods (MPS-SIAM Series on Optimization)".
• 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.
• Yuan, Y. "A review of trust region algorithms for optimization" in ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh, 2000 Oxford University Press, USA.
• Yuan, Y. "Recent Advances in Trust Region Algorithms", Math. Program., 2015

External links

• Kranf site: Trust Region Algorithms
• Trust-region methods

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software