Metodi di Ottimizzazione per Big Data (MOBD)

A.A. 2017-2018



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 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:

  1. lunedì ore 9:30-11:00 in Aula C6 (Nuovo Complesso della didattica);
  2. mercoledì ore 11:30-13:15 in Aula C12 (Nuovo Complesso della didattica);
  3. giovedì ore 11:30-13:15 in Aula B6 (Nuovo Complesso della didattica);
  4. venerdì ore 11:30-13:15 in Aula B9 (Nuovo Complesso della didattica);

Ricevimento

lunedì ore 11:30 - 12: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, deep learning, e 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 di massima del corso


Introduzione all'ottimizzazione: approccio modellistico

Problemi di ottimizzazione: classificazione

Problemi di Programmazione Matematica: condizioni di esistenza della soluzione

Ottimizzazione non vincolata: condizioni di ottimo, algoritmi di soluzione: condizioni di convergenza globale, ricerca di linea, metodo del gradiente, cenni sul metodo di Newton. Metodi di decomposizione.

Ottimizzazione non vincolata: addestramento di reti neurali. Deep Learning

Ottimizzazione vincolata: condizioni di ottimo e algoritmi di soluzione

Duale di Wolfe e SVM


Testo adottato e altro materiale

  1. Luigi Grippo, Marco Sciandrone, Metodi di Ottimizzazione Non Vincolata, Springer, Unitext 2011. Errata Corrige
  2. Marco Sciandrone, Support Vector Machines. Errata Corrige
  3. Luigi Grippo, Marco Sciandrone, Metodi di ottimizzazione per le reti neurali.
  4. 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.


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ì 25/09/17.

    Introduzione al corso: esempi di problemi di decisione (Slide della lezione).

    2. mercoledì 26/09/17.

    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.

    3. giovedì 28/09/17.

    Convessità e differenziabilità. Criteri per verificare se una matrice è definita (criterio di Sylvester) o semidefinita positiva (criterio dei minori principali). Esempi.

    4. venerdì 29/09/17.

    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.

    5. lunedì 2/10/17.

    Ottimizzazione non vincolata: condizioni necessarie del primo e secondo ordine (con dimostrazione). Condizioni sufficienti (senza dimostrazione). Caso convesso. Esempi.

    6. mercoledì 4/10/17.

    Ottimizzazione non vincolata: caso quadratico (con dimostrazione). Esempi. Introduzione agli algoritmi.

    7. giovedì 5/10/17.

    Struttura e convergenza di algoritmi. Esempi di sequenze non convergenti a punti stazionari.

    8. venerdì 06/10/17.

    AMPL: introduzione al linguaggio. Esempio di file .mod e .dat.

    9. lunedì 09/10/17.

    Proposizione 4.1 con dimostrazione. Condizione d'angolo. Esempi di direzioni che soddisfano la condizione d'angolo. Linesearch esatta. Caso quadratico strettamente convesso.

    10. mercoledì 11/10/17.

    Ricerca di linea inesatta: concetti generali. Ricerca di linea di Armijo: finitezza e proprietà di convergenza (senza dimostrazione).

    11. giovedì 12/10/17.

    Metodo del gradiente. Convergenza. Metodo del gradiente a passo costante. Metodo Heavy Ball. Rapidità di convergenza. Esempi in matlab.

    12. venerdì 13/10/17.

    AMPL: esempi e utilizzo dell'insieme di numeri naturali: problema dell'assegnamento.

    13. lunedì 16/10/17.

    Metodo di Newton. Proprietà di convergenza. Modifiche globalmenti convergenti. Cenni su quasi Newton.

    14. mercoledì 18/10/17.

    Introduzione ai metodi di decomposizione. Decomposizione in blocchi. Algoritmi sequenziali e paralleli. Metodi di Gauss Seidel, Gauss Seidel con proximal point. Esempi.

    15. giovedì 19/10/17.

    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). Esempi.

    16. venerdì 20/10/17.

    AMPL: dichiarazione di parametri indicizzati su insiemi (vettori e matrici) Esempio di PL.

    17. lunedì 23/10/17.

    Introduzione alle reti neurali. (Slide della lezione)

    18. mercoledì 25/10/17.

    Perceptron. Addestramento e dimostrazione di convergenza.

    19. giovedì 26/10/17.

    Reti multistrato. Addestramento e costruzione dell'architettura.(Slide delle lezioni 18 e 19)

    20. venerdì 27/10/17.

    AMPL: esempio di PL e problema del poligono di massima area. Introduzione agli script. Esempio di script per il problema del poligono di massima area.

    21. lunedì 30/10/17.

    Reti RBF regolarizzate. Reti RBF generalizzate. Proprietà e Addestramento (Slide della lezione).

    22. giovedì 02/11/17.

    Condizioni di ottimo per problemi con insieme convesso. Direzioni ammissibili, condizioni necessarie di ottimo. Esempi di condizioni per problemi con vincoli strutturati: vincoli di box

    22. venerdì 03/11/17.

    Esercitazione su ottimizzazione non vincolata e decomposizione.

    23. lunedì 06/11/17.

    Operatore di Proiezione e sue proprietà. Esempi di Proiezione: vincoli di non negatività e vincoli di box. Riformulazione della condizione di stazionarietà tramite proiezione.

    24. mercoledì 08/11/17.

    Metodo di Frank Wolfe e metodo del gradiente proiettato (senza dimostrazione di convergenza). Esempi.

    25. giovedì 09/11/17.

    Esercizi su ottimizzazione vincolata.

    26. venerdì 10/11/17.

    Condizioni di Fritz John. Qualificazione dei vincoli. Indipendenza lineare dei vincoli attivi.

    27. lunedì 13/11/17.

    Condizioni di KKT. Sufficienza nel caso convesso.

    28. mercoledì 15/11/17.

    Esercitazione su condizioni di ottimo.

    29. giovedì 16/11/17.

    Risultato di Vapnik. Minimizzazione del rischio strutturale: SVM e reti neurali. Iperpiano con gap di tolleranza ottimo. Caratterizzazione della distanza da un iperpiano.

    30. venerdì 17/11/17.

    AMPL: script per l'addestramento di una rete MLP, prima parte.

    31. lunedì 20/11/17.

    AMPL: script per l'addestramento di una rete MLP, seconda parte.

    32. giovedì 23/11/17.

    AMPL: script per l'addestramento di una rete MLP, terza parte. Introduzione al duale di Wolfe.

    33. venerdì 24/11/17.

    Teoria della dualità di Wolfe. Caso generale e caso quadratico. Esempi.

    34. lunedì 27/11/17.

    Seminario dell'Ing. Chiara Liti: Introduction to Neural Networks.

    35. mercoledì 29/11/17.

    SVM lineari per insiemi linearmente separabili e non linearmente separabili.

    36. giovedì 30/11/17.

    SVM non lineari. Funzioni kernel. Esempi.

    37. venerdì 1/12/17.

    Introduzione ad R: sintassi di base, vettori, matrici, liste e dataframe

    38. lunedì 4/12/17.

    Le funzioni in R, loops, condizioni if-else e le funzioni della famiglia apply

    39. mercoledì 6/12/17.

    SVM lineari per insiemi linearmente separabili e non linearmente separabili.

    40. giovedì 7/12/17.

    Prime fasi del CRISP-DM e esempio di data preparation in R

    41. lunedì 11/12/17.

    Seminario Andrea Pomente : Convolutional Neural Networks

    42. mercoledì 13/12/17.

    Features Selection: trasformazione di una variabile nominale in numerica, introduzione alla features selection, scelta del subset (metodi best-first, esponenziali, sequenziali e randomizzati), valutazione del subset (filtri, wrapper, metodi embedded), esempio: Relief-ReliefF, il package CORELearn (esempio ReliefF in R).

    43. giovedì 14/12/17.

    Condizioni di ottimo per il problema duale di addestramento di una SVM