Ottimizzazione
Docente
prof. aggr. Daniele CASAGRANDE
Crediti
6 CFU
Lingua
Italiano
Obiettivi formativi specifici
Il corso introduce la teoria dell'ottimizzazione in spazi a dimensione finita e i principali algoritmi per la ricerca dei minimi. Saranno trattati sia algoritmi esatti che algoritmi approssimati. Il corso si propone di estendere le conoscenze apprese dai corsi di analisi matematica e di algebra lineare applicandole ai problemi di ottimizzazione. Alla fine del corso lo studente dovrebbe essere in grado di interpretare un'ampia classe di problemi di ottimizzazione sia dal punto di vista analitico, ricavando il modello matematico del problema, sia proponendo, per ogni problema, un algoritmo di risoluzione adeguato.
Competenze acquisite
Il corso prepara all’interpretazione di un'ampia classe di problemi di ottimizzazione sia statica che dinamica.
Lo studente acquisisce sia la capacità di formalizzare un problema in termini matematici sia gli strumenti teorici per studiare la soluzione e, ove possibile, trovarla.
Programma
Introduzione: introduzione al corso; esempi di problemi di ottimizzazione (2 ore).
Generalità sui problemi di ottimizzazione: classificazione dei problemi di ottimizzazione.; problemi vincolati e non vincolati; problemi statici e dinamici; problemi lineari, quadratici, geometrici e non lineari; programmazione intera; controllo ottimo; esempio a tempo discreto; esempio a tempo continuo; ottimizzazione stocastica (6 ore).
Risultati di esistenza: prime definizioni; minimo locale; minimo globale; risultati di esistenza nel caso vincolato e nel caso non vincolato; funzioni radialmente illimitate; insiemi di livello (4 ore).
Problemi convessi: insiemi convessi; definizioni; funzioni convesse; definizioni e condizioni per la convessità; problemi convessi (4 ore).
Ottimizzazione non vincolata: generalità sull'ottimizzazione non vincolata; direzione di discesa; condizioni necessarie e sufficienti; struttura di un algoritmo di ottimizzazione; commenti sul punto iniziale, sulla direzione di discesa, sullo spostamento, sull'esistenza di punti di accumulazione; velocità di convergenza; condizioni sull'angolo; metodi di ricerca in linea, esatti e non esatti; metodo di Armijo; interpretazione geometrica, teorema di terminazione e di convergenza; metodo di Goldstein; interpretazione geometrica; il metodo del gradiente; caso particolare delle funzioni quadratiche; metodo delle direzioni coniugate; metodo del gradiente coniugato (12 ore).
Ottimizzazione vincolata: generalità; definizioni; introduzione al metodo del simplesso per la programmazione lineare (4 ore).
Metodo del simplesso: soluzioni di base, definizioni e interpretazione.; come ottenere una soluzione di base; giustificazione del metodo del simplesso; diagonalizzazione delle equazioni dei vincoli; interpretazione geometrica del passaggio da una base ad un'altra (6 ore).
Programmazione non lineare: condizioni necessarie del prim'ordine (Karush‐Kuhn‐Tucker); condizioni sufficienti del second'ordine per un minimo locale; esempio; programmazione non lineare; generalità; metodo della sequenza di funzioni di penalità metodo delle funzioni di penalità sequenziali; metodo delle funzioni lagrangiane aumentate sequenziali; metodo delle funzioni di penalità esatte; metodo delle funzioni lagrangiane aumentate esatte; programmazione quadratica ricorsiva (12 ore).
Controllo ottimo: formalizzazione di un problema di controllo ottimo; esempi di problemi senza controlli ammissibili; esempi di problemi che non ammettono soluzione; esempi di problemi che ammettono infinite soluzioni; condizioni per l'esistenza e unicità della soluzione; l'equazione di Hamilton‐Jacobi; l'equazione di Bellman; il principio del massimo di Pontryagin; definizione e interpretazione del costato; condizioni necessarie per avere una soluzione; significato delle condizioni di trasversalità (10 ore).
Bibliografia
- L.D. Berkovitz, "Optimal control theory", Springer verlag
- S.S. Rao, "Optimization", Wiley
- L.C. Young, "Optimal Control Theory", AMS Chelsea Publishing
- P. Serafini, "Ottimizzazione", Zanichelli
Modalità d'esame
prova orale