On Exact Polya, Hilbert-Artin and Putinar's Representations

Victor Magron, Mohab Safey El DinarXiv 2018 · arXiv · OpenReview

Abstract

We consider the problem of computing exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers. We provide a hybrid numeric-symbolic algorithm computing exact rational SOS decompositions with rational coefficients for polynomials lying in the interior of the SOS cone. The first step of this algorithm computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. Next, an exact SOS decomposition is obtained thanks to the perturbation terms and a compensation phenomenon. We prove that bit complexity estimates on output size and runtime are both singly exponential in the cardinality of the Newton polytope (or doubly exponential in the number of variables). Next, we apply this algorithm to compute exact Reznick, Hilbert-Artin's representation and Putinar's representations respectively for positive definite forms and positive polynomials over basic compact semi-algebraic sets. We also report on practical experiments done with the implementation of these algorithms and existing alternatives such as the critical point method and cylindrical algebraic decomposition.

Introduction

In the domains of formal verification, control theory, and global optimization, proving the non-negativity of multivariate polynomials is a fundamental challenge. A polynomial $f(x)$ is non-negative if it never drops below zero for any input. The gold standard for certifying this property is the Sum of Squares (SOS) decomposition. If a polynomial can be expressed as $f(x) = \sum s_i(x)^2$, its non-negativity is self-evident.

While Semidefinite Programming (SDP) solvers are typically used to find these decompositions, they generally rely on floating-point arithmetic. This results in "approximate" certificates that fail to satisfy the exact equality $f = \sum s_i^2$ due to rounding errors. For rigorous mathematical proofs or safety-critical formal verification, exact rational certificates are required. Traditional symbolic methods like Cylindrical Algebraic Decomposition (CAD) provide exactness but suffer from doubly exponential complexity in the number of variables, rendering them impractical for many real-world problems. This paper presents a hybrid numeric-symbolic framework that bridges this gap for polynomials lying in the interior of the SOS cone.

The Hybrid Numeric-Symbolic Framework

The authors introduce a suite of algorithms—intsos, Reznicksos, Hilbertsos, and Putinarsos—implemented in the Maple library multivsos. These algorithms compute exact rational SOS decompositions for various classical representations, including Reznick’s (for forms), Hilbert-Artin’s (for rational functions), and Putinar’s (for polynomials over constrained semi-algebraic sets).

The core of the framework is a four-step perturbation-compensation technique:

  1. Perturbation: Rather than solving for the input polynomial $f$ directly, the algorithm targets a "shrunken" version: $f_\epsilon = f - \epsilon \sum X^{2\alpha}$. The $\epsilon$ term acts as a safety buffer, ensuring the target lies strictly within the interior of the SOS cone.
  2. Numerical Solve: An arbitrary-precision SDP solver (such as SDPA-GMP) is employed to find an approximate Gram matrix for the perturbed polynomial $f_\epsilon$.
  3. Exact Recovery (Compensation): A key "compensation" phenomenon allows the small numerical errors inherent in the approximate decomposition to be absorbed by the $\epsilon$ buffer.
  4. Rounding and Projection: The resulting matrices are rounded to rational numbers. A final symbolic check ensures that the identity $f = \sum s_i^2$ holds exactly.

Theoretical Complexity and the Newton Polytope

A significant contribution of this work is the first-ever bit complexity analysis for exact multivariate SOS decompositions. The authors prove that the runtime and output size are singly exponential in the cardinality of the Newton polytope of the polynomial. Specifically, the runtime is shown to be $\tau^2 d^{d^{O(n)}}$, where $\tau$ represents the bit size of the coefficients, $d$ the degree, and $n$ the number of variables.

This complexity measure is more refined than traditional metrics, as it accounts for the sparsity and structure of the polynomial. However, the efficiency of this approach relies on the polynomial being in the interior of the SOS cone. If a polynomial is non-negative but touches zero (residing on the boundary of the cone), the perturbation buffer cannot be applied, necessitating a fallback to slower algebraic methods like the critical point method (RAGLib).

Experimental Evaluation

The multivsos library was evaluated against several benchmarks, including univariate polynomials from previous literature, classic "hard" multivariate polynomials (e.g., the Motzkin polynomial), and inequalities from the Flyspeck project.

Key findings from the experiments include:

  • Efficiency: multivsos frequently outperformed the "Rounding-Projection" algorithm, producing more compact and easily verifiable certificates.
  • Scalability: The tool successfully handled problems with up to 10 variables. In a notable test on the f859 benchmark (6 variables, degree 7), multivsos completed the task in approximately 300 seconds. In contrast, CAD-based methods failed to solve the problem within a reasonable timeframe.
  • Conciseness: The hybrid approach generates certificates that are significantly smaller than those produced by purely symbolic methods, facilitating easier integration with external proof assistants like Coq or Isabelle.

Conclusion

This research demonstrates that combining high-precision numerical solvers with symbolic recovery techniques offers a powerful alternative to traditional algebraic geometry for polynomial optimization. While the "boundary problem" remains a limitation for polynomials that are not strictly positive, the hybrid framework provides a scalable and efficient path for certifying a wide class of multivariate inequalities. Future work will explore extensions to non-commutative polynomial data and alternative certification schemes such as geometric programming relaxations.

Summary updated

Abstract

We consider the problem of computing exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers. We provide a hybrid numeric-symbolic algorithm computing exact rational SOS decompositions with rational coefficients for polynomials lying in the interior of the SOS cone. The first step of this algorithm computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. Next, an exact SOS decomposition is obtained thanks to the perturbation terms and a compensation phenomenon. We prove that bit complexity estimates on output size and runtime are both singly exponential in the cardinality of the Newton polytope (or doubly exponential in the number of variables). Next, we apply this algorithm to compute exact Reznick, Hilbert-Artin's representation and Putinar's representations respectively for positive definite forms and positive polynomials over basic compact semi-algebraic sets. We also report on practical experiments done with the implementation of these algorithms and existing alternatives such as the critical point method and cylindrical algebraic decomposition.
BibTeX
@misc{magron2018exact,
  author = {Victor Magron and Mohab Safey El Din},
  title = {{On Exact Polya, Hilbert-Artin and Putinar's Representations}},
  year = {2018},
  eprint = {1811.10062},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.10062},
}

Loading related content...

Figure