Sintesi Tecnica: Ottimizzazione Vincolata Funzionale Senza Proiezione per l'Avversione al Rischio e il Controllo della Sparsità

1. Formulazione del Problema

Il documento affronta il problema di ottimizzazione vincolata funzionale:
$$\begin{aligned} f^* := \min_{x} \quad & f(x) \\ \text{s.t.} \quad & h_i(x) \le 0, \quad i = 1, \dots, m, \\ & x \in X, \end{aligned} \tag{1.1}$$
dove $X \subseteq \mathbb{R}^n$ è un insieme non vuoto, compatto e convesso. Le funzioni $h_i$ sono proprie, semicontinue inferiormente e convesse. L'obiettivo $f$ è studiato in due regimi:

1. Regime Convesso: $f$ è convessa (eventualmente non liscia).
2. Regime Non Convesso: $f$ è differenziabile con gradienti lipschitziani.

Questo quadro modella applicazioni in cui criteri consapevoli del rischio e vincoli di sparsità compaiono simultaneamente, come nell'ottimizzazione di portafoglio (minimizzazione del rischio di sottoperformance con limiti sugli asset) e nella pianificazione della radioterapia a intensità modulata (IMRT) (minimizzazione del sovradosaggio/sottodosaggio con selezione sparsa dei fasci).

Sfida: I metodi standard basati su proiezione (ad esempio, penalità, Lagrangiano aumentato, primale-duale) richiedono proiezioni ripetute su $X$, che possono essere computazionalmente costose e distruggere le strutture di sparsità intrinseche nella soluzione. I metodi senza proiezione esistenti gestiscono solo vincoli semplici o hanno limiti di complessità dipendenti dall'entità dei moltiplicatori di Lagrange ottimali, che possono essere arbitrariamente grandi.

2. Metodologia

Gli autori propongono algoritmi senza proiezione che sostituiscono le proiezioni con chiamate a un Oracolo di Minimizzazione Lineare (LMO) su $X$. L'innovazione principale è un Ciclo Esterno a Livello combinato con un Oracolo Condizionale del Gradiente (CGO) per i sottoproblemi di punto di sella.

2.1 Regime Convesso: Gradiente Condizionale a Livello (LCG)

Per il caso convesso, il problema è ridotto alla ricerca della radice di una funzione di valore $\phi(l) = \min_{x \in X} \max \{ f(x) - l, h_1(x), \dots, h_m(x) \}$.

• Ciclo Esterno: Un metodo di Newton approssimato aggiorna la stima del livello $l_k$. Invece di gradienti esatti, utilizza un limite inferiore $L_k$ e un subgradiente approssimato derivato dall'oracolo interno.
• Ciclo Interno (CGO): Un Oracolo Condizionale del Gradiente specializzato risolve il sottoproblema di punto di sella $\min_{x \in X} \max_{z \in Z} [f(x) - l_k] + \langle h(x), z \rangle$.
  • L'oracolo restituisce un'iterata primaria $x_k$ e un intervallo di certificazione $[L_k, U_k]$.
  • Crucialmente, l'insieme duale $Z$ è il simplesso standard, garantendo che il metodo non dipenda dall'entità dei moltiplicatori di Lagrange ottimali.
  • Il gap $U_k - L_k$ guida la regola di arresto e gli aggiornamenti del livello.
• Estensione Non Liscia: Per funzioni strutturate non lisce (struttura max), il metodo impiega la lisciatura di Nesterov all'interno del quadro CGO, mantenendo lo stesso ordine di complessità.

2.2 Regime Non Convesso: LCG a Punto Prossimale Inesatto (IPP-LCG)

Per $f$ non convessa, il metodo riduce il problema a una sequenza di sottoproblemi convessi tramite regolarizzazione a punto prossimale:
$$\min_{x \in X} f(x) + L_f \|x - x_{j-1}\|^2 \quad \text{s.t.} \quad h_i(x) \le 0.$$

• Meccanismo: Il metodo LCG del regime convesso è utilizzato come risolutore inesatto per ogni sottoproblema prossimale.
• Output: L'algoritmo seleziona l'iterata che minimizza la diminuzione dell'obiettivo lungo la sequenza.
• Garanzia: Sotto la condizione di Slater e ipotesi di regolarità, il metodo calcola un punto $(\epsilon, \epsilon)$-quasi-KKT.

3. Contributi Chiave

1. LCG per Vincoli Funzionali Convessi:

   • Propone il metodo del Gradiente Condizionale a Livello (LCG).
   • Raggiunge una complessità iterativa di $O(\epsilon^{-2} \log(\epsilon^{-1}))$ per ottenere una soluzione $\epsilon$-ottima e $\epsilon$-ammissibile.
   • Significato: Il limite di complessità è indipendente dall'entità del moltiplicatore di Lagrange duale ottimale, un limite presente nei lavori precedenti senza proiezione (ad esempio, Lan et al., 2021).

2. IPP-LCG per Obiettivi Non Convessi Lisci:

   • Sviluppa il metodo del Punto Prossimale Inesatto LCG (IPP-LCG).
   • Risolve una sequenza di sottoproblemi convessi utilizzando LCG, mantenendo tutte le risoluzioni interne senza proiezione.
   • Raggiunge una complessità iterativa di $O(\epsilon^{-3} \log(\epsilon^{-1}))$ per calcolare un punto $(\epsilon, \epsilon)$-quasi-KKT.

3. Meccanismo di Certificazione:

   • Il CGO restituisce certificati espliciti inferiore e superiore ($L_k, U_k$) che guidano gli aggiornamenti del livello e le regole di arresto, evitando la necessità di soluzioni esatte del punto di sella.

4. Risultati Numerici

Gli autori valutano i metodi su due domini applicativi:

4.1 Selezione del Portafoglio

• Configurazione: Ottimizzazione di portafoglio avverso al rischio con obiettivi di rischio a gradino (convessificati tramite CVaR o surrogati non convessi lisciati) e vincoli di sparsità (limitazione del numero di asset).
• Baseline: Confronto contro CoexDurCG (senza proiezione), FISTA, PGD e varie euristiche orientate alla sparsità (Greedy+Refit, IRL1, ecc.) sotto un budget fisso di 5 secondi di tempo reale.
• Risultati:
  • Modello Convesso: LCG ha ottenuto il miglior rischio a gradino fuori campione ammissibile su 5 dataset su 6, rispettando rigorosamente gli obiettivi di sparsità.
  • Modello Non Convesso: IPP-LCG ha ottenuto il miglior rischio a gradino ammissibile su 4 dataset su 6.
  • Compromesso: I metodi hanno navigato con successo il compromesso accuratezza-sparsità, spesso superando le baseline basate su proiezione nella riduzione del rischio ammissibile entro lo stesso budget temporale.

4.2 Radioterapia a Intensità Modulata (IMRT)

• Configurazione: Pianificazione del trattamento con vincoli di sparsità di gruppo (limitazione del numero di angoli del fascio) e vincoli clinici di volume-dose.
• Risultati:
  • Convesso: LCG ha migliorato la soddisfazione dei vincoli rispetto a CoexDurCG con tempi di esecuzione simili.
  • Non Convesso: È stata testata una strategia di "avvio caldo" (warm-start) in cui un piano LCG convesso e sparso inizializzava la raffinazione non convessa IPP-LCG.
  • Risultato: L'IPP-LCG avviato a caldo ha ridotto significativamente la violazione massima dei vincoli (da 0.8438 a 0.1675) rispetto a un IPP-LCG avviato a freddo, preservando al contempo una struttura di trattamento clinicamente sparsa (7 angoli, 20 aperture). L'ottimizzazione non convessa avviata a freddo non è riuscita a trovare piani clinicamente vitali a causa di un grave sottodosaggio del bersaglio.

5. Significato e Affermazioni

Il documento afferma che il suo contributo principale risiede nell'estendere i metodi senza proiezione a vincoli funzionali generali senza fare affidamento sull'entità dei moltiplicatori duali per le garanzie di complessità. Combinando un ciclo esterno a livello con un oracolo compatto di punto di sella, gli autori mantengono i benefici della rappresentazione sparsa dei metodi del gradiente condizionale (iterati come combinazioni convesse di punti estremi) gestendo al contempo vincoli non lineari complessi.

I risultati numerici suggeriscono che:

1. LCG è efficace per problemi di rischio-sparsità convessi, offrendo prestazioni competitive o superiori rispetto ai metodi esistenti senza proiezione e basati su proiezione.
2. IPP-LCG è più efficace non come risolutore autonomo da un inizio casuale, ma come meccanismo di raffinazione quando inizializzato con una soluzione convessa sparsa di alta qualità.

Gli autori concludono che questi metodi sono particolarmente adatti per applicazioni su larga scala dove le proiezioni sono costose e sono desiderabili rappresentazioni strutturali sparse. Le direzioni di lavoro futuro identificate includono lo sviluppo di schemi non convessi più leggeri, il rilassamento delle ipotesi di tipo Slater e la progettazione di LMO specifici per l'applicazione per insiemi ammissibili impliciti.