Región de confianza

En optimización, una región de confianza es el subconjunto de la región de la función objetivo que se aproxima usando una función modelo (a menudo cuadrática). Si dentro de la región de confianza se encuentra un modelo adecuado de la función objetivo, entonces la región se expande; caso contrario, si la aproximación es pobre, se contrae.

El ajuste se evalúa comparando la proporción de mejora esperada de la aproximación del modelo con la mejora real observada en la función objetivo. El umbral simple de la relación se utiliza como criterio para la expansión y la contracción; se «confía» en una función modelo solo en la región donde proporciona una aproximación razonable.

Los métodos de región de confianza primero eligen un tamaño de paso (el tamaño de la región de confianza) y luego una dirección de paso, mientras que, los métodos de búsqueda lineal primero eligen una dirección de paso y luego un tamaño de paso.

La idea general detrás de los métodos de región de confianza se conoce por muchos nombres; el primer uso del término parece ser de Sorensen.^[1] Un libro popular de Fletcher llama a estos algoritmos métodos de pasos restringidos.^[2] Además, en un trabajo fundacional temprano sobre el método, Goldfeld, Quandt y Trotter se refieren a él como escalada cuadrática.^[3]

Ejemplo[editar]

Conceptualmente, en el algoritmo de Levenberg-Marquardt, la función objetivo se aproxima de manera iterativa mediante una superficie cuadrática y luego, mediante un solucionador lineal, se actualiza la estimación. Esto por sí solo puede no converger bien, si la suposición inicial está demasiado lejos del óptimo. Por esta razón, el algoritmo en cambio restringe cada paso, evitando que avance «demasiado lejos» de la siguiente manera. En lugar de resolver $A\,\Delta x=b$ por $\Delta x$ , resuelve ${\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b$ , dónde $\operatorname {diag} (A)$ es la matriz diagonal con la misma diagonal que A, y λ es un parámetro que controla el tamaño de la región de confianza. Geométricamente, esto agrega un paraboloide centrado en $\Delta x=0$ a la forma cuadrática, resultando en un paso más pequeño.

El truco es cambiar el tamaño de la región de confianza (λ). En cada iteración, el ajuste cuadrático amortiguado predice una cierta reducción en la función de costo, $\Delta f_{\text{pred}}$ , que esperaríamos que fuera una reducción menor que la reducción real. Dado $\Delta x$ , se puede evaluar

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

Al observar la relación $\Delta f_{\text{pred}}/\Delta f_{\text{actual}}$ , podemos ajustar el tamaño de la región de confianza. En general, esperamos que $\Delta f_{\text{pred}}$ sea un poco más pequeño que $\Delta f_{\text{actual}}$ , por lo que, la relación estaría entre 0,25 y 0,5. Si la relación es superior a 0,5, se está amortiguando demasiado el paso, por lo tanto, hay que expandir la región de confianza (disminuir λ) e iterar. Si la relación es menor que 0,25, entonces la verdadera función se está desviando «demasiado» de la aproximación de la región de confianza, por lo tanto, hay que reducir la región de confianza (aumentar λ) y volver a intentarlo.

Referencias[editar]

↑ Sorensen, D. C. (1982). «Newton's Method with a Model Trust Region Modification». SIAM J. Numer. Anal. 19 (2): 409-426. doi:10.1137/0719026.
↑ Fletcher, Roger (1987). «Restricted Step Methods». Practical Methods of Optimization (Second edición). Wiley. ISBN 0-471-91547-5.
↑ Goldfeld, Stephen M.; Quandt, Richard E.; Trotter, Hale F. (1966). «Maximization by Quadratic Hill-Climbing». Econometrica 34 (3): 541-551. doi:10.2307/1909768.

Bibliografía[editar]

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