Teaching‎ > ‎

MTAT.05.120 Combinatorial and Convex Optimization (CooCoo)

This terms (spring 2017) course materials


Overview

This course teaches the optimization tools that computer scientists need. On the practical side, these are:
  • Learn to recognize an optimization problem when you see one.
  • Learn to determine what type of optimization problem it is.
  • Learn to decide which type of algorithm you need to solve it.
  • Learn to use the software libraries solving optimization problems.
For really understanding what is going on, and to create and solve more difficult optimization problems, more Theory is necessary:
  • Optimality conditions
  • Lagrange duality (including LP duality)
  • Algorithms based on Linear Programming and Semidefinite Programming; Sums of Squares.
The focus of the course is on practical examples.

What Students Say

What students taking the course in Spring '15 replied to the question, What would you say about the course to future students?
  • ``The practical tasks were really interesting.''
  • ``Interesting material, interactive teacher, and cool applications.''
  • ``Fun one, go for it. ''
  • ``The tasks given are fun in the sense of them having a real-world background or twist. ''

Branches

NEW! To better adapt to students' individual backgrounds and tastes, from this year on, the participants of the course can choose one of two branches:
  • Proofs Branch
  • No-Proofs Branch
The main difference between the branches is, obviously, that the Proofs Branch has proofs, whereas the No-Proofs Branch doesn't. The Proofs Branch also looks at some of the mathematics which is required to understand how the algorithms work, whereas the No-Proofs Branch is focused entirely on implementing the optimization models. On the other side, the No-Proofs branch gets to do some of the more technical stuff (learning the programming language Julia, working with the guts of the software libraries).

Practical Info

  • All students attend: Tue 12:00-13:00 lecture, Mon 11:00-14:00 software project
  • "Proofs Branch" students attend: Tue 13:00-14:00 lecture, Mon 10:00-11:00 practice
  • "No-Proofs Branch" students attend: Tue 13:00-14:00 + Mon 10:00-11:00 labs (getting started with software libraries etc)
  • Software projects are solved in groups, groups compete
  • Software projects are started in the software project session, then continued/finished as homework. (No other homework.)

Syllabus

Content Common to Both Branches

  1. Linear Programming, Integer Programming
    • What is that, that's the difference?
    • Using the Gurobi software library for LP, IP
    • Modeling applications as LPs, IPs
    • LP/IP software project
  2. Linear-Programming-Based Algorithms
    • Algorithm for Min-Cost-Flow (minimum cost transportation)
    • Example of a Primal-Dual approximation algorithm
    • Primal-Dual software project
  3. Linear-Programming Rounding Algorithms
    • How approximate a hard problem by rounding an LP
    • Example of an LP-rounding approximation algorithm
    • LP-rounding software project
  4. Quadratic Programming and Quadratically Constrained Programming
    • What is that?
    • Using the Gurobi software library for QP, QCP
    • Modeling applications as QPs, QCQPs
    • QP/QCP software project
  5. General Convex Programming
    • What is that?
    • Interior Point methods vs. First Order methods
    • Using the Ipopt, Mosek software libraries (Interior Point method)
    • A software for a First Order method (not decided yet, maybe TensorFlow)
    • Semidefinite Programming rounding algorithms
    • Convex Programming software project
  6. Cone Programming w/ Algorithms
    • What is that?
    • Using the SCS software library (First Order method)
    • Using the Mosek, CvxOpt software libraries (Interior Point method)
    • Semidefinite Programming rounding algorithms
    • Cone Programming software project
  7. Non-Convex Programming
    • Why is that so difficult?
    • NEW!Google TensorFlow (for First Order methods)
    • TensorFlow software project

Addidional Material in the Proofs Branch

  1. Linear Programming, Integer Programming
    • Separating Hyperplane theorem
    • Linar Programming Duality theorem
    • Complementary Slackness theorem
    • von Neumann MinMax theorem
  2. Linear-Programming-Based Algorithms
    • Proof of approximation guarantee
  3. Linear-Programming Rounding Algorithms
    • Proof of approximation guarantee
  4. Quadratic Programming and Quadratically Constrainted Programming
    • Review of positive definite matrices and their properties
    • Lagrange dual
  5. General Convex Programming
    • First order optimality conditions (Karush-Kuhn-Tucker)
    • Crash course on Newton's method
    • Understanding Interior Point methods
    • Understanindg First Order methods
    • Proof of approximation guarantee for Semidefinite Programming rounding algorithm
  6. Cone Programming w/ Algorithms
    • Conic duality
    • Sums-Of-Squares
  7. Non-Convex Programming
    • (No additional material)

Addidional Material in the No-Proofs Branch

  1. Linear Programming, Integer Programming
    • Lab: Learn to use Gurobi resources from Python
  2. Linear-Programming-Based Algorithms
    • Lab: Learn the programming language Julia
  3. Linear-Programming Rounding Algorithms
    • Learn using JuliaOpt
  4. Quadratic Programming and Quadratically Constrainted Programming
    • Lab: Learn to use Gurobi/QP from Python
  5. General Convex Programming
    • Lab: Use Mosek resources
    • Lab: TensorFlow resources
  6. Cone Programming w/ Algorithms
    • Lab: Sparse matrix formats in Mosek (Python), SCS (C), and Julia
  7. Non-Convex Programming
    • Lab: More TensorFlow