L'algorisme de Frank-Wolfe és un algorisme iteratiu d'optimització de primer ordre per a l'optimització convexa restringida. També conegut com a mètode de gradient condicional, algorisme de gradient reduït i algorisme de combinació convexa, el mètode va ser proposat originalment per Marguerite Frank i Philip Wolfe a 1956. En cada iteració, l'algorisme de Frank-Wolfe considera una aproximació lineal de la funció objectiu i es mou cap a un minimitzador d'aquesta funció lineal (pres sobre el mateix domini).
Plantejament del problema Suposem és un conjunt convex compacte en un espai vectorial i és una funció convexa i diferenciable amb valors reals. L'algorisme de Frank-Wolfe resol el problema d'optimització
Minimitzar subjecte a .
Algorisme miniatura|Un pas de l'algorisme de Frank-Wolfe Inicialització: Deixeu , i deixeu ser qualsevol punt en .
Pas 1. Subproblema de radiogoniometria: Trobar resolent Minimitzar Subjecte a (Interpretació: Minimitzar l'aproximació lineal del problema donat per l'aproximació de Taylor de primer ordre de al voltant obligat a quedar-se dins .)
Pas 2. Determinació de la mida del pas: Establir , o alternativament trobar que minimitza subjecte a .
Pas 3. Actualització: Deixeu , deixem i aneu al pas 1.
Propietats Mentre que els mètodes competidors, com ara el descens de gradient per a l'optimització restringida, requereixen un pas de projecció cap al conjunt factible en cada iteració, l'algorisme de Frank-Wolfe només necessita la solució d'un problema convex sobre el mateix conjunt en cada iteració i es manté automàticament al conjunt factible.
La convergència de l'algorisme de Frank-Wolfe és sublineal en general: l'error de la funció objectiu a l'òptim és després de k iteracions, sempre que el gradient sigui continu de Lipschitz respecte a alguna norma. La mateixa taxa de convergència també es pot demostrar si els subproblemes només es resolen aproximadament.
Les iteracions de l'algorisme sempre es poden representar com una combinació convexa dispersa dels punts extrems del conjunt factible, cosa que ha contribuït a la popularitat de l'algorisme per a l'optimització voraç dispersa en problemes d'aprenentatge automàtic i processament de senyals, així com, per exemple, l'optimització de fluxos de cost mínim en xarxes de transport.
Si el conjunt factible ve donat per un conjunt de restriccions lineals, aleshores el subproblema a resoldre en cada iteració esdevé un programa lineal.
Mentre que la taxa de convergència del pitjor dels casos amb no es pot millorar en general, es pot obtenir una convergència més ràpida per a classes de problemes especials, com ara alguns problemes fortament convexos.
Límits inferiors del valor de la solució i anàlisi primal-dual Des de és convex, per a dos punts qualssevol tenim:
Això també és vàlid per a la solució òptima (desconeguda) És a dir, El millor límit inferior respecte a un punt donat ve donat per
Aquest darrer problema d'optimització es resol en cada iteració de l'algorisme de Frank-Wolfe, per tant, la solució del subproblema de la radiogoniometria La iteració -èsima es pot utilitzar per determinar límits inferiors creixents durant cada iteració establint i
Aquests límits inferiors del valor òptim desconegut són importants a la pràctica perquè es poden utilitzar com a criteri d'aturada i donen un certificat eficient de la qualitat de l'aproximació en cada iteració, ja que sempre .
Aplicacions L'algorisme de Frank-Wolfe es pot utilitzar per calcular un equilibri de Wardrop.
Referències
Categoria:Algorismes Categoria:Optimització