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 ${𝐬}^T\mathrm{\nabla }f({𝐱}_k)$ est minimal (On cherche le vecteur $s\in D$ qui a le produit scalaire le plus faible avec $\mathrm{\nabla }f({𝐱}_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 ${𝐱}_{k+1}\leftarrow {𝐱}_k+\gamma (𝐬-{𝐱}_k)$

Utilisation

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