INGLESE

L’insegnamento introduce metodologie e algoritmi di ottimizzazione per problemi di programmazione non lineare. Il programma affronta: (1) Introduzione ai problemi di ottimizzazione non vincolata; (2) Metodi di ricerca in linea (gradiente, Newton, quasi-Newton) ; (3) Metodi di tipo Trust-Region; (4) Cenni sulla risoluzione di problemi di ottimizzazione vincolata.

Nocedal, J., & Wright, S. J. (2006). Numerical optimization. New York, NY: Springer New York.

Bhunia, A. K., Sahoo, L., & Shaikh, A. A. Advanced Optimization and Operations Research. Springer, Cham, 2020.

Luenberger, D. G., & Ye, Y. Linear and Nonlinear Programming. 3rd ed., Springer, New York, 2008.


Appunti e materiale didattico fornito dal docente sulla piattaforma e-learning di Ateneo.

Al termine dell’insegnamento, lo studente dovrà aver acquisito:
Conoscenza e capacità di comprensione: Comprendere i concetti fondamentali della teoria dell’ottimizzazione; conoscere i principali algoritmi risolutivi.
Utilizzazione delle conoscenze e capacità di comprensione: Saper selezionare e applicare correttamente a problemi reali i metodi di base utilizzando strumenti software appropriati (MATLAB, Python).
Capacità di trarre conclusioni (Autonomia di giudizio): Valutare criticamente la robustezza delle soluzioni ottenute e interpretare i risultati ottenuti nel contesto del problema reale.
Abilità comunicative: saper esprimere formulazioni matematiche di problemi di ottimizzazione, saper illustrare i metodi e gli strumenti appropriati per la loro risoluzione, saper comunicare i risultati ottenuti utilizzando un linguaggio tecnico-scientifico adeguato.
Capacità di apprendere: Disporre degli strumenti metodologici per approfondire autonomamente tecniche avanzate di ottimizzazione e nuove applicazioni del mondo reale.

Si raccomanda la conoscenza solida dell’algebra lineare numerica e dell’analisi matematica.

L’insegnamento prevede 48 ore totali (6 CFU), così ripartite:
Lezioni frontali (40 ore) articolate nei seguenti moduli didattici:
Moduli teorici frontali: presentazione della teoria dell’ottimizzazione e delle metodologie per la risoluzione numerica di problemi di programmazione non lineare.

Moduli laboratoriali: attività di "learning by doing", simulazioni e applicazione pratica delle conoscenze acquisite.
Esercitazioni (8 ore): risoluzione pratica di esercizi tratti dai test di riferimento, inclusi test intermedi e finali di autovalutazione. 
La frequenza non è obbligatoria ma è fortemente consigliata.

La verifica è costituita da una prova computer-based seguita da un colloquio articolato in domande sulle performance degli algoritmi utilizzati e l’analisi dei risultati ottenuti, allo scopo di accertare il livello di conoscenze raggiunto.
Per la prova computer-based lo studente potrà utilizzare programmi di propria implementazione o forniti dal docente.
Struttura della valutazione: 
I voti sono espressi in trentesimi. Il punteggio minimo richiesto è 18/30. Il voto massimo è 30/30 e lode.

Parametri di valutazione: La valutazione considera: (1) correttezza della formulazione matematica, (2) capacità di applicazione del metodo appropriato al problema in esame e dei concetti teorici correlati, (3) qualità dell’interpretazione dei risultati, (4) uso del lessico specialistico.

Per essere ammessi alla valutazione, gli studenti devono presentare un documento d'identità valido.

Il materiale didattico, gli script e gli esercizi saranno resi disponibili dal docente.

Preliminari Matematici (0.25 CFU / 2 ore):
Introduzione ai problemi di ottimizzazione, motivazione ed esempi. Formulazione generale dei problemi di ottimizzazione non vincolata e vincolata. Velocità di convergenza degli schemi iterativi (definizioni). Richiami di analisi convessa.
Introduzione all’Ottimizzazione non vincolata ( 0.5 CFU / 4 ore):
Minimi globali e locali (definizioni). Teorema di Taylor. Condizioni necessarie del primo ordine e condizioni sufficienti del secondo ordine per l’ottimalità locale. Il caso delle funzioni convesse.
Metodi di ricerca in linea (3 CFU / 24 ore):
Metodi di ricerca in linea: direzione di discesa (definizione); strategie per la scelta del passo: passo costante, regola di minimizzazione, ricerca in linea esatta e passo di Cauchy; strategie di ricerca in linea inesatta: condizioni di Wolfe.

Risultati teorici sulla convergenza dei metodi di ricerca in linea: condizione d’angolo, teorema di Zoutendijk.

Metodo steepest descent e sua velocità di convergenza.
Direzione di Newton, velocità di convergenza del metodo di Newton. Metodo di Newton globale.
Metodi quasi-Newton: formule SR1, DFP e BFGS e relative proprietà; condizioni di convergenza.
Utilizzo di software in ambiente Excel, Matlab e Python per la risoluzione di problemi di programmazione lineare.
Metodi Trust-Region (0.75 CFU / 6 ore):
scelta del raggio di Trust-region, risoluzione del sottoproblema quadratico per la determinazione della direzione di discesa, punto di Cauchy, strategia dogleg.

