##### Dagstuhl Seminar 15082

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

##### ( Feb 15 – Feb 20, 2015 )

##### Permalink

##### 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)

##### Contact

- Susanne Bach-Bernhard (for administrative matters)

##### Dagstuhl Seminar Wiki

- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)

##### Impacts

- On the Linear Extension Complexity of Regular n-gons : also published in "Linear Algebra and its Applications" : article - Vandaele, Arnaud; Gillis, Nicolas; Glineur, Francois - Cornell University : arXiv.org, 2015. - 15 pp..
- On the Linear Extension Complexity of Regular n-gons : article - Vandaele, Arnaud; Gillis, Nicolas; Glineur, Francois - Elsevier, 2017. - pp. 217-239 - (Linear Algebra and its Applications ; 521. 2017 : article).

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.

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.

- Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
- LeRoy B. Beasley (Utah State University, US) [dblp]
- Greg Blekherman (Georgia Institute of Technology - Atlanta, US) [dblp]
- Daniel Dadush (CWI - Amsterdam, NL) [dblp]
- Ronald de Wolf (CWI - Amsterdam, NL) [dblp]
- Samuel Fiorini (University of Brussels, BE) [dblp]
- Nicolas Gillis (University of Mons, BE) [dblp]
- Francois Glineur (University of Louvain, BE) [dblp]
- João Gouveia (University of Coimbra, PT) [dblp]
- Sebastian Gruler (Universität Konstanz, DE)
- Alexander Guterman (Moscow State University, RU) [dblp]
- Volker Kaibel (Universität Magdeburg, DE) [dblp]
- Hartmut Klauck (Nanyang TU - Singapore, SG) [dblp]
- Kaie Kubjas (Aalto Science Institute, FI) [dblp]
- James R. Lee (University of Washington - Seattle, US) [dblp]
- Troy Lee (National University of Singapore, SG) [dblp]
- Arnau Padrol Sureda (FU Berlin, DE) [dblp]
- Kanstantsin Pashkovich (University of Waterloo, CA) [dblp]
- Teresa Piovesan (CWI - Amsterdam, NL) [dblp]
- Sebastian Pokutta (Georgia Institute of Technology, US) [dblp]
- Raman Sanyal (FU Berlin, DE) [dblp]
- Markus Schweighofer (Universität Konstanz, DE) [dblp]
- Yaroslav Shitov (NRU Higher School of Economics - Moscow, RU) [dblp]
- David Steurer (Cornell University, US) [dblp]
- Jonathan Swenson (University of Washington - Seattle, US)
- Dirk Oliver Theis (University of Tartu, EE) [dblp]
- Rekha R. Thomas (University of Washington - Seattle, US) [dblp]
- Hans Raj Tiwary (Charles University - Prague, CZ) [dblp]
- Antonios Varvitsiotis (National University of Singapore, SG) [dblp]
- Stefan Weltge (Universität Magdeburg, DE) [dblp]

##### Related Seminars

- Dagstuhl Seminar 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (2013-02-17 - 2013-02-22) (Details)

##### 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