Course Announcement - Fall 2010

Math 275: Geometry of Convex Optimization

Instructor: Bernd Sturmfels

Office hours: Wednesdays 10:00-12:00 and by appointment
Contact: bernd at math, 925 Evans

Time and Place: Tuesdays and Thursdays, 8:00-9:30am, 6 Evans Hall

Prerequisites: Optimization and Algebraic Geometry at the undergraduate level (e.g. Math 170, Math 143 and Cox-Little-O'Shea).
Prior experience with mathematical software (e.g. Matlab, Maple, Mathematica or Magma). Willingness to get up early in the morning.

Syllabus: Convexity, Semidefinite Programming, Linear Matrix Inequalities, Polynomial Optimization, Computational Algebra, Real Algebraic Geometry.

Objective: This class offers an opportunity for graduate students with different backgrounds and interests to learn from each other.
To accomplish this, participants will work on course projects, ideally in teams of two or three, and present their findings in class.

Reading: The material will be drawn from various articles and books. The following titles are on 1-day reserve in the Math Library:
A. Barvinok: A Course in Convexity, American Math. Soc., 2002, QA639.5 .B37 2002
S. Basu, R. Pollack and M-F. Roy: Algorithms in Real Algebraic Geometry, Springer, 2006, QA564 .B38 2006
S. Boyd and L. Vandenberghe: Convex Optimization, Cambridge University Press, 2004, QA402.5 .B69 2004
D. Cox, J. Little and D. O'Shea: Using Algebraic Geometry, Springer, 1998, QA564 .C6883 1998
J. Lasserre: Moments, Positive Polynomials and their Applications, Imperial College Press, London, 2010, QA402.5 .L377 2010
M. Marshall: Positive Polynomials and Sums of Squares, American Math. Soc, 2008, QA3 .M283 no.146

Pablo Parrilo's course notes Algebraic Techniques and Semidefinite Optimization from Spring 2010 at MIT.
My book Solving Systems of Polynomial Equations, Amer.Math.Soc., CBMS Regional Conferences Series, No 97, Providence, 2002.

Software: Students are encouraged to familiarize themselves with some software tools. Possibilities include
Bertini, CVX, GloptiPoly, Macaulay2, QEPCAD, SAGE, Singular, SOSTools, Surfex, YALMIP.

Schedule of lectures:
August 26: Introduction to Spectrahedra
August 31: Minimizing Polynomial Functions
September 2: Convex Hull of a Space Curve
September 7: Philipp Rostalski: Wiki and Numerical Software
September 9: Polytopes and Linear Programming
September 14: The Central Path
September 16: Cynthia Vinzant: The Real Nullstellensatz
September 21: Convex Bodies and Their Algebraic Boundary
September 23: Raman Sanyal: Orbitopes and Theta Bodies
September 28: Lagrange Duality and Projective Duality
September 30: Shaowei Lin: Symbolic Software
October 5: The Optimal Value Function
October 7: Petter Branden: Hyperbolic Programming
October 12: Spectrahedra and Semidefinite Programming
October 14: Quartic Curves and Their Bitangents
October 19: Spectrahedral Shadows
October 21: Angelica Cueto and Felipe Rincon: Discriminants
October 26: Nonnegative Polynomials and Sums of Squares (after Greg Blekherman)
October 28: Nonnegative Polynomials and Sums of Squares (after Greg Blekherman)
November 2:
Daniel Plaumann: Computing Linear Matrix Representations
November 4: Ngoc Tran and Volkmar Welker: Mathematics of Statistical Ranking
November 9: Patrik Noren and Cynthia Vinzant: Convex Hulls of Monomial Curves
November 11: No class: Administrative Holiday
November 16: Avinash Bhardwaj and Anand Kulkarni: Recognition and Types of Spectrahedra
November 18: No class: Please attend the MSRI workshop
November 23: No class: Thanksgiving
November 25: No class: Thanksgiving
November 30: Natth Bejraburnin and Jonathan Terhorst
December 2: Jose Rodriguez and Charles Chen
December 6 (Monday, 9:00-noon, 939 Evans): Olya Mandelshtam, Andreas Gross, Thanh Vu and Qi Zhang

Homework: In the first eight weeks there will be regular assignments, posted here in pdf format:
Homework 1 is due Tuesday, September 7.
Homework 2 is due Tuesday, September 21.
Homework 3 is due Tuesday, October 5.
Homework 4 is due Tuesday, October 19.

Course project deadlines: The following dates are all Thursdays:
October 21: Project proposal is due
November 18: Preliminary report is due
December 9: Final paper is due

Grading: The course grade will be based on both the homework and the course projects. No need to worry about this.