15.02.15 - 20.02.15, Seminar 15082

Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.


Cone ranks of nonnegative matrices are new ordered notions of matrix rank with emerging applications in several fields. A well-known example is the nonnegative rank of a nonnegative matrix that appears in areas ranging from communication complexity, to statistics, to combinatorial optimization, and algebraic complexity theory. A related notion arising as an invariant in representations of convex sets as projections of affine slices of the positive semidefinite (psd) cone is the positive semidefinite (psd) rank. The psd rank is a very new quantity and is still relatively poorly understood.

The purpose of this seminar is to bring together researchers from optimization, computer science, real/convex/tropical algebraic geometry, and matrix theory, to discuss relevant techniques from each area that can contribute to the development of both the theory and computation of cone ranks and cone factorizations of nonnegative matrices, as well as their many emerging applications.

We now briefly review the appearance of cone ranks in each of these areas.

In optimization and computer science, a common approach to finding approximate solutions to NP-hard problems is to look at tractable convex relaxations of the problem as either a linear or semidefinite program. An optimal solution to such a relaxation gives a bound on the objective value of the original problem. While much previous work has focused on specific relaxations of a problem, or a family of relaxations coming from a hierarchy, cone ranks allow the study of the best possible linear, semidefinite, or other convex formulations of a NP-hard problem independent of specific construction methods. Linear extended formulations are the best understood so far and an exciting development in this area is the recent breakthrough by Rothvoss showing that the matching polytope does not admit a polynomial sized linear extended formulation, settling a notorious open problem in combinatorial optimization.

In the field of communication complexity, nonnegative and psd ranks are exactly characterized by a model of randomized and quantum communication complexity, respectively. This connection has allowed tools from communication and information theory to help create lower bounds for these ranks.

A central question in the field of real algebraic geometry is the semidefinite representability of convex sets. While polytopes only project to polytopes, affine slices of psd cones have much greater expressive power as their projections are convex sets, which allows the definition of psd rank for semi algebraic convex sets. Psd rank has inherent semi algebraic structure and its study crosses over into real and convex algebraic geometry, algebraic complexity, and semidefinite programming.