Algorithme de Frank-Wolfe

L'algorithme de Frank-Wolfe, ou algorithme du gradient conditionnel, est une méthode itérative du premier ordre permettant de résoudre des problèmes d'optimisation convexe contraints à des ensembles compacts. Il a été proposé pour la première fois par Marguerite Frank et Philip Wolfe en 1956^[1]. À chaque itération, l'algorithme utilise une direction de descente obtenue en minimisant un développement en série de Taylor au premier ordre de la fonction tout en restant dans le domaine de conraintes. Plusieurs variantes de l'algorithme existent; elles diffèrent notamment par le choix du pas d'optimisation, qui peut dépendre ou non de la fonction à optimiser.

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.

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.

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