Numerical Analysis and Optimization

06 Feb 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Descrizione del corso. Prerequisiti. Ripasso di nozioni di base di algebra lineare. Norme su uno spazio vettoriale. Equivalenza di norme nel caso di dimensione finita. Norme matriciali. Nozione di problema ben posto. Condizionamento.

08 Feb 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

La decomposizione ai valori singolari (SVD) e la determinazione del rango numerico di una matrice. Proprieta` di ottimalita` della SVD. Lemma di Banach. Condizionamento di un matrice rispetto all'inversione. Teoria delle perturbazioni per sistemi lineari. Esempi. La nozione di algoritmo "backward stable".

13 Feb 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Condizionamento e distanza dalla singolarita`. Stima dell'errore relativo nella soluzione di un sistema lineare in termini di backward error e condizionamento del problema. Soluzione di sistemi triangolari. La fattorizzazione LU (condizioni di esistenza e unicita`). Esempio: il Laplaciano discreto e sue proprieta`.

15 Feb 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Numeri di macchina e aritmetica in precisione finita. Stabilita` degli algoritmi di risoluzione dei sistemi triangolari inferiori e superiori. Stabilita` della fattorizzazione LU. Metodo del pivoting parziale. Fattore di crescita. Matrice di Wilkinson. Fattorizzazione LU e matrici elementari di Gauss.

20 Feb 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Analisi dell'errore nel metodo di eliminazione Gaussiana con la tecnica del pivoting parziale. Classi di matrici per le quali non e` necessaria la tecnica del pivoting. Fattorizzazione di Cholesky. Introduzione al problema dei minimi quadrati. Le equazioni normali.

22 Feb 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

La pseudoinversa di Moore-Penrose. Condizioni di Penrose. Uso della pseudoinversa per il calcolo della soluzione di minima norma del problema dei minimi quadrati. Trasformazioni di Householder e primi cenni alla fattorizzazione QR.

06 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Costruzione e proprieta` delle trasformazioni di Householder. Fattorizzazione QR con il metodo di Householder e soluzione del problema dei minimi quadrati. La fattorizzazione QR con scambi di colonna. Rotazioni di Givens. Confronto tra i vari metodi. Condizionamento del problema di minimi quadrati.

13 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Ripasso di nozioni fondamentali relative agli autovalori, autovettori, e autospazi di matrici. Matrici simili. Caratterizzazione delle matrici diagonalizzabili. Similitudine unitaria. Matrici normali e diagonalizzabilita` unitaria. La forma canonica di Schur e il Teorema Spettrale. Caratterizzazione variazionale (di Rayleigh-Ritz) degli autovalori di matrici Hermitiane.

15 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Teorema di Courant-Fischer e Teorema di Weyl. Elementi di teoria delle perturbazioni per autovalori. Malcondizionamento degli autovettori corrispondenti ad autovalori molto vicini. Introduzione ai metodi numerici per autovalori e autovettori. Riduzione alla forma di Hessenberg (o tridiagonale) mediante trasformazioni di similitudine col metodo di Householder. Il caso riducibile.

20 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Il metodo QR per il calcolo di autovalori di matrici generiche e di matrici reali simmetriche. Tecniche di shift. Convergenza, costo computazionale e stabilita` numerica. Il metodo di Jacobi per matrici simmetriche. Convergenza nel caso classico. Parallelizzazione del metodo di Jacobi.

22 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Il metodo delle potenze. Metodo delle potenze inverse, metodo shift-and-invert, e metodo dell'iterazione inversa. Cenni sui metodi di Krylov. Metodo di Lanczos.

27 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Introduzione alla Teoria dell'Ottimizzazione. Classificazione dei problemi di ottimizzazione. Punti critici; punti di minimo, di massimo, di sella. Metodi di discesa. Tasso di convergenza (lineare, superlineare, quadratica). Metodo del gradiente, metodo della piu` ripida discesa, scelta della lunghezza del passo (line search method). Il caso quadratico. Condizioni sufficienti per la convergenza del metodo del gradiente.

29 Mar 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Principali limiti dei metodi di tipo gradiente. Il metodo di Newton. Invarianza di scala e convergenza asintoticamente quadratica. Differenziazione numerica. Bilanciamento degli errori di toncamento e di arrotondamento. Il metodo dei gradienti coniugati (CG) e il suo uso all'interno del metodo di Newton inesatto. Criteri di arresto dell'iterazione CG.

19 Apr 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

I metodi Quasi-Newtoniani: SR1, SR2, DFP, BFGS e L-BFGS.

24 Apr 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Tecniche di globalizzazione: condizioni di Wolfe I-II; backtracking. interpolazione. Metodo della regione di confidenza ("Trust region methods"). Risultati di convergenza (solo enunciato). Metodi omotopici ("Davidenko path method"). Teorema di Watson (solo enunciato). Cenno sul metodo differenziale.

26 Apr 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

I metodi del gradiente come discretizzazione del flusso gradiente col metodo di Eulero esplicito. Il metodo "heavy ball" di Polyak e il metodo AD di Nesterov di accelerazione della discesa. Proprieta` di convergenza e interpretazione differenziale di Boyd/Su/Candes. Il metodo di Eulero implicito per il flusso gradiente. Relazione col metodo di Newton (inesatto). Ottimizzazione vincolata: moltiplicatori di Lagrange. Sistemi punto sella associati alla minimizzazione quadratica con vincoli lineari di uguaglianza.

03 Maggio 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - In presenza

Esempi di problemi di punto sella legati alla programmazione quadratica con vincoli lineari. Le condizioni di ottimalita` di Karush-Kuhn-Tucker (KKT). Esempio: programmazione lineare. Dualita`, Teorema di Mini-Max di von Neumann e relazione con la Teoria dei Giochi.

08 Maggio 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Metodo del gradiente proiettato per la minimizzazione di funzioni con vincoli di nonnegativita` o di tipo "box constraints". I metodi di punto interno per la minimizzazione vincolata: barriera logaritmica, metodo di Newton inesatto per le condizioni KKT, metodi di riduzione (complemento di Schur).

15 Maggio 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Il metodo di Uzawa per la minimizzazione vincolata. Esempi. Problemi di ottimizzazione nella scienza dei dati: Basis Pursuit e LASSO. Decomposizione duale per problemi separabili. Il metodo della Lagrangiana aumentata. Metodo dei moltiplicatori (Hestenes).

17 Maggio 2023 (2h 00m)

Michele Benzi - Corso (attività didattica) - Mista

Il metodo ADMM (Alternating Direction Method of Multipliers). Applicazione del metodo ADMM ai problemi di tipo Basis Pursuit, LASSO, programmazione vincolata convessa, programmazione lineare. L'operatore di "soft tresholding" (o "shrinkage") e il suo uso nel metodo ADMM.