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

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

Algorithme

Initialisation : On initialise $x$ avec une valeur aléatoire de $D$ et $k=0$

Lancement de la boucle sur $k$

1. On cherche $s$ tel que $\mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})$ est minimal (On cherche le vecteur $s\in D$ qui a le produit scalaire le plus faible avec $\nabla f(\mathbf {x} _{k})$ - donc qui va dans la direction la plus opposée.)
2. Classiquement, on utilise une variable $\gamma ={\frac {2}{2+k}}$
3. On met à jour $\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