Provable guarantees and complexity bounds for exact rational sum-of-squares certification from floating-point computations

The hybrid numeric-symbolic pipeline of Kaltofen, Li, Yang, and Zhi (ISSAC 2008) converts floating-point semidefinite-programming outputs into exact rational sum-of-squares (SOS) certificates proving rational lower bounds in global polynomial optimization, and it left open five guarantee questions: when rationalization preserves positive semidefiniteness, whether an SDP solve is needed to seed the refinement, whether orthogonal projection is the best rationalization step, how to extend to Artin-style rational-function SOS, and how required precision and certificate size scale. The Artin-style rational-function extension posed in the same conclusion is not part of the open core: it was resolved by the authors' journal version (Kaltofen, Li, Yang, and Zhi, J. Symbolic Comput. 47, 2012). The surviving open core is the guarantee and complexity theory of the practical rounding-projection pipeline: positive-semidefiniteness preservation for boundary and rank-deficient Gram matrices, reliability of SDP-free seeding of the Gauss-Newton refinement, the adequacy or optimality of orthogonal projection versus rationalization projections biased toward the positive-semidefinite cone, and precision and certificate-height bounds that scale with problem size.

Background

Minimizing a multivariate polynomial or rational function over the reals is a basic problem of nonlinear optimization with applications in control, program verification, and computer algebra. For data with rational coefficients, a lower bound $r$ for $\min_{x\in\mathbb{R}^n} f(x)/g(x)$ can be proved by an algebraic identity: if $f(X)-r\,g(X)$ is a sum of squares (SOS), meaning a finite sum $\sum_i q_i(X)^2$ of squared polynomials, then $f-r\,g\ge 0$ everywhere, so $r$ is certified. Writing $m_d(X)$ for the column vector of all monomials up to degree $d$, a polynomial of degree at most $2d$ is an SOS exactly when it can be written as $m_d(X)^T W\,m_d(X)$ for a positive semidefinite (PSD) symmetric matrix $W$, called the Gram or moment matrix; the coefficient equations are linear in the entries of $W$, so searching for $W$ is a semidefinite program (SDP).

Interior-point SDP solvers (SeDuMi, SOSTOOLS, YALMIP) compute such $W$ only in floating point: the returned matrix satisfies the linear constraints approximately, is only approximately PSD, and the true optimum may be an irrational algebraic number. Numeric SOS output is therefore not a proof; published examples even show numeric lower bounds exceeding known upper bounds. To close this gap, Kaltofen, Li, Yang, and Zhi (ISSAC 2008), extending the Macaulay 2 package of Peyrl and Parrilo, introduced a hybrid numeric-symbolic pipeline: (i) solve a sparsity-exploiting SDP numerically; (ii) refine the numeric SOS by a rank- and structure-preserving Gauss-Newton iteration (Gauss-Newton: the classical iterative linearization method for nonlinear least squares), reducing the backward error; (iii) replace the optimal value by a slightly smaller rational lower bound $\tilde r$; (iv) round the entries of $W$ to rationals and orthogonally project onto the affine subspace $\mathcal{X}=\{A=A^T:\ f(X)-\tilde r\,g(X)=m_d(X)^T A\,m_d(X)\}$ of symmetric matrices satisfying the coefficient equations exactly, by exact rational least squares; and (v) certify that the projected rational matrix $\widetilde W$ is PSD via an exact $L^TDL$ factorization (a symmetric rational matrix is PSD exactly when this factorization exists with nonnegative pivots). The resulting identity is an exact rational SOS certificate, and $\tilde r$ is a proven lower bound. On benchmark problems from hybrid symbolic-numeric computation (approximate greatest common divisors, nearest-factor distances, and a structured global-optimization model problem of S. M. Rump), the method certified lower bounds accurate to several decimal places, with rational certificate entries reaching over a thousand decimal digits; the largest Rump instance certified at fixed 15-digit precision was $n=14$. The paper also reports certifying Rump instances without solving any SDP, by initializing the Gauss-Newton refinement from random PSD matrices of prescribed rank, although that empirical validation extended only up to $n=10$.

The only known reliability guarantee is local: by a neighborhood, eigenvalue-gap type condition of Peyrl and Parrilo, sufficiently many digits eventually succeed provided the optimal Gram matrix stays PSD in a neighborhood, that is, lies in the interior of the PSD cone. At a true optimum, however, the Gram matrix is typically rank-deficient and hence on the boundary of the cone; the source paper reports that refining toward the exact target value pushes $W$ so close to the boundary that orthogonal projection fails to preserve semidefiniteness. The available remedies are heuristic (lower $\tilde r$ further, or raise precision), with no general bounds predicting when they work. Two further obstructions shape the problem. First, not every nonnegative polynomial is an SOS (a classical theorem of Hilbert; the Motzkin polynomial is the standard counterexample); by Artin's theorem, the solution of Hilbert's 17th problem, every nonnegative polynomial with rational coefficients is a sum of squares of rational functions, so fully general certificates need denominators. The source paper left this extension open; its own journal version later implemented it. Second, the cost of a certificate is governed by the logarithmic height of its rational numbers, that is, the number of digits in their numerators and denominators: under a well-conditionedness restriction the source paper shows the digit count grows at most quadratically in the dimension of $W$, while the best worst-case height bounds for purely symbolic methods grow exponentially in the number of variables. A complexity theory matching the practical pipeline has been missing.

Problem Statement

The problem is the guarantee gap left by the rationalization pipeline of Kaltofen, Li, Yang, and Zhi (ISSAC 2008), as stated in that paper's conclusion and remarks and still open for the practical rounding-projection methodology. The common objective is to turn the heuristically successful conversion of floating-point SOS computations into exact rational certificates into a procedure with provable correctness and resource guarantees. Concretely, for the step that maps a numeric Gram matrix $W$ to an exact rational certificate:

