Algoritmo di Frank-Wolfe

Per minimizzare una funzione convessa $f$ (in blu) su un insieme convesso $D$ (in verde), l'algoritmo di Frank-Wolfe considera la linearizzazione della funzione obiettivo all'iterazione corrente (in rosso)

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 $D$ un insieme convesso compatto in uno spazio vettoriale, e sia $f:D\to ℝ$ una funzione convessa e differenziabile. L'algoritmo di Frank-Wolfe trova $\underset{𝐱\in D}{\min }f(𝐱)$ in modo iterativo.

* Passo 0 (Inizializzazione): Si sceglie un punto ${𝐱}_0\in D$ e si pone $k=0.$
* Passo 1: Si determina ${𝐬}_k=\underset{𝐬\in D}{\min }{𝐬}^T\mathrm{\nabla }f({𝐱}_k)$.
* Passo 2: Si determina $\alpha =\underset{0\le \alpha \le 1}{\min }f({𝐱}_k+\alpha ({𝐬}_k-{𝐱}_k))$.
* Passo 3: Si pone ${𝐱}_{k+1}={𝐱}_k+\alpha ({𝐬}_k-{𝐱}_k)$.
* Passo 4: Si pone $k=k+1$ e si torna al Passo 1.

A ogni iterazione l'algoritmo determina la direzione ${𝐬}_k$ e la dimensione del passo $\alpha$ 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 $D$.

La convergenza dell'algoritmo di Frank-Wolfe è sublineare: l'errore nella funzione obiettivo è minimo dopo $k$ iterazioni, purché il gradiente sia Lipschitziano rispetto ad una norma.

Bibliografia

• Template:Cita libro