Condiciones de Wolfe

Desigualdades para búsqueda de rectas inexactas

En el problema de minimización sin restricciones , las condiciones de Wolfe son un conjunto de desigualdades para realizar una búsqueda de línea inexacta , 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 un punto de equilibrio . Cada paso suele implicar la solución aproximada del subproblema donde es la mejor estimación actual, es una dirección de búsqueda y es la longitud del paso. $${\displaystyle \min _{x}f(\mathbf {x} )}$$ ${\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} }$ $${\displaystyle \min _{\alpha }f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$$ ${\displaystyle \mathbf {x} _{k}}$ ${\displaystyle \mathbf {p} _{k}\in \mathbb {R} ^{n}}$ ${\displaystyle \alpha \in \mathbb {R} }$

Las búsquedas de línea 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 con exactitud. Un algoritmo de búsqueda de línea puede utilizar las condiciones de Wolfe como requisito para cualquier , antes de encontrar una nueva dirección de búsqueda . ${\displaystyle \alpha }$ ${\displaystyle \alpha \in \mathbb {R} ^{+}}$ ${\displaystyle \alpha }$ ${\displaystyle \mathbf {p} _{k}}$

Regla de Armijo y curvatura

Se dice que una longitud de paso satisface las condiciones de Wolfe , restringidas a la dirección , si se cumplen las dos desigualdades siguientes: ${\displaystyle \alpha _{k}}$ ${\displaystyle \mathbf {p} _{k}}$

1. ${\displaystyle f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq f(\mathbf {x} _{k})+c_{1}\alpha _{k}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),}$
2. ${\displaystyle {-\mathbf {p} }_{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq -c_{2}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),}$

con . (Al examinar la condición (ii), recuerde que para asegurar que es una dirección de descenso, tenemos , como en el caso del descenso de gradiente , donde , o Newton–Raphson , donde con definida positiva). ${\displaystyle 0<c_{1}<c_{2}<1}$ ${\displaystyle \mathbf {p} _{k}}$ ${\displaystyle \mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})<0}$ ${\displaystyle \mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$ ${\displaystyle \mathbf {p} _{k}=-\mathbf {H} ^{-1}\nabla f(\mathbf {x} _{k})}$ ${\displaystyle \mathbf {H} }$

${\displaystyle c_{1}}$se elige generalmente bastante pequeño mientras que es mucho más grande; Nocedal y Wright dan valores de ejemplo 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 la regla de Armijo ^[4] y ii) como la 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) pueden interpretarse como que proporcionan respectivamente un límite superior e inferior en los valores de longitud de paso admisibles. ${\displaystyle c_{2}}$ ${\displaystyle c_{1}=10^{-4}}$ ${\displaystyle c_{2}=0.9}$ ${\displaystyle c_{2}=0.1}$ ${\displaystyle \alpha _{k}}$ ${\displaystyle f}$

Condición de Wolfe fuerte en curvatura

Denotemos una función univariante restringida a la dirección como . Las condiciones de Wolfe pueden dar como resultado un valor para la longitud del paso que no esté cerca de un minimizador de . Si modificamos la condición de curvatura a lo siguiente, ${\displaystyle \varphi }$ ${\displaystyle \mathbf {p} _{k}}$ ${\displaystyle \varphi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ ${\displaystyle \varphi }$

3. ${\displaystyle {\big |}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}){\big |}\leq c_{2}{\big |}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}){\big |}}$

entonces i) y iii) juntos forman las llamadas condiciones fuertes de Wolfe , y fuerzan a estar cerca de un punto crítico de . ${\displaystyle \alpha _{k}}$ ${\displaystyle \varphi }$

Razón fundamental

La razón principal 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á acotado lejos de cero y se cumplen las condiciones i) y ii), entonces . ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha \mathbf {p} _{k}}$ ${\displaystyle \mathbf {p} _{k}}$ $${\displaystyle \cos \theta _{k}={\frac {\nabla f(\mathbf {x} _{k})^{\mathrm {T} }\mathbf {p} _{k}}{\|\nabla f(\mathbf {x} _{k})\|\|\mathbf {p} _{k}\|}}}$$ ${\displaystyle \nabla f(\mathbf {x} _{k})\rightarrow 0}$

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 , entonces si es definida positiva ii) implica que también es definida positiva. ${\displaystyle \mathbf {p} _{k}=-B_{k}^{-1}\nabla f(\mathbf {x} _{k})}$ ${\displaystyle B_{k}}$ ${\displaystyle B_{k}}$ ${\displaystyle B_{k+1}}$

Comentarios

Las condiciones de Wolfe son más complicadas que la condición de Armijo, y un algoritmo de descenso de gradiente basado en la condición de Armijo tiene una mejor garantía teórica que uno basado en las condiciones de Wolfe (consulte las secciones sobre "Límite superior para las tasas de aprendizaje" y "Garantía teórica" ​​en el artículo de búsqueda de línea de retroceso ).

Véase también

• Búsqueda de línea de retroceso

Referencias

1. Wolfe, P. (1969). "Condiciones de convergencia para métodos de ascenso". SIAM Review . 11 (2): 226–235. doi :10.1137/1011036. JSTOR  2028111.
2. Wolfe, P. (1971). "Condiciones de convergencia para métodos de ascenso. II: Algunas correcciones". SIAM Review . 13 (2): 185–188. doi :10.1137/1013035. JSTOR  2028821.
3. Nocedal, Jorge ; Wright, Stephen (1999). Optimización numérica. p. 38.
4. Armijo, Larry (1966). "Minimización de funciones con derivadas parciales primeras continuas de Lipschitz". Pacific J. Math . 16 (1): 1–3. doi : 10.2140/pjm.1966.16.1 .

Lectura adicional

• "Métodos de búsqueda lineal". Optimización numérica . Springer Series in Operations Research and Financial Engineering. 2006. págs. 30-32. doi :10.1007/978-0-387-40065-5_3. ISBN 978-0-387-30303-1.
• "Métodos cuasi-newtonianos". Optimización numérica . Springer Series in Operations Research and Financial Engineering. 2006. págs. 135-163. doi :10.1007/978-0-387-40065-5_6. ISBN 978-0-387-30303-1.