30553 - ADVANCED PROGRAMMING AND OPTIMIZATION ALGORITHMS
Course taught in English
Go to class group/s: 27
In order to successfully follow this course, students should be familiar with basic linear algebra and mathematical analysis.
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.
- 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.
|Continuous assessment||Partial exams||General exam|
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.