This paper, presented at the intersection of formal verification and global optimization, introduces a scalable method for certifying lower bounds of complex, non-linear functions. By combining Semidefinite Programming (SDP) with a "templates" approach inspired by static analysis, the authors provide a framework capable of handling transcendental functions and thousands of variables—all while remaining compatible with formal proof assistants like Coq.
TL;DR
The authors propose a "Templates Method" to certify lower bounds for non-linear and transcendental functions by approximating them with suprema of quadratic forms. This approach prevents the computational "blow-up" typical of standard optimization hierarchies, enabling the formal verification of large-scale inequalities like those found in the Flyspeck project (the formal proof of Kepler’s conjecture).
What Problem Does This Paper Address?
In fields like formal verification and control theory, researchers often need to prove that a multivariate function $f(x)$ never drops below a certain value $m$ over a set $K$. This is a global optimization problem.
While numerical solvers can find these bounds, they aren't "certified"—meaning a formal proof assistant like Coq cannot inherently trust the floating-point result. The standard rigorous approach uses Lasserre’s hierarchy of Sum-of-Squares (SOS) relaxations, which converts the problem into Semidefinite Programming (SDP). However, this faces two major hurdles:
- The Curse of Dimensionality: As the number of variables or the degree of the polynomial increases, the size of the SDP problem grows exponentially.
- Transcendental Functions: Functions like $\sin(x)$, $\exp(x)$, or $\arctan(x)$ are not polynomials. Handling them usually requires "lifting" (adding auxiliary variables) or Taylor approximations, both of which further exacerbate the scalability issue.
Methods
The authors introduce an algorithm called template_optim that blends three distinct fields:
- Semialgebraic Lifting: Non-polynomial parts of a function are replaced by auxiliary variables and polynomial constraints.
- Max-plus Approximation: Instead of using high-degree Taylor polynomials, the authors approximate transcendental functions from below using a supremum of quadratic forms (quadratic "cuts"). This keeps the polynomial degree low (degree 2) while allowing for high accuracy by simply adding more cuts.
- The Templates Method: Borrowed from static analysis, this method limits the number of "lifting variables." When the complexity of the problem exceeds a threshold, the algorithm "coarsens" the approximation by projecting the feasible set onto a smaller number of quadratic inequalities (the "templates").
The process is iterative: the algorithm finds a candidate minimizer, adds a new quadratic cut at that point to refine the bound, and repeats until the desired lower bound is certified. Finally, the numerical SOS result is converted into a rational certificate that Coq can formally verify.
Datasets
The authors evaluated their method on two main sets of benchmarks:
- Standard Global Optimization Problems: Classic test cases including Hartman 3, McCormick, Modified Langerman, Paviani, Shubert, and a Modified Schwefel problem.
- Flyspeck Project Inequalities: Real-world, "hard" inequalities involving many variables and transcendental functions (like sums of arctans) taken from the formal proof of Kepler’s conjecture.
Key Insights and Ideas
- Quadratic Cuts > High-Degree Polynomials: For large-scale problems, it is computationally cheaper to use many simple quadratic approximations than a few high-degree minimax polynomials. High-degree polynomials cause the SDP matrices to explode in size.
- Controlled Coarsening: The "Template" acts as a safety valve. By approximating complex projections of the feasible set with a fixed number of quadratic forms, the researchers can prevent the "lifting" process from generating too many variables for the SDP solver to handle.
- Dynamic Refinement: The algorithm doesn't pick approximation points blindly. It uses the current numerical minimizer as a "control point" for the next quadratic cut, ensuring the approximation is tightest exactly where the function is most likely to violate the bound.
Key Results
- Massive Scalability: The method successfully certified bounds for the Modified Schwefel problem with up to 1,000 variables. Traditional interval arithmetic and standard SOS methods either timed out or failed to reach the required precision.
- Flyspeck Success: The tool certified several tight Flyspeck inequalities that involve complex compositions of transcendental functions, which were previously difficult to automate.
- Performance vs. Alternatives: On a 10-variable Schwefel problem, the template method was 57 times faster than using high-degree minimax polynomial approximations via the Sollya tool.
- Formal Proofs: The authors demonstrated the generation of exact rational certificates for the McCormick problem, though they noted that formal verification in Coq is currently much slower than the numerical phase (e.g., 13x slower to prove than to solve).
Limitations and Future Work
- Verification Overhead: While the numerical part is fast, the "formal" part (generating rational certificates and checking them in Coq) remains a bottleneck. The authors suggest that better Coq libraries for algebraic numbers and floating-point arithmetic are needed.
- Heuristic Dependency: The choice of "templates" and control points relies on heuristics. While effective in the paper, more robust strategies for choosing these could improve performance on irregular functions.
- Symmetry and Sparsity: The authors mention that further exploiting the inherent symmetry or sparsity of optimization problems could lead to even greater scalability in the future.
Summary updated