ORIE 637 Spring 2008

Semidefinite Programming

Course Announcement (text file)

Note: first class 3/10, 11:15, in Phillips 213.
**Time and Room Change. Starting March 24th, we'll meet on Mondays and Wednesdays from 10:50 to 12:05 in Upson 211.**

Here are the lecture notes:

• lec01.pdf
• lec02.pdf
• lec03.pdf
• lec04.pdf
• lec05.pdf
• lec06.pdf
• lec07.pdf
• lec08.pdf
• lec09.pdf
• lec10.pdf
• lec11.pdf
• lec12.pdf
• lec13.pdf
• lec14.pdf
• lec15.pdf

Here is the final exam, due Wednesday at 10 am.

Here is HW1, due Wednesday March 26th.

Here is HW2, due Monday April 21st.

Here is HW3, due Wednesday April 30th.

Some books/course notes (do *not* distribute!).

• Farid Alizadeh's lecture notes are here.
• Carsten Scherer and Siep Weiland's notes on linear matrix inequalities in control.
• David Williamson's notes on approximation algorithms , including SDP approaches for combinatorial optimization.
• Denis Arzelier's and Didier Henrion's lecture notes on LMI optimization and applications (this page is French, but the notes aren't!). See in particular the section on Relaxations LMI.
• Lieven Vandenberghe and Steve Boyd's SIAM Review paper on SDP.
• Michel Goeman's survey paper on SDP in combinatorial optimization.
• Don Knuth's survey paper on Lovasz's sandwich theorem for $\vartheta$.
• Laszlo Lovasz's Shannon capacity paper.
• The Goemans-Williamson paper on MAXCUT.
• Pablo Parrilo's paper on SDP approaches to semialgebraic problems.
• Renato Monteiro's paper on methods for solving SDPs.
• My paper on potential-reduction algorithms, mostly for linear programming but Section 8 deals with extensions including SDP.
  There are also chapters on path-following and potential-reduction methods in the Handbook on SDP -- follow the link below.
• The Handbook on Semidefinite Programming ps file.
• Some useful references are here.
• And here is a bibliography on SDP compiled by Henry Wolkowicz.

Useful sites

• Home pages on SDP: Farid Alizadeh's and Christoph Helmberg's. Both have links to papers and software.
• A useful page from Henry Wolkowicz.
• The Interior-Point Methods Online archive.
• The software package SDPT3.
• Some benchmark results by Hans Mittelmann can be found here.
• The DIMACS challenge on SDP and results of some codes.