Algorithme de Frank-Wolfe

Il existe de nombreuses variantes de l'algorithme de Frank-Wolfe. Nous en donnons ici une version pour laquelle le pas ${\displaystyle \gamma _{i}}$ ne nécessite pas d'information a priori sur la fonction à minimiser.

 Entrée: Fonction ${\displaystyle f}$, dictionnaire ${\displaystyle D}$, nombre d'itérations ${\displaystyle I}$ 
 Sortie: Estimateur ${\displaystyle x_{I}}$
  
 Initialisation: ${\displaystyle x_{0}\in D}$ (donné ou choisi aléatoirement) 
 Pour ${\displaystyle i=0,\dots ,I-1}$  
   Trouver ${\displaystyle s_{i}\in D}$ minimisant ${\displaystyle \langle \nabla f(x_{i}),s\rangle }$
   ${\displaystyle \gamma _{i}={\frac {2}{2+i}}}$ 
   ${\displaystyle x_{i+1}=x_{i}+\gamma _{i}(s_{i}-x_{i})}$
 FinPour
 Retourner ${\displaystyle x_{I}}$

La descente s'effectue donc à chaque itération dans la direction ${\displaystyle s_{i}}$ du dictionnaire la plus opposée au gradient.

Dans l'algorithme ci-dessus, le pas ${\displaystyle \gamma _{i}}$ ne dépend que de ${\displaystyle i}$. Des variantes existent^[3], par exemple lorsque ${\displaystyle \nabla f}$ est ${\displaystyle L}$-Lipschitz pour une valeur de ${\displaystyle L}$ connue il est courant de choisir un paramètre ${\displaystyle \gamma _{i}}$ dépendant de cette valeur. Une autre alternative, souvent plus coûteuse, consiste à ne pas fixer de pas a priori mais à directement construire ${\displaystyle x_{i+1}=\arg \min _{\alpha \in [0,1]}f(\alpha x+(1-\alpha )s_{i})}$.

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

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting

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