Fall 2014

Semidefinite Programming Hierarchies I: Convex Relaxations for Hard Optimization Problems

Wednesday, August 27th, 2014 2:00 pm3:00 pm

Add to Calendar

Convex programming relaxations achieve for a broad range of computationally hard optimization problems the best known approximation guarantees. For many such problems, stronger relaxations are the most promising approach to obtain better and potentially optimal guarantees. We will discuss systematic methods for devising increasingly stronger relaxations, both in the linear programming and semidefinite programming case, and how to reason about their guarantees. We will introduce the sum-of-squares method which is a conceptually simple meta-algorithm that unifies all existing relaxation methods. Finally, we will illustrate its connections to spectral methods, proof complexity, and real algebraic geometry and applications to quantum information, multilinear algebra, sparse recovery, and machine learning.

The second session of this talk will take place on Thursday, August 28 from 11:30 am – 12:30 pm; the third session of this talk will take place on Friday, August 29 from 11:30 am – 12:30 pm.