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 f {\displaystyle f} définie sur un espace vectoriel D {\displaystyle D} ou une partie convexe de celui-ci.

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

Algorithme

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

Lancement de la boucle sur k {\displaystyle k}

  1. On cherche s {\displaystyle s} tel que s T ∇ f ( x k ) {\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})} est minimal (On cherche le vecteur s ∈ D {\displaystyle s\in D} qui a le produit scalaire le plus faible avec ∇ f ( x k ) {\displaystyle \nabla f(\mathbf {x} _{k})} - donc qui va dans la direction la plus opposée.)
  2. Classiquement, on utilise une variable γ = 2 2 + k {\displaystyle \gamma ={\frac {2}{2+k}}}
  3. On met à jour x k + 1 ← x k + γ ( s − x k ) {\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,‎ , p. 95 (DOI 10.1002/nav.3800030109)
  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique