Algorithme de Frank-Wolfe

L'algorithme a été introduit par Marguerite Frank et Philip Wolfe en 1956^[1], et a été généralisé par Evgenii S. Levitin et Boris T. Polyak^[2].

On cherche à minimiser une fonction convexe ${\displaystyle f}$ définie sur une partie ${\displaystyle D}$ compacte et convexe d'un espace vectoriel.

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

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.

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