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

[1] Practical Optimization - Algorithms and Engineering Applications, Andreas Antoniou Wu-Sheng Lu
[2] Practical Optimization Methods: With Mathematica Applications, M. Asghar Bhatti
[3] Introduction to Linear Optimization, Bertsimas and Tsitsiklis
[4] Multiplicative weights method: a meta-algorithm and its applications (A survey), Sanjeev Arora, Elad Hazan, and Satyen Kale
[5] Simulated annealing for convex optimization, Adam Kalai and Santosh Vempala
[6] Solving convex programs by random walks, Dimitris Bertsimas and Santosh Vempala
[7] Lagrangian Relaxation Based Algorithms for Convex Programming, Rohit Khandekar, Ph.D. Thesis

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