max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Optimization II (Winter semester 2011/12)

Basic Information

Lecture time: Wednesday 16:00-18:00
Lecture room: 023, Campus E 14
Lecturers: Khaled Elbassioni and Saurabh Ray
Tutorial time & place: TBA
Tutors: TBA
   

Description

This class is the follow-up to Optimization I, which is regularly offered during the Summer term. It is recommended, but not absolutely necessary to haven taken Optimization I in order to take Optimization II. The class will focus mostly on how to solve linear/convex programs, with emphasis on methods applied in practice. We will cover mainly 3 topics: Interior point methods (Potential reduction methods, path following methods, matrix scaling methods), multiplicative weight update methods, and sampling based methods.

Prerequisites: Basics in linear algebra, discrete mathematics, calculus, algorithms, and complexity. At Saarland University these topics are covered in the bachelor courses: Mathematik für Informatiker (1+2), Grundzüge der Theoretischen Informatik, Grundzüge von Algorithmen und Datenstrukturen.

This is a 6-credit-point course. There will be homeworks/programming assignments. There will be a midterm and a final exam. The final grade will be based on these two exams and the assignments.

References

Lectures

Date Topic Readings
Lecturer
19.10.2011
Warm-up: Some basics, KKT conditions and the Simplex method
Ch. 10, 11 in [1]

Khaled
26.10.2011
Affine scaling and the the potential reduction method Ch. 12 in [1] and Ch. 9 in [3]

Khaled
02.11.2011
Path following methods Ch. 12 in [1] and Ch. 9 in [3]

Khaled
09.11.2011
Primal-dual Path following method
Ch. 12 in [1] and Interior path following primal-dual algorithms. part I: Linear Programming

Khaled
23.10.2011
Linear Programming in Randomized Subexponential Time Linear Programming - Randomization and Abstract Frameworks

Saurabh
30.11.2011
Mutiplicative Weight Updates Method for convex packing-coveringi porblems
Ch. 5 in [7]
Fahimeh
11.01.2012
Solving Convex Programs Programs by Random Walks 
Bertsimas-Vempala Paper

Saurabh
18.01.2012
Solving Convex Programs Programs by Random Walks contd.

Saurabh
25.01.2012
Simulated Annealing for Convex Optimization
Kalai-Vempala Paper

Saurabh
01.02.2012
Proving High Conductance of Geometric Random Walks
Chapter 6 of Mark Jerrum's Book

Saurabh
08.02.2012
Jerrum-Sinclair Inequality


Saurabh

































More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)