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   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 en   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,  , que esperaríamos que fuera una reducción menor que la reducción real. Dado  , se puede evaluar

 

Al observar la relación  , podemos ajustar el tamaño de la región de confianza. En general, esperamos que   sea un poco más pequeño que  , 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
  1. 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. 
  2. Fletcher, Roger (1987). «Restricted Step Methods». Practical Methods of Optimization (Second edición). Wiley. ISBN 0-471-91547-5. 
  3. 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

Enlaces externos

editar