REGISTRO DELLE LEZIONI DI
OTTIMIZZAZIONE
CORSO DI LAUREA MAGISTRALE IN MATEMATICA
8 CFU - A.A. 2017/2018
DOCENTE: PROF. GIUSEPPE RODRIGUEZ
ULTIMO AGGIORNAMENTO: 16. marzo 2021

1.          Martedì 6/03/2018, 9-11.         ore: 2(2)

Introduzione al corso. Problemi di migliore approssimazione. Riassunto di alcuni argomenti: problemi ben posti, prodotti scalari, norme vettoriali e matriciali, condizionamento, aritmetica di macchina, cancellazione, metodi diretti (fattorizzazione $PA=LU$) per sistemi lineari, Matlab.

2.          Giovedì 8/03/2018, 9-11.         ore: 2(4)

Metodi iterativi per sistemi lineari. Vantaggi e svantaggi rispetto ai metodi diretti. Interpolazione polinomiale e approssimazione di dati affetti da errori sperimentali. Formulazione del problema ai minimi quadrati e del problema algebrico corrispondente. Approssimazione ai minimi quadrati mediante una somma di esponenziali. Esempio: decadimento di un materiale radioattivo. Cenni sui problemi nonlineari. Interpretazioni alternative del prodotto matriciale. BLAS livello 1, 2 e 3. Inner e outer products.

3.          Martedì 13/03/2018, 9-11.         ore: 2(6)

Inner products e outer products: corrispondenti interpretazioni dei prodotti vettore-vettore, matrice-vettore e matrice-matrice. Esempi. Calcolo dell'inversa. Prodotti matriciali a blocchi. I prodotti di Hadamard e di Kronecker. Autovalori e autovettori. Diagonalizzabilità. Il caso particolare delle matrici Hermitiane: il teorema spettrale. Matrici ortogonali. Matrice di adiacenza associata ad un grafo.

4.          Mercoledì 14/03/2018, 9-11.         ore: 2(8)

Laboratorio Matlab. Creazione e manipolazione di matrici. Calcolo matriciale e vettoriale. Estrazione di sottoarray. Indicizzazione con vettori di indici e con vettori logici. Grafici 2D, 3D e visualizzazione di immagini. Esempi.

5.          Giovedì 15/03/2018, 9-11.         ore: 2(10)

Fattorizzazione spettrale di una matrice Hermitiana e sua interpretazione come outer product. Approssimazione a rango basso di una matrice Hermitiana. Definizione di $\epsilon$-rango. Applicazione alla principal component analysis e all'analisi di reti complesse. Significato delle potenze della matrice di adiacenza di una rete. Sistemi lineari quadrati, sovradeterminati e sottodeterminati, a rango pieno. Interpretazione mediante il sottospazio generato dalle colonne di $A$. Conseguenze della presenza di errori nei termini noti. Rumore bianco. Sistemi lineari rettangolari: il caso a rango non pieno. Sistemi quadrati singolari. Il range (immagine) e il nucleo (spazio nullo) di una matrice, vista come operatore lineare.

6.          Martedì 20/03/2018, 9-11.         ore: 2(12)

Sistemi sovradeterminati a rango pieno: formulazione del problema ai minimi quadrati (LSP). Calcolo del gradiente di alcune funzioni vettoriali. Risoluzione di un LSP mediante il sistema delle equazioni normali. Cenni sull'algoritmo di risoluzione. Matrice pseudo-inversa. Consistenza delle equazioni normali. Risoluzione delle equazioni normali con la fattorizzazione di Cholesky. Introduzione alla fattorizzazione QR. Risoluzione di un LSP mediante la fattorizzazione QR. Caratterizzazione delle soluzioni di un LSP. Decomposizione di uno spazio come somma diretta di sottospazi ortogonali. Significato geometrico della condizione di ortogonalità.

7.          Mercoledì 21/03/2018, 9-11.         ore: 2(14)

Media e varianza di vettori di variabili aleatorie. Trasformazioni lineari tra vettori aleatori. Modello statistico lineare standard. Stimatori unbiased di minima varianza (BLUE). Teorema di Gauss-Markov. Media e varianza della soluzione dei minimi quadrati. Il metodo di Newton per la risoluzione di un sistema di equazioni nonlineari. Il metodo di Gauss-Newton per la risoluzione di un problema ai minimi quadrati nonlineare. Dimostrazioni del teorema di caratterizzazione della soluzione di un LSP.

8.          Giovedì 22/03/2018, 9-11.         ore: 2(16)

Sottoinsiemi convessi di uno spazio vettoriale. Norme strettamente convesse. Unicità della soluzione di un LSP di minima norma. Riformulazione ben-posta di un sistema sottodeterminato a rango pieno. La soluzione normale è ortogonale al nucleo di $A$. Formulazione primale e duale di un LSP. Metodo dei moltiplicatori di Lagrange. Equazioni normali del secondo tipo. Matrice pseudoinversa per un sistema sottodeterminato a rango pieno. Sperimentazione numerica in Matlab sulla risoluzione di sistemi sovradeterminati e sottodeterminati.

9.          Martedì 27/03/2018, 9-11.         ore: 2(18)

Considerazioni numeriche sul calcolo della matrice $A^TA$: vantaggi, svantaggi, algoritmi. Inerzia di una matrice, legge di Sylvester. Fattorizzazione di Cholesky: esistenza della fattorizzazione, verifica di alcuni casi particolari e formulazione generale. Implementazione dell'algoritmo per colonne e per righe. Complessità. Cenni sulla influenza dell'ordine di memorizzazione delle matrici. Applicazione alla risoluzione di un problema ai minimi quadrati. Esempi.

10.          Mercoledì 28/03/2018, 9-11.         ore: 2(20)

Introduzione alla fattorizzazione QR. Principali proprietà e applicazione alla risoluzione di un sistema lineare e di un LSP sovradeterminato. Interpretazione come algoritmo di ortogonalizzazione. Matrici elementari di Householder. Proprietà e algoritmo di costruzione. Possibili ottimizzazioni della procedura di calcolo. Algoritmo di fattorizzazione QR di Householder. Descrizione dei primi tre passi e del passo generico. Complessità. Differenze nella fattorizzazione di una matrice quadrata e di una rettangolare. Impostazione di un esercizio.

11.          Mercoledì 4/04/2018, 9-11.         ore: 2(22)

Fattorizzazione QR di una matrice mediante il metodo di ortogonalizzazione di Gram-Schmidt classico (CGS, presentazione di Marcello Cabboi). Ortogonalità e indipendenza lineare. Breakdown dell'algoritmo: rilevazione di vettori dipendenti e del rango della matrice. Fattorizzazione QR mediante il metodo di Gram-Schmidt modificato (MGS). Cenni sull'algoritmo privo di radici quadrate e sull'equivalenza di MGS con l'algoritmo di Householder applicato ad una matrice aumentata. Fattorizzazione QR completa e compatta. Connessione tra MGS e fattorizzazione di Cholesky. Cenni sulla stabilità dei metodi analizzati.

12.          Giovedì 5/04/2018, 9-11.         ore: 2(24)

Riepilogo fattorizzazione QR di Householder. Rotazioni piane. Matrici elementari di Givens. Algoritmo di fattorizzazione QR di Givens. Ottimizzazione dell'algoritmo. Indicatori numerici di performance per la fattorizzazione QR. Esempi numerici sul calcolo degli autovalori e su fenomeni di instabilità.

13.          Martedì 10/04/2018, 9-11.         ore: 2(26)

Riepilogo su autovalori e autovettori: polinomio caratteristico, calcolo di autovalori e autovettori, molteplicità algebrica e geometrica, quoziente di Rayleigh. Matrici simili. Diagonalizzabilità. Fattorizzazione spettrale. Forma canonica di Schur. Teorema spettrale come corollario al Teorema di Schur. Matrici normali. Introduzione agli algoritmi numerici. Sottoproblemi legati al calcolo degli autovalori. Teorema di Bauer-Fike. Il caso di una matrice Hermitiana. Il metodo delle potenze. Ipotesi del metodo e analisi della convergenza. Problemi numerici e normalizzazione. Criteri di stop. Mappa strutturale dell'algoritmo. Applicazione: eigenvalue centrality di una rete non orientata.

14.          Mercoledì 11/04/2018, 9-11.         ore: 2(28)

Proiezioni ortogonali su un sottospazio: definizione, unicità. Proiezioni ortogonali derivanti dal partizionamento per colonne di una matrice ortogonale. Proiettori sul range di $A$ e sul nucleo di $A^T$ espressi mediante la matrice pseudo-inversa e mediante la fattorizzazione QR di $A$. Riepilogo algoritmo MGS. Proiezioni ortogonali effettuate a ogni passo. Versione dell'algoritmo che aggiorna il termine noto $\mathbf{b}$ del sistema lineare.

15.          Giovedì 12/04/2018, 9-11.         ore: 2(30)

Discussione sul processo di pubblicazione degli articoli scientifici e la valutazione bibliometrica della qualità della ricerca, delle riviste scientifiche e degli articoli stessi. Riepilogo metodo delle potenze. Il metodo delle potenze inverse per l'approssimazione dell'autovalore di minimo modulo. Potenze inverse con shift dello spettro per il calcolo di altri autovalori, il miglioramento di una stima, la determinazione dell'autovettore associato ad un autovalore assegnato. Matrici sparse: memorizzazione ottimizzata e vantaggi computazionali. Cenni su altre strutture algebriche che consentono un calcolo veloce del prodotto matrice-vettore.

16.          Martedì 17/04/2018, 9-11.         ore: 2(32)

Laboratorio. Sperimentazione numerica sulla risoluzione di sistemi lineari al variare della dimensione. Grafici in scala semilogaritmica. Minimi quadrati: risoluzione con Cholesky e QR. Sistemi sovradeterminati compatibili e incompatibili. Costruzione di un termine noto con una componente ortogonale all'immagine della matrice e con residuo assegnato. Introduzione del noise nel termine noto. Ottimizzazione del codice relativamente all'uso della memoria.

17.          Mercoledì 18/04/2018, 9-11.         ore: 2(34)

Dimostrazione del Teorema di Bauer-Fike. Forma normale di Jordan. Blocchi e catene di Jordan. Autovettori generalizzati. Molteplicità algebrica e geometrica di un autovettore. Esempi. Formulazione del problema di migliore approssimazione in uno spazio di Hilbert. Teorema di caratterizzazione della migliore approssimazione. Sua interpretazione in ${\mathbb{R}}^3$ e in ${\mathbb{R}}^n$.

18.          Giovedì 19/04/2018, 9-11.         ore: 2(36)

Matrice compagna associata ad un polinomio monico. Calcolo delle radici del polinomio come autovalori della matrice compagna. Algoritmo QR per il calcolo degli autovalori. Invarianti per trasformazioni QR: similitudine, simmetria. Costruzione della forma di Schur e, per una matrice simmetrica, della fattorizzazione spettrale. Matrici di fase. Teorema di convergenza e rilassamento delle ipotesi. Riduzione del costo computazionale: passaggio in forma di Hessenberg e uso di trasformazioni di Givens. Accelerazione della convergenza mediante shift dello spettro.

19.          Martedì 24/04/2018, 9-11.         ore: 2(38)

Riepilogo algoritmo QR. Algoritmo per portare una matrice quadrata in forma di Hessenberg attraverso trasformazioni di similitudine. Decomposizione ai valori singolari (SVD). Forma della fattorizzazione per matrici di diverse dimensioni e a rango non pieno. Forma compatta. Vettori singolari destri e sinistri. Sistema singolare come generalizzazione di autovalori e autovettori. Decomposizione di una matrice come somma di matrici a rango uno. Approssimazioni a rango basso e principal component analysis.

20.          Giovedì 26/04/2018, 9-11.         ore: 2(40)

Riepilogo SVD. Esempi numerici sul calcolo della SVD. Legame tra la SVD e la fattorizzazione spettrale di $A^*A$ e $AA^*$. Possibile algoritmo di calcolo e sue condtroindicazioni numeriche. Identificazione mediante i vettori singolari dei quattro sottospazi fondamentali di una matrice. Proprietà di ortogonalità che li lega. Soluzione generale di un sistema omogeneo. Il caso particolare di rango $n-1$ e cenni sull'applicazione alla camera calibration.

21.          Mercoledì 2/05/2018, 9-11.         ore: 2(42)

Dimostrazione dell'esistenza della SVD (presentazione di Vincenzo Solinas). Migliore approssimazione in uno spazio di Hilbert. Sistema delle equazioni normali. Matrice di Gram. Momenti e coefficienti di Fourier. Polinomio di migliore approssimazione in $L^2[0,1]$. La matrice di Hilbert. Serie di Fourier. Importanza dell'ortogonalità delle funzioni di base.

22.          Giovedì 3/05/2018, 9-11.         ore: 2(44)

Soluzione di un sistema quadrato non singolare mediante SVD. Osservazioni sulla propagazione degli errori. Cenni sulla soluzione regolarizzata di un sistema malcondizionato mediante la TSVD. Soluzione di un problema ai minimi quadrati mediante la SVD. Rappresentazione generale della matrice pseudoinversa. Confronto con la rappresentazioni particolari ricavate nelle precedenti lezioni. Alcune proprietà della pseudoinversa. Introduzione al problema dello shape from shading della computer vision.

23.          Martedì 8/05/2018, 9-11.         ore: 2(46)

Applicazione nella computer vision: la tecnica del photometric stereo. Ricostruzione di modelli 3D a partire da immagini. La legge di Lambert: formulazione scalare e matriciale. che consente di determinare il campo normale. Discussione sul numero minimo di immagini necessarie per la risoluzione del problema. Ruolo della matrice pseudoinversa, sotto l'ipotesi che sia nota la posizione delle fonti di illuminazione. Cenni sui modelli differenziali associati al problema e sulla loro risoluzione numerica. Costruzione di fattorizzazioni a rango fissato mediante la SVD. Illustrazione di risultati sperimentali.

24.          Mercoledì 9/05/2018, 9-11.         ore: 2(48)

Momenti e coefficienti di Fourier. Importanza dell'ortogonalità delle funzioni di base. Generalità sulle formule di quadratura. Precisione algebrica, formule interpolatorie. Funzioni peso ed integrali con singolarità. Esempio: costruzione di una formula a due punti per un peso particolare. Formule a precisione ottimale. Polinomi ortogonali. Costruzione di una base di polinomi ortogonali monici mediante il metodo di Gram-Schmidt.

25.          Giovedì 10/05/2018, 9-11.         ore: 2(50)

Laboratorio. Sperimentazione sulla fattorizzazione QR. Costruzione ottimizzata di una matrice elementare di Householder. Implementazione dell'algoritmo di fattorizzazione in forma standard. Ottimizzazione successiva del programma. Verifica dell'accuratezza della fattorizzazione e osservazione del miglioramento nella complessità computazionale.

26.          Martedì 15/05/2018, 9-11.         ore: 2(52)

