Course 2024-2025 a.y.

30553 - ADVANCED PROGRAMMING AND OPTIMIZATION ALGORITHMS

Department of Computing Sciences

Course taught in English

Class timetable
Exam timetable
BAI (8 credits - II sem. - OB  |  INF/01)
Course Director:
MAREK ELIAS

Classi: 27 (I/II sem.)
Docenti responsabili delle classi:
Classe 27: 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
  • Prova individuale scritta (tradizionale/online)
  x x
  • Assignment individuale (relazione, esercizio, dimostrazione, progetto etc.)
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 // :