2023/02/08 by Julia Lindberg, Lindberg, Julia, Leonid Monin +3
Computer Science · Mathematics · #13P25 #65H14 #90C23 #90C26 #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #Commutative Algebra and Its Applications #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2302.04117
openalex publication_date 2023/02/08 · openalex created_date 2023/02/13 · openalex updated_date 2026/07/28
In this paper we propose a method that uses Lagrange multipliers and numerical algebraic geometry to find all critical points, and therefore globally solve, polynomial optimization problems. We design a polyhedral homotopy algorithm that explicitly constructs an optimal start system, circumventing the typical bottleneck associated with polyhedral homotopy algorithms. The correctness of our algorithm follows from intersection theoretic computations of the algebraic degree of polynomial optimization programs and relies on explicitly solving the tropicalization of a corresponding Lagrange system. We present experiments that demonstrate the superiority of our algorithm over traditional homotopy continuation algorithms.