TL;DR
This paper introduces a novel method for finding the global minimum of multivariate polynomials by leveraging the gradient variety. By reformulating the sum-of-squares (SOS) relaxation over this variety, the authors achieve faster convergence and improved performance compared to existing SOS techniques, even for problems where the gradient ideal is not radical.
What Problem Does This Paper Address?
Finding the global minimum of a multivariate polynomial is a fundamental problem in optimization, known to be NP-hard. A common approach is to use Sum of Squares (SOS) relaxations, which transform the problem into a Semidefinite Program (SDP). However, the standard SOS relaxation can be computationally expensive and may not always yield the exact global minimum, especially for polynomials that are nonnegative but not sums of squares. This gap leaves many challenging optimization problems unsolved. The paper addresses this by proposing a more efficient and robust SOS-based method that utilizes the gradient variety of the polynomial.
Methods
The core innovation lies in reformulating the SOS relaxation. Instead of requiring a polynomial to be a sum of squares in the entire polynomial ring, the authors require it to be a sum of squares modulo the gradient ideal. The gradient ideal is generated by all partial derivatives of the polynomial. This means we are looking for a polynomial $f(x) - \gamma$ to be a sum of squares of polynomials, where the sum of squares is taken in the quotient ring $R[x]/I_{grad}(f)$.
Key theoretical results include:
- Theorem 3.1: If the gradient ideal $I_{grad}(f)$ is radical and $f(x)$ is nonnegative on its gradient variety, then $f(x)$ can be expressed as a sum of squares modulo $I_{grad}(f)$.
- Theorem 3.5: If $f(x)$ is strictly positive on its real gradient variety, it is SOS modulo $I_{grad}(f)$, even if the ideal is not radical.
These theoretical underpinnings lead to a new SOS optimization problem (Equation 4.1) that is solved using SDP. The paper also extends these ideas to constrained optimization by considering the KKT (Karush-Kuhn-Tucker) system and its associated ideal.
Datasets
Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on generated polynomial families.
Key Insights and Ideas
- Gradient Variety as a Key: The critical insight is that all local and global minima of a polynomial occur on its gradient variety (where the gradient is zero). This geometric property is leveraged to constrain the SOS relaxation.
- SOS Modulo Gradient Ideal: The ability to express a polynomial as an SOS modulo its gradient ideal, even when the ideal isn't radical, is a significant theoretical breakthrough. This allows for finite convergence in many cases where standard SOS methods struggle.
- Faster Convergence: The new method, by incorporating gradient information, leads to faster convergence to the global minimum compared to traditional SOS relaxations.
- Handling Non-Radical Ideals: The paper provides a way to handle cases where the gradient ideal is not radical, which is a limitation of some existing methods.
Key Results
- Improved Performance: Numerical experiments show that the proposed method (formulation 4.1) is faster than the traditional SOS approach (formulation 1.2), using approximately three-quarters of the CPU time for the tested polynomial families.
- Accurate Lower Bounds: For polynomials where the infimum is attained, the method provides lower bounds that converge to the true minimum. In cases where the gradient ideal is radical, finite convergence is achieved.
- Effectiveness on Challenging Examples: The method successfully finds accurate lower bounds for polynomials that are nonnegative but not sums of squares, and for homogeneous polynomials.
Limitations and Future Work
- Attainability of Infimum: The theoretical results often rely on the assumption that the polynomial's infimum is attained. Verifying this property is a non-trivial problem that is not addressed.
- Radical Ideal Assumption: While the paper provides ways to handle non-radical ideals, the most robust theoretical guarantees (finite convergence) are often tied to the ideal being radical. Computing radicals of polynomial ideals is computationally expensive.
- Computational Cost for Many Constraints: For constrained optimization with many equality constraints, the computational cost can still be high due to the introduction of Lagrange multipliers.
- Future Work: The authors suggest exploring coordinate transformations and preprocessing for problems with many inequality constraints. Further research into the stability analysis of scaling and the speed-up from adding gradients is also mentioned. The paper also notes that if the gradient variety is infinite, extracting minimizers might require solving polynomial equations rather than relying solely on the rank condition.
Summary updated