Lifts of Polytopes and Matrix Factorization

Linear programming is an ubiquitous technique used in a wide variety of disciplines, ranging from scheduling and planning in management, to signal processing and control theory in engineering. From a mathematical point of view, linear programming is the problem of maximizing a linear function over a polytope. In order to solve such an optimization problem in practice, it is important to have a concise description of the polytope under consideration. Consider for example the hexagon depicted in Figure 1 (left), which is a simple example of a polytope. The hexagon has six sides and thus the "trivial" representation of the hexagon requires six linear inequalities, one for each side. The picture in Figure 1 (right) shows however that one can obtain a smaller representation of the hexagon using only five linear inequalities: indeed, the figure shows that the hexagon can be expressed as the projection of a three-dimensional polytope with only five facets (the polytope in green). Mathematically, this means that by introducing one auxiliary variable, the number of linear inequalities needed to represent a hexagon can be reduced from six to five. This phenomenon, whereby one can obtain a more efficient representation of a set by going to a higher-dimensional space is well-known in the optimization community and is commonly known as "lifting".

A fundamental question in optimization is to determine the smallest possible lift for a given polytope P, i.e., to find a polytope Q that projects onto P with the smallest number of facets. To investigate this question, we study a quantity known as the nonnegative rank which is defined for matrices with nonnegative entries. The connection between the nonnegative rank and lifts of polytopes was established in a remarkable theorem by Yannakakis where he showed that the nonnegative rank of a certain matrix is equal to the size of the smallest linear programming lift of a given polytope. Unfortunately however, the nonnegative rank is very hard to compute in general and researchers have been looking at ways to obtain efficient lower and upper bounds on this quantity. In a recent paper, we developed a new technique to obtain a lower bound on the nonnegative rank which improves on previously existing techniques. One interesting aspect of the bound we propose is that it allows to bridge two seemingly different methods from the literature to bound the nonnegative rank. Also the technique we propose can be applied to a wide variety of other rank functions such as the nonnegative tensor rank or the so-called completely-positive-rank.

The question of finding an efficient representation of a polytope can actually be posed in the broader context of conic programming, which is a far-reaching generalization of linear programming. For example, instead of representing a polytope as the projection of another polytope, we can ask instead to represent the polytope as the projection of a so-called "spectrahedron": a spectrahedron is a particular type of convex set that arises in semidefinite programming and is defined using linear matrix inequalities (LMIs). In a recent paper, we studied lifts using spectrahedra for a certain specific class of polytopes with a rich symmetry structure. For these symmetric polytopes, we looked at lifts that respect their symmetry and we investigated the question of how small such lifts can be. By establishing a connection with so-called sum-of-squares hierarchies we proved that, for the well-known cut polytope family, any symmetric semidefinite programming lift must have exponential size.

There are many questions pertaining to lifts of polytopes that still remain open. For example a question that is still largely open is to study semidefinite programming lifts that are not symmetry-preserving. It was shown in the context of linear programming lifts that breaking the symmetry of polytopes can greatly help in obtaining smaller lifts, but this question is not yet resolved in the case of semidefinite programming.