Insegnamento a.a. 2022-2023

30553 - ADVANCED PROGRAMMING AND OPTIMIZATION ALGORITHMS

Department of Computing Sciences

Course taught in English
Go to class group/s: 27
BAI (8 credits - II sem. - OB  |  INF/01)
Course Director:
MAREK ELIAS

Classes: 27 (II sem.)
Instructors:
Class 27: MAREK ELIAS


Lezioni della classe erogate in presenza

Suggested background knowledge

In order to successfully follow this course, students should be familiar with basic linear algebra and mathematical analysis.

Mission & Content Summary

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.

CONTENT SUMMARY

  • 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 
     

Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • 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.
     

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • 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.
     

Teaching methods

  • Face-to-face lectures
  • Exercises (exercises, database, software etc.)
  • Individual assignments

DETAILS

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.
 


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
  x x
  • Individual assignment (report, exercise, presentation, project work etc.)
x    

ATTENDING AND NOT ATTENDING STUDENTS

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.


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

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.

Last change 03/02/2023 07:56