A fundamental question in optimization is whether a polytope can be written as the projection of a simpler body in some space over which one can optimize efficiently. In this talk, I will consider the general question of when a given polytope P can be expressed as the image under a linear map of the intersection of a closed convex cone K with an affine space. In 1991, Yannakakis proved that when K is a positive orthant, the answer depends on the existence of a nonnegative factorization of the slack matrix of P of size equal to the dimension of the orthant. We generalize this result to arbitrary closed convex cones, and in the process, define a notion of K-factorization of a nonnegative matrix. When the cones K come in a family such as the family of positive orthants of varying dimension or the family of positive semidefinite cones, we obtain notions of ranks of a polytope and relations among these ranks.
Joint work with Joao Gouveia and Pablo Parrilo
Copyright. All Rights Reserved.