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. À 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 contrainte. 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.

Historique

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

Présentation du problème

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


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

Algorithme

Visualisation d'une étape de l'algorithme de Frank-Wolfe, appliqué à la minimisation d'une fonction convexe (bleu) sur une partie convexe bornée d'un espace en deux dimensions D (vert). La linéarisation vers la fonction finale lors de l'itération x est en rouge.

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

 Entrée: Fonction f, dictionnaire D, nombre d'itérations I 
 Sortie: Estimateur xI
  
 Initialisation: x0∈D (donné ou choisi aléatoirement) 
 Pour i=0,…,I−1  
   Trouver si∈D minimisant ⟨∇f(xi),s⟩
   γi=22+i 
   xi+1=xi+γi(si−xi)
 FinPour
 Retourner xI

La descente s'effectue donc à chaque itération dans la direction si du dictionnaire la plus opposée au gradient.

Choix du pas

Dans l'algorithme ci-dessus, le pas γi ne dépend que de i. Des variantes existent, par exemple lorsque ∇f est L-Lipschitz pour une valeur de L connue il est courant de choisir un paramètre γi dépendant de cette valeur. Une autre alternative, souvent plus coûteuse, consiste à ne pas fixer de pas a priori mais à directement construire xi+1=arg⁡minα∈[0,1]f(αx+(1−α)si).

Utilisation

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