Abstract In this paper, we focus on computing local minimizers of a multivariate polynomial optimization problem under certain genericity conditions. Using a technique from computer algebra and the second-order optimality condition, we provide a univariate representation for the set of local minimizers. In particular, for the unconstrained problem, i.e., the constraint set is $${{\,\mathrm{\mathbb {R}}\,}}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mi>R</mml:mi> <mml:mspace/> </mml:mrow> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> , the coordinates of all local minimizers can be represented by the values of n univariate polynomials at the real solutions of a univariate system containing a polynomial equation and a polynomial matrix inequality. We also develop the technique for problems with equality/inequality constraints. Based on the above technique, we design algorithms to enumerate the local minimizers and provide some experimental examples based on hybrid symbolic-numerical computations. For the case that the genericity conditions fail, at the end of the paper we propose a perturbation technique to compute approximately a global minimizer, provided that the constraint set is compact.
This paper presents a novel approach for computing local minimizers of polynomial optimization problems, focusing on scenarios where certain genericity conditions hold. Unlike much of the existing literature which primarily targets global minima, this work offers a method for the exact symbolic enumeration of all local minimizers, an aspect crucial for applications in fields like computational chemistry (e.g., identifying stable molecular structures) and machine learning (e.g., enumerating diverse solutions in non-convex models).
The key innovation lies in transforming the multivariate polynomial optimization problem into a univariate one under specific genericity assumptions. For unconstrained problems, the method provides a univariate representation of all local minimizers. This means that the coordinates of these minimizers are expressed as univariate polynomials evaluated at the real roots of a single polynomial equation. This representation is derived by leveraging the first and second-order optimality conditions (i.e., critical points and positive definiteness of the Hessian matrix) in conjunction with powerful tools from computer algebra. Specifically, the paper introduces a symbolic algorithm, GRULOM, that computes the radical of the gradient ideal (an ideal generated by partial derivatives of the objective function) and uses a Gröbner basis in “shape position” to achieve this univariate parameterization. A similar approach is extended to constrained problems involving equality and inequality constraints. For equality constraints, Lagrange multipliers are incorporated, forming a Lagrangian function, and the same algebraic techniques are applied to its gradient ideal. Inequality constraints are handled by introducing squared slack variables, converting them into equality constraints, which then fall under the same framework.
For cases where the strict genericity conditions (e.g., zero-dimensionality of the gradient ideal or non-singularity of the Hessian on the critical set) are not met, leading to infinitely many local minimizers or degenerate Hessians, the paper proposes a perturbation technique. This technique aims to approximate a global minimizer by introducing a small perturbation term, ensuring that the perturbed problem satisfies the genericity conditions and can then be solved using the developed methods. The final approximate global minimizer is obtained by taking the limit as the perturbation goes to zero.
The methodology relies heavily on several main prior ingredients from commutative algebra and optimization theory. Foremost among these are the first and second-order optimality conditions, which define local minimizers. Algebraic geometry forms the computational backbone, particularly the theory of ideals and varieties (complex and real algebraic sets). The concept of zero-dimensional ideals is critical, as it ensures a finite number of critical points, enabling exact enumeration. Gröbner bases are indispensable for computing radical ideals, transforming ideals into specific forms like “shape position” (which directly yields univariate representations), and performing symbolic manipulations. The Shape Lemma is a cornerstone, providing the theoretical guarantee for obtaining such univariate representations when the critical points have distinct coordinates in one dimension. The use of Lagrange multipliers for equality-constrained optimization and the squared slack variable technique for inequality constraints are standard optimization tools. The paper also builds upon prior work in polynomial optimization that established genericity conditions for finite sets of critical points, and on results from perturbation theory for handling non-generic scenarios and approximating global minima.