OTTIMIZZAZIONE (2011/2012)

ESAME:

IMPORTANTE !

Appelli sifa ufficiali:

27 Gennaio, 1 febbraio, 23 aprile, 11 giugno, 2luglio, 3 settembre

APPELLI:

31 gennaio, 22 febbraio, da marzo in poi su appuntamento

Gli appelli sifa sono solo fittizzi e ai fini della verbalizzazione, per fare l’orale e’ necessario contattare il docente via email.

IMPORTANTE: procedura per fare l’orale in una certa data:

1) iscriversi al ultimo appello sifa precedente alla data

2) contattare via email il docente per stipulare un giorno e orario, almeno 2 settimane di anticipo rispetto al periodo desiderato

DOCENTE: Lourenco Beirao da Veiga

Codice: F4Y1U-
SSD: MAT/08
Crediti: 6
Ore totali Lezioni + Esercitazioni/Laboratorio: 52 ore

PROPEDEUTICITA’:

-- Primi due anni di corsi di Analisi

-- Basi di algebra lineare

-- Basi di linguaggio MATLAB

-- Utile aver seguito il corso di Calcolo Numerico

PROGRAMMA BREVE DEL CORSO:

PARTE 1 Metodi di punto fisso, maggiorazioni dell’errore, rapidita’ di convergenza e legame con la ricerca degli zeri. Ricerca degli zeri, il metodo di Newton e sue varianti.

PARTE 2 Ottimizzazione libera. Metodi line search, possibili scelte del passo e della direzione, proprieta’ di convergenza. Metodi thrust region. Cenni ai metodi conjugate gradient.

PARTE 3 Ottimizzazione vincolata. Condizioni di Kuhn-Tucker, metodi di proiezione, programmazione quadratica, minimi vincolati e punti sella, metodo di Uzawa.

Utilizzo di quanto visto per la risoluzione di semplici problemi applicati. Il laboratorio e’ svolto in linguaggio MATLAB.

RICEVIMENTI:

appuntamento via email

LIBRI DI TESTO PRINCIPALI:

P.G. Ciarlet, Introduzione all'analisi numerica matriciale e all'ottimizzazione, Masson 1989.

J. Nocedal, S.J. Wright, Numerical Optimization, Springer, 1999.

C. T. Kelley, Iterative methods for linear and nonlinear equations, SIAM 1995.

Altro materiale didattico fornito in corso d’opera

DIARIO DELLE LEZIONI:

