Benvenuto alla pagina del corso di Metodi di Ottimizzazione per Big Data. Il corso è destinato agli studenti del primo anno dei Corsi di Laurea Magistrale in Ingegneria Gestionale, Ingegneria Informatica e Ingegneria dell'Automazione.
Consulta questa pagina per ottenere informazioni aggiornate sui seguenti argomenti:
Per ogni richiesta o dubbio scrivi a: veronica.piccialli@uniroma2.it .
Bacheca
Qui sono riportati gli avvisi e le informazioni più urgenti.
Orario delle lezioni
Semestre: I
Orari:
Ricevimento
lunedì ore 10:30 - 11:30 (stanza D2-10, Edifici Ingegneria dell'Informazione.) Per il ricevimento è necessario prenotarsi inviando un mail all'indirizzo veronica.piccialli@uniroma2.it
Obiettivi e Prerequisiti del corso
Il corso vale 12 crediti.
Obiettivi. L'obiettivo del corso è quello di introdurre all'ottimizzazione non vincolata e vincolata con attenzione alle applicazioni nel campo dell'addestramento di reti neurali, SVM (Support Vector Machine) e tecniche di clustering.
Prerequisiti. è raccomandabile aver seguito i moduli di Analisi Matematica 1 e 2, di Geometria 1, e di Ricerca Operativa.
Programma del corso
Introduzione all'ottimizzazione: approccio modellistico
Problemi di ottimizzazione: classificazione
Problemi di Programmazione Matematica: condizioni di esistenza della soluzione (capitolo 1 del libro di testo escluso Paragrafi 1.5.3, 1.5.5 e 1.5.6).
Ottimizzazione non vincolata: condizioni di ottimo (Capitolo 2 escluso dimostrazioni delle Proposizioni 2.6 e 2.7 ), algoritmi di soluzione: condizioni di convergenza globale (Capitolo 3 solo 3.1, 3.3 fino a pagina 65 inclusa, 3.4 fino a pagina 70 inclusa (solo Q convergenza) e 3.5), Convergenza di metodi con ricerche unidimensionali (Capitolo 4 fino a pagina 80), Ricerca unidimensionale (Capitolo 5 fino a pagina 99 inclusa esclusa la dimostrazione della Proposizione 5.2). Metodo del gradiente(Capitolo 6 fino a pagina 161 escluse le dimostrazioni delle Proposizioni 6.2, 6.3,6.5, 6.6). Metodo di Newton (Capitolo 7 : 7.1, 7.2 esclusa dimostrazione delle Proposizioni 7.1 e 7.2, 7.4.1). Metodi di decomposizione: introduzione, algoritmi sequenziali e paralleli. Metodo di Gauss Seidel, metodo di Gauss Soutwell, metodo di discesa a blocchi, cenni su decomposizione con sovrapposizione dei blocchi. Metodo di Jacobi (Capitolo 16 :16.1, 16.2, 16.3.1, Proposizioni 16.3, 16.4, 16.6 senza dimostrazioni, 16.3.3, 16.4 senza dimostrazioni, 16.5 senza dimostrazioni, 16.7 senza dimostrazioni ).
Ottimizzazione non vincolata: addestramento di reti neurali (vedere le slides delle lezioni). Dimostrazione di convergenza dell'algoritmo del perceptron.
Ottimizzazione vincolata: Ottimizzazione vincolata: condizioni di ottimo e algoritmi di soluzione (Capitolo 17: 17.1, 17.2, 17.3 (esclusa la dimostrazione della 17 Proposizione.13), 17.4, 17.5). Condizioni di ottimo analitiche: condizioni di Fritz John, qualificazione dei vincoli (solo indipendenza lineare gradienti vincoli di eguaglianza e vincoli attivi) (Appendice D: D.1 esclusa dimostrazione Teorema D.1, D.2 solo (a) e Teorema D.2, D.3, D.4, D.5.2, D.5.3).
Duale di Wolfe e SVM: dispense del prof. Sciandrone: tutto tranne dimostrazione del Teorema 1, Lemma 1, dimostrazione del Lemma 2, dimostrazione della Proposizione 1, dimostrazione della Proposizione 2, dimostrazione di Proposizione 5 e Proposizione 6, paragrafo 5, dimostrazioni della Proposizione 10, Appendice A).
Testo adottato e altro materiale
Testi d'esame
Modalità d'esame
Date d'esame
Link utili
Questi link contengono dispense, esercizi, software freeware, curiosità relativi al mondo della ricerca operativa.
Agenda del corso
1. lunedì 3/10/16.
Introduzione al corso: esempi di problemi di decisione (Slide della lezione).
2. martedì 4/10/16.
Approccio modellistico ed esempi.
3. giovedì 6/10/16.
Definizioni di punto di minimo locale e punto di minimo globale. Caso convesso: definizioni di insieme e funzione convessi. Proposizione 1.1 del libro di testo.
4. venerdì 7/10/16.
Convessità e differenziabilità. Criteri per verificare se una matrice è definita (criterio di Sylvester) o semidefinita positiva (criterio dei minori principali). Esempi.
5. lunedì 10/10/16.
Esempio di funzioni convesse. Esercizi. Condizioni sufficienti di esistenza: teorema di Weierstrass (senza dimostrazione).Insiemi di livello inferiori di una funzione, coercività. Esempi di funzioni coercive. Condizioni sufficienti di esistenza basate sulla coercività della funzione obiettivo. Esempi.6. martedì 11/10/16.
Ottimizzazione non vincolata: condizioni necessarie del primo e secondo ordine (con dimostrazione). Condizioni sufficienti (senza dimostrazione). Esempi.7. giovedì 13/10/16.
Ottimizzazione non vincolata: caso convesso e caso quadratico (con dimostrazione). Esempi.8. venerdì 14/10/16.
Riepilogo su condizioni di ottimalità. Esercizi.9. lunedì 17/10/16.
Introduzione agli algoritmi. Struttura e convergenza. Esempi di sequenze non convergenti a punti stazionari.
10. martedì 18/10/16.
Proposizione 4.1 con dimostrazione. Condizione d'angolo.
11. giovedì 20/10/16.
Esempi di direzioni che soddisfano la condizione d'angolo. Linesearch esatta. Caso quadratico strettamente convesso. Esempi.
12. venerdì 21/10/16.
Prima lezione su AMPL: introduzione al linguaggio ed esempio di file .mod.
13. lunedì 24/10/16.
Ricerca di linea inesatta: concetti generali. Ricerca di linea di Armijo: finitezza e proprietà di convergenza (senza dimostrazione).
14. giovedì 27/10/16.
Dimostrazione della convergenza della ricerca di linea di Armijo. Esempi.
15. venerdì 28/10/16.
AMPL: separazione tra modello e dati: esempio di file .mod e .dat. Esempi e utilizzo dell'insieme di numeri naturali: problema dell'assegnamento.16. giovedì 03/11/16.
Metodo del gradiente. Convergenza. Esempi.
17. venerdì 04/11/16.
AMPL: dichiarazione di parametri indicizzati su insiemi (vettori e matrici) Esempio di PL.18. lunedì 07/11/16.
Metodo del gradiente a passo costante. Metodo Heavy Ball. Rapidità di convergenza.
19. martedì 08/11/16.
Metodo di Newton. Proprietà di convergenza. Modifiche globalmenti convergenti.
20. giovedì 09/11/16.
Panoramica sull'ottimizzazione non vincolata. Esempi in matlab21. venerdì 10/11/16.
AMPL: esempio di PL e problema del poligono di massima area. Introduzione agli script22. lunedì 14/11/16.
Introduzione alle reti neurali (svolta dall'Ing Chiara Liti).
23. martedì 15/11/16.
Perceptron. Addestramento e dimostrazione di convergenza (svolta dall'Ing Chiara Liti).
24. giovedì 17/11/16.
Reti multistrato (svolta dall'Ing Chiara Liti). Addestramento e costruzione dell'architettura.'25. venerdì 18/11/16.
WEKA: Istallazione e introduzione al suo utilizzo (svolta dall'Ing Chiara Liti).26. lunedì 21/11/16.
Introduzione ai metodi di decomposizione. Decomposizione in blocchi. Algoritmi sequenziali e paralleli. Esempi.27. martedì 22/11/16.
Metodi di Gauss Seidel, Gauss Seidel con proximal point, GS in due blocchi con modifica. Metodo di Gauss Southwell, metodo di discesa a blocchi, metodo di Jacobi, cenni sui metodi con sovrapposizione di blocchi (senza dimostrazioni).28. giovedì 24/11/16.
Esercizi sui metodi di decomposizione29. venerdì 25/11/16.
Algoritmi di minimizzazione non vincolata in pratica. Modello del volley. Lezione svolta da Ing. Alessandro Calligari e Ing. Guido Cocchi30. lunedì 28/11/16.
Reti RBF regolarizzate. Reti RBF generalizzate. Proprietà.31. martedì 29/11/16.
WEKA. Preprocessing e Multilayer Perceptron. (Svolta dall'Ing. Chiara Liti)32. giovedì 01/12/16.
Introduzione all'ottimizzazione vincolata. Direzioni ammissibili, condizioni di ottimo necessarie.33. venerdì 02/12/16.
Script AMPL: istruzione printf, ciclo for, ciclo while, if then else. Variabile solve_result_num per il controllo dell'output dei solutori. Esempio di script per il problema del poligono di massima area.34. lunedì 05/12/16.
Condizioni di ottimo per problemi con insieme convesso. Direzioni ammissibili, condizioni necessarie di ottimo. Esempi di condizioni per problemi con vincoli strutturati: vincoli di box35. lunedì 12/12/16.
Operatore di Proiezione e sue proprietà. Esempi di Proiezione: vincoli di non negatività e vincoli di box.36. martedì 13/12/16.
WEKA. RBF classifier e introduzione a LibSVM (svolta dall'Ing. Chiara Liti).37. giovedì 15/12/16.
Algoritmo di Frank Wolfe e convergenza. Metodo del Gradiente Proiettato e convergenza. Esempi.38. venerdì 16/12/16.
AMPL. Algoritmo Monotonic Basin Hopping.39. lunedì 19/12/16.
AMPL. Problema del Packing. Miglioramento dello script di MBH.40. martedì 20/12/16.
WEKA. SVM e feature selection (svolta dall'Ing. Chiara Liti).41. lunedì 09/01/17.
Condizioni di Fritz John.42. martedì 10/01/17.
Condizioni di KKT. Caso convesso, dimostrazione di sufficienza.43. giovedì 11/01/17.
Risultato di Vapnik. Minimizzazione del rischio strutturale: SVM e reti neurali. SVM lineari: iperpiano con gap di tolleranza ottimo. .Caratterizzazione della distanza da un iperpiano.44. venerdì 12/01/17.
Duale di Wolfe nel caso generale e nel caso quadratico.45. lunedì 16/01/17.
SVM lineari.46. martedì 17/01/17.
SVM non lineari. Funzioni Kernel.47. giovedì 19/01/17.
Esercitazione su ottimizzazione vincolata (svolta dall'Ing. Chiara Liti).48. venerdì 20/01/17.
WEKA: esempio di processamento di un dataset.49. lunedì 23/01/17.
Condizioni di ottimo per il problema dell'addestramento di SVM light.50. martedì 24/01/17.
SVM light: scelta del Working Set convergenza, criterio di arresto51. giovedì 26/01/17.
Esercitazione riepilogativa su tutto il programma52. venerdì 27/01/17.
Simulazione di esam.