Algorithme de Frank-Wolfe

L' algorithme de Frank-Wolfe permet de résoudre des problèmes d'optimisation pour des fonctions convexes. Il a été proposé pour la première fois par Marguerite Frank et Philip Wolfe en 1956^[1]. Le principe de fonctionnement est d'approximer à chaque itération une fonction par son développement en série de Taylor au premier ordre.

Présentation du problème

On cherche à minimiser une fonction convexe ${\displaystyle f}$ définie sur un espace vectoriel ${\displaystyle D}$ ou une partie convexe de celui-ci.

On veut donc trouver ${\displaystyle x}$ tel que ${\displaystyle f(x)=\min\{f(y)|y\in D\}}$.

Algorithme

Initialisation : On initialise ${\displaystyle x}$ avec une valeur aléatoire de ${\displaystyle D}$ et ${\displaystyle k=0}$

Lancement de la boucle sur ${\displaystyle k}$

1. On cherche ${\displaystyle s}$ tel que ${\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}$ est minimal (On cherche le vecteur ${\displaystyle s\in D}$ qui a le produit scalaire le plus faible avec ${\displaystyle \nabla f(\mathbf {x} _{k})}$ - donc qui va dans la direction la plus opposée.)
2. Classiquement, on utilise une variable ${\displaystyle \gamma ={\frac {2}{2+k}}}$
3. On met à jour ${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\gamma (\mathbf {s} -\mathbf {x} _{k})}$

Utilisation

Cet algorithme est notamment utilisé pour l'apprentissage des réseaux de neurones comme le codage parcimonieux

Notes et références

1. (en) M. Frank et P. Wolfe, « An algorithm for quadratic programming », Naval Research Logistics Quarterly, vol. 3,‎ 1956, p. 95 (DOI 10.1002/nav.3800030109)

• Portail des mathématiques
• Portail de l'informatique théorique