Discrete optimization

MATH-261

This file is part of the content downloaded from Discrete optimization.
Course summary

This course is an introduction to linear and discrete optimization which is a ubiquitous paradigm in modern data science.

Warning: This is a mathematics course! While much of the content will be about algorithms having impact in practice, we will look at these from the angle of a mathematician/theoretical computer scientist. The most important prerequisite is advanced linear algebra I&II.

Syllabus

  • Linear optimization problems 
  • Convex geometry: Polyhedra, convex sets, Farkas' Lemma 
  • The simplex algorithm
  • Duality, Zero sum games: Von Neumann's theorem 
  • Analysis of algorithms: Gaussian elimination and running time of simplex algorithm
  • Ellipsoid method and convex optimization problems

Times and Places

  • Lectures on Tuesdays 10-12 (CM 1105), starting from February 18.
  • Exercise sessions on Tuesdays 8-10 (CM 1105), starting from February 25.


Forum

You may use the Ed Discussion forum for asking questions. 


Grading

Validation of the course will be 100% via a final exam during the exam session.  


Teaching team

Instructor: Friedrich Eisenbrand <friedrich.eisenbrand@epfl.ch>

TAs: Neta Singer <neta.singer@epfl.ch>, Jiaye Wei <jiaye.wei@epfl.ch>

SAs: Sayantan Biswas <sayantan.biswas@epfl.ch>, Mehdi Aziz Jelassi <mehdi.jelassi@epfl.ch>

Easter Break