PROGRAMMA DEL CORSO DI METODI NUMERICI PER
L'OTTIMIZZAZIONE
Prof. Luigi Brugnano
Corso di Laurea Specialistica in Matematica,
a.a. 2006-07
(mutuato dalla Laurea specialistica e dalla Laurea triennale in
Informatica).
Numero crediti: 6.
Problemi di Programmazione Nonlineare non vincolata. Generalita' ed esempi. Minimi locali e globali: direzioni ammissibili, condizioni necessarie del primo e secondo ordine, condizioni sufficienti. Approssimazione lineare ai minimi quadrati e decomposizione ai valori singolari di una matrice. Funzioni convesse. Algoritmi iterativi di discesa: generalita', ordine e convergenza; Teorema di convergenza globale. Minimizzazione unidimensionale: il metodo di Fibonacci ed il metodo della sezione aurea, richiami su equazioni alle differenze lineari, il metodo di Newton, metodo delle secanti, fit quadratico e cubico. Convergenza globale dei metodi di fit. Metodi line-search: generalita’, il metodo del gradiente, precondizionamento, il metodo di Newton e tipo Levemberg-Marquardt. Metodi quasi-Newton: generalita’, correzione di rango uno, il metodo di Davidon-Fletcher and Powell, formule complementari e metodi della famiglia di Broyden, il metodo DFP con autoscaling. Metodi ibridi. Cenni sui metodi Trust-region: generalita’, punto di Cauchy, il metodo "dogleg".
Problemi di Programmazione Nonlineare vincolata.
Un esempio: ottimizzazione di un portafoglio. Generalita’, vincoli
attivi e iperpiano tangente. Condizioni del primo
ordine
per vincoli di uguaglianza. Condizioni del
secondo
ordine. Caso generale: condizioni di Kuhn-Tucker e condizioni del
secondo
ordine. Applicazioni: cenni sui metodi primale-duale per problemi di
Linearita' complementare e Programmazione quadratica. Metodi delle
direzioni
ammissibili: generalita', il metodo del gradiente proiettato e sua
implementazione. Cenni sui metodi di penalita' e sui metodi
barriera e loro implementazione.
Testi consigliati.