A normal fan projection algorithm for low-rank optimization

We devise a method for minimizing a low-rank quasiconcave objective function over a polytope by first projecting the polytope’s normal fan, then using the projected fan to obtain candidate solutions. When the polytope’s maximal number of nonparallel edges is bounded by a polynomial in its dimension, our method solves the problem in time that is polynomial in the number of variables and exponential in the rank of the objective function. We discuss several problems from previous literature that can be solved efficiently using this method. In all cases, our proposed algorithm matches or improves on the running time of existing problem-specific algorithms, while providing the first polynomial-time algorithm we know of for finding a spanning tree on a graph with multiple edge weight types, such that the product of the different weight types is minimized.