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

Docente: Prof. Gaetano Zanghirati

A.A. 2014/2015

Avvisi

Orario
Lunedì 16:30 - 18:30; giovedì 14:30 - 17:30, dipartimento di Matematica e Informatica, sede di via Machiavelli, 30.

Modalità d'esame
Prova orale.

Sessioni d'esame

• Giugno 2015
• Luglio 2015
• Settembre 2015
• Settembre 2015
• Gennaio 2016
• Febbraio 2016

Lezioni

23/2/2015

Presentazione del corso. Breve introduzione agli argomenti generali. Cenno ai riferimenti bibliografici e al software. Definizione di Ottimizzazione Numerica.
(1 ora)

2/3

Esempi di problemi di ottimo. Notazione. Richiami di algebra e analisi multivariata, esempi.
(2 ore)

5/3

Ancora richiami di algebra e analisi multivariata. Elementi del caso quadratico. Esempi di problemi non vincolati e di problemi vincolati. Esercizio.
(3 ore)

9/3

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. Esempi.
(2 ore)

12/3

Brevi richiami sulle serie numeriche e di funzioni e la loro convergenza, sulle formule di Taylor di di McLaurin in una variabile. Formula di Taylor in più variabili, espressione e alcune proprietà del resto, interpretazione geometrica con esempi in 2d. Condizioni di ottimalità non vincolata del 1° e del 2° ordine. Esempi.
(3 ore)

16/3

Metodi numerici per problemi non vincolati: introduzione ai metodi di discesa. Tecnica di ricerca in linea per funzioni di più variabili: interpretazione geometrica. Condizioni di Wolfe deboli e forti, loro interpretazione geometrica e loro implicazioni.
(2 ore)

23/3

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.
(2 ore)

26/3

Proprietà delle condizioni di Goldstein per ricerca in linea non vincolata. Brevissimi richiami sulle serie numeriche a termini positivi. Teorema di Zoutendijk di convergenza globale per metodi di discesa non vincolata con linesearch di Wolfe. Conseguenze. Condizione dell’angolo per la convergenza globale dei metodi di ricerca in linea.
(3 ore)

30/3

Linesearch + condizione dell'angolo: casi 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 (senza dim.).
(2 ore)

13/4

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/4

Teoremi di convergenza e velocità di convergenza per SD con LS esatta. Teorema di Dennis-Moré per metodi quadi-Newton generali (senza dim.). Teorema di convergenza del metodo di Newton (senza dim.).Cenni ai metodi di Newton modificati, metodo di Levenberg-Marquardt, restricted-step, curvatura negativa, differenze finite.
(2 ore)

27/4

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. Aggiornamenti di rango 2. Formula DFP: proprietà, teorema di mantenimento della definita positività.
(2 ore)

30/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. Introduzione alla minimizzazione vincolata: concetti di base, esempi. Caso di un vincolo di uguaglianza.
(3 ore)

4/5

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.
(2 ore)

7/5

Analisi di sensitività dei vincoli: il significato dei moltiplicatori di Lagrange. Elementi per la dimostrazione del Teroema KKT: successioni ammissibili, direzioni ammissibili, esempi. Vari casi con tipi di versi di vincoli.
(3 ore)

18/5

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

21/5

Cono normale all'insieme ammissibile in un punto di minimo vincolato. Lemma di Farkas (con dimostrazione) e dimostrazione del Teorema KKT. Cond. necessaria del second'ordine e cond. nec. e suff. del second'ordine per un punto di minimo vincolato (senza dimostrazioni).
(3 ore)

25/5

Il metodo dello spazio nullo per problemi lineari o quadratici con soli vincoli di uguaglianza (ECLP e ECQP).
(2 ore)

27/5

Il metodo dello spazio nullo per problemi non lineari generali con soli vincoli di uguaglianza (ENLP).
(1 ora)

 

Testi consigliati

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