NUMERICAL OPTIMIZATION METHODS
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2015/2016
- Docente
- MICHAEL MATTHIAS HERTY
- Crediti formativi
- 6
- Periodo didattico
- Secondo Semestre
- SSD
- MAT/08
Obiettivi formativi
- Il corso illustra i moderni metodi per l'ottimizzazione non lineare. Esso fornisce le basi teoriche e introduce i metodi attualmente utilizzati in matematica applicata. Si analizzeranno i diversi metodi per quanto riguarda velocità di convergenza. Proprietà come la definita positività e la teoria dell'approssimazione saranno discusse.
Le conoscenze principali acquisite saranno:
• Sistema Karush-Kuhn-Tucker;
• conoscenza qualificazione vincolo;
• la comprensione di concetti come la velocità di convergenza;
• metodi principali per l'ottimizzazione vincolata;
• metodi per la programmazione quadratica;
• metodi sequenzialidi programmazione quadratica;
• metodi del punto interno.
Le principali competenze (che sono la capacità di applicare le conoscenze acquisite) saranno:
• identificare il metodo moderno più adatto per l'applicazione;
• individuare i requisiti e la velocità di convergenza dei metodi;
• comprendere l'importanza dei sistemi Karush-Kuhn-Tucker;
• individuare le condizioni necessarie per l’applicazione dei metodi;
• individuare i requisiti per i metodi sequenziali di programmazione quadratica;
• identificare i requisiti per i metodi del punto interno;
• analizzare problema di ottimizzazione e comprendere le applicazioni di base.
Le conoscenze e le abilità acquisite possono essere utilizzate in tutti gli altri corsi di matematica applicata. Prerequisiti
- Per seguire il corso sono necessari una piena conoscenza delle nozioni di base di algebra lineare e calcolo.
Contenuti del corso
- Il corso prevede 42 ore. Trattando argomenti di base, di preparazione per altri corsi, non ci sono applicazioni di laboratorio.
Introduzione (9 ore)
Differenziabilità - Condizioni necessarie nel caso di vincoli – condizioni di primo ordine e secondo ordine - interpretazione geometrica di vincoli – teorema di Karush-Kuhn-Tucker - qualifiche di vincolo (MFCQ, Licq, Adabie) - Interpretazione della qualifica di vincolo – esempi di applicazione di condizioni – caso lineare e quadratico
Metodi per la minimizzazione senza vincoli (4 ore)
Metodo di Newton – Metodo del Gradiente - Line-Search – Regola di Armijo – Regola di Paul-Wolffe - BFGS - DFP - metodo SR1 - interpretazione geometrica dei metodi - Condizioni necessarie per la convergenza - risultati di convergenza e ordine di convergenza
Programmazione quadratica (5 ore)
condizioni di KKT - caso lineare - caso quadratico - Metodo di proiezione primale - Proprietà e velocità di convergenza - dominio irrealizzabile – Metodo Primale-Duale - metodi iterativi di proiezione - moltiplicatori
Programmazione quadratica sequenziale (12 ore)
Metodi di Lagrange-Newton - convergenza locale - informazioni al secondo ordine - modifica BFGS - Interpretazione come metodo Primale-Duale - Estensione a vincoli di disuguaglianza - metodi SQP irrealizzabili - Metodi adattivi - globalizzazione - funzione di penalità esatta - funzione L1- Direzioni di discesa e proprietà - Altre funzioni di penalità - metodo del lagrangiano aumentato
Metodi Trust Region (6 ore)
Definizioni - metodi pratici – Raggio Trust-Region – Punto di Cauchy - proprietà di convergenza - Relazione con SQP - Aggiornamento Formule - Tecniche di globalizzazione - regolarizzazione cubica – Effetto Maratos – Dimostrazione di Convergenza
Metodi Interior Point (12 ore)
Definizione – Funzione di barriera logaritmica - Sistema KKT perturbato – Cammino Centrale - Proprietà del cammino centrale - Aggiornamento per Moltiplicatori - tecniche di globalizzazione - Funzione Merito - Estensione a uguaglianze – Sistema esteso KKT perturbato - Relazione con i metodi Trust Region - problemi pratici – Dettagli implementativi Metodi didattici
- Il corso è organizzato come segue:
• lezioni con esercitazioni su tutti gli argomenti del corso (42 ore) Modalità di verifica dell'apprendimento
- Esame orale.
La revisione mira a valutare la capacità dello studente nel collegare gli argomenti discussi di ottimizzazione e metodi. Testare la capacità di identificare i metodi e le relative applicazioni. Testare la comprensione dei meccanismi di base dei metodi.
Il test copre tutti gli argomenti del corso.
Allo studente verranno assegnati tre argomenti e, prima di esporli, lui/lei ha tempo per organizzare la risposta (di solito da 30' a 60', a seconda delle esigenze dello studente).
Data la complessità dei problemi di ottimizzazione generale lo studente non è tenuto a conoscere tutti i dettagli. Una comprensione di base del meccanismo dei metodi nonché il background teorico è comunque necessaria. L'obiettivo dello studio, infatti, non è quello di memorizzare metodi e problemi che, probabilmente, in pochi anni non saranno più utilizzati, ma capire le ragioni teoriche che hanno portato allo sviluppo di certi metodi.
La preparazione dello studente sarà valutata sulla base della capacità di ricordare il meccanismo e le idee dei metodi e spiegare le ragioni che hanno portato alla costruzione dei metodi e identificarne eventuali limitazioni. Testi di riferimento
- dispense del docente.
Argomenti specifici possono essere ulteriormente sviluppati nei seguenti testi:
Numerical Optimization by J. Nocedal and S. Wright, Springer, 2006
Numerical Methods for Unconstrained Optimization and Nonlinear Equations by J.E. Dennis and R.B. Schnabel
