Algoritmo di Frank-Wolfe

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.

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)

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\colon D\to \mathbb {R}$ una funzione convessa e differenziabile. L'algoritmo di Frank-Wolfe trova $\min _{\mathbf {x} \in D}f(\mathbf {x} )$ in modo iterativo.

* Passo 0 (Inizializzazione): Si sceglie un punto $\mathbf {x} _{0}\in D$ e si pone $k=0.$
* Passo 1: Si determina $\mathbf {s} _{k}=\min _{\mathbf {s} \in D}\mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})$.
* Passo 2: Si determina $\alpha =\min _{0\leq \alpha \leq 1}f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))$.
* Passo 3: Si pone $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})$.
* Passo 4: Si pone $k=k+1$ e si torna al Passo 1.

A ogni iterazione l'algoritmo determina la direzione $\mathbf {s} _{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

• (EN) Jorge Nocedal e Stephen J. Wright, Numerical Optimization, 2ª ed., Berlino, Springer-Verlag, 2006, ISBN 978-0-387-30303-1.