En el problema de minimización sin restricciones , las condiciones de Wolfe son un conjunto de desigualdades para realizar búsquedas de líneas inexactas , especialmente en métodos cuasi-Newton , publicados por primera vez por Philip Wolfe en 1969. [1] [2]
En estos métodos la idea es encontrar
para algunos suaves . Cada paso a menudo implica resolver aproximadamente el subproblema.
dónde es la mejor suposición actual, es una dirección de búsqueda, y es la longitud del paso.
Las búsquedas de líneas inexactas proporcionan una forma eficiente de calcular una longitud de paso aceptable que reduce la función objetivo 'suficientemente', en lugar de minimizar la función objetivo sobreexactamente. Un algoritmo de búsqueda de líneas puede utilizar las condiciones de Wolfe como requisito para cualquier, antes de encontrar una nueva dirección de búsqueda .
Regla y curvatura de Armijo
Una longitud de paso se dice que satisface las condiciones de Wolfe , restringidas a la dirección, si se cumplen las siguientes dos desigualdades:
con . (Al examinar la condición (ii), recuerde que para asegurarse de que es una dirección de descenso, tenemos , como en el caso del descenso de gradiente , dondeo Newton-Raphson , donde con positivo definitivo.)
generalmente se elige para ser bastante pequeño mientras es mucho más grande; Nocedal y Wright dan ejemplos de valores de y para los métodos de Newton o cuasi-Newton y para el método de gradiente conjugado no lineal . [3] La desigualdad i) se conoce como regla de Armijo [4] y ii) como condición de curvatura ; i) asegura que la longitud del paso disminuye 'suficientemente', y ii) asegura que la pendiente se ha reducido lo suficiente. Las condiciones i) y ii) se pueden interpretar como que proporcionan respectivamente un límite superior e inferior en los valores de longitud de paso admisibles.
Fuerte condición de Wolfe en la curvatura
Denotar una función univariante restringido a la dirección como . Las condiciones de Wolfe pueden dar como resultado un valor para la longitud del paso que no se acerca a un minimizador de. Si modificamos la condición de curvatura a lo siguiente,
entonces i) y iii) juntos forman las llamadas condiciones de Wolfe fuerte , y fuerzanestar cerca de un punto crítico de.
Razón fundamental
La principal razón para imponer las condiciones de Wolfe en un algoritmo de optimización donde es asegurar la convergencia del gradiente a cero. En particular, si el coseno del ángulo entre y el gradiente,
está delimitado desde cero y las condiciones i) y ii) se mantienen, entonces .
Una motivación adicional, en el caso de un método cuasi-Newton , es que si, donde la matriz se actualiza mediante la fórmula BFGS o DFP , si es positivo definido ii) implica también es positivo definido.
Comentarios
Si bien las condiciones de Wolfe son más complicadas que la condición de Armijo, a partir de ahora el algoritmo basado en la condición de Armijo (es decir, Descenso de gradiente de retroceso) tiene una mejor garantía teórica, consulte las secciones "Límite superior para las tasas de aprendizaje" y "Garantía teórica" en Búsqueda de línea de retroceso. .
Ver también
Referencias
- ^ Wolfe, P. (1969). "Condiciones de convergencia para métodos de ascenso". Revisión SIAM . 11 (2): 226–235. doi : 10.1137 / 1011036 . JSTOR 2028111 .
- ^ Wolfe, P. (1971). "Condiciones de convergencia para los métodos de ascenso. II: Algunas correcciones". Revisión SIAM . 13 (2): 185–188. doi : 10.1137 / 1013035 .
- ^ Nocedal, Jorge ; Wright, Stephen (1999). Optimización numérica . pag. 38.
- ^ Armijo, Larry (1966). "Minimización de funciones con primeras derivadas parciales continuas de Lipschitz" . Pacific J. Math . 16 (1): 1-3. doi : 10.2140 / pjm.1966.16.1 .
Otras lecturas
- "Métodos de búsqueda de línea". Optimización numérica . Serie Springer en Investigación de Operaciones e Ingeniería Financiera. 2006. págs. 30–32. doi : 10.1007 / 978-0-387-40065-5_3 . ISBN 978-0-387-30303-1.
- "Métodos cuasi-Newton". Optimización numérica . Serie Springer en Investigación de Operaciones e Ingeniería Financiera. 2006. págs. 135-163. doi : 10.1007 / 978-0-387-40065-5_6 . ISBN 978-0-387-30303-1.