1. PSD preservation under rationalization. Characterize, by necessary-and-sufficient conditions or tight sufficient bounds, when rounding $W$ to rationals and orthogonally projecting it exactly onto the affine Gram hyperplane $\mathcal{X}=\{A=A^T:\ f(X)-\tilde r\,g(X)=m_d(X)^T A\,m_d(X)\}$ yields a PSD matrix, including the boundary case in which the true Gram matrix is singular or nearly rank-deficient. The existing Peyrl-Parrilo neighborhood condition covers only the interior case, and the fallback remedies (lowering $\tilde r$, raising precision) come with no general bounds.

2. SDP-dependence. Characterize the class of problems for which the Gauss-Newton refinement can be seeded without solving any SDP (the source paper validated this empirically only up to moderate sizes, Rump's model problem with $n\le 10$), with proven reliability rather than empirical success rates.

3. The projection step. Analyze whether orthogonal projection is adequate or optimal for preserving positive semidefiniteness near the cone boundary, or construct and analyze alternative exact rationalization projections biased toward the PSD cone.

4. Precision and certificate height. Prove bounds, as functions of the number of variables, the degree, the sparsity pattern, the rank, and the conditioning of the instance, on the floating-point precision the pipeline requires and on the logarithmic height of the rational coefficients of the certificates it produces (beyond the quadratic-in-dimension growth known under well-conditionedness), and on the computational cost of producing them; situate these against the general but far more expensive exact decision procedures for SOS over $\mathbb{Q}$.

These four questions jointly constitute the single objective above — a hybrid numeric-symbolic certification pipeline every step of which carries a provable guarantee. The further extension posed in the same conclusion, Artin-style sums of squares of rational functions in place of polynomial SOS, is not part of the open core: it was implemented and validated by the authors' journal version (Kaltofen, Li, Yang, and Zhi, J. Symbolic Comput. 47, 2012), which however restates the absence of principled rules with provable correctness and complexity guarantees and of scalable algorithms with provable resource bounds.

References

1. Erich Kaltofen, Bin Li, Zhengfeng Yang, Lihong Zhi, 'Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars', ISSAC 2008, pp. 155-164. DOI: 10.1145/1390768.1390792, https://doi.org/10.1145/1390768.1390792 (author copy: https://kaltofen.math.ncsu.edu/bibliography/08/KLYZ08.pdf)
2. Erich L. Kaltofen, Bin Li, Zhengfeng Yang, Lihong Zhi, 'Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients', Journal of Symbolic Computation 47 (2012). DOI: 10.1016/j.jsc.2011.08.002, https://doi.org/10.1016/j.jsc.2011.08.002
3. Helfried Peyrl, Pablo A. Parrilo, 'Computing sum of squares decompositions with rational coefficients', Theoretical Computer Science 409 (2008). DOI: 10.1016/j.tcs.2008.09.025, https://doi.org/10.1016/j.tcs.2008.09.025
4. Helfried Peyrl, Pablo A. Parrilo, 'A Macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients', SNC 2007. DOI: 10.1145/1277500.1277534, https://doi.org/10.1145/1277500.1277534
5. Mohab Safey El Din, Lihong Zhi, 'Computing rational points in convex semialgebraic sets and sum of squares decompositions', SIAM Journal on Optimization 20 (2010), pp. 2876-2889. DOI: 10.1137/090772459, https://doi.org/10.1137/090772459
6. Qingdong Guo, Mohab Safey El Din, Lihong Zhi, 'Computing rational solutions of linear matrix inequalities', ISSAC 2013. DOI: 10.1145/2465506.2465949, https://doi.org/10.1145/2465506.2465949
7. Simone Naldi, 'Solving rank-constrained semidefinite programs in exact arithmetic', ISSAC 2016. DOI: 10.1145/2930889.2930925, https://doi.org/10.1145/2930889.2930925
8. Dávid Papp, Sercan Yıldız, 'Sum-of-squares optimization without semidefinite programming', SIAM Journal on Optimization 29 (2019). DOI: 10.1137/17M1160124, https://doi.org/10.1137/17M1160124
9. Maria M. Davis, Dávid Papp, 'Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets', SIAM Journal on Optimization 32 (2022). DOI: 10.1137/21M1422574, https://doi.org/10.1137/21M1422574
10. Victor Magron, Mohab Safey El Din, 'On exact Reznick, Hilbert-Artin and Putinar's representations', Journal of Symbolic Computation 107 (2021). DOI: 10.1016/j.jsc.2021.03.005, https://doi.org/10.1016/j.jsc.2021.03.005
11. Victor Magron, Mohab Safey El Din, Trung-Hieu Vu, 'Sum of squares decompositions of polynomials over their gradient ideals with rational coefficients', SIAM Journal on Optimization 33 (2023). DOI: 10.1137/21M1436245, https://doi.org/10.1137/21M1436245
12. Victor Magron, Henning Seidler, Timo de Wolff, 'Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials', ISSAC 2019, pp. 291-298. DOI: 10.1145/3326229.3326271, https://doi.org/10.1145/3326229.3326271
13. Teresa Krick, Bernard Mourrain, Agnes Szanto, 'Univariate rational sums of squares', arXiv:2112.00490 (2021). DOI: 10.48550/arXiv.2112.00490, https://arxiv.org/abs/2112.00490
14. Zhenbing Zeng, Yong Huang, Lu Yang, Yongsheng Rao, 'A novel algorithm for representing positive semi-definite polynomials as sums of squares with rational coefficients', arXiv:2510.01568 (2025). DOI: 10.48550/arXiv.2510.01568, https://arxiv.org/abs/2510.01568