Confusion au sujet de la règle d'Armijo

13

J'ai cette confusion sur la règle Armijo utilisée dans la recherche en ligne. Je relisais la recherche de ligne de suivi, mais je n'ai pas compris de quoi s'agissait cette règle Armijo. Quelqu'un peut-il expliquer ce qu'est la règle d'Armijo? Le wikipedia ne semble pas bien expliquer. Merci

user34790
la source
Et si dans l'équation la variable x n'est pas un vecteur mais une matrice? Comment mettre à jour la règle Armijo?
Frank Puk
rien ne change. vous devez simplement remodeler votre matrice en un vecteur (colonne) x k . Xkxk
GoHokies
C'est là que je suis resté coincé. Lorsque devient une matrice, la valeur sur le côté gauche ( f ( x k + α p k ) ) est toujours un scalaire. Mais la valeur sur le côté droit n'est pas - à la place, c'est une matrice ( f ( x k ) est un scalaire et β α f ( x k ) T p k est une matrice.)xkf(xk+αpk)f(xk)βαf(xk)Tpk
Frank Puk
vous devrez travailler avec un vecteur, pas avec une matrice. vous remodelez donc votre matrice de variables de contrôle (je l'ai désignée par X k ) en un vecteur x k avec N 2 éléments. La direction de recherche et le gradient seront également des vecteurs à N 2 éléments. de cette façon, les RHS et LHS de la condition d'Armijo sont des scalaires et peuvent être comparés. N×NXkxkN2N2
GoHokies

Réponses:

19

Une fois que vous avez obtenu une direction de descente pour votre fonction objectif f ( x ) , vous devez choisir une "bonne" longueur de pas. Vous ne voulez pas faire un pas trop grand pour que la fonction à votre nouveau point soit plus grande que votre point actuel. Dans le même temps, vous ne voulez pas faire votre pas trop petit de telle sorte qu'il faut une éternité pour arriver à converger.pf(x)

L'état d'Armijo suggère essentiellement qu'une "bonne" longueur de pas est telle que vous avez "une diminution suffisante" de à votre nouveau point. La condition est mathématiquement énoncée comme f ( x k + α p k ) f ( x k ) + β α f ( x k ) T p kp k est une direction de descente à x k et β ( 0 , 1 ) . f

f(xk+αpk)f(xk)+βαf(xk)Tpk
pkxkβ(0,1)

L'intuition derrière cela est que la valeur de la fonction au nouveau point devrait être sous la "ligne tangente" réduite à x k dans la direction de p k . Voir le livre de Nocedal & Wright "Numerical Optimization". Dans le chapitre 3, il y a une excellente description graphique de la condition de diminution suffisante d'Armijo.f(xk+αpk)xkpk

Paul
la source
1
βα
La raison pour laquelle cela importe du tout, c'est-à-dire pourquoi une "bonne" étape est nécessaire, est que de nombreux schémas d'optimisation convergeront plus lentement, comme le dit Paul, ou pourraient ne pas converger du tout. Ainsi, les recherches en ligne - qui existent en plusieurs variétés, Armijo est juste la plus populaire - peuvent être utilisées pour donner aux algorithmes des propriétés de convergence plus robustes.
cjordan1
1
Paul: votre explication est incomplète. Cette inégalité à elle seule ne garantit pas une diminution «suffisante». En fait, vous pouvez avoir alpha = 0 et satisfait toujours l'inégalité que vous avez écrite. Une caractéristique importante est que la règle d'Armijo est de délimiter la taille du pas à partir de zéro, ce qui se fait par une autre inégalité: f (gamma * x_new) -f (x_old)> beta * (gamma * x_new-x_old) ^ T * grad (f (x_old))
f(x)=x2xk=1pk=2αf(xk+αpk)α=1/2β>1/2f(xk+1/2pk)=0>12β=f(xk)+βαf(xk)pkβ
β>1/2β=104β
0

Cinq ans plus tard, cette question est toujours d'actualité.

Ici (pages 16 et 17), vous pouvez trouver une excellente explication, y compris un algorithme.

Bojan Hrnkas
la source