Ottimizzazione convessa — concetti, metodi e applicazioni

L’ottimizzazione convessa consiste nel minimizzare una funzione convessa su un insieme ammissibile convesso. Il motivo principale per cui è importante è semplice: se queste condizioni di convessità valgono, ogni minimo locale è anche un minimo globale.

Questa garanzia rende questi problemi molto più affidabili dei problemi di ottimizzazione generale. Bisogna comunque modellare correttamente il problema, ma una volta che il modello è convesso, non si cerca una soluzione che sembra migliore solo in un piccolo intorno.

Una forma comune è

$$\text{minimize } f(x)$$

subject to

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

dove $f$ e ciascuna $g_i$ sono convesse, e i vincoli di uguaglianza sono affini. In queste condizioni, l’insieme ammissibile è convesso e il problema di ottimizzazione è convesso.

Definizione di ottimizzazione convessa

Una funzione $f$ è convessa se, per due punti qualsiasi $x$ e $y$ del suo dominio e per ogni $0 \le t \le 1$,

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

In parole semplici, il segmento che unisce due punti del grafico sta al di sopra del grafico stesso. In una variabile, molte funzioni convesse hanno una forma “a ciotola”, ma il vero criterio è la disuguaglianza.

Un insieme è convesso se, ogni volta che contiene due punti, contiene anche tutti i punti del segmento che li unisce.

Servono entrambe le condizioni:

• una funzione obiettivo convessa
• un insieme ammissibile convesso

Se una delle due manca, il problema può smettere di essere convesso.

Perché l’ottimizzazione convessa è più facile da analizzare

L’ottimizzazione è spesso difficile perché possono esserci molte valli. Un algoritmo può continuare a migliorare la funzione obiettivo e fermarsi comunque in un punto che è ottimo solo localmente.

L’ottimizzazione convessa elimina proprio questa modalità di fallimento. Se la funzione obiettivo è convessa e la regione ammissibile è convessa, allora un punto che non può essere migliorato localmente è già ottimo globalmente. Per questo i problemi convessi sono importanti in statistica, machine learning, controllo e ricerca operativa.

Questo non significa che ogni problema convesso sia facile. Alcuni sono comunque grandi o costosi dal punto di vista computazionale. Significa che la struttura è abbastanza pulita da permettere a buoni algoritmi di puntare al vero ottimo invece di restare intrappolati in comportamenti locali fuorvianti.

Esempio svolto di ottimizzazione convessa

Considera il problema senza vincoli

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

Questo è un problema di ottimizzazione convessa perché $f(x)$ è una funzione quadratica con coefficiente principale positivo, quindi è convessa su tutti i numeri reali.

Per trovare il minimizzatore, deriviamo:

$$f'(x) = 2(x-3).$$

Poniamo la derivata uguale a zero:

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

Ora valutiamo la funzione obiettivo:

$$f(3) = (3-3)^2 + 2 = 2.$$

Quindi il valore minimo è $2$, ottenuto per $x=3$.

Questo esempio è semplice, ma mostra l’idea principale. Una volta arrivati a $x=3$, non c’è una valle più bassa nascosta da qualche altra parte.

Metodi comuni per l’ottimizzazione convessa

Il metodo dipende dalla struttura del problema.

Per problemi regolari senza vincoli o con vincoli semplici, sono comuni i metodi basati sul gradiente, perché muoversi nella direzione opposta al gradiente può ridurre la funzione obiettivo.

Per molti problemi convessi con vincoli, i metodi del punto interno sono molto usati perché gestiscono direttamente i vincoli e spesso funzionano bene nella pratica.

Per problemi convessi non regolari, i metodi del sottogradiente o i metodi prossimali possono essere più adatti. L’idea importante non è l’elenco degli algoritmi. È la garanzia che la struttura convessa offre a questi algoritmi qualcosa di stabile su cui lavorare.

Errori comuni nell’ottimizzazione convessa

Supporre che un grafico dimostri la convessità

Un grafico può sembrare “a ciotola” in una rappresentazione e comunque non essere convesso sull’intero dominio o in dimensioni superiori. La definizione o le regole standard di convessità contano più di uno schizzo.

Dimenticare che i vincoli contano

Una funzione obiettivo convessa da sola non basta. Se l’insieme ammissibile non è convesso, il problema complessivo non è un problema di ottimizzazione convessa.

Trattare ogni punto critico come un minimo

Per una funzione convessa differenziabile, un punto con gradiente nullo è un minimizzatore globale. Senza convessità, questa conclusione in generale non vale.

Confondere convesso con strettamente convesso

La stretta convessità è una proprietà più forte. Spesso garantisce un minimizzatore unico, mentre la semplice convessità non garantisce sempre l’unicità.

Dove si usa l’ottimizzazione convessa

L’ottimizzazione convessa compare ogni volta che un problema reale può essere modellato con costi convessi e vincoli convessi.

Esempi comuni includono l’adattamento ai minimi quadrati, le support vector machine, la selezione di portafoglio con modelli di rischio convessi e molti problemi di allocazione delle risorse. Il modello preciso conta: un’applicazione è convessa solo quando la funzione obiettivo e i vincoli scelti soddisfano davvero le ipotesi di convessità.

Quando la convessità aiuta nella pratica

L’ottimizzazione convessa è particolarmente utile quando serve più di un semplice numero. Spesso si vuole una garanzia che la risposta sia davvero ottimale per il modello che si è scritto.

Questa garanzia conta in ingegneria e nel lavoro sui dati perché separa due domande:

1. Abbiamo risolto correttamente il problema matematico?
2. Il problema matematico era un buon modello della realtà?

La convessità aiuta molto con la prima domanda. Non risolve automaticamente la seconda.

Prova un problema simile

Prendi $f(x) = (x+1)^2 + 5$ e trovane il minimo. Poi confrontala con $f(x) = -(x+1)^2 + 5$, che è concava, non convessa. Questo confronto affiancato rende molto più chiaro il ruolo della convessità.

Se vuoi esplorare un altro caso, prova a impostare un piccolo problema di minimi quadrati e osserva come la minimizzazione di una funzione di errore convessa porti a un miglior adattamento stabile.