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 realworld background or twist. ''
Branches
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
 NoProofs Branch
The main difference between the branches is, obviously, that the Proofs Branch has proofs, whereas the NoProofs Branch doesn't. The Proofs Branch also looks at some of the mathematics which is required to understand how the algorithms work, whereas the NoProofs Branch is focused entirely on implementing the optimization models. On the other side, the NoProofs 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:0013:00 lecture, Mon 11:0014:00 software project
 "Proofs Branch" students attend: Tue 13:0014:00 lecture, Mon 10:0011:00 practice
 "NoProofs Branch" students attend: Tue 13:0014:00 + Mon 10:0011: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
 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
 LinearProgrammingBased Algorithms
 Algorithm for MinCostFlow (minimum cost transportation)
 Example of a PrimalDual approximation algorithm
 PrimalDual software project
 LinearProgramming Rounding Algorithms
 How approximate a hard problem by rounding an LP
 Example of an LProunding approximation algorithm
 LProunding software project
 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
 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
 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
 NonConvex Programming
 Why is that so difficult?
 Google TensorFlow (for First Order methods)
 TensorFlow software project
Addidional Material in the Proofs Branch
 Linear Programming, Integer Programming
 Separating Hyperplane theorem
 Linar Programming Duality theorem
 Complementary Slackness theorem
 von Neumann MinMax theorem
 LinearProgrammingBased Algorithms
 Proof of approximation guarantee
 LinearProgramming Rounding Algorithms
 Proof of approximation guarantee
 Quadratic Programming and Quadratically Constrainted Programming
 Review of positive definite matrices and their properties
 Lagrange dual
 General Convex Programming
 First order optimality conditions (KarushKuhnTucker)
 Crash course on Newton's method
 Understanding Interior Point methods
 Understanindg First Order methods
 Proof of approximation guarantee for Semidefinite Programming rounding algorithm
 Cone Programming w/ Algorithms
 Conic duality
 SumsOfSquares
 NonConvex Programming
Addidional Material in the NoProofs Branch
 Linear Programming, Integer Programming
 Lab: Learn to use Gurobi resources from Python
 LinearProgrammingBased Algorithms
 Lab: Learn the programming language Julia
 LinearProgramming Rounding Algorithms
 Quadratic Programming and Quadratically Constrainted Programming
 Lab: Learn to use Gurobi/QP from Python
 General Convex Programming
 Lab: Use Mosek resources
 Lab: TensorFlow resources
 Cone Programming w/ Algorithms
 Lab: Sparse matrix formats in Mosek (Python), SCS (C), and Julia
 NonConvex Programming
