Worldlex Wiki L' algorithme de Frank-Wolfe est un algorithme d'optimisation itératif du premier ordre pour l'optimisation convexe sous contraintes . Également connu sous le nom de méthode du gradient conditionnel , d'algorithme du gradient réduit et d' algorithme de combinaison convexe , il a été initialement proposé par Marguerite Frank et Philip Wolfe en 1956 À chaque itération, l'algorithme de Frank-Wolfe considère une approximation linéaire de la fonction objectif et tend vers un minimiseur de cette fonction linéaire (sur le même domaine).
Énoncé du problème
Supposer
- Minimiser
- sous réserve de
Algorithme
- Initialisation : Soit
- Étape 1. Sous-problème de recherche de direction : Trouver
- (Interprétation : Minimiser l'approximation linéaire du problème donnée par l' approximation de Taylor du premier ordre de
- Étape 2. Détermination de la taille du pas : Définir
- Étape 3. Mise à jour : Laissez
Propriétés
Alors que les méthodes concurrentes telles que la descente de gradient pour l'optimisation sous contraintes nécessitent une étape de projection vers l'ensemble réalisable à chaque itération, l'algorithme de Frank-Wolfe ne nécessite que la solution d'un problème convexe sur le même ensemble à chaque itération et reste automatiquement dans l'ensemble réalisable.
La convergence de l'algorithme de Frank-Wolfe est généralement sous-linéaire : l'erreur de la fonction objectif par rapport à l'optimum est
Les itérations de l'algorithme peuvent toujours être représentées comme une combinaison convexe creuse des points extrêmes de l'ensemble admissible, ce qui a contribué à la popularité de l'algorithme pour l'optimisation gloutonne creuse dans les problèmes d'apprentissage automatique et de traitement du signal , ainsi que par exemple l'optimisation des flux à coût minimal dans les réseaux de transport .
Si l'ensemble admissible est donné par un ensemble de contraintes linéaires, alors le sous-problème à résoudre à chaque itération devient un programme linéaire .
Alors que le taux de convergence dans le pire des cas avec
Bornes inférieures de la valeur de la solution et analyse primale-duale
Depuis
Cela vaut également pour la solution optimale (inconnue).
Ce dernier problème d'optimisation est résolu à chaque itération de l'algorithme de Frank-Wolfe, donc la solution
Ces bornes inférieures sur la valeur optimale inconnue sont importantes en pratique car elles peuvent servir de critère d'arrêt et fournir une certification efficace de la qualité de l'approximation à chaque itération, puisque toujours
Il a été démontré que cet écart de dualité correspondant , c'est-à-dire la différence entre
Applications
L'algorithme de Frank-Wolfe peut être utilisé pour calculer un équilibre de Wardrop .