Lezioni ed appelli A.A. 2016-2017

Docente: Prof. Gaetano Zanghirati

A.A. 2016/2017

Avvisi

Orario
Mercoledì 14:30 - 16:30, aula 1; giovedì 16:30 - 18:30, aula 1, Dipartimento di Matematica e Informatica, sede di via Machiavelli, 30.

Modalità d'esame
Prova orale.

Sessioni d'esame

• Giugno 2017
• Luglio 2017
• Settembre 2017
• Settembre 2017
• Gennaio 2018
• Febbraio 2018

Orario di ricevimento
Giovedì 12:30 - 13:30 presso il Dipartimento di Matematica, salvo diverse indicazioni o appuntamenti.

Lezioni

1/3/2017

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)

2/3

Ancora richiami di algebra e analisi multivariata. Elementi del caso quadratico. Interpretazione geometrica della derivata direzionale.
(2 ore)

8/3

Esempi di problemi non vincolati e di problemi vincolati. Esercizio. Definizione di punti di minimo locale e globale, relativo e assoluto. Condizioni di esistenza di minimi globali. vincolati e non. Teroma di Weirstrass.
(2 ore)

15/3

Convessità e condizioni per il caso convesso. Esempi. Brevi richiami sulle serie numeriche e di funzioni e la loro convergenza, sulle formule di Taylor e di McLaurin in una variabile. Formula di Taylor in più variabili, espressione del resto, interpretazione geometrica con esempi in 2d. Condizioni di ottimalità non vincolata del 1° e del 2° ordine. Esempi.
(2 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. 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. Proprietà delle condizioni di Goldstein per ricerca in linea non vincolata.
(2 ore)

22/3

Esercizio: costruzione di vari elementi di un metodo di discesa con ricerca in linea esatta su un problema 2D. Verifica delle proprietà e dei risultati teorici.
(2 ore)

23/3

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. Linesearch + condizione dell'angolo: casi del metodo di discesa più ripida (steepest descent) e dei metodi quasi-Newton.
(2 ore)

29/3

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)

30/3

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)

5/4

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

6/4

Motivazioni dei metodi quasi-Newton. Metodi quasi-Newton: algoritmo, proprietà di discesa, costo computazionale, metodi a metrica variabile. 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: DFP.
(2 ore)

10/4

Formula DFP: proprietà, teorema di mantenimento della definita positività. Formula BFGS. 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 (senza dim.). Metodo trust-region: motivazioni, algoritmo generale, teorema di convergenza del prim'ordine per la successione TR (senza dim.).
(2 ore)

20/4

Teorema di convergenza del second'ordine per TR (senza dim.). Esercizi: caratterizzazione punti critici, SD, SD + LS esatta su quadratiche.
(2 ore)

26/4

Introduzione alla minimizzazione vincolata: concetti di base, esempi. Caso di un vincolo di uguaglianza. Esempio.
(1 ora)

27/4

Minimizzazione vincolata: 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)

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

4/5

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

10/5

Lemma di Farkas (con dimostrazione) e dimostrazione del Teorema KKT. Cond. necessaria del second'ordine per un punto di minimo vincolato (con dimostrazione).
(2 ore)

11/5

Cond. suff. del second'ordine per un punto di minimo stretto locale vincolato (con dimostrazione). Il metodo dello spazio nullo per problemi lineari o quadratici con soli vincoli di uguaglianza (ECLP e ECQP): funzione ridotta, gradiente ridotto, hessiano ridotto.
(2 ore)

18/5

Il metodo dello spazio nullo per problemi non lineari generali con soli vincoli di uguaglianza (ENLP): motivazioni, costruzione, parametrizzazione locale della regione ammissibile in un intorno di un punto di minimo locale vincolato.
(2 ore)

24/5

ENLP: altra interpretazione dei moltiplicatori di Lagrange. Metodo dei moltiplicatori di Lagrange. Condizioni necessarie e condizioni sufficienti del second'ordine per ENLP regolari. EQP: sistema aumentato, metodo dello spazio immagine. ENLP: sistema aumentato, metodo SEQP. Problemi NLP con vincoli di disuguaglianza: richiamo delle condizioni necessarie e delle condizioni sufficienti del second'ordine, breve cenno al metodo dell'insieme attivo (ASM).
(2 ore)

25/5

Esercizi su problemi EQP ed ENLP.
(2 ore)

Testi consigliati

• "Numerical Optimization", 2nd ed., J. Nocedal, S.J. Wright.
• "Practical Methods of Optimization", 2nd ed., R. Fletcher.
• "Mathematical Programming", 2nd ed., D. Bertsekas.
• "AMPL - Algebraic Modelling Programming Language": download versione per studenti