Course Announcement (text file)

Lecture: TR 11:40-12:55, in Phillips 307. Office hours: MT 2:30-3:30; W 1:30-2:30 or by appointment.

Here are the lecture notes:

- lec01.pdf (and as a template, the tex file).
- 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
- lec16.pdf
- lec17.pdf
- lec18.pdf
- lec19.pdf
- lec20.pdf
- lec21.pdf
- lec22.pdf
- lec23.pdf
- lec24.pdf
- lec25.pdf
- lec26.pdf
- lec27.pdf
- lec28.pdf

Here are the homeworks and final:

Some books/course notes:

- Bernd Gaertner and Jiri Matousek's book on Approximation Algorithms and Semidefinite Programming.
- Yinyu Ye's lecture notes on Linear Conic Optimization.
- 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 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.
- Anthony So and Yinyu Ye's paper on SDP relaxations for sensor localization.
- The Goemans-Williamson paper on MAXCUT.
- Laszlo Lovasz's Shannon capacity paper.
- Don Knuth's survey paper on Lovasz's sandwich theorem for $\vartheta$.
- Alper Yildirim and Xiaofei Fan-Orzechowski's paper on using the Lovasz theta function to extract a maximum stable set for perfect graphs.
- Michel Goemans's survey paper on SDP in combinatorial optimization.
- Pablo Parrilo's paper on SDP approaches to semialgebraic (polynomial optimization) problems.
- Renato Monteiro's paper on methods for solving SDPs.
- Christoph Helmberg's and Franz Rendl's paper on spectral bundle methods for SDP.
- My paper
on potential-reduction algorithms, mostly for linear
programming but Section 8 deals with extensions including SDP.

There are also chapters on applications and path-following and potential-reduction methods in - The Handbook on Semidefinite Programming, online here, and that on semidefinite, conic, and polynomial programming here.
- Some useful references are here.
- And here is a bibliography on SDP compiled by Henry Wolkowicz.

Useful sites

- Home pages on SDP: Christoph Helmberg's and Farid Alizadeh's. Both have links to papers and software; the second is very much out of date, but can also be helpful.
- A useful page from Henry Wolkowicz.
- The Interior-Point Methods Online and Optimization Online archives.
- The software package SDPT3.
- Some benchmark results by Hans Mittelmann can be found here.
- The DIMACS challenge on SDP and results of some codes.

Click to send e-mail to Mike Todd (mjt7@cornell.edu),