Utilisateur:Pamango/Brouillon Convergence FW

Résultats de convergence

L'analyse de convergence de l'algorithme de Frank-Wolfe dépend fondamentalement d'une mesure de non-linéarité de la fonction minimisée, la constante de courbure. Cette constante, définie pour une fonction $f$ et un ensemble compact ${\mathcal {D}}$ est la suivante :

$C_{f}=\sup _{x,s\in {\mathcal {D}},\gamma \in [0,1]}{\frac {2}{\gamma ^{2}}}(f(x+\gamma (s-x))-f(x)-\gamma \langle s-x,\nabla f(x)\rangle .$

Convergence — Soit f une fonction convexe différentiable sur un ensemble convexe et compact ${\mathcal {D}}$. L'algorithme de Frank-Wolfe ci-dessus, génère une suite $\{x_{k}\}_{k\geqslant 1}$ convergeant sous-linéairement vers l'unique minimum x_* de f. Plus précisément, on a

$\forall k,f(x_{k})-f(x^{*})\leq {\frac {2C_{f}}{k+2}}.$

Contrairement à d'autres algorithmes d'optimisation, comme l'algorithme du gradient, la convergence linéaire de l'algorithme de Frank-Wolfe n'est pas établie. Toutefois, une modification dans le choix choix de la direction de descente permet d'obtenir ce type de convergence plus rapide.