https://www.dagstuhl.de/15082

### February 15 – 20 , 2015, Dagstuhl Seminar 15082

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

## Organizers

Hartmut Klauck (Nanyang TU – Singapore, SG)

Troy Lee (National University of Singapore, SG)

Dirk Oliver Theis (University of Tartu, EE)

Rekha R. Thomas (University of Washington – Seattle, US)

## For support, please contact

## Documents

Dagstuhl Report, Volume 5, Issue 2

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Wiki

(Use seminar number and access code to log in)

## Summary

The topic of this seminar was the rapidly developing notion of *cone rank* of a matrix/polytope that is an important invariant controlling several properties of the matrix/polytope with connections to optimization, communication complexity and theoretical computer science. This meeting was a follow-up to the 2013 Dagstuhl seminar *13082: "Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices"* organized by Leroy Beasley, Hartmut Klauck, Troy Lee and Dirk Oliver Theis.

The cone rank of a nonnegative matrix is an ordered notion 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 was 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.

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. These formulations all write the underlying feasible set as the projection of an affine slice of a closed convex cone and is commonly refereed to as an extended formulation of the underlying feasible region. The nonnegative rank of a polytope is the smallest size of a linear extended formulation of the polytope while psd rank of the polytope is the size of the smallest possible semidefinite extended formulation of the polytope. Linear extended formulations are the best understood so far and an exciting development in this area is the recent breakthrough by Rothvoß showing that the matching polytope does not admit a polynomial sized linear extended formulation, settling a notorious open problem in combinatorial optimization. Very recently, there has also been exciting new developments in the area of psd rank such as the result of Lee, Raghavendra, and Steurer that shows that the psd rank of certain polytopes such as the traveling salesman polytope of a graph with n vertices must be exponential in n.

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.

**Summary text license**

Creative Commons BY 3.0 Unported license

Hartmut Klauck, Troy Lee, Dirk Oliver Theis, and Rekha R. Thomas

## Related Dagstuhl Seminar

- 13082: "Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices" (2013)

## Classification

- Data Structures / Algorithms / Complexity
- Optimization / Scheduling

## Keywords

- Linear
- Semidefinite
- And Combinatorial Optimization
- Matrix Theory
- Communication Complexity
- Information Theory
- Quantum Information
- Convex and Real Algebraic Geometry