Introduzione all’ottimizzazione vincolata (0.5 CFU / 4 ore):
Soluzioni locali e globali (definizioni). Vincoli semplici. Definizione di vincolo attivo. Direzione di discesa ammissibile. Condizione di stazionarietà. Funzione lagrangiana. Proprietà LICQ. Condizioni di ottimalità del primo ordine per problemi vincolati (condizioni di Karush–Kuhn–Tucker). Cenni al metodo del gradiente proiettato.

Esercitazione (1 CFU / 8 ore): 
- Risoluzione pratica di esercizi tratti dai test di riferimento, test intermedi e finali di autovalutazione.

English

The course introduces optimization methodologies and algorithms for nonlinear programming problems. The program covers: (1) Introduction to unconstrained optimization problems; (2) Line-search methods (gradient, Newton, and quasi-Newton methods); (3) Trust-region methods; (4) Introduction to constrained optimization problems.

Nocedal, J., & Wright, S. J. (2006). Numerical optimization. New York, NY: Springer New York.

Bhunia, A. K., Sahoo, L., & Shaikh, A. A. Advanced Optimization and Operations Research. Springer, Cham, 2020.

Luenberger, D. G., & Ye, Y. Linear and Nonlinear Programming. 3rd ed., Springer, New York, 2008

Lecture notes and teaching materials provided by the instructor on the university e-learning platform.

Upon completion of the course, students will have acquired:
• Knowledge and understanding: Understanding of the fundamental concepts of optimization theory and knowledge of the main solution algorithms.
• Applying knowledge and understanding: Ability to select and correctly apply basic optimization methods to real-world problems using appropriate software tools (MATLAB, Python).
• Making judgements (Autonomy of judgement): Ability to critically evaluate the robustness of the obtained solutions and to interpret the results within the context of the real problem.
• Communication skills: Ability to express mathematical formulations of optimization problems, to explain the methods and tools used for their solution, and to communicate the results using appropriate technical and scientific language.
• Learning skills: Ability to independently deepen advanced optimization techniques and explore new real-world applications.

Solid knowledge of Linear Numerical Algebra and Mathematical Analysis is strongly recommended.

48 total hours (6 CFU - ECTS credits).

Lectures (40 hours):
Theoretical modules: Presentation of optimization theory and numerical methods for solving nonlinear programming problems.
Laboratory modules: “Learning by doing” activities, simulations, and practical application of acquired knowledge.


Tutorials / Problem Sessions (8 hours):
Practical exercises drawn from reference tests, including midterm and final self-assessments tests to monitor learning progress.
Attendance is not mandatory but strongly recommended.

Assessment consists of a computer-based test followed by an oral examination, including questions on the performance of the implemented algorithms and the analysis of the obtained results, aimed at assessing the level of knowledge achieved.
For the computer-based test, students may use software programs developed by themselves or provided by the instructor.
Evaluation structure:
Marks are expressed in a scale ranging from 0 to 30. The minimum passing mark is 18/30. Outstanding performance is marked 30/30 cum laude.

Evaluation criteria:
Assessment is based on: (1) correctness of the mathematical formulation, (2) ability to apply the method appropriate to the problem under examination and the related theoretical concepts, (3) quality of result interpretation, and (4) use of appropriate technical terminology.


Students must present a valid ID document to be admitted to the exam.

Teaching materials, scripts, and exercises will be provided by the instructor.

• Mathematical Preliminaries (0.25 ECTS / 2 hours):
Introduction to optimization problems, motivation and examples. General formulation of unconstrained and constrained optimization problems. Rate of convergence of iterative schemes (definitions). Recalls of convex analysis.

Introduction to Unconstrained Optimization (0.5 ECTS / 4 hours): Global and local minima (definitions). Taylor’s theorem. First-order necessary conditions and second-order sufficient conditions for local optimality. The case of convex functions.

Line Search Methods (3 ECTS / 24 hours):

Line search methods: descent direction (definition); step-length selection strategies: constant step-length, minimization rule, exact line search and Cauchy step-length; inexact line search strategies: Wolfe conditions.

Theoretical results on the convergence of line search methods: the angle condition, the Zoutendijk theorem.

Steepest descent method and its convergence rate.
The Newton’s direction, convergence rate of the Newton’s
method. Global Newton’s method. Quasi-Newton methods: SR1 formula, DFP formula, BFGS formula and related properties; convergence conditions.

Trust-Region Methods (0.75 ECTS / 6 hours):
Choice of the trust region radius, solving the quadratic subproblem to determine the descent direction, the Cauchy point, the dogleg strategy.

Introduction to Constrained Optimization (0.5 ECTS / 4 hours):
Local and global solutions (definitions). Simple constraints.
Definition of active constraint. Feasible descent direction. Stationarity condition.The Lagrangian function. LICQ property. First-order optimality conditions
for constrained problems (Karush-Khun-Tucker conditions). Overview of the projected gradient method.

Practice Sessions (1 ECTS / 8 hours):
Practical solution of exercises drawn from the reference textbooks, midterm and final self-assessment tests.