Rational Certification of Numerical Optimization

38 concepts24 papers1 proposal

When verifying safety-critical software or proving complex algebraic theorems, computer scientists and mathematicians are often caught between two opposing paradigms. On one side stands symbolic verification: exact, rigorous, and capable of producing absolute mathematical proofs. However, purely symbolic algorithms (such as Cylindrical Algebraic Decomposition) scale poorly, frequently hitting exponential or double-exponential complexity walls. On the other side stands numerical optimization: blazing fast, highly scalable, and capable of handling thousands of variables via floating-point algorithms like Semidefinite Programming (SDP). Yet, numerical methods suffer from rounding errors, truncation errors, and a fundamental lack of formal mathematical rigor.

A powerful hybrid paradigm bridges this gap: hybrid symbolic-numeric verification. The core intuition is elegant: use fast numerical optimization to find a candidate solution or witness rapidly, then use symbolic algebra to clean, round, and formally certify it. Instead of searching for a needle in a symbolic haystack, we use a numerical magnet to pull the needle out, and then use formal logic to verify that it is indeed the correct needle.

The Geometry of Rounding and Absorption

To understand why this hybrid approach works, let us look at a classic problem: proving that a multivariate polynomial is globally non-negative. One standard way to prove this is by finding a Sum of Squares (SOS) decomposition. If a polynomial $P(x)$ can be written as a sum of squared polynomials, $\sum f_i(x)^2$, it is indisputably non-negative for all real inputs.

Finding an SOS decomposition can be cast as a Semidefinite Program (SDP), which numerical solvers solve using floating-point arithmetic. However, because of floating-point inaccuracies, the solver will return a matrix of coefficients that is only approximately positive semidefinite. If you plug these coefficients back into the polynomial, you get an approximation, $P(x) \approx \sum f_i(x)^2$, leaving a tiny residual error that invalidates the strict mathematical proof.

How do we recover an exact proof from an approximate numerical output? The answer lies in the geometry of the solution space.

   Purely Numerical Solution             Hybrid Rational Solution
   (Floating-point, approximate)         (Rounded & error-absorbed)

          Cone of Positive                      Cone of Positive
            Polynomials                           Polynomials
         /**************/                      /**************/
        /  .-----------* /                    /  .-----------. /
       /  /   Approx   / /                   /  /   Exact   / /
      /  /   Numerical/ /                   /  /   Rational/ /
     /  /    Solution/ /                   /  /    Solution/ /
    /  *------------' /                   /  '-----------' /
   /**************/                      /**************/
          |                                     |
   Leaves a tiny residual error          Residual error is algebraically
   (Not a formal proof)                  absorbed (Absolute certainty)

The true solution space—the interior of the semidefinite cone—has volume. If our numerical optimization is sufficiently precise, the floating-point solution will land deep within this interior, meaning it has a small amount of geometric "breathing room."

As implemented by Victor Magron et al. in RealCertify: a Maple package for certifying non-negativity, we can exploit this breathing room by rounding the floating-point coefficients to the nearest rational numbers. Because the candidate solution sits safely inside the cone's interior, a small rounding step will not push it outside the valid space.

Once rounded, any remaining discrepancy between the original polynomial and the rational SOS candidate is handled via an algebraic technique known as perturbation and absorption. As shown by Victor Magron et al. in On Exact Polya and Putinar's Representations, the residual error polynomial can be systematically "absorbed" into the dominant positive terms of the decomposition. This yields an exact, human-readable rational certificate that can be verified by any standard computer algebra system or formal proof assistant like Coq, a workflow detailed by Xavier Allamigeon et al. in Certification of Bounds of Non-linear Functions: the Templates Method.

This division of labor has proven highly versatile:

Numerical Solutions as Formal Logic Witnesses

Beyond static polynomials, hybrid verification solves a major bottleneck in software and dynamical systems verification: finding inductive invariants. An invariant is a mathematical boundary enclosing all reachable states of a system; if you can prove the invariant never intersects an "unsafe" state, you have proven the system safe.

Finding these invariants symbolically is a brutal combinatorial search problem. In the hybrid paradigm, we offload this search to numerical engines. The numerical solver acts as a witness generator, proposing a candidate boundary that the symbolic engine merely has to check.

   Purely Symbolic Search                 Hybrid Witness Verification

   [Infinite Proof Space]                 [Numerical Solver]
             |                                    |  Generates a concrete
             | (Slow, combinatorial               v  geometric candidate
             |  search)                   [Candidate Invariant]
             v                                    |
   [Discovered Invariant]                         v (Fast, local check)
                                          [Symbolic Logic Engine]
                                                  |
                                                  v
                                          [Formal Certificate]

For instance, Assalé Adjé et al. demonstrated in Property-based Polynomial Invariant Generation using Sums-of-Squares Optimization that SOS optimization can numerically generate candidate polynomial invariants for non-linear programs. Similarly, Yijun Feng et al. in Finding polynomial loop invariants for probabilistic programs used numerical SDP solvers to discover quantitative loop invariants for complex probabilistic programs, subsequently validating them via exact symbolic methods like Cylindrical Algebraic Decomposition.

But how can a rigorous logic engine trust a floating-point numerical trajectory? André Platzer et al. solved this in Axiomatization of Compact Initial Value Problems: Open Properties by integrating symbolic representations of numerical solutions—such as Taylor polynomials or splines—directly into a formal differential dynamic logic. The numerical engine computes the trajectory, and the symbolic logic uses provable error bounds to construct a formal "tube" around that trajectory, guaranteeing the true continuous solution cannot escape.

This cooperation allows deductive theorem provers to scale to systems that were previously completely intractable. By utilizing numerical optimization to generate local Lyapunov functions, Nikos Aréchiga et al. introduced "forward invariant cuts" in Forward invariant cuts to simplify proofs of safety, breaking down massive global safety proofs for hybrid systems into small, mode-specific, numerically-guided pieces.

Managing Precision and Complexity

When systems are highly non-linear or recursive, finding an absolute, exact rational solution can become theoretically undecidable. In these challenging regimes, the hybrid paradigm shifts its objective from finding an exact solution to finding a soundly bounded numerical solution.

One prominent manifestation of this is $\delta$-satisfiability ($\delta$-SAT), pioneered in the dReal solver. As explained by Kyungmin Bae et al. in SMT Encoding of Hybrid Systems in dReal, instead of asking whether a non-linear system can exactly violate a safety property, $\delta$-SAT checks if a violation exists within a strictly bounded numerical precision $\delta$. By framing the problem this way, undecidable non-linear ordinary differential equations are transformed into decidable interval arithmetic problems.

To maintain mathematical soundness across continuous timelines, tools evaluated in the ARCH competition report by Luca Geretti et al. in ARCH-COMP21 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics combine interval arithmetic with validated integration schemes (such as validated Runge-Kutta methods). This ensures that floating-point rounding errors and truncation errors are captured inside rigorous mathematical enclosures, preventing the numerical solver from ever returning a false safety assurance.

This interplay between numerical exploration and symbolic validation continues to expand into other fields:

  • Probabilistic Verification: In recursive probabilistic systems, Ezio Bartocci et al. developed POPACheck: A Model Checker for Probabilistic Pushdown Automata, which pairs optimistic numerical value iteration for rapid convergence with SMT solvers to formally verify termination probabilities across millions of non-linear equations.
  • Algebraic Geometry: In Numerical algebraic geometry: a new perspective on gauge and string theories, Dhagash Mehta et al. demonstrated how Numerical Algebraic Geometry (NAG) uses certified numerical homotopy continuation to locate vacuum configurations in string theory. They leverage Smale's $\alpha$-theory to mathematically guarantee that a numerical approximation is a valid starting point for Newton's method to converge to a true, exact solution.
  • Model Reduction: When dealing with complex, over-parameterized models, Dhruva V. Raman et al. showed in Delineating parameter unidentifiabilities in complex models that numerical exploration can serve as a powerful pre-conditioning step, mapping out parameter redundancies before handing the system off to symbolic algebra for formal model reduction.
  • Exact Linear Inequalities: Even when dealing with highly sensitive irrational systems of inequalities where standard floating-point arithmetic fails completely, the integration of symbolic computation within defined algebraic fields allows researchers like Gennadiy Averkov et al. in The role of rationality in integer-programming relaxations to verify complex geometric configurations with absolute certainty.

Ultimately, the power of hybrid symbolic-numeric verification lies in its division of labor. Continuous numerical optimization excels at global exploration—navigating vast spaces to locate candidate solutions. Symbolic logic excels at local verification—rounding, bounding, and absorbing errors to construct unassailable mathematical certificates. By forcing numerical solvers to act as witness generators for symbolic checkers, this paradigm achieves the best of both worlds: the speed of continuous mathematics and the absolute certainty of formal logic.

Key Foundational Work

A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions (2009) — contributed 3 concept elements to this direction.
Numerical algebraic geometry: a new perspective on gauge and string theories (2012) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hybrid_symbolic_numeric_verification_a4300647,
  title = {hybrid symbolic-numeric verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hybrid-symbolic-numeric-verification/rdr_a4300647209c41b5b0ef072329c795ad},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_hybrid_symbolic_numeric_verification_a4300647_v1,
  title = {hybrid symbolic-numeric verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hybrid-symbolic-numeric-verification/rdr_a4300647209c41b5b0ef072329c795ad/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake