Lower bounds on the nonnegative rank using a nested polytopes formulation

Computing the nonnegative rank of a nonnegative matrix has been proven to be, in general, NP-hard. However, this quantity has many interesting applications, e.g., it can be used to compute the ex- tension complexity of polytopes. Therefore researchers have been trying to approximate this quantity as closely as possible with strong lower and upper bounds. In this work, we introduce a new lower bound on the nonnegative rank based on a representation of the matrix as a pair of nested polytopes. The nonnegative rank then corresponds to the minimum num-er of vertices of any polytope nested between these two polytopes. Using the geometric concept of supporting corner, we introduce a parametrized family of computable lower bounds and present preliminary numerical results on slack matrices of regular polygons.