Algorithme de Frank-Wolfe

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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]. 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[modifier | modifier le code]

On 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[modifier | modifier le code]

Initialisation : On initialise avec une valeur aléatoire de et

Lancement de la boucle sur

  1. 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.)
  2. Classiquement, on utilise une variable
  3. On met à jour

Utilisation[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. (en) M. Frank et P. Wolfe, « An algorithm for quadratic programming », Naval Research Logistics Quarterly, vol. 3,‎ , p. 95 (DOI 10.1002/nav.3800030109)