Trust region

Trust region is a term used in mathematical optimization to denote 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. Trust region methods are also known as restricted step methods.

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 earliest use of the term seems to be by Sorensen (1982).

Conceptually, in the Levenberg–Marquardt algorithm, the objective function is iteratively approximated by a quadratic surface, then using a linear solve, 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 (A+\lambda \operatorname {diag} (A))\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.

...
Wikipedia