2022/09/26 by Aida Khajavirad, Khajavirad, Aida · 2 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Commutative Algebra and Its Applications #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2209.13034
openalex publication_date 2022/09/26 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence, and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation that is a natural generalization of the flower relaxation introduced by Del Pia and Khajavirad 2018, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.