Metodi Numerici ed Ottimizzazione
a.a. 2010/2011
Il corso si propone di presentare alcune delle principali metodologie e tecniche relative alla soluzione di problemi numerici. Tali metodologie richiedono l'utilizzo, spesso in combinazione tra loro, di tecniche dell'analisi numerica e di algoritmi di ottimizzazione. Verranno illustrati alcuni dei principali casi in cui i metodi di ottimizzazione trovano applicazione nella risoluzione di problemi di analisi numerica e, viceversa, le tecniche di analisi numerica risultano fondamentali per la soluzione di problemi di ottimizzazione. Le metodologie introdotte saranno illustrate mediante l'applicazione ad alcuni specifici problemi selezionati, ad esempio, nei seguenti ambiti: regressione e stima di parametri in statistica, approssimazione e data fitting, machine learning, data mining, ricostruzioni di immagini e segnali, equilibri economici e problemi finanziari.
PROGRAMMA DEL CORSO
(per un programma più dettagliato consultare il registro delle lezioni)
- Richiami di topologia e calcolo differenziale
- Insiemi aperti, chiusi, limitati e compatti nello spazio euclideo
- Successioni e limiti nello spazio euclideo
- Funzioni di più variabili: continuità, derivate direzionali, differenziabilità
- Funzioni di più variabili: formule di Taylor del primo e del secondo ordine
- Richiami di algebra lineare
- Matrici normali, unitarie, hermitiane, definite positive, riducibili
- Polinomio minimo, diagonalizzabilità, forme canoniche di Jordan e di Schur
- Forme quadratiche
- Teorema di Gerschgorin per matrici irriducibili
- Norme matriciali indotte
- Funzioni, insiemi convessi e problemi di ottimizzazione
- Funzioni convesse, strettamente convesse, insiemi convessi: proprietà e caratterizzazioni
- Classificazione dei problemi di ottimizzazione; minimi [e massimi] locali e globali
- Proprietà dei problemi di ottimizzazione convessa
- Condizioni di ottimalità per l'ottimizzazione non vincolata
- Condizioni necessarie di ottimalità del primo e del secondo ordine
- Condizioni sufficienti di ottimalità; il caso convesso
- Metodi diretti ed iterativi per sistemi lineari
- Fattorizzazioni di matrici e matrici elementari
- Fattorizzazioni LU, QR e LL^H, metodi di Gauss, Householder e Cholesky
- Convergenza di metodi iterativi
- Teorema di Stein-Rosenberg
- Risultati per matrici tridiagonali e definite positive
- Il metodo del gradiente coniugato per sistemi lineari
- Metodi iterativi per sistemi non lineari
- Generalità e condizioni di convergenza.
- Metodo di Newton-Raphson e convergenza per funzioni convesse
- Metodi risolutivi per l'ottimizzazione non vincolata
- I metodi del gradiente con ricerca esatta ed inesatta
- Il metodo di Newton
- Il metodo del gradiente coniugato
- Metodi senza derivate: gli algoritmi di ricerca a compasso
- Il problema dei minimi quadrati
- Il problema lineare e le equazioni normali
- Il metodo QR, la decomposizione ai valori singolari ed il relativo metodo
- Risoluzione delle equazioni normali tramite il metodo del gradiente coniugato
- Il problema nonlineare ed il metodo di Gauss-Newton
- Metodi iterativi per il calcolo di autovalori
- Teorema di Bauer-Fike
- Il metodo delle potenze
- Riduzione a forma tridiagonale
- Matrici tridiagonali e successioni di Sturm
- Il metodo QR e la sua convergenza
- Condizioni di ottimalità per l'ottimizzazione vincolata
- Condizione necessarie di ottimalità con vincolo insiemistico
- Condizioni necessarie di Fritz John e di Karush-Kuhn-Tucker: i moltiplicatori di Lagrange
- Condizioni necessarie e sufficienti nel caso di vincoli convessi
- Metodi risolutivi per l'ottimizzazione vincolata
- I metodi delle direzioni ammissibili; il metodo di Frank-Wolfe
- Proiezioni su un insieme convesso ed il metodo del gradiente proiettato
- Eliminazione di variabili: il caso dei vincoli lineari
- Metodi di penalizzazione: penalizzazione esterna e Lagrangiana aumentata
- Metodi barriera; metodi primali-duali del punto interno per programmazione lineare
- La trasformata discreta di Fourier
- La matrice di Fourier e le sue proprietà
- L'algoritmo e alcune applicazioni numeriche