Certification of Bounds of Non-linear Functions: the Templates Method

Xavier Allamigeon, Stéphane Gaubert, Victor Magron, Benjamin Werner

Abstract

The aim of this work is to certify lower bounds for real-valued multivariate functions, defined by semialgebraic or transcendental expressions. The certificate must be, eventually, formally provable in a proof system such as Coq. The application range for such a tool is widespread; for instance Hales' proof of Kepler's conjecture yields thousands of inequalities. We introduce an approximation algorithm, which combines ideas of the max-plus basis method (in optimal control) and of the linear templates method developed by Manna et al. (in static analysis). This algorithm consists in bounding some of the constituents of the function by suprema of quadratic forms with a well chosen curvature. This leads to semialgebraic optimization problems, solved by sum-of-squares relaxations. Templates limit the blow up of these relaxations at the price of coarsening the approximation. We illustrate the efficiency of our framework with various examples from the literature and discuss the interfacing with Coq.

Introduction

In fields ranging from control theory to formal mathematics, researchers frequently encounter the need to prove that a multivariate function $f(x)$ remains above a specific threshold $m$ over a defined set $K$. While numerical solvers can often find these bounds, they lack the rigor required for formal verification. This paper introduces a scalable framework for certifying lower bounds of complex, non-linear, and transcendental functions, ensuring they can be formally verified within proof assistants like Coq.

The Challenge of Non-linear Certification

The standard rigorous approach to this problem involves Lasserre’s hierarchy of Sum-of-Squares (SOS) relaxations, which transforms global optimization into Semidefinite Programming (SDP). However, this approach faces two significant hurdles:

  1. The Curse of Dimensionality: The size of the SDP problem grows exponentially as the number of variables or the polynomial degree increases.
  2. Transcendental Functions: Functions such as $\sin(x)$, $\exp(x)$, or $\arctan(x)$ are not polynomials. Standard methods to handle them, such as Taylor approximations or "lifting" (adding auxiliary variables), often lead to a computational explosion.

The Templates Method

The authors propose an algorithm called template_optim that integrates techniques from static analysis and optimal control to mitigate these issues. The method relies on three core pillars:

1. Semialgebraic Lifting

Non-polynomial components of a function are replaced by auxiliary variables governed by polynomial constraints. This allows the algorithm to treat transcendental functions within a semialgebraic framework.

2. Max-plus Approximation

Rather than relying on high-degree Taylor polynomials, the algorithm approximates transcendental functions from below using a supremum of quadratic forms, known as quadratic "cuts." By keeping the polynomial degree at two (quadratic), the method maintains computational efficiency while achieving high accuracy through the addition of multiple cuts.

3. Template-Based Coarsening

Borrowed from the field of static analysis, the "Templates Method" prevents the number of lifting variables from becoming unmanageable. When the complexity of the problem exceeds a certain threshold, the algorithm projects the feasible set onto a fixed number of quadratic inequalities (the "templates"), effectively coarsening the approximation to maintain scalability.

This process is iterative. The algorithm identifies a candidate minimizer, adds a new quadratic cut at that point to refine the bound, and repeats the cycle until the desired lower bound is certified. The resulting numerical SOS proof is then converted into a rational certificate for formal verification.

Experimental Evaluation

The framework was tested against standard global optimization benchmarks and real-world inequalities from the Flyspeck project (the formal proof of Kepler’s conjecture).

  • Scalability: The method successfully certified bounds for a Modified Schwefel problem involving up to 1,000 variables. Traditional interval arithmetic and standard SOS methods typically fail or time out on problems of this magnitude.
  • Efficiency: On a 10-variable Schwefel problem, the template method outperformed high-degree minimax polynomial approximations (via the Sollya tool) by a factor of 57.
  • Flyspeck Inequalities: The tool successfully certified several tight inequalities involving complex compositions of transcendental functions, such as sums of arctangents, which are notoriously difficult to automate.

Conclusion and Future Work

The Templates Method provides a robust path forward for the formal verification of large-scale non-linear inequalities. While the numerical phase is highly efficient, the authors note that the formal verification step in Coq remains a bottleneck, often taking significantly longer than the initial solve. Future research will focus on improving Coq’s libraries for algebraic numbers and further exploiting problem sparsity and symmetry to enhance scalability.

Summary updated

Abstract

The aim of this work is to certify lower bounds for real-valued multivariate functions, defined by semialgebraic or transcendental expressions. The certificate must be, eventually, formally provable in a proof system such as Coq. The application range for such a tool is widespread; for instance Hales' proof of Kepler's conjecture yields thousands of inequalities. We introduce an approximation algorithm, which combines ideas of the max-plus basis method (in optimal control) and of the linear templates method developed by Manna et al. (in static analysis). This algorithm consists in bounding some of the constituents of the function by suprema of quadratic forms with a well chosen curvature. This leads to semialgebraic optimization problems, solved by sum-of-squares relaxations. Templates limit the blow up of these relaxations at the price of coarsening the approximation. We illustrate the efficiency of our framework with various examples from the literature and discuss the interfacing with Coq.
BibTeX
@inproceedings{allamigeon2013certification,
  author = {Xavier Allamigeon and Stéphane Gaubert and Victor Magron and Benjamin Werner},
  title = {{Certification of Bounds of Non-linear Functions: the Templates Method}},
  booktitle = {MKM/Calculemus/DML},
  year = {2013},
  url = {https://openreview.net/forum?id=SexXDMwUFP},
}
Figure