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[ 1] itération une fonction par son développement en série de Taylor au premier ordre.
On cherche à minimiser une fonction convexe
f
{\displaystyle f}
D
{\displaystyle D}
convexe de celui-ci.
On veut donc trouver
x
{\displaystyle x}
f
(
x
)
=
min
{
f
(
y
)
|
y
∈ ∈ -->
D
}
{\displaystyle f(x)=\min\{f(y)|y\in D\}}
Algorithme
Initialisation : On initialise
x
{\displaystyle x}
D
{\displaystyle D}
k
=
0
{\displaystyle k=0}
Lancement de la boucle sur
k
{\displaystyle k}
On cherche
s
{\displaystyle s}
s
T
∇ ∇ -->
f
(
x
k
)
{\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}
s
∈ ∈ -->
D
{\displaystyle s\in D}
produit scalaire le plus faible avec
∇ ∇ -->
f
(
x
k
)
{\displaystyle \nabla f(\mathbf {x} _{k})}
Classiquement, on utilise une variable
γ γ -->
=
2
2
+
k
{\displaystyle \gamma ={\frac {2}{2+k}}}
On met à jour
x
k
+
1
← ← -->
x
k
+
γ γ -->
(
s
− − -->
x
k
)
{\displaystyle \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
↑ (en) M. Frank et P. Wolfe , « An algorithm for quadratic programming », Naval Research Logistics Quarterly vol. 3, 1956 , p. 95 (DOI 10.1002/nav.3800030109 
