On the convergence of critical points on real algebraic sets and applications to optimization

2025/06/25 by Saugata Basu, Basu, Saugata, Ali Mohammad-Nezhad +1
Computer Science · Mathematics · #14P10 #90C23 #90C51 #Advanced Differential Equations and Dynamical Systems #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #FOS: Mathematics #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2506.20565

openalex publication_date 2025/06/25 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28

Abstract

Let F ∈ \R[X₁,…,X_n] and the zero set V=\zero(P,\Rⁿ), where P:=\P₁,…,P_s\ ⊂ \R[X₁,…,X_n] is a finite set of polynomials. We investigate existence of critical points of F on an infinitesimal perturbation V_ξ = \zero(\P₁-ξ₁,…,P_s-ξ_s\,\Rⁿ). Our main motivation is to understand the limiting behavior of local minimizers of the log-barrier function (and central paths) in polynomial optimization, whose existence plays a fundamental role, in theory and practice, for modern interior point methods. We establish different sets of conditions that ensure existence, finiteness, boundedness, and non-degeneracy of critical points of F on V_ξ, respectively. These lead to new conditions for the existence, convergence, and smoothness of central paths of polynomial optimization and its extension to non-linear optimization problems involving definable sets and functions in an o-minimal structure. In particular, for non-linear programs defined by real globally analytic functions, our extension provides a stronger form of the convergence result obtained by Drummond and Peterzil.

Citations

• On the complexity of analyticity in semi-definite optimization
• On the central path of semidefinite optimization: Degree and worst-case convergence rate
• The degree of the central curve in semidefinite, linear, and quadratic programming
• Stochastic subgradient method converges on tame functions
• Critical Point Computations on Smooth Varieties: Degree and Complexity bounds
• Multi-degree bounds on the Betti numbers of real varieties and semi-algebraic sets and applications
• Algorithms in Real Algebraic Geometry: A Survey
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods
• A baby step-giant step roadmap algorithm for general algebraic sets
• On the Curvature of the Central Path of Linear Programming Theory
• Interior Methods for Nonlinear Optimization
• The Field of Reals with Multisummable Series and the Exponential Function
• Geometric categories and o-minimal structures

Related

• Exact polynomial optimization strengthened with Fritz John conditions
• The Hierarchy of Local Minimums in Polynomial Optimization
• A remark about polynomials with specified local minima and no other critical points
• On the computation of asymptotic critical values of polynomial maps and applications
• Polynomial Optimization with Real Varieties