The algebraic degree of sparse polynomial optimization

2023/08/15 by Julia Lindberg, Lindberg, Julia, Leonid Monin +3 · 1 citation
Computer Science · Mathematics · #14M25 #14Q20 #52B20 #90C26 #Advanced Differential Equations and Dynamical Systems #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.2308.07765

openalex publication_date 2023/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study a broad class of polynomial optimization problems whose constraints and objective functions exhibit sparsity patterns. We give two characterizations of the number of critical points to these problems, one as a mixed volume and one as an intersection product on a toric variety. As a corollary, we obtain a convex geometric interpretation of polar degrees, a classical invariant of algebraic varieties, as well as Euclidean distance degrees. Furthermore, we prove the BKK generality of Lagrange systems in many instances.

Cited by

• The Critical Point Degree of a Periodic Graph

Related

• Optimization of Polynomials with Sparsity Encoded in a Few Linear Forms
• Algebraic Degree of Polynomial Optimization
• Sparse Polynomial Optimization: Theory and Practice
• Algebraic degree of optimization over a variety with an application to p-norm distance degree
• Lower bounds in real algebraic geometry and orientability of real toric varieties