Numerical Analysis and Optimization

09 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Presentazione del corso. Richiami di algebra lineare.

11 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Norme matriciali. Equivalenza di norme in dimensione finita. Basi ortonormali, trasformazioni unitarie, diagonalizzazione mediante trasformazioni unitarie, Teorema spettrale, riduzione unitaria a forma triangolare (decomposizione di Schur), decomposizione ai valori singolari (SVD).

16 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Proprieta` della SVD. SVD troncata e Teorema di Eckart-Young. Determinazione del rango numerico di una matrice. I numeri di macchina. Fattore di amplificazione dell'errore per le operazioni aritmetiche su numeri finiti. Cancellazione catastrofica.

18 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Stabilita` numerica e condizionamento di problemi matematici. Il numero di condizionamento di una matrice. Esempi (Laplaciano discreto, matrice di Hilbert). Variazione nella soluzione di un sistema lineare in presenza di perturbazioni sui dati. La fattorizzazione LU. Soluzione di sistemi triangolari.

23 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Fattorizzazione LU con scambi di riga (partial pivoting). Stabilita` numerica della fattorizzazione LU. Fattore di crescita. Matrice di Wilkinson.

25 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Stime sull'errore backward e forward nella soluzione di sitemi lineari mediante fattorizzazione LU con pivoting parziale. Cenni sulla risoluzione numerica di sistemi con matrice sparsa o a banda. Matrice inversa (e come evitarla). La fattorizzazione di Cholesky. Sistemi rettangolari e introduzione al metodo dei minimi quadrati.

30 Nov 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Minimi quadrati: equazioni normali di Gauss e metodo di Cholesky. Soluzione del problema dei minimi quadrati con la SVD. Pseudoinvesa di Moore-Penrose. La fattorizzazione QR. Soluzione del problema dei minimi quadrati con la fattorizzazione QR. Trasformazioni di Householder.

02 Dic 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Soluzione del problema di minimi quadrati con il metodo di Householder. Stabilita` numerica e costo computazionale. Fattorizzazione QR con scambi di colonna. Il metodo delle rotazioni piane di Givens. Confronto tra i vari metodi. Sensibilita` della soluzione del problema di minimi quadrati rispetto a perturbazioni nei dati. Primi cenni sul problema agli autovalori.

07 Dic 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Teoremi di Rayleigh-Ritz, Courant-Fischer, Weyl e Hoffman-Wielandt. Condizionamento del problema agli autovalori. Condizionamento degli autovettori di matrici Hermitiane. Introduzione ai metodi per il calcolo degli autovalori. Riduzione a forma di Hessenberg superiore mediante trasformazioni di similitudine unitarie (metodo di Householder).

09 Dic 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Il metodo QR per il calcolo degli autovalori. Tecniche di shift. Stabilita` del metodo QR. Il problema del calcolo di autovalori molto piccoli. Il metodo di Jacobi per matrici reali simmetriche.

14 Dic 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Il metodo delle potenze e delle potenze inverse. Tecniche "shift-and-invert". Cenni sui metodi di Krylov. Il metodo di Lanczos per matrici Hermitiane.

16 Dic 2021 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Ottimizzazione numerica: classiifcazione dei problemi ed esempi. Punti critici. Metodi di discesa. Metodo del gradiente (gradient descent). Line search. Risultati sulla convergenza nel caso quadratico. Primi cenni sul metodo di Newton. Il flusso gradiente.

11 Gen 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Risultati sulla convergenza del metodo del gradiente (solo enunciati). Tecnica del backtracking. Non-invarianza di scala del metodo del gradiente. Il metodo di Newton. Principali proprieta`. Introduzione ai metodi Quasi-Newtoniani. Derivazione del metodo SR1.

13 Gen 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

I metodi di Davidon-Fletcher-Powell (SR2), BFGS, e L-BFGS. Approssimazione del gradiente e della matrice Hessiana mediante differenze finite. Scelta del passo h ottimale. Il metodo di Newton inesatto. Il metodo dei gradienti coniugati.

18 Gen 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Il metodo dei gradienti coniugati precondizionato e il suo uso nel metodo di Newton inesatto. Tecniche di globalizzazione per il metodo di Newton: regole per la scelta della steplength (Wolfe I-II), metodo delle regioni di confidenza (trust region method).

20 Gen 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Risultati sulla convergenza dell'algoritmo di Newton con il metodo delle regioni di confidenza. Cenni sui metodi di tipo "path-following" (omotopia). Accelerazione dei metodi di tipo grdiente: Metodo Heavy Ball (Polyak), Accelerated Gradient Descent (Nesterov). Convergenza del metodo di Nesterov. Interpretazione in termini di sistema dinamico (oscillatore nonlineare smorzato). Metodo di Eulero implicito per il flusso gradiente. Introduzione all'ottimizzazione vincolata (moltiplicatori di Lagrange).

25 Gen 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Problemi di minimo vincolato con vincoli di uguaglianza: problemi di punto sella. Vincoli di disuguaglianza. Vincoli attivi. Esempi. Condizioni di Karush-Kuhn-Tucker (KKT). Condizione di qualificazione dei vincoli. Le condizioni KKT per problemi di programmazione lineare.

27 Gen 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Dualita` in Programmazione Lineare. Programmazione Lineare e Teoria dei Giochi. Condizioni KKT per il problema di Programmazione Quadratica. Metodo del gradiente proiettato. Barriera logaritmica e metodi di punto interno.

01 Feb 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Implementazione dei metodi di punto interno. Il metodo di Uzawa per problemi quadratici con vincoli lineari di uguaglianza. Problemi di ottimizzazione nella Scienza dei Dati: soluzioni sparse di sistemi sottodeterminati (Basis Pursuit). LASSO. Metodo di Uzawa per problemi separabili. Lagrangiana aumentata e Metodo dei Moltiplicatori (MM).

03 Feb 2022 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Convergenza del metodo dei moltiplicatori per problemi quadratici con vincoli linear di uguaglianza. Il metodo ADMM (Alternating Direction Method of Multipliers) e il metodo Scaled ADMM. Esempi.