condiciones de lobo

Desigualdades para búsqueda de líneas inexactas

En el problema de minimización sin restricciones , las condiciones de Wolfe son un conjunto de desigualdades para realizar una búsqueda lineal inexacta , especialmente en métodos cuasi-Newton , publicado por primera vez por Philip Wolfe en 1969. ^{[1] [2]}

En estos métodos la idea es encontrar

$${\displaystyle \min _{x}f(\mathbf {x} )}$$

suaves ${\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íneas inexactas proporcionan una manera eficiente de calcular una longitud de paso aceptable que reduce la función objetivo "suficientemente", en lugar de minimizar la función objetivo exactamente. Un algoritmo de búsqueda de líneas puede utilizar las condiciones de Wolfe como requisito para cualquier conjetura , 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 la longitud de un 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 garantizar que sea 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}}$Por lo general, se elige que sea 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 regla de Armijo ^[4] y ii) como condición de curvatura ; i) garantiza que la longitud del paso disminuye "suficientemente", y ii) garantiza 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 para 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}$

Fuerte condición de Wolfe en la curvatura.

Denota una función univariada restringida 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, ${\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 de Wolfe fuertes y obligan 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 es asegurar la convergencia del gradiente a cero. En particular, si el coseno del ángulo entre y el gradiente, ${\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 la línea de retroceso artículo de búsqueda ).

Ver también

• Búsqueda de línea de retroceso

Referencias

1. Wolfe, P. (1969). "Condiciones de convergencia para métodos de ascenso". Revisión SIAM . 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". Revisión SIAM . 13 (2): 185–188. doi :10.1137/1013035. JSTOR  2028821.
3. Nocedal, Jorge ; Wright, Stephen (1999). Optimización numérica. pag. 38.
4. Armijo, Larry (1966). "Minimización de funciones que tienen primeras derivadas parciales continuas de Lipschitz". Pacífico J. Matemáticas . 16 (1): 1–3. doi : 10.2140/pjm.1966.16.1 .

Otras lecturas

• "Métodos de búsqueda de líneas". 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.