Confusión sobre la regla Armijo

Tengo esta confusión sobre la regla de Armijo utilizada en la búsqueda de línea. Estaba leyendo la búsqueda de la línea de seguimiento, pero no entendí de qué se trata esta regla de Armijo. ¿Alguien puede explicar qué es la regla Armijo? La wikipedia no parece explicar bien. Gracias

optimization usuario34790
fuente

¿Qué pasa si en la ecuación la variable x no es un vector sino una matriz? ¿Cómo se debe actualizar la regla de Armijo?

Frank Puk

nada cambia. simplemente debe remodelar su matriz

en un vector (columna)

X_{k}

$X_k$

x_{k}

$x_k$

GoHokies

Ahí es donde me quedé atrapado. Cuando

convierte en una matriz, el valor en el lado izquierdo (

) sigue siendo un escalar. Pero el valor en el lado derecho no es, en cambio, es una matriz (

es un escalar y

es una matriz.)

x_{k}

$x_k$

f (x_{k} + α p_{k})

$f(x_k+\alpha p_k)$

f (x_{k})

$f(x_k)$

β α \nabla f (x_{k})^{T} p_{k}

$\beta\alpha∇f(x_k)^Tp_k$

Frank Puk

necesitará trabajar con un vector, no con una matriz. así que reestructura su matriz

de variables de control (lo he denotado por

) en un vector

con elementos

. La dirección de búsqueda y el gradiente también serán vectores con elementos

. De esta manera, tanto el RHS como el LHS de la condición de Armijo son escalares y se pueden comparar.

N \times N

$N \times N$

X_{k}

$X_k$

x_{k}

$x_k$

N^{2}

$N^2$

N^{2}

$N^2$

GoHokies

Respuestas:

Una vez que obtenga una dirección de descenso para su función objetivo , debe elegir una longitud de paso "buena". No desea dar un paso que sea demasiado grande para que la función en su nuevo punto sea más grande que su punto actual. Al mismo tiempo, no desea hacer que su paso sea demasiado pequeño, de modo que se necesite una eternidad para converger. $p$ $f(x)$

La condición de Armijo básicamente sugiere que una longitud de paso "buena" es tal que tiene una "disminución suficiente" en en su nuevo punto. La condición se establece matemáticamente como donde es una dirección de descenso en y . $f$

f (x_{k} + α p_{k}) \leq f (x_{k}) + β α \nabla f (x_{k})^{T} p_{k}

$f(x_k+\alpha p_k)\leq f(x_k)+\beta\alpha\nabla f(x_k)^Tp_k$

p_{k}

$p_k$

x_{k}

$x_k$

β \in (0, 1)

$\beta\in(0,1)$

La intuición detrás de esto es que el valor de la función en el nuevo punto debe estar debajo de la "línea tangente" reducida en en la dirección de . Ver el libro de Nocedal & Wright "Optimización numérica". En el capítulo 3, hay una excelente descripción gráfica de la condición de disminución suficiente de armijo. $f(x_k+\alpha p_k)$ $x_k$ $p_k$

Paul
fuente

β

$\beta$

α

$\alpha$

La razón por la que esto es importante, es decir, por qué es necesario un "buen" paso, es que muchos esquemas de optimización convergerán más lentamente, como dice Paul, o podrían no converger en absoluto. Entonces, las búsquedas de línea, que vienen en varias variedades, Armijo es solo la más popular, se pueden usar para dar a los algoritmos propiedades de convergencia más robustas.

cjordan1

Paul: tu explicación es incompleta. Esta desigualdad por sí sola no garantiza la disminución "suficiente". De hecho, puede tener alfa = 0, y aún así satisface la desigualdad que escribió. Una característica importante es que la regla de Armijo es unir el tamaño del paso lejos de cero, lo que se hace por otra desigualdad: f (gamma * x_new) -f (x_old)> beta * (gamma * x_new-x_old) ^ T * grad (f (x_old))

f (x) = x^{2}

$f(x) = x^2$

x_{k} = - 1

$x_k = -1$

p_{k} = - 2

$p_k = -2$

α

$\alpha$

f (x_{k} + α p_{k})

$f(x_k + \alpha p_k)$

α = 1 / 2

$\alpha = 1/2$

β > 1 / 2

$\beta > 1/2$

f (x_{k} + 1 / 2 p_{k}) = 0 > 1 - 2 β = f (x_{k}) + β α f^{'} (x_{k}) p_{k}

$f(x_k + 1/2 p_k) = 0 > 1 - 2 \beta = f(x_k) + \beta \alpha f'(x_k) p_k$

β

$\beta$

β > 1 / 2

$\beta > 1/2$

β = 10^{- 4}

$\beta = 10^{-4}$

β

$\beta$

Cinco años después, esta pregunta sigue siendo válida.

Aquí (páginas 16 y 17) puede encontrar una gran explicación, incluido un algoritmo.

Bojan Hrnkas
fuente