Metodi di Ottimizzazione per Big Data
!! Questa pagina si riferisce a un passato A.A. 2021-22 !!
Dall'A.A. 2022-23 il titolare del corso è il prof. Andrea Cristofari
A.A. 2021-22 per i CdS LM in Ingegneria Informatica (cod. 8039833); ICT and Internet Engineering (Optimization Methods for Big data, cod. 80300002) e Matematica Pura e Applicata (cod. 8067458).
Programma di massima del corso
Approccio modellistico e ottimizzazione. Classificazione dei problemi di ottimizzazione e condizioni di esistenza di una soluzione. Ottimizzazione non vincolata: condizioni di ottimo, algoritmi di soluzione e condizioni di convergenza globale, ricerca di linea, cenni sul metodo del gradiente. Metodi di decomposizione. Ottimizzazione vincolata: condizioni di ottimo e algoritmi di soluzione. Duale di Wolfe e Support Vector Machines. Clustering non supervisionato: formulazione e algoritmo k-means batch e on line. Alberi di decisione per la Classificazione. Classificazione robusta.
Software
NEW! Puoi scaricare AMPL qui (la licenza scade il 30/09/2022, informatemi quando/se vi serve rinnovarla). Per installarlo, segui le indicazioni che trovi in questa pagina.
Testi e dispense di riferimento
Luigi Grippo, Marco Sciandrone, Metodi di Ottimizzazione Non Vincolata, Springer, Unitext 2011. Errata Corrige.
Marco Sciandrone, Support Vector Machines. Errata Corrige.
Luigi Grippo, Marco Sciandrone, Metodi di ottimizzazione per le reti neurali.
I seguenti testi sono disponibili presso il mio ufficio:
a. Olvi L. Mangasarian, Nonlinear Programming, SIAM Classics in Applied Mathematics.
b. Jorge Nocedal, Stephen J. Wright, Numerical Optimization, Springer.
c. Dimitri P. Bertsekas, Convex Analysis and Optimization, Athena Scientific.
d. Dimitri P. Bertsekas, Nonlinear Programming, Athena Scientific.
e. J.E. Dennis, Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM Classics in Applied Mathematics.
Invitiamo gli studenti a prendere anche visione del materiale (note e riferimenti) sul link Microsoft Teams del corso.
Agenda del corso
Qui di seguito riportiamo gli argomenti trattati nelle singole lezioni.
1. mer 2/3/22 Introduzione al corso. Administrivia. Esempi di problemi di decisione. Approccio modellistico ed esempi.
2. gio 3/3/22 Definizioni di punto di minimo locale e punto di minimo globale. Caso convesso: definizioni di insieme e funzione convessi.
3. lun 7/3/22 Ottimizzazione convessa: insiemi convessi, funzioni convesse, gradiente, hessiana, derivata direzionale, sviluppo di Taylor del 1o e 2o ordine (per funzioni di più variabili).
4. mer 9/3/22 Caratterizzazioni di funzioni convesse (del I e II ordine). Matrici semi-definite positive e negative. Minori, minori principali e minori principali di NW. C.S. di (semi-)definitezza positiva per matrici simmetriche.
5. gio 10/3/22 Esempi ed esercizi. Insiemi aperti, chiusi, illimitati, compatti. Esistenza di minimi globali. Teor. di Weierstrass. Insiemi di livello. Funzioni coercive.
6. lun 14/3/22 Funzioni quadratiche. Condizioni di convessità e coercività di funzioni quadratiche. Esempi.
7. mer 16/3/22 Lezione cancellata (per evento in memoriam Prof. Mario Lucertini).
8. gio 17/3/22 Condizioni di ottimo locale. Direzioni di discesa. Caso convesso. Direzioni a curvatura negativa.
9. lun 21/3/22 Ancora sulle condizioni necessarie (del I e II ordine) di ottimo locale e sul caso convesso. Punti stazionari. Regione ammissibile poliedrale.
10. mer 23/3/22 Condizioni di ottimo locale nel caso di "box constraints". Condizioni analitiche di ottimo: condizioni necessarie di Fritz-John. Condizioni di regolarità.
11. gio 24/3/22 Condizioni suff. di regolarità: LICQ, Slater, Mangasarian-Fromovitz, h lineari+g concave. Condizioni di Karush-Kuhn-Tucker. Esempi.
12. lun 28/3/22 Esercizi: applicazione delle condizioni di FJ e KKT.
13. mer 30/3/22 Condizioni nec. e suff. di Karush-Kuhn-Tucker di ottimo globale nel caso convesso. Esempi.
14. gio 31/3/22 Problemi di apprendimento statistico (supervised e unsupervised learning, classificazione, regressione). Cenni di teoria statistica dell'apprendimento: Rischio effettivo ed empirico. Bound di Vapnik-Chervonenkis. VC-confidence.
15. lun 4/4/22 VC-dimension. Iperpiani orientati e bound sulla loro VC-dimension. Rischio strutturale di una macchina di apprendimento e prototipo di procedimento euristico per la sua minimizzazione.
16. mer 6/4/22 Fenomeni di overfitting e underfitting. Iperpiani con gap di tolleranza e bound sulla loro VC-dimension. Iperpiano ottimo.
17. gio 7/4/22 Introduzione ad AMPL a cura della dott.ssa C. Salvatore.
18. lun 11/4/22 Caso separabile: Equivalenza del problema di determinare l'iperpiano ottimo con il problema quadratico min ||w||^2
19. mer 13/4/22 Esercizi (determinazione di un iperpiano ottimo, distanza punto iperpiano).
20. gio 14/4/22 Duale di Wolfe. Applicazione alla PL. Problema di ottimizzazione quadratica e suo duale di Wolfe.
21. mer 20/4/22 KKT per il duale. Programmazione quadratica per SVM lineari (caso separabile).
22. gio 21/4/22 SVM lineari: caso non separabile (primale con var di slack e duale).
23. mer 27/4/22 SVM non lineari. Funzioni kernel.
24. gio 28/4/22 Esempi di funzioni kernel. Algoritmo di decomposizione per l'addestramento di una SVM.
25. lun 2/5/22 Condizioni di ottimalità per il problema di addestramento di una SVM.
26. mer 4/5/22 Ancora sulle condizioni di ottimalità per il problema di addestramento di una SVM.
27. gio 5/5/22 Algoritmo SVM light.
28. lun 9/5/22 Clustering. Misure di dissimilarità. Formulazione del problema di ottimizzazione.
29. mer 11/5/22 Decomposizione del problema: soluzione fissati i centroidi e fissati i cluster: Algoritmo k-means (versione batch)
30. gio 12/5/22 Algoritmo k-means (versione batch): criterio di arresto. Criteri per determinare il numero di cluster ottimale (Silhouette, Elbow method)
31. lun 16/5/22 Alberi di decisione per la classificazione. Il modello OCT-MIO: struttura dell'albero
32. mer 18/5/22 Il modello OCT-MIO: classificazione dei punti del TS e funzione obiettivo
33. gio 19/5/22 Addestramento di OCT-MIO: warm start, definizione del problema Pb(C) e individuazione del fattore di complessità
34. lun 23/5/22 Algoritmi TDIDT (Top-Down-Induction Decision Trees) e algoritmo di Hunt per la costruzione di un albero di decisione. Indici di impurità per la selezione dei test (Misclassification, Gini Index, Entropia).
–. mer 25/5/22 Lezione cancellata
35. gio 26/5/22 Esercitazione su preprocessing e analisi dati (a cura della dott.ssa Salvatore)
36. lun 30/5/22 Alberi di decisione per la classificazione (e la regressione): bagging, errore "OOB", Random Forests. Estensione del di OCT al caso multivariato: Modello OCT-H (hyperplane)
37. mer 1/6/22 Ancora sul modello OCT-H. Ottimizzazione robusta: uncertainty set, approccio minmax.
38. lun 6/6/22 Robust classification trees.
39. mer 8/6/22 Robust classification trees.
36. gio 9/6/22 Esercitazione. Assegnazione progetti (a cura della dott.ssa C. Salvatore). Fine del corso.