Kursöversikt
Course-PM
TDA206/DIT370 Discrete optimization HT19 (7,5hp)
Departmen of Computer Science and Engineering.
Course purpose
The goal of the course is to introduce basic concepts of optimization, developing both the theory and applications. In roughly the first two-thirds of the course we will cover linear programming and its applications and in the last part we will introduce basic algorithms in convex optimization and their applications.
Schedule
Contact details
- Examiner and Lecturer: Devdatt Dubhashi (dubhashi@chalmers.se)
-
Course Assistants:
- Elisabet Lobo Vesga (elilob@chalmers.se)
- Divya Grover (divya.grover@chalmers.se)
- Simon Robillard (simon.robillard@chalmers.se)
- Course Representatives
-
Angelika Strandberg, angstr@stud.chalmers.se
-
David Donato, donatod@student.chalmers.se
-
Ted Eriksson tede@student.chalmers.se
-
Carl-Johan Heiker heikerc@student.chalmers.se
-
Ahmet Batikan Unal ahmetbatikan.94@gmail.com
-
Yonca Yunatci yyunatci95@gmail.com
-
Office hours
Office hours will normally take place on Wednesday and Friday afternoons.
- Friday 01/25 - 1pm-3pm - Simon - Room 5453
- Wednesdays 13-14, room 6472.
Course literature
For approximately the first two-thirds of the course, we'll use this little gem available from Chalmers library:
- [MG] Matousek, Jiri, Gärtner, Bernd, Understanding and Using Linear Programming, Springer 2007.
For the last part, we will use the following lecture notes:
- [J] Martin Jaggi (ETH Zurich) Optimization for Machine Learning
and this review article:
- [BCN] L. Bottou, F. Curtis and J. Nocedal, "Optimization Methods for Large Scale Machine Learning", SIAM Review2018.sirev-2018.pdf
Other good lecture notes covering the same topics are:
- Moritz Hardt (UC Berkeley): Convex Optimization and Approximation
- Nisheeth Vishnoi (ETH Zurich, Yale): Algorithms for Convex Optimization
The following are good textbooks on convex optimization:
- S. Boyd and L. Vandenberghe. Convex Optimization (available for free)
-
G. Calafiore, L. El Ghaoui. Optimization Models. Cambridge University Press, October 2014.
We will use the CVX programming framework.
Course design
Lectures
| Date | Topic | Reading |
| 21/1 | Introduction, LP models 1 | [MG, Chap. 1, 2.1-2.3] |
| 23/1 | LP models 2 | [MG, 2.4-2.7] |
| 28/1 | Integer LP | |
| 30/1 | Rounding LPs | |
| 11/2 | Basics of Convexity | |
| 13/2 | Simplex | |
| 18/2 | Branch and Bound | |
| 20/2 | LP in Industry | |
| 25/2 | Duality theory | |
| 27/2 | Duality examples | |
| 4/3 | Primal-dual algorithms | |
| 6/3 | Convex Optimization/Gradient Descent | |
| 11/3 | Projected Gradient Descent and Frank Wolf Conditional Gradient Descent | |
| 13/3 | Non-convex Opt: Backpropagation |
Homeworks
- Homework 1 (deadline Jan. 28.)
- Homework 2 (deadline Feb. 11)
- Homework 3 (deadline March 11)
- Homework 4 (deadline April 4 )
Assignments should be submitted via Fire.
Unfortunately there will be no resubmissions and all deadlines are strict!
Python and CVXOPT
For the homework assignments, you will need to use Python and the package CVXOPT.
Installation
The required software should be installed on machines in the EDIT building. If you wish to install it on your own machine, follow these instructions. Make sure that your installation also includes the extension GLPK, which is needed for integer linear programming.
Using CVXOPT
The documentation provides a quick introduction to CVXOPT for linear programming.
Examination form
Evaluation will be based on
- Homework assignments (50%)
- Final written in-class exam (50%) (You may bring class notes and the textbook and notes above to the exam)
Learning objectives and syllabus
- Develop optimization models (linear and convex) for various problems.
- Solve them using the CVX programming environment.
- Develop integer constrained optimization models and understand their relation to their LP (and other) relaxations.
- Understand LP duality and how it can be applied, in particular to develop primal-dual algorithms.
Kurssammanfattning:
| Datum | Information | Sista inlämningsdatum |
|---|---|---|