Syllabus del corso
Obiettivi formativi
Apprendere le principali metodologie di risoluzione di problemi di ottimizzazione, con particolare riferimento a problemi tipici del mondo reale nonché algoritmi per il "fitting" di modelli statistici e l'apprendimento automatico (Machine Learning). Il linguaggio di programmazione di riferimento sarà Python, ma saranno presentate anche librerie in R.
Contenuti sintetici
Concetti fondamentali, ammissibilità di un problema di ottimizzazione, tipologie di problemi di ottimizzazione (lineare, intera, non-lineare), richiami di geometria e algebra lineare.
Programmazione lineare e lineare intera.
Programmazione non lineare e metodi basati sul gradiente.
Problemi di ottimizzazione black-box e metodi "derivative-free"
Esempi ed esercizi su problemi ispirati ad applicazioni reali
Programma esteso
Introduzione
- Concetti fondamentali di un problema di ottimizzazione: variabili decisionali, dati di input, funzione obiettivo, vincoli
- Ammissibilità di un problema di ottimizzazione: ammissibile, inammissibile, ilimitato
- Tipologie notevoli di problemi di ottimizzazione: lineare, convesso, non-convesso, black-box
- Richiami di geometria e algebra lineare
Programmazione Lineare
- Esempi di probemi lineari e semplice risoluzione grafica
- L'algoritmo del simplesso e il concetto di dualità
Programmazione Lineare Intera
- Esempi di problemi di ottimizzazione lineare intera (assegnamento, knapsack, travel salesman problem)
- Accenni sulla complessità computazionale: metodi esatti vs euristiche
- Branch & Bound
- Visita dei nodi di un grafo: ricerca in profondità (backtracking e identificazione di cicli) vs in ampiezza (per problemi di routing, algoritmo di Dijkstra)
Programmazione non-lineare
- Condizioni di ottimalità.
- Metodi basati sul gradiente per l'ottimizzazione vincolata e non vincolata
- Minimizzazione di una funzione di loss (o massimizzazione di una funzione di verosimglianza)
Problemi di ottimizzazione black-box
- Metodi derivative free: meta-euristiche di ricerca (Tabu-Search, Simulatd Annealing, Genetic Algorithms, e Ant Colony Optimization per problemi su grafi)
- Metodi derivative free: learning-and-optimization (una "overview" su Bayesian Optimization)
Prerequisiti
Nessun prerequisito
Metodi didattici
22 ore di lezione in modalità erogativa in presenza
8 ore di laboratorio ed esercitazione in modalità interattiva in presenza
12 ore di laboratorio ed esercitazione in modalità interattiva in presenza
Modalità di verifica dell'apprendimento
La verifica dell'apprendimento consiste in una prova scritta e in una successiva discussione/accetazione del voto finale. Per sostenere l'esame è obbligatorio effettuare l'iscrizione attraverso segreterie online secondo le scadenze stabilite.
La prova scritta consiste in 8 domande a risposta chiusa e 2 domande a risposta aperta. Il tempo a disposizione per l'esame sarà 2 ore.
Domande a riposta chiusa
Le domande a risposta chiusa riguarderanno argomenti di teoria oppure richiederanno di individuare il risultato di un semplice esercizio. Una risposta sbagliata non darà luogo ad alcuna penalizzazione, le risposte corrette contribuiranno al raggiungimento del voto finale.
Domande a risposta aperta
Verrà richiesto di (a) riassumere uno specifico argomento e/o descrivere un algoritmo e (b) risolvere un esercizio.
Esiti
L'esame è superato se viene raggiunta la sufficienza sia nelle domande a risposta chiusa, sia nelle domande a risposta aperta. In caso di compito gravemente insufficiente, non ci sono limitazioni a ripresentarsi ad uno degli appelli successivi: si confida tuttavia che lo studente si presenti agli appelli preparato o che chieda di non correggere la prova qualora ritenesse di aver svolto il compito in modo gravemente insufficiente.
Testi di riferimento
Materiale fornito dal professore
Periodo di erogazione dell'insegnamento
Secondo semestre
Lingua di insegnamento
Italiano
Sustainable Development Goals
Learning objectives
Learn the most relevant methods for solving optimization problems, with examples from real-life applications as well as algorithms for fitting statistical models and at the core of Machine Learning. The programming language will be Python, but also R libraries will be presented.
Contents
Basics, feasibility of an optimization problem, main types of optimization problems (linear, integer, non-linear), recap on geometry and linear algebra.
Linear and linear-integer programming
Non-linear programming and gradient-based methods
Black-box optimization and derivative-free methods.
Examples and exercises on problems inspired from real-life applications
Detailed program
Introduction
- Basic concepts of an optimization problem: decision variables, input data, objetive functions, constraints
- Feasibility of an optimization problem: feasible, infeasible, unlimited
- Relevant types of optimization problems: linear, convex, non-convex, black-box
- Recap about geometry and linear algebra
Linear Programming
- Examples for linear problems and simple graphical resolution
- Simplex algorithm and duality
Linear-Integer Programming
- Examples of linear-integer programing problems (assignment, knapsack, travel salesman problem)
- Hints about computational complexity: exact vs heuristic methods
- Branch & Bound
- Visiting nodes of a graph: in-depth search (for backtracking and detection of loops) vs in-breadth (for routing problems, Dijkstra's algorithm)
Non-linear programming
- Optimality conditions.
- Gradient-based method for unconstrained and constrained optimization
- Minimizing a loss function (or maximizing a likelihood function)
Black-box Optimization
- Derivative-free methods: meta-herustics methods (Tabu-Search, Simulatd Annealing, Genetic Algorithms, and Ant Colony Optimization for graph-related problems)
- Derivative-free methods: learning-and-optimization (an "overview" on Bayesian Optimization)
Prerequisites
No prerequisite
Teaching methods
22 hours of in-person lessons
8 hours of in-person laboratory and exercises
12 hours of remote laboratory and exercises
Assessment methods
The final exam consists of a written test and a subsequent discussion/acceptance of the final grade. Registration through the online system is mandatory.
The written test consists of 8 "multiple-choice" questions and 2 "open-ended" questions. The time available for the exam will be 2 hours.
Multiple choice questions
The multiple-choice questions will concern theoretical topics or will require you to identify the result of a simple exercise. A wrong answer will not give rise to any penalty, the correct answers will contribute to the achievement of the final grade.
Open-ended questions
You will be asked to (a) summarize a specific topice and/or describe an algorithm and (b) solving an exercise
Outcomes
The exam is passed if a sufficient grade is achieved both in the multiple-choice questions and in the open-ended questions. In the event of a seriously insufficient test, there are no limitations on returning to one of the subsequent exams: however, we are confident that the student will present himself for the exams prepared or that he will ask not to correct the test if he considers that he has carried out the task in a seriously insufficient way.
Textbooks and Reading Materials
Material provided by the Professor
Semester
Second semester
Teaching language
Italian
Sustainable Development Goals
Staff
-
Antonio Candelieri