DATA	LEZIONE	LABORATORIO
6 Ottobre 2011	Rapida presentazione generale del corso. Il problema della ricerca degli zeri per funzioni di R^d, qualche esempio e importanza del problema. Il problema del punto fisso e legame con il problema degli zeri “G=I-AF”. Definizione di contrazione. Teorema del punto fisso (o di Banach) e iterazioni di punto fisso. Esercizio circa la valutazione del parametro di contrazione per funzioni regolari.
10 Ottobre 2011	Definizione di ordine di convergenza per successioni. Proposizione di comportamento locale per le iterate di punto fisso. Commenti circa il test di arresto sugli scarti per le iterate di punto fisso. Utilizzo della teoria sviluppata per la ricerca dei punti fissi ai fini di avere indicazioni per la costruzione di metodi per la ricerca degli zeri.	Lab 1
17 Ottobre 2011	Lemma algebrico 1 e 2. Lemma di comportamento locale per funzioni F che soddisfano le condizioni “standard”. Teorema di convergenza locale per il metodo di Newton. Test di arresto per il metodo di Newton.	Lab 2
20 Ottobre 2011	Metodi quasi-Newton. Risultato di convergenza generale per i metodi quasi-Newton. Metodo di Newton-Jacobi e condizione che garantisce la convergenza. Metodo delle corde. Risultato di convergenza per il metodo delle corde.
24 Ottobre 2011	Matrici di rango uno. Metodo di Broyden (con costruzione e motivazione). Risultato di convergenza senza dimostrazione (per chi fosse interessato, può trovarla qui)	Lab 3
27 Ottobre 2011	Formula di Sherman-Morrison-Woodbury. Sua applicazione per il metodo di Broyden. Discretizzazione con differenze finite di una semplice problema applicato modello. Commenti al laboratorio del 24 ottobre.
7 Novembre 2011	Minimi di funzioni. Ripasso di alcuni risultati di analisi. Metodi di discesa. Alcune scelte per la direzione di discesa (steepest descent, Newton, quasi- Newton). Metodo exact line search per la scelta del passo. Condizioni di Wolfe con interpretazione grafica. Proposizione circa l’esistenza di un intervallo che soddisfa le condizioni di Wolfe. Teorema di convergenza dei metodi di discesa (CMD).	Problema modello Lab 4
10 Novembre 2011	Condizione di discesa uniforme. Corollario 1 ( f’(x_k) à 0 ) e Corollario 2 (convergenza all’insieme S dei punti stazionari) al teorema CMD. Osservazioni (importanza della proprieta’ di decrescita, caso di funzioni coercive, convesse, e strettamente convesse + coercive). Significato della condizione di discesa e di discesa uniforme sul angolo θ_k, analisi del caso con direzioni di discesa steepest descent, Newton e quasi-Newton. Caso di sottosuccessioni che soddisfano la condizione uniforme sul angolo θ_k. Metodo del backtracking per la scelta del passo alfa_k. Teorema C.M.D. con il backtracking.
14 Novembre 2011	Dimostrazione del Teorema CMD con il backtracking. Commenti utili alla programmazione del Exact Line Search utilizzando un Newton uno dimensionale.	Lab 5
17 Novembre 2011	Esempio e commenti circa la velocità di convergenza dello steepest descent. Proposizione e commenti: convergenza quadratica del metodo di discesa di Newton. Metodi di discesa di Newton con modifica della matrice Hessiana, due possibili algoritmi. Scalabilità del Newton e non scalabilità dello steepest descent, conseguenze per la scelta del α zero iniziale.
21 Novembre 2011	Commenti a laboratori precedenti. Metodi del gradiente coniugato, Fletcher Reeves, un paio di risultati senza dimostrazione. Minimi quadrati nonlineari.	Lab 6
24 Novembre 2011	Metodi thrust region. Idea e algoritmo generale. Punto di Cauchy. Metodo dogleg per la scelta di p_k. Lemma utile ai fini del calcolo del p_k del metodo dogleg.
28 Novembre 2011	Il problema della superficie di rivoluzione di area minima: modello, discretizzazione con elementi finiti e derivate utili ai fini della implementazione.	Lab 7
1 Dicembre 2011	Lemma di decrescita minima in termini della funzione m_k per scelte Cauchy point e dogled. Teorema di convergenza globale per i metodi thrust region (dogleg, Cauchy point): caso con parametro eta pari a 0 e successivamente caso con parametro eta strettamente positivo. Corollari.
5 Dicembre 2011	Commenti ai laboratori precedenti. Il problema della ricerca di minimi vincolati. Nomenclatura di base. Teorema di caratterizzazione delle funzioni convesse regolari (e caso strettamente convesso). Lemmi circa i punti di minimo di funzioni convesse e strettamente convesse. Una condizione necessaria (e sufficiente nel caso di funzione convessa) affinche’ un punto sia di minimo su un convesso. Teorema di proiezione su convessi chiusi e non vuoti.
12 Dicembre 2011	Qualche esempio di minimo vincolato. Costruzione e presentazione del metodo del gradiente con proiezione. Teorema di convergenza per il metodo suddetto (dimostrazione nella prossima lezione). Funzioni alfa-ellittiche e un paio di semplici lemmi. Casi particolari di convessi in cui la proiezione P è facile da calcolare (iper-rettangolo, sfera).	Lab 8
19 Dicembre 2011	Dimostrazione del Teorema di cui al 12 dicembre. Lemma di Farkas-Minkowski (senza dimostrazione). Insieme degli indici attivi, vincoli qualificati nel caso convesso. Proposizione (con dimostrazione parziale): minimi vincolati e condizioni di Kuhn-Tucker. Commenti e interpretazione grafica. Proposizione: sotto determinate condizioni le KT implicano che un punto sia di minimo. Punti sella. Proprieta’ inf-sup e sup-inf dei punti sella. Funzione lagriangiana associata a un problema (P) di minimo vincolato. Proposizione: i punti sella della funzione lagrangiana sono soluzioni del problema (P).
22 Dicembre 2011	Proposizione: le soluzioni del problema (P) corrispondono a punti sella della Lagrangiana. Scrittura del problema duale, derivate della funzione ausiliaria F, metodo del gradiente proiettato applicato al problema duale: costruzione del metodo di Uzawa. Teorema di convergenza per il metodo di Uzawa (dimostrazione nella prossima lezione).
9 Gennaio 2012	Dimostrazione del teorema di convergenza del metodo di Uzawa. Corollario (senza dimostrazione) sulla convergenza del moltiplicatore lambda. Commenti sulla unicità del lambda.	Lab 9
12 Gennaio 2012	Interpretazione di Uzawa come algoritmo sulla variabile x. Uzawa: scrittura esplicita e commenti nel caso di problemi di ottimizzazione quadratica. Metodo del rilassamento con proiezione. Scrittura esplicita e commenti nel caso quadratico.
16 Gennaio 2012	Filo teso sopra ostacolo: modello, discretizzazione, costruzione del problema di ottimizzazione quadratica associato.	Lab 10