An Efficient Framework for Global Non-Convex Polynomial Optimization with Algebraic Constraints

2023/11/03 by Mitchell Tong Harris, Pierre-David Létourneau, Harris, Mitchell Tong +5
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Software (cs.MS) #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2311.02037

openalex publication_date 2023/11/03 · openalex created_date 2023/11/07 · openalex updated_date 2026/07/28

Abstract

We present an efficient framework for solving algebraically-constrained global non-convex polynomial optimization problems over subsets of the hypercube. We prove the existence of an equivalent nonlinear reformulation of such problems that possesses essentially no spurious local minima. Through numerical experiments on previously intractable global constrained polynomial optimization problems in high dimension, we show that polynomial scaling in dimension and degree is achievable when computing the optimal value and location.

Related

• An Efficient Framework for Global Non-Convex Polynomial Optimization over the Hypercube
• On enforcing non-negativity in polynomial approximations in high dimensions
• Minimizing Polynomial Functions
• A Bounded Degree Lasserre Hierarchy with SOCP Relaxations for Global Polynomial Optimization and Applications
• Computing local minimizers in polynomial optimization under genericity conditions