Benvenuto alla pagina del corso di Ottimizzazione. 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 e alle disequazioni variazionali con attenzione alle applicazioni nel campo dell'addestramento di reti neurali e SVM (Support Vector Machine) e alla teoria dei giochi.
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. Dimostrazione della Proposizione 5.2 solo per la lode). 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).
Ottimizzazione non vincolata: addestramento di reti neurali (vedere le slides delle lezioni).
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 delle Proposizioni 7, 8, 9, 10 e 11, Appendice A).
Disequazioni Variazionali: dalle dispense del Prof. Facchinei i capitoli: 1.1-1.2-1.3-1.4- 1.5 tranne paragrafo 1.3.2, Proposizione 1.5.8, dimostrazione di Proposizione 1.5.12, dimostrazione 1.5.13- 1.6 tranne seconda parte dimostrazioni di 1.6.2, 1.6.3 (dimostrare solo che e'una funzione di complementarita'), tranne dimostrazioni di Teoremi 1.6.4, 1.6.5, 1.6.8-1.7 fino a pagina 60 esclusa dimostrazione di Teorema 1.7.5 e l'algoritmo di proiezione sull'iperpiano.
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ì 29/09/14.
Introduzione al corso di Ottimizzazione: esempi di problemi di decisione (Slide della lezione).
2. martedì 30/09/14.
Approccio modellistico ed esempi. Definizioni di punto di minimo locale e punto di minimo globale.
3. giovedì 2/10/14.
Caso convesso: definizioni di insieme e funzione convessi. Proposizione 1.1 del libro di testo. Convessità e differenziabilità. Criteri per verificare se una matrice è definita (criterio di Sylvester) o semidefinita positiva (criterio dei minori principali). Esempio di funzioni convesse. Esercizi.
4. venerdì 3/10/14.
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.
5. lunedì 6/10/14.
Prima lezione su AMPL: introduzione al linguaggio ed esempio di file .mod e .dat.6. martedì 7/10/14.
Condizioni di ottimalità per ottimizzazione non vincolata. Esempi di funzioni coercive e soluzione grafica di problemi di ottimizzazione7. giovedì 9/10/14.
Condizioni necessarie del primo e secondo ordine (con dimostrazione). Condizioni sufficienti (senza dimostrazione). Esempi.8. venerdì 10/10/14.
Caso convesso: condizioni di ottimalità globale. Caso particolare: funzione quadratica. Esempi.
9. lunedì 13/10/14.
AMPL: esempi di dichiarazioni di parametri a una o più dimensione. Modello di programmazione lineare.
10. martedì 14/10/14.
Introduzione agli algoritmi. Struttura e convergenza. Esempi di sequenze non convergenti a punti stazionari.
11. giovedì 16/10/14.
Rapidità di convergenza. Convergenza di metodi con ricerche unidimensionali: Proposizione 4.1 con dimostrazione.
12. venerdì 17/10/14.
Condizione d'angolo ed esempi di direzioni che la soddisfano. Esempi. Linesearch esatta. Caso quadratico strettamente convesso. Esempi.
13. lunedì 20/10/14.
AMPL: esempi e utilizzo dell'insieme di numeri naturali.
14. martedì 21/10/14.
Ricerca di linea inesatta: concetti generali. Ricerca di linea di Armijo: finitezza e proprietà di convergenza.
15. giovedì 23/10/14.
Armijo nel caso quadratico: relazioni con ricerca di linea esatta. Esempi.
12. venerdì 24/10/14.
Metodo del gradiente. Convergenza. Esempi.
13. lunedì 27/10/14.
AMPL: esempio di script. Comandi di lettura e scrittura da/su file.
14. martedì 28/10/14.
lezione cancellata
15. giovedì 30/10/14.
Metodo di Newton. Convergenza locale. Esempi. Modifiche globalmente convergenti del metodo di Newton.
16. venerdì 31/10/14.
Panoramica sull'ottimizzazione non vincolata (lezione tenuta dal prof. Sciandrone).
17. lunedì 3/11/14.
Script AMPL: algoritmo monotonic basin hopping per cluster di Lennard Jones. Prima parte.
18. martedì 4/11/14.
Script AMPL: algoritmo monotonic basin hopping per cluster di Lennard Jones. Seconda parte.
19. giovedì 6/11/14.
Introduzione alle reti neurali. Problemi di data mining: classificazione supervisionata e non supervisionata, regressione. Esempi. Concetti base per le reti neurali. Neurone formale. Slide della lezione
20. venerdì 7/11/14.
Perceptron e suo addestramento. Reti multistrato: capacità di approssimazione. Scelta dell'architettura: stabilizzazione strutturale e tecniche di regolarizzazione. Early stopping. Addestramento batch e online.
21. martedì 11/11/14.
Esercitazione svolta dall' Ing. Marco Senatore
22. giovedì 13/11/14.
Esercitazione svolta dall' Ing. Marco Senatore
23. lunedì 17/11/14.
Funzioni di Base Radiali. Reti RBF regolarizzate e reti RBF generalizzate. Addestramento tramite tecniche di decomposizione: scelta non supervisionata dei centri e supervisionata dei pesi o scelta supervisionata di pesi e centri
24. martedì 18/11/14.
Introduzione all'ottimizzazione vincolata. Condizioni necessarie di Fritz John. Regolarità dei vincoli: indipendenza lineare dei gradienti dei vincoli di uguaglianza e dei vincoli attivi.
25. giovedì 20/11/14.
Condizioni di KKT. Caso convesso. Esempi.
26. venerdì 21/11/14.
Condizioni di KKT per problemi strutturati: vincoli di non negatività, vincoli di box, vincoli lineari, programmazione quadratica, programmazione lineare. Esempi.
27. lunedì 24/11/14.
Condizioni di ottimo per problemi con insieme convesso. Direzioni ammissibili, condizioni necessarie di ottimo. Esempi.
28. martedì 25/11/14.
Esempi di condizioni per problemi con vincoli strutturati: ortante non negativo e simplesso. Proiezione su un insieme convesso: proprietà ed esempi. Proiezione sull'ortante non negativo e su vincoli di box. Condizione necessaria basata sulla proiezione. Esempi.
29. giovedì 27/11/14.
Linesearch di Armijo per problemi con insieme ammissibile convesso. Metodo di Frank Wolfe e dimostrazione di convergenza. Esempi.
30. venerdì 28/11/14.
Metodo del gradiente proiettato e dimostrazione di convergenza. Esempi. Cenni sull'ottimizzazione vincolata per problemi generali.
31. lunedì 1/12/14.
Risultato di Vapnik. Minimizzazione del rischio strutturale: SVM e reti neurali. SVM lineari: iperpiano con gap di tolleranza ottimo.
32. martedì 2/12/14.
Iperpiano ottimo nel caso di insiemi linearmente separabili: intuizione.
33. giovedì 4/12/14.
Definizione del problema: duale di Wolfe nel caso generale.
34. venerdì 5/12/14.
Duale di Wolfe nel caso quadratico. Esempi. Caratterizzazione della distanza da un iperpiano.
35. lunedì 8/12/14.
Applicazione del duale di Wolfe al problema di SVM lineari. Calcolo dell'iperpiano ottimo.'
36. martedì 9/12/14.
Caso non linearmente separabile. Duale di Wolfe e proprietà.
37. giovedì 11/12/14.
Caso non lineare. Funzioni kernel.
38. venerdì 12/12/14.
Condizioni di ottimo per il problema quadratico risolto da SVMlight.
39. lunedì 15/12/14.
WEKA: istallazione e introduzione. Explorer ed esempi di problemi di classificazione.
40. martedì 16/12/14.
WEKA: ambiente Experimenter ed esempi di utilizzo avanzato.41. giovedì 18/12/14.
SVM light: scelta del working set e criterio di arresto. Esercizi.42. venerdì 19/12/14.
WEKA: strumenti avanzati e problemi di regressione.
43. giovedì 08/01/15.
Lezione su algoritmi di ottimizzazione globale per il progetto AMPL.
44. venerdì 09/01/15.
Introduzione alle disequazioni variazionali. Problemi di complementarità ed equivalenza con le VI. Problemi di complementarità mista.
45. lunedì 12/01/15.
Esempi di problemi di complementarità e complementarità mista. Condizioni di KKT per VI.
46. martedì 13/01/15.
Esercizi sulle condizioni di KKT per VI. Riformulazione come problema di punto fisso e teorema di esistenza. Esempi.
47. giovedì 15/01/15.
Giochi di Nash: equivalenza con VI e teorema di esistenza. Gioco di Nash- Cournot. Esempi.
48. venerdì 16/01/15.
Esercizi su giochi di Nash. Cenni su giochi di Nash generalizzati. Esempio di applicazione.
49. lunedì 19/01/15.
Funzioni monotone, strettamente monotone e fortemente monotone. Caratterizzazione degli insiemi di soluzioni per VI con funzioni monotone, strettamente monotone e fortemente monotone. Esempi.
50. martedì 20/01/15.
Funzioni di complementarità: funzione minimo, classe di mangasarian, funzione di Fischer-Burmeister. Rifromulazione di un NCP come sistema di equazioni e proprietà. Cenni sulla riformulazione di una VI come sistema di equazioni.
51. giovedì 22/01/15.
Teorema di Banach. Algoritmo di proiezione di base e proprietà di convergenza.
52. venerdì 23/01/15.
Esercizi su VI e giochi di Nash.
53. lunedì 26/01/15.
Esercizi di riepilogo.
54. martedì 27/01/15.
Simulazione di esame e correzione (il testo con soluzione si trova qui).
55. giovedì 29/01/15.
Ricevimento collettivo.