Docente/i: Raffaella Guglielmann  

Denominazione del corso: Ottimizzazione
Codice del corso: 064078
Corso di laurea: Ingegneria Informatica, Ingegneria dei Servizi
Settore scientifico disciplinare: MAT/08
Crediti formativi: CFU 5
Sito web del corso: http://www-dimat.unipv.it/~gugliel/teach.html

Obiettivi formativi specifici

Il corso si propone di fornire i concetti ed il linguaggio relativi ai problemi di minimo, sia libero che vincolato, e di stimolare lo studente a formulare, classificare e risolvere i problemi di ottimizzazione. Lo studente verrà inoltre introdotto ai principali algoritmi implementati sia in librerie di calcolo scientifico che nell’Optimization Toolbox di MATLAB ed alla valutazione dell’efficienza e dei limiti degli algoritmi mediante applicazioni a problemi modello.

Programma del corso

Durante il corso verranno illustrati i principali algoritmi di ottimizzazione per problemi di minimo, vincolati e non, con particolare attenzione alle relative proprietà di convergenza. Fanno parte integrante del corso le esercitazioni svolte in laboratorio, necessarie per la verifica numerica dei risultati teorici illustrati durante le lezioni.

1. Sistemi di equazioni non lineari

Modello affine e metodo di Newton-Raphson: proprietà di convergenza.
• Metodi senza derivate: jacobiana approssimata e proprietà di convergenza. Approssimazione secante o quasi-newton: updates quasi-newton di rango 1.
• Update di Broyden: good Broyden. Formula di Sherman-Morrison-Woodbury. Update in forma inversa. Dualità e diagramma commutativo con update bad Broyden. Forma diretta: update della fattorizzazione.
• Metodi di Newton inesatti.

2. Problemi di ottimizzazione non vincolati
Dopo aver caratterizzato i punti di minimo locale, si passa alla descrizione dei principali metodi di risoluzione.

Metodo di Newton: modello quadratico. Proprietà di convergenza. Vantaggi e svantaggi.
• Metodi basati su ricerche lungo direzioni di discesa: metodo del gradiente. Prototipo algoritmo basato su ricerche unidimensionali approssimate. Regole di Wolfe-Powell. Risultati di convergenza: teorema di Dennis-Morè. Ammissibilità asintotica dello step di Newton in relazione alle regole di Wolfe-Powell.
• Metodi Quasi-Newton: equazione quasi-newton. Update simmetrico di rango 1: SR1. Updates simmetrici quasi-newton di rango 2. Proprietà variazionali degli updates. Updates definiti positivi : DFP e BFGS. Updates duali e inversi. Famiglia di Broyden. Proprietà per funzioni quadratiche. Risultati di convergenza globale e superlineare.
• Metodi a direzioni coniugate: terminazione finita per funzioni quadratiche.
• Metodo del gradiente coniugato lineare. Metodi di tipo gradiente coniugato non lineare. Regole di Wolfe-Powell forti e convergenza globale del metodo di Fletcher-Revees. Metodo BFGS a memoria limitata e relazione con i metodi di tipo gradiente coniugato non lineare.
• Metodo della Trust Region: prototipo algoritmo. Risultato di convergenza globale quadratica. Metodi di risoluzione esatta ed approssimata. Metodo alla Levenberg-Marquardt.
• Problemi di minimo quadrato non lineari: metodi di Gauss-Newton, Gauss-Newton damped, Levenberg-Marquardt, Trust-region. Formule di updates per metodi Quasi-Newton. Metodi ibridi.

3. Problemi di ottimizzazione vincolati
Dopo aver definito la struttura dei problemi di minimo vincolati, se ne dà una classificazione sulla base delle caratteristiche della funzione obiettivo e dei vincoli e si illustrano alcuni dei metodi per la loro risoluzione.

Vincoli di uguaglianza e disuguaglianza: condizioni di ottimalità di Kuhn-Tucker e condizioni del secondo ordine. Funzione Lagrangiana, moltiplicatori di Lagrange.
• Ottimizzazione non lineare: metodi di penalizzazione e delle barriere; risultati di convergenza e approssimazione dei moltiplicatori; metodo della Lagrangiana aumentata. Programmazione quadratica sequenziale (SQP).
• Problemi di programmazione lineare: descrizione del problema in forma standard. Rappresentazione dei vincoli lineari. Metodo del simplesso e del simplesso revised.

Prerequisiti

I contenuti dei corsi di matematica della laurea triennale (con particolare attenzione al calcolo vettoriale e matriciale, alla definizione di gradiente, jacobiana, hessiana).

Tipologia delle attività formative

Lezioni (ore/anno in aula): 28
Esercitazioni (ore/anno in aula): 9
Laboratori (ore/anno in aula): 15
Progetti (ore/anno in aula): 0

Materiale didattico consigliato

J. Nocedal, S.J. Wright. Numerical Optimization. Springer Verlag, 1999. (Testo di riferimento).

R. Fletcher. Practical Methods of Optimization. John Wiley, 1991.

S.G. Nash, A. Sofer. Linear and Nonlinear Programming. McGraw-Hill, 1996.

P.E. Gill, W. Murray, M.H. Wright. Practical Optimization. Academic Press, 1981.

MATLAB Optimization Toolbox User's Guide. The Math WOrks Inc., 1996.

Modalità di verifica dell'apprendimento

Valutazione delle esercitazioni svolte in laboratorio e prova orale.