A normal fan projection algorithm for low-rank optimization

• 成果类型: Article
• 署名作者: Scott, James R.; Geunes, Joseph
• 署名单位: Texas A&M University System; Texas A&M University College Station; Duke University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02079-y
• 发表日期: 2025
• 页码: 681-702
• 关键词: concave minimization; search algorithms; arrangements; FPTAS

摘要

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.