# Optimisation and Approximation

## General information

Lecture times: Tuesday, 10.15-12.15am.
Instructor: Nicolas Bousquet.
Teaching Assistant: Johanna Seif and Dewi Sintiari.
Email: firstname.lastname@grenoble-inp.fr

## Pre-requisites

Students should know the basics from Calculus and Linear Algebra.

## Content

Lecture notes (which will be updated all along the term) will be provided after each lecture (hopefully shortly after the lecture !). Exercises sessions will also be added. Note that all the exercises won't be treated during the lectures. The additional exercises are there to give you some material on which you can work on.

### Lectures

Lecture 1: Introduction to optimization.
Lecture 2: Introduction to polytopes.
Lecture 3: Simplex algorithm.
Lecture 4: Simplex algorithm - Initialization and Termination.
Lecture 5: Duality of LP.
Lecture 6: Sensitivity analysis.
Lecture 7: Totally unimodular matrices.
Lecture 8: Hitting sets and VC-dimension.
Lecture 9: Economic Game Theory.
Lecture 10 and 11 on rounding algorithms and primal dual algorithms follow the scheme of the lectures given by Alantha Newman two years ago: rounding algorithms and primal dual algorithms.

### Exercises sessions

TD1: Modelization and Linear Programming. (elements of correction)
TD2: Polytopes and simplex algorithm. (elements of correction)
TD3 & 4: Simplex algorithm. (elements of correction)
TD5: Duality.
TD6: Sensitivity analysis.
TD7: Totally unimodular matrices.
TD8: On Farkas' Lemma.
TD10: Primal dual algorithms and rounding algorithms.

### Homework

Homework 1: You have two choices, either you decide to implement the Simplex algorithm or you decide to make a more theoretical work. You have to do exactly one of them:
Simplex homework.
Extended formulation homework.
The deadline is the 30th of November, beginning of the lecture.

Homework 2: Deadline 11th of January, beginning of lecture. Homework 2.

Midterm 2017
Exam 2017

## Textbooks

• Understanding and Using Linear Programming, by Jiri Matousek and Bernd Gartner (2006).