30553 - ADVANCED PROGRAMMING AND OPTIMIZATION ALGORITHMS
Department of Computing Sciences
Course taught in English
Course Director:
MAREK ELIAS
MAREK ELIAS
Conoscenze pregresse consigliate
In order to successfully follow this course, students should be familiar with basic linear algebra and mathematical analysis.
Mission e Programma sintetico
MISSION
Optimization is in the core of both Computer Science and Machine Learning. This course covers fundamental techniques for solving optimization problems, namely linear programming as well as discrete and convex optimization. Students will learn how to recognize problems which can be solved efficiently and formulate problems in the language of optimization. They will also get familiar with software tools and libraries which can be used to solve optimization problems.
PROGRAMMA SINTETICO
- Convex geometry: polyhedra, convex sets, and convex functions
- Linear programming: formulation of linear programs, simplex method, duality
- Integer linear programming: total unimodularity, matchings, matroids, submodular optimization, heuristics
- Convex optimization: formulation of convex programs, duality, gradient descent, Newton method
- Non-convex optimization: heuristics
Risultati di Apprendimento Attesi (RAA)
CONOSCENZA E COMPRENSIONE
Al termine dell'insegnamento, lo studente sarà in grado di...
- Describe the main algorithms for linear and convex optimization.
- Explain the basic properties of polyhedra, convex sets, and convex functions.
- Recognize problems for which exact optimization algorithms exist.
CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE
Al termine dell'insegnamento, lo studente sarà in grado di...
- Formulate complex computational problems in the language of optimization.
- Apply advanced programming and optimization techniques to solve optimization problems.
- Implement algorithms for solving optimization problems.
Modalità didattiche
- Lezioni frontali
- Esercitazioni (esercizi, banche dati, software etc.)
- Lavori/Assignment individuali
DETTAGLI
Exercises: solving homework assignments to improve understanding of the discussed theoretical results
Individual assignments: Implement algorithms based on course topics to solve sample optimization problems.
Metodi di valutazione dell'apprendimento
| Accertamento in itinere | Prove parziali | Prova generale | |
|---|---|---|---|
|
x | x | |
|
x |
STUDENTI FREQUENTANTI E NON FREQUENTANTI
Written exam (76% of the final grade) consists of open and closed answer questions aimed to assess theoretical understanding of key concepts in optimization theory, ability to express complex computational problems as optimization problems, ability to describe the main optimization techniques covered, and recognize problems for which efficient exact algorithms exist.
Students can take a mid-term written exam and complete the written exam at the end of the course. In this case the weight is: 38% for the mid-term exam and 38% for the end
of term exam. Alternatively, students can take a final written exam that accounts for 76% of the final grade.
Individual assignments (24% of the final grade) consist of 4 programming assignments to implement optimization algorithms and solve sample optimization problems.
Materiali didattici
STUDENTI FREQUENTANTI E NON FREQUENTANTI
1. Jiri Matousek Bernd Gartner. Understanding and Using Linear Programming. Springer, Berlin, Heidelberg (2007). ISBN 978-3-540-30697-9 (Soft cover), ISBN 978-3-540-30717-4 (eBook)
2. Convex Optimization by Boyd and Vandenberghe (2004), PDF available at https://stanford.edu/~boyd/cvxbook/
Further readings will be distributed on blackboard during the course.
Modificato il // :