Course 2021-2022 a.y.

• 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 
   

• 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.
   

• 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.
   

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

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.
 

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.

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.