Utilisateur:Renard Arctique/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 Franck et Philippe Wolfe en 1956.[1] 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
modifierOn cherche à minimiser une fonction convexe définie sur un espace vectoriel ou une partie convexe de celui-ci.
on veut donc trouver tel que
Algorithme
modifierInitialisation : On initialise avec une valeur aléatoire de et
Lancement de la boucle sur
- On cherche tel que est minimal (On cherche le vecteur qui a le produit scalaire le plus faible avec - donc qui va dans la direction la plus opposée.)
- Classiquement, on utilise une variable
- On met à jour
Utilisation
modifierCet algorithme est notamment utilisé pour l'apprentissage des réseaux de neurones comme le codage parcimonieux
Notes et Références
modifier- M. Frank et P. Wolfe, « An algorithm for quadratic programming », Naval Research Logistics Quarterly, vol. 3, , p. 95 (DOI 10.1002/nav.3800030109)
<code> [[Catégorie:Apprentissage automatique]] [[Catégorie:Exploration de données]] [[Catégorie:Informatique théorique]]