James Saunderson - University of Washington

Monday, November 23, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)

Title:

Semidefinite descriptions of regular polygons (and beyond)

Abstract:

Semidefinite programs are a family of convex optimization problems that generalize linear programs and can model a wide range of problems from areas as diverse as statistics, robotics, and combinatorial optimization. Despite this, understanding the expressive power and limitations of (small) semidefinite programs remains a significant challenge.

This talk is centered on new efficient descriptions of regular polygons (and related polytopes) in terms of the feasible regions of semidefinite programs. These constructions, for instance, give the first known family of polytopes with semidefinite programming descriptions that are asymptotically smaller than the best linear programming descriptions.

Based on joint work with Hamza Fawzi (MIT) and Pablo Parrilo (MIT).

Host is Greg Blekherman (greg@math.gatech.edu).