Relazione tra la norma-2 e la norma di Frobenius di una matrice e i suoi valori singolari. Approssimazione di una matrice mediante ls SVD troncata e espressione dell'errore di approssimazione. Teorema di Weyl e sua dimostrazione. Teorema di Courant-Fisher. Dimostrazione della stabilità dei valori singolari. Migliore approssimazione di una matrice con una matrice a rango fissato, nella norma 2 e nella norma di Frobenius. Risultati di stabilità per la pseudoinversa. Espressione del numero di condizionamento di una matrice mediante i valori singolari. Condizionamento di un problema ai minimi quadrati.

27.          Mercoledì 16/05/2018, 9-11.         ore: 2(54)

Riepilogo formule di ricorrenza per polinomi ortogonali. Proprietà dei polinomi ortogonali: radici, matrice di interpolazione. Formule di quadratura Gaussiane: calcolo di nodi e pesi. Matrice di Jacobi associata ai polinomi. Famiglie di polinomi ortogonali classici. Dimostrazione del teorema sulla precisione algebrica e l'ottimalità delle formule Gaussiane.

28.          Giovedì 17/05/2018, 9-11.         ore: 2(56)

Schema dell'algoritmo di Golub-Reinsch per il calcolo della SVD: passaggio in forma bidiagonale e applicazione implicita dell'algoritmo QR. Riepilogo sui metodi iterativi per sistemi lineari. Vantaggi rispetto ai metodi diretti. Criteri di stop. Precondizionamento e proprietà connesse. Metodi di Richardson. Fattorizzazione LU incompleta. Cenni su un'applicazione: problema ai minimi quadrati nonlineare derivante dall'inversione di dati elettromagnetici in geofisica applicata.

29.          Martedì 22/05/2018, 9-11.         ore: 2(58)

Introduzione ai metodi iterativi di massima discesa per sistemi con matrice simmetrica definita positiva. Determinazione del passo ottimale. Il metodo del gradiente. Ottimizzazione del calcolo del residuo. Test di convergenza. Algoritmo. Convergenza lenta del metodo. Implementazione del precondizionamento. Ottimalità di un punto rispetto ad una direzione. Condizione necessaria e sufficiente per l'ottimalità. Direzioni coniugate.

30.          Giovedì 24/05/2018, 9-11.         ore: 2(60)

Riepilogo metodo del gradiente, ottimalità di un punto rispetto ad una direzione, direzioni coniugate. Determinazione di direzioni coniugate a partire dal residuo. Il metodo del gradiente coniugato. Aggiornamento del residuo. Schema dell'algoritmo e ottimizzazione dei calcoli. Precondizionamento. Metodi di proiezione in spazi di Krylov. Conseguenze del breakdown del metodo. Il metodo del gradiente coniugato come metodo di Krylov. Condizione di ottimalità verificata dalla generica iterazione.

31.          Martedì 29/05/2018, 9-11.         ore: 2(62)

Laboratorio. Memorizzazione, uso e visualizzazione delle matrici sparse in Matlab. Creazione di un sistema lineare test con matrice sparsa simmetrica definita positiva. Sintassi di chiamata della funzione pcg, che implementa il metodo del gradiente coniugato. Costruzione di un precondizionatore mediante fattorizzazione di Cholesky incompleta e suo uso nella funzione pcg. Sperimentazione numerica al variare di alcuni parametri. Implementazione del metodo del gradiente coniugato.

32.          Giovedì 31/05/2018, 9-11.         ore: 2(64)

Applicazione implicita del gradiente coniugato alle equazioni normali: il metodo CGLS. Riepilogo metodi di Krylov. Decomposizione parziale di Lanczos per una matrice simmetrica. Costruzione dell'algoritmo. Possibile breakdown dell'algoritmo e cenni sulla riortogonalizzazione. Risoluzione di un sistema lineare col metodo di Lanczos. Approssimazione degli autovalori estremali di una matrice simmetrica. Idea alla base dei metodi di proiezione. Cenni su alcune generalizzazioni del metodo di Lanczos: l'iterazione di Arnoldi per matrici quadrate non simmetriche e l'iterazione di Golub-Kahan per matrici rettangolari.

Totale ore: 64