Programma A.A. 2013-2014 - Prof. G. Zanghirati

Docente: Prof. Gaetano Zanghirati

A.A. 2013/2014

Avvisi

Orario
Lunedì 11:30 - 13:30; giovedì 10:30 - 12:30 e 13:30 - 15:30. Polo Scientifico-Tecnologico, Blocco B, terzo piano, aula seminari.

Modalità d'esame
Prova orale.

Sessioni d'esame

• 13 Giugno 2014, ore 11:00, Polo Sci.-Tec., blocco B, terzo piano, aula seminari.
• 16 Luglio 2014, ore 9:30, Polo Sci.-Tec., blocco F, aula F6.
• 4 Settembre 2014, ore 9:30, Polo Sci.-Tec., blocco B, terzo piano, Lab. studenti.
• 20 Settembre 2014, ore 10:30, Polo Sci.-Tec., blocco B, terzo piano, aula seminari.
• 25 Gennaio 2015, ore 10:30, Polo Sci.-Tec., blocco B, terzo piano, aula seminari.
• 10 Febbraio 2015, ore 10:30, Polo Sci.-Tec., blocco B, terzo piano, aula seminari.

Lezioni

24/2/2014

Presentazione del corso. Breve introduzione agli argomenti generali. Cenno ai riferimenti bibliografici e al software. Definizione di Ottimizzazione Numerica. Esempi di problemi di ottimo. Notazione. Richiami di algebra e analisi multivariata, esempi.
(2 ore)

3/3

Esempi di problemi non vincolati e di problemi vincolati. Definizione di punti di minimo locale e globale, relativo e assoluto. Condizioni di esistenza di minimi globali. vincolati e non. Teroma di Weirstrass. Convessità e condizioni per il caso convesso.
(2 ore)

6/3

Formula di Taylor in più variabili. Condizioni di ottimalità non vincolata del 1° e del 2° ordine. Esempi. Metodi numerici per problemi non vincolati: introduzione ai metodi di discesa. Tecnica di ricerca in linea per funzioni di più variabili. Lemma di esistenza per ricerca in linea con condizioni di Wolfe (deboli e forti). Esempi. Condizioni di Goldstein per la ricerca in linea. Tecniche di arretramento: algoritmo di Armijo.
Lab. Introduzione al linguaggio AMPL per la programmazione matematica: sintassi, struttura dei sorgenti, insiemi, parametri, variabili, funzioni obiettivo, funzioni vincolari, dichiarazione, definizione, inizializzazione, assegnamento.
(4 ore)

10/3

Proprietà delle condizioni di Goldstein per ricerca in linea non vincolata. Teorema di Zoutendijk di convergenza globale per metodi di discesa non vincolata con linesearch di Wolfe. Conseguenze.
(2 ore)

13/3

Condizione dell’angolo per la convergenza globale dei metodi di ricerca in linea. Caso del metodo di discesa più ripida (steepest descent) e dei metodi quasi-Newton. Algoritmo pratico di ricerca in linea con cond. di Wolfe forti, risultato di esistenza della soluzione. Proprietà dell'algoritmo. Algoritmo di sezionamento. Teorema di convergenza dell'algoritmo di sezionamento per la ricerca in linea limitata.
(4 ore)

17/3

Strategie di interpolazione per la scelta della lunghezza del passo. Regola di Armijo. Metodo di discesa più ripida (SD) con ricerca in linea esatta per quadratiche strettamente convesse. Velocità di convergenza di SD + LS esatta sulle quadratiche strett. convesse.
(2 ore)

20/3

Teoremi di convergenza e velocità di convergenza per SD con LS esatta. Teorema di Dennis-Moré per metodi quadi-Newton generali. Teorema di convergenza del metodo di Newton.
(4 ore)

24/3

Metodi trust-region (o restricted step): motivazioni, algoritmo prototipo. Teorema generale di convergenza globale, teorema di convergenza del second'ordine, discussione.
(3 ore)

26/3

Cenni ai metodi di Newton modificati, metodo di Levenberg-Marquardt, restricted-step, curvatura negativa, differenze finite. Motivazioni dei metodi quasi-Newton. Metodi quasi-Newton: algoritmo, proprietà di discesa, costo computazionale, variable metric methods. Condizione quasi-Newton. Formula con aggiornamento di rango 1. Teorema di convergenza su quadratiche convesse per formule di rango 1. Proprietà ereditaria.
Lab. Esercizio di programmazione in AMPL: un problema non lineare vincolato (problema di massima capienza serbatoio-magazzino).
(3 ore)

31/3

Aggiornamenti di rango 2. Formula DFP: proprietà, teorema di mantenimento della definita positività.
(1 ora)

2/4

Formule duali per DFP e BFGS. Cenno alla famiglia delle formule di Broyden. Formula di Shermann-Morrison. Invarianza per trasformazioni affini delle formule quasi-Newton.
Lab: esercizio in AMPL.
(2,5 ore)

14/4

Introduzione alla minimizzazione vincolata: concetti di base, esempi. Caso di un vincolo di uguaglianza.
(2 ore)

16/4

Caso di uno e due vincoli di disuguaglianza: esempi. Caso generale, funzione Lagrangiana. Condizioni di qualificazione dei vincoli: LICQ. Condizioni necessarie del prim'ordine: enunciato del Teorema KKT. Analisi di sensitività dei vincoli: il significato dei moltiplicatori di Lagrange. Elementi per la dimostrazione del Teroema KKT: successioni ammissibili, direzioni ammissibili, esempi.
(3 ore)

28/4

Cono tangente all'insieme ammissibile, risultati di caratterizzazione per le direzioni ammissibili nei punti di minimo vincolato (con dimostrazioni).
(2 ore)

5/5

Lemma di Farkas (con dimostrazione) e dimostrazione del Teorema KKT.
(1 ora)

12/5

Cond. necessaria del second'ordine e cond. nec. e suff. del second'ordine per un punto di minimo vincolato (con dimostrazioni).
(1,5 ore)

14/5

Il metodo dello spazio nullo per problemi quadratici con soli vincoli di uguaglianza (ECQP).
(3 ore)

Testi consigliati

• "Numerical optimization", 2nd ed., J. Nocedal, S.J. Wright.
• "Practical Methods of Optimization", 2nd ed., R. Fletcher.