“Trust region”的意思、由来-开放百科全书

词条

Trust region

释义

Example
References
External links

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

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 for , it solves , where 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 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, , which we would expect to be a smaller reduction than the true reduction. Given , we can evaluate

By looking at the ratio , we can adjust the trust-region size. In general, we expect to be a bit less than , 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 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

Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint "[https://books.google.com/books?id=5kNC4fqssYQC 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.
Sorensen, D. C.: "Newton’s Method with a Model Trust Region Modification", SIAM J. Numer. Anal., 19(2), 409–426 (1982).
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. "[https://link.springer.com/article/10.1007%2Fs10107-015-0893-2 Recent Advances in Trust Region Algorithms]", Math. Program., 2015

External links

Kranf site: Trust Region Algorithms
[https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods Trust-region methods]

1 : Optimization algorithms and methods

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。