En la optimización matemática , 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 una cuadrática ). Si se encuentra un modelo adecuado de la función objetivo dentro de la región de confianza, entonces la región se expande; por el contrario, si la aproximación es mala, la región se contrae.
El ajuste se evalúa comparando la relació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 razón se utiliza como criterio para la expansión y la contracción; una función del modelo es "confiable" solo en la región donde proporciona una aproximación razonable.
Los métodos de la región de confianza son, en cierto sentido, duales a los métodos de búsqueda de línea: los métodos de la 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 de línea primero eligen una dirección de paso y luego un tamaño de paso.
La idea general detrás de los métodos de la región de confianza se conoce por muchos nombres; el primer uso del término parece ser el de Sorensen (1982). [1] Un libro de texto popular de Fletcher (1980) 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 (1966) se refieren a él como escalada cuadrática . [3]
Ejemplo
Conceptualmente, en el algoritmo de Levenberg-Marquardt , la función objetivo se aproxima iterativamente mediante una superficie cuadrática , luego, utilizando un solucionador lineal, se actualiza la estimación. Esto por sí solo puede no converger bien si la conjetura inicial está demasiado lejos del óptimo. Por esta razón, el algoritmo, en cambio, restringe cada paso, evitando que se vaya "demasiado lejos". Operacionaliza "demasiado lejos" de la siguiente manera. En lugar de resolver por , resuelve , dónde 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 ena la forma cuadrática , resultando en un paso más pequeño.
El truco consiste en 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,, que esperaríamos que fuera una reducción menor que la verdadera reducción. Dado, podemos evaluar
Mirando la proporción , podemos ajustar el tamaño de la región de confianza. En general, esperamos ser un poco más pequeño que , por lo que la relación estaría entre, digamos, 0,25 y 0,5. Si la relación es más de 0.5, entonces estamos amortiguando mucho el paso, así que expanda la región de confianza (disminuya λ) e itere. Si la relación es menor que 0,25, entonces la función verdadera diverge "demasiado" de la aproximación de la región de confianza, por lo tanto, reduzca la región de confianza (aumente λ) y vuelva a intentarlo.
Referencias
- ^ Sorensen, DC (1982). "Método de Newton con una modificación de la región de confianza del modelo" . SIAM J. Numer. Anal . 19 (2): 409–426. doi : 10.1137 / 0719026 .
- ^ Fletcher, Roger (1987) [1980]. "Métodos de pasos restringidos". Métodos prácticos de optimización (Segunda ed.). Wiley. ISBN 0-471-91547-5.
- ^ Goldfeld, Stephen M .; Quandt, Richard E .; Trotter, Hale F. (1966). "Maximización por escalada cuadrática". Econometrica . 34 (3): 541–551. doi : 10.2307 / 1909768 . JSTOR 1909768 .
- Dennis, JE, Jr .; Schnabel, Robert B. (1983). "Modificaciones globalmente convergentes del método de Newton". Métodos numéricos para optimización no restringida y ecuaciones no lineales . Acantilados de Englewood: Prentice-Hall. págs. 111-154. ISBN 0-13-627216-9.
- Andrew R. Conn, Nicholas IM Gould, Philippe L. Toint " Métodos de región de confianza (Serie MPS-SIAM sobre optimización) ".
- Byrd, R. H, RB Schnabel y GA Schultz. " Un algoritmo de región de confianza para la optimización con restricciones no lineales ", SIAM J. Numer. Anal., 24 (1987), págs. 1152-1170.
- Yuan, Y. " Una revisión de los algoritmos de la región de confianza para la optimización " en ICIAM 99: Actas del Cuarto Congreso Internacional de Matemáticas Industriales y Aplicadas, Edimburgo, 2000 Oxford University Press, EE. UU.
- Yuan, Y. " Avances recientes en algoritmos de regiones de confianza ", Matemáticas. Programa., 2015