In ottimizzazione convessa vincolata e in analisi numerica, l'algoritmo di Frank-Wolfe (detto anche algoritmo del gradiente condizionale, oppure del gradiente ridotto; in inglese conditional gradient o reduced gradient) è un metodo iterativo che consente di determinare il punto di minimo di un'approssimazione lineare della funzione obiettivo.
Il metodo fu sviluppato da Marguerite Frank e Philip Wolfe nel 1956.
Descrizione Sia un insieme convesso compatto in uno spazio vettoriale, e sia una funzione convessa e differenziabile. L'algoritmo di Frank-Wolfe trova in modo iterativo.
* Passo 0 (Inizializzazione): Si sceglie un punto e si pone * Passo 1: Si determina . * Passo 2: Si determina . * Passo 3: Si pone . * Passo 4: Si pone e si torna al Passo 1. A ogni iterazione l'algoritmo determina la direzione e la dimensione del passo lungo quella direzione in modo da minimizzare l'approssimazione lineare del problema. A differenza di metodi per l'ottimizzazione non vincolata, quali ad esempio la discesa del gradiente, l'algoritmo di Frank-Wolfe non necessita di proiezioni, poiché in ciascuna iterazione richiede soltanto la soluzione di un problema lineare sull'insieme .
La convergenza dell'algoritmo di Frank-Wolfe è sublineare: l'errore nella funzione obiettivo è minimo dopo iterazioni, purché il gradiente sia Lipschitziano rispetto ad una norma.
Note
Bibliografia
Categoria:Algoritmi di ottimizzazione Categoria:Ricerca operativa