Algoritmo di Frank-Wolfe

Per minimizzare una funzione convessa ${\displaystyle f}$ (in blu) su un insieme convesso ${\displaystyle 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^[1], 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^[2].

Descrizione

Sia ${\displaystyle D}$ un insieme convesso compatto in uno spazio vettoriale, e sia ${\displaystyle f\colon D\to \mathbb {R} }$ una funzione convessa e differenziabile. L'algoritmo di Frank-Wolfe trova ${\displaystyle \min _{\mathbf {x} \in D}f(\mathbf {x} )}$ in modo iterativo.

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

A ogni iterazione l'algoritmo determina la direzione ${\displaystyle \mathbf {s} _{k}}$ e la dimensione del passo ${\displaystyle \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 ${\displaystyle D}$.

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

Note

1. (EN) E.S. Levitin e B.T. Polyak, Constrained minimization methods, in USSR Computational Mathematics and Mathematical Physics, vol. 6, n. 5, gennaio 1966, pp. 1-50, DOI:10.1016/0041-5553(66)90114-5. URL consultato l'8 marzo 2024.
2. (EN) Marguerite Frank e Philip Wolfe, An algorithm for quadratic programming, in Naval Research Logistics Quarterly, vol. 3, n. 1-2, marzo 1956, pp. 95-110, DOI:10.1002/nav.3800030109. URL consultato l'8 marzo 2024.

Bibliografia

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica