Ottimizzazione Convessa

📚 Riepilogo del Contenuto

Un corso e un testo universitario completo a livello avanzato che copre la teoria, le applicazioni e gli algoritmi numerici dell'ottimizzazione convessa. Si concentra sulla capacità di riconoscere e formulare problemi convessi nell'ingegneria e nelle scienze.

Padroneggia la base matematica e gli algoritmi pratici dell'ottimizzazione convessa per l'ingegneria e la scienza dei dati.

Autore: Stephen Boyd, Lieven Vandenberghe

Ringraziamenti: Supportato in parte dal NSF, e grazie ai contributi degli studenti e colleghi di Stanford e UCLA, con particolare menzione ad Arkadi Nemirovski e Kishan Baheti.

🎯 Obiettivi di Apprendimento

1. Definire i componenti di un problema di ottimizzazione matematica, inclusa la funzione obiettivo, i vincoli e le variabili.
2. Distinguere tra problemi di minimi quadrati, programmazione lineare e ottimizzazione convessa in base alle loro proprietà matematiche.
3. Confrontare strategie di ottimizzazione locale e globale e valutare la complessità computazionale associata a ciascuna.
4. Definire e distinguere insiemi affini, insiemi convessi e coni utilizzando notazioni formali di combinazione.
5. Identificare e rappresentare insiemi convessi standard come sfere euclidee, ellissoidi, poliedri e il cono semidefinito positivo.
6. Applicare operazioni che preservano la convessità, come intersezione, trasformazioni affini e funzioni prospettiche, per verificare le proprietà degli insiemi.
7. Identificare e applicare operazioni che preservano la convessità, incluse la suprema puntiforme di funzioni affini e le regole di composizione vettoriale.
8. Derivare il coniugato di Lagrange di diverse funzioni e applicare la disuguaglianza di Young.
9. Caratterizzare la quasiconvessità utilizzando insiemi di sottolivello e condizioni differenziali del primo e secondo ordine.
10. Formulare e Trasformare: Convertire problemi di ottimizzazione grezzi in forme convessi standard utilizzando variabili ausiliarie e eliminazione di vincoli.

🔹 Lezione 1: Introduzione all'Ottimizzazione Matematica

Panoramica: Questa lezione introduce i concetti fondamentali dell'ottimizzazione matematica, passando dalla formulazione generale del problema a classi specifiche risolvibili come minimi quadrati e programmazione lineare. Sottolinea la distinzione critica tra ottimizzazione convessa e non convessa, spiegando come i metodi convessi fungano da "linea di demarcazione" affidabile per l'efficienza e forniscano strumenti essenziali per affrontare problemi non lineari più difficili.

Risultati dell'Apprendimento:

• Definire i componenti di un problema di ottimizzazione matematica, inclusa la funzione obiettivo, i vincoli e le variabili.
• Distinguere tra problemi di minimi quadrati, programmazione lineare e ottimizzazione convessa in base alle loro proprietà matematiche.
• Confrontare strategie di ottimizzazione locale e globale e valutare la complessità computazionale associata a ciascuna.

🔹 Lezione 2: Teoria degli Insiemi Convessi

Panoramica: Questa lezione esplora la geometria fondamentale dell'ottimizzazione, passando dalle strutture lineari di base alle proprietà complesse degli insiemi convessi e dei coni. Copre le definizioni matematiche di insiemi affini e convessi, esamina geometrie specifiche come poliedri e coni semidefiniti positivi, e dettaglia le operazioni e i teoremi che consentono ai ricercatori di caratterizzare e manipolare insiemi convessi nello spazio ad alta dimensione.

Risultati dell'Apprendimento:

• Definire e distinguere tra insiemi affini, insiemi convessi e coni utilizzando notazioni formali di combinazione.
• Identificare e rappresentare insiemi convessi standard come sfere euclidee, ellissoidi, poliedri e il cono semidefinito positivo.
• Applicare operazioni che preservano la convessità, come intersezione, trasformazioni affini e funzioni prospettiche, per verificare le proprietà degli insiemi.

🔹 Lezione 3: Funzioni Convessi e Proprietà

Panoramica: Questa lezione esplora operazioni avanzate che preservano la convessità, come la suprema puntiforme e regole specifiche di composizione, e introduce la funzione coniugata di Lagrange. Estende il concetto di convessità a funzioni quasiconvesse e log-convesse, esaminando anche la convessità rispetto a disuguaglianze generalizzate e proprietà matriciali specifiche come il complemento di Schur. Questi concetti costituiscono la base matematica per identificare e formulare problemi di ottimizzazione complessi.

Risultati dell'Apprendimento:

• Identificare e applicare operazioni che preservano la convessità, incluse la suprema puntiforme di funzioni affini e le regole di composizione vettoriale.
• Derivare il coniugato di Lagrange di diverse funzioni e applicare la disuguaglianza di Young.
• Caratterizzare la quasiconvessità utilizzando insiemi di sottolivello e condizioni differenziali del primo e secondo ordine.

🔹 Lezione 4: Formulazione del Problema di Ottimizzazione Convessa

Panoramica: Questa lezione copre la struttura formale e la trasformazione dei problemi di ottimizzazione convessa, che vanno dalle forme standard e condizioni di ottimalità a classi specifiche di problemi come Programmazione Lineare (LP), Quadratica (QP) e Programmazione Semidefinita (SDP). Gli studenti impareranno a identificare l'ottimalità globale, utilizzare il metodo della bisezione per problemi quasiconvessi e applicare la scalarizzazione per l'ottimizzazione multi-criterio vettoriale.

Risultati dell'Apprendimento:

• Formulare e Trasformare: Convertire problemi di ottimizzazione grezzi in forme convessi standard utilizzando variabili ausiliarie e eliminazione di vincoli.
• Analizzare l'ottimalità: Applicare il criterio di ottimalità basato sul gradiente per determinare se un punto è globalmente ottimo.
• Classificare e Risolvere: Distinguere tra LP, QP, SOCP, GP e SDP, e applicare metodi specializzati come il Metodo della Bisezione per funzioni quasiconvesse.

🔹 Lezione 5: Dualità di Lagrange e Condizioni KKT

Panoramica: Questa lezione esplora la teoria fondamentale della dualità di Lagrange, passando dalla definizione della funzione duale di Lagrange alla formulazione del problema duale. Copre il gap critico tra i valori ottimali primale e duale, le interpretazioni geometriche e gioco-teoriche di queste relazioni, e le condizioni Karush-Kuhn-Tucker (KKT) che caratterizzano le soluzioni ottimali. Infine, la lezione estende questi concetti all'analisi di sensibilità e ai prezzi ombra.

Risultati dell'Apprendimento:

• Derivare la funzione duale di Lagrange e formulare il problema duale per diversi problemi di ottimizzazione.
• Valutare il rapporto tra problemi primale e duale utilizzando dualità debole e forte, e la condizione di qualificazione di Slater.
• Applicare le condizioni di ottimalità KKT per risolvere e verificare soluzioni ottimali per problemi convessi e non convessi.

🔹 Lezione 6: Approssimazione, Adattamento e Regolarizzazione

Panoramica: Questa lezione esplora le basi matematiche e le applicazioni pratiche dell'approssimazione di soluzioni a sistemi di equazioni lineari e dell'adattamento di funzioni ai dati. Copre l'approssimazione basata su norme, inclusi funzioni di penalità e regolarizzazione per gestire outlier e sparsità, e tecniche di ottimizzazione robusta per affrontare l'incertezza nei dati. Inoltre, dettaglia l'adattamento di funzioni sotto vincoli specifici come convessità e monotonia.

Risultati dell'Apprendimento:

• Formulare e risolvere problemi di approssimazione basati su norme e interpretare le differenze geometriche e statistiche tra approcci dei minimi quadrati, di Chebyshev e L1.
• Progettare e implementare modelli di approssimazione regolarizzata per ottenere compromessi tra errore residuo, magnitudine della soluzione e sparsità.
• Costruire framework di approssimazione robusta per tener conto delle incertezze nella matrice dei dati.

🔹 Lezione 7: Stima Statistica e Inference

Panoramica: Questa lezione esplora l'intersezione tra inferenza statistica e ottimizzazione convessa. Si concentra sulla formulazione di problemi di stima — inclusi massima verosimiglianza, stima non parametrica della distribuzione e progettazione ottimale di rivelatori — come programmi convessi. Gli studenti impareranno a utilizzare l'ottimizzazione per trovare parametri e progettare esperimenti informativi.

Risultati dell'Apprendimento:

• Formulare e risolvere problemi di Massima Verosimiglianza (MLE) e regressione logistica come compiti di ottimizzazione convessa.
• Progettare rivelatori ottimali usando la Programmazione Lineare (LP) e interpretare le curve ROC (Receiver Operating Characteristics).
• Applicare tecniche di stima non parametrica, incluse entropia massima e minimizzazione della divergenza di Kullback-Leibler.

🔹 Lezione 8: Problemi Geometrici e Classificazione

Panoramica: Questa lezione esplora l'applicazione dell'ottimizzazione convessa a problemi geometrici, inclusi la proiezione di punti su insiemi, il calcolo delle distanze tra insiemi e la caratterizzazione dei centri degli insiemi. Estende ulteriormente questi principi geometrici a compiti reali come classificazione lineare e non lineare, posizionamento ottimale di impianti e piani di pavimento tramite programmazione geometrica.

Risultati dell'Apprendimento:

• Formulare e risolvere problemi di proiezione e distanza tra insiemi convessi utilizzando le condizioni KKT e rappresentazioni duali.
• Approssimare insiemi convessi complessi usando ellissoidi di volume estremo e identificare i loro fattori di efficienza.
• Calcolare vari centri di insiemi e applicarli alla discriminazione e classificazione robusta.

🔹 Lezione 9: Algoritmi di Minimizzazione Senza Vincoli

Panoramica: Questa lezione copre le basi teoriche e le implementazioni algoritmiche della minimizzazione senza vincoli per funzioni convessi. Dettaglia metodi di discesa che vanno dal Gradient Descent del primo ordine al metodo di Newton del secondo ordine. Una parte significativa è dedicata all'analisi della convergenza, focalizzandosi sulla convessità forte e sulla teoria affine-invariante della self-concordance.

Risultati dell'Apprendimento:

• Definire la convessità forte e utilizzare le sue implicazioni per fornire limiti superiori sulla subottimalità e sulla distanza dall'ottimizzatore.
• Confrontare e contrapporre Gradient Descent con Steepest Descent sotto norme Euclidee, quadratiche e L1.
• Calcolare lo step di Newton e il decremento di Newton, spiegando perché il metodo di Newton è affine-invariante.

🔹 Lezione 10: Minimizzazione con Vincoli di Uguaglianza

Panoramica: Questa lezione esplora metodi per risolvere problemi di ottimizzazione convessa con vincoli lineari di uguaglianza. Si concentra sulla derivazione e implementazione dello step di Newton, confrontando metodi con partenza ammissibile e inammissibile, e interpretando questi passi all'interno di un quadro primale-duale. Un'enfasi particolare è posta sull'implementazione numerica efficiente tramite eliminazione a blocchi del sistema KKT.

Risultati dell'Apprendimento:

• Calcolare e interpretare lo step di Newton e il decremento per problemi con vincoli di uguaglianza.
• Dimostrare l'equivalenza tra il metodo di Newton con vincoli di uguaglianza e l'eliminazione di tali vincoli.
• Implementare il metodo di Newton con partenza inammissibile e spiegare la sua proprietà di riduzione del residuo primale-duale.

🔹 Lezione 11: Metodi dei Punti Interni

Panoramica: Questa lezione copre i metodi dei punti interni, che risolvono problemi di ottimizzazione convessa con vincoli di disuguaglianza applicando il metodo di Newton a una sequenza di problemi con vincoli di uguaglianza. Il nucleo riguarda le funzioni barriere logaritmiche, tracciamento di una via centrale verso la soluzione ottimale e utilizzo di framework primale-duale per aumentare efficienza e robustezza.

Risultati dell'Apprendimento:

• Definire e costruire funzioni barriere logaritmiche e caratterizzare la via centrale e i suoi punti duali associati.
• Implementare il metodo barriera, includendo il trade-off tra passi di centratura e iterazioni esterne.
• Formulare e risolvere problemi di fase I per trovare punti iniziali strettamente ammissibili.