Benvenuto alla pagina del corso di Ottimizzazione. Il corso è destinato agli studenti del primo anno dei Corsi di Laurea Magistrale in Ingegneria Gestionale e Ingegneria dell'Automazione.
Consulta questa pagina per ottenere informazioni aggiornate sui seguenti argomenti:
Per ogni richiesta o dubbio scrivi a: piccialli@disp.uniroma2.it .
Bacheca
Qui sono riportati gli avvisi e le informazioni più urgenti.
Orario delle lezioni
Semestre: I
Orari:
Ricevimento
mercoledì ore 10:30 - 11:30 (stanza D2-10, Edifici Ingegneria dell'Informazione.) Per il ricevimento è necessario prenotarsi inviando un mail all'indirizzo piccialli@disp.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 di massima del corso (sarà dettagliato durante il 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). Cenni sui metodi Quasi Newton (Capitolo 10: paragrafo 10.1). Metodo delle direzioni coniugate nel caso quadratico strettamente convesso (Capitolo 8: 8.1, 8.2 esclusa Proposizione 8.3 esclusa dimostrazione Proposizione 8.5 e paragrafi 8.3.1, 8.3.3 da pagina 222 alla fine e 8.3.4 (leggere solo l'idea), 8.4 solo fino a pagina 232). Metodo trust region (Capitolo 9: 9.1,9.2 esclusa la Proposizione 9.1, 9.4.1, 9.4.2).
Ottimizzazione non vincolata: addestramento di reti neurali (vedi slides).
Ottimizzazione vincolata: caso convesso e cenni sul caso non convesso. Algoritmi di soluzione (Capitolo 17: 17.1, 17.2, 17.3 (esclusa la dimostrazione della 17 Proposizione.13), 17.4, 17.5)
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, dimostrazione Proposizione 10, dimostrazione Proposizione 11, Appendice A).
Disequazioni Variazionali: dalle dispense del Prof. Facchinei i capitoli: 1.1-1.2-1.3-1.4- 1.5 tranne 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'), 1.6.4, 1.6.5, 1.6.8-1.7 fino a pagina 60 escluso 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ì 1/10/12.
Introduzione al corso di Ottimizzazione: esempi di problemi di decisione.
2. martedì 2/10/12.
Richiami e notazione (concetto di norma, norma euclidea, distanze, sfera aperta e sfera chiusa, differenziabilità in forma forte del primo e secondo ordine). 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. Convessità e differenziabilità.
3. mercoledì 3/10/12.
Criteri per verificare se una matrice è definita (criterio di Sylvester) o semidefinita positiva (criterio dei minori principali). Esempio di funzioni convesse. Esercizi.
4. lunedì 8/10/12.
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. martedì 9/10/12.
Condizioni di ottimalità per ottimizzazione non vincolata. Condizioni necessarie del primo e secondo ordine (con dimostrazione). Condizioni sufficienti (senza dimostrazione). Esempi.
6. mercoledì 10/10/12.
Caso convesso: condizioni di ottimalità globale. Caso particolare: funzione quadratica. Esempi.
7. lunedì 15/10/12.
Introduzione agli algoritmi. Struttura e convergenza. Esempi di sequenze non convergenti a punti stazionari.
8. martedì 16/10/12.
Convergenza di metodi con ricerche unidimensionali: Proposizione 4.1 con dimostrazione. Condizione d'angolo ed esempi di direzioni che la soddisfano. Esempi.
9. mercoledì 17/10/12.
Linesearch esatta. Caso quadratico strettamente convesso. Esempi. Regressione lineare come caso particolare di minimi quadrati lineari.
10. lunedì 22/10/12.
Ricerca di linea inesatta: concetti generali. Ricerca di linea di Armijo: finitezza e proprietà di convergenza.
11. martedì 23/10/12.
Armijo nel caso quadratico: relazioni con ricerca di linea esatta. Esempi.
12. mercoledì 24/10/12.
Metodo del gradiente: convergenza globale. Velocità di convergenza. Esempi.
13. lunedì 29/10/12.
Metodo di Newton per sistemi di equazioni. Metodo di Newton per problemi di ottimizzazione non vincolata. Proprietà di convergenza locale. Globalizzazione del metodo di Newton: metodi tipo Newton (cenni). Metodi Quasi Newton: l'idea.
14. martedì 30/10/12.
Metodo delle direzioni coniugate nel caso quadratico strettamente convesso: definizioni e convergenza finita. Metodo del gradiente coniugato per il caso quadratico strettamente convesso. Esempi.
15. mercoledì 31/10/12.
Metodo del gradiente coniugato per problemi di minimi quadrati lineari. Cenni sul metodo del gradiente coniugato nel caso generale. Esempi.
16. lunedì 5/11/12.
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
17. martedì 6/11/12.
Perceptron e suo addestramento. Dimostrazione di convergenza. Reti multistrato: capacità di approssimazione. Scelta dell'architettura: stabilizzazione strutturale e tecniche di regolarizzazione. Early stopping. Addestramento batch e online. Slide della lezione
18. lunedì 12/11/12.
Funzioni di Base Radiali. Reti RBF regolarizzate e reti RBF generalizzate. Addestramento tramite tecniche di decomposizione: scelta non supervsionata dei centri e supervisionata dei pesi o scelta supervisionata di pesi e centri
19. martedì 13/11/12.
Relazione tra Ottimizzazione e Apprendimento Automatico. Alcune applicazioni (lezione tenuta dal Prof. Sciandrone).
20. mercoledì 14/11/12.
Introduzione all'ottimizzazione vincolata. Condizioni necessarie di Fritz John. Regolarità dei vincoli: indipendenza lineare dei gradienti dei vincoli di uguaglianza e dei vincoli attivi. Condizioni di KKT. Esempi.
21. lunedì 19/11/12.
Condizioni di KKT per problemi strutturati: vincoli di non negatività, vincoli di box, vincoli lineari, programmazione quadratica, programmazione lineare. Esempi.
22. martedì 20/11/12.
Metodi di tipo trust region: introduzione e definizioni. Passo di Cauchy.
23. lunedì 26/11/12.
Esercitazione svolta dall' Ing. Marco Senatore
24. martedì 27/11/12.
Condizioni di ottimo globale per il sottoproblema della trust region (con dimostrazione). Esempi.
25. mercoledì 28/11/12.
Lezione di riepilogo sull'ottimizzazione non vincolata svolta dal Prof. Marco Sciandrone
26. lunedì 03/12/12.
Introduzione all'ottimizzazione vincolata su insiemi convessi. Direzioni ammissibili, condizioni necessarie di ottimo.
27. martedì 04/12/12.
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.
28. mercoledì 05/12/12.
Linesearch di Armijo per problemi con insieme ammissibile convesso. Metodo di Frank Wolfe e metodo del gradiente proiettato. Esempi.
29. lunedì 10/12/12.
Convergenza del metodo del gradiente proiettato. Cenni sull'ottimizzazione vincolata per problemi generali. Duale di WOlfe: caso generale. Esempi.
30. martedì 11/12/12.
Duale di Wolfe nel caso quadratico. Esempi. Caratterizzazione della distanza da un iperpiano. Iperpiano ottimo nel caso di insiemi linearmente separabili: intuizione.
31. mercoledì 12/12/12.
Risultato di Vapnik. Minimizzazione del rischio strutturale: SVM e reti neurali. SVM lineari: iperpiano con gap di tolleranza ottimo. Definizione del problema: duale di Wolfe.
32. lunedì 17/12/12.
Caso non linearmente separabile. Duale di Wolfe e proprietà. Condizioni di ottimo per il problema.
33. martedì 18/12/12.
SVM non lineari: funzioni kernel. Introduzione a SVM light: scelta del working set.
34. mercoledì 19/12/12.
SVM light arresto e convergenza. Introduzione al software WEKA. (le slides sono consultabili a questo link)
35. lunedì 7/1/13.
Riepilogo SVMlight. Esempi. Introduzione alle disequazioni variazionali (VI): definizione di soluzione. Esempi.
36. martedì 8/1/13.
Problema di complementarità: definizione ed equivalenza con VI. Problema di complementarità non lineare. Problema di complementarità mista. Condizioni di KKT per una VI.
37. mercoledì 9/1/13.
Esempio di applicazione: problemi di equilibrio di traffico a cura del Prof. Marco Sciandrone.
38. lunedì 14/1/13.
Riformulazione della VI come problema di punto fisso. Teorema di esistenza. Equivalenza con i giochi di Nash. Esempi di giochi di Nash (Nash-Cournot) e di problemi di equilibrio (Walras).
39. martedì 15/1/13.
Funzioni monotone, strettamente monotone e fortemente monotone. Caratterizzazione degli insiemi di soluzioni per VI con funzioni monotone, strettamente monotone e fortemente monotone. Esempi40. mercoledì 16/1/13.
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.41. lunedì 21/1/13.
Teorema di Banach. Algoritmo di proiezione di base e proprietà di convergenza.
42. martedì 22/1/13.
Esercizi su VI e giochi di Nash.
43. mercoledì 23/1/13.
Esercitazione tenuta dall'ing. Marco Senatore.
44. lunedì 28/1/13.
Simulazione di esame.