ORIE 6327 Spring 2012
Semidefinite Programming
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:
Here are the homeworks and final:
HW1, due Thursday February 9th.
HW2, due Thursday March 8th.
HW3, due Thursday April 5th.
HW4, due Thursday April 19th.
The final, and
comments on its solution.
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
Click to send e-mail to
Mike Todd
(mjt7@cornell.edu),