TL;DR
This paper introduces a novel "nonlinear template" method for certifying lower bounds of complex real-valued functions, including transcendental ones. By combining the precision of sums-of-squares (SOS) relaxations with the scalability of abstract interpretation techniques (templates), the method offers a more efficient way to tackle challenging global optimization problems, particularly those arising in formal verification like the Flyspeck project.
What Problem Does This Paper Address?
Formally verifying mathematical inequalities, especially those involving transcendental functions and many variables, is a significant challenge. Traditional methods like interval arithmetic can be too coarse, while high-degree polynomial optimization (e.g., using sums of squares) becomes computationally intractable for larger problems. The authors aim to bridge this gap by developing a method that can certify lower bounds for these complex functions, drawing inspiration from both optimal control and static analysis. This is crucial for applications like the Flyspeck project, which requires rigorous verification of numerous intricate inequalities.
Methods
The core of the paper is the nonlinear template method. This approach iteratively refines approximations of the objective function. Key techniques include:
- Sums of Squares (SOS) Relaxations: A standard technique for obtaining certified lower bounds for polynomial optimization problems. The paper leverages Lasserre's hierarchy of SOS relaxations.
- Maxplus Approximations: Originally from optimal control, this method approximates functions from below using suprema of simpler functions (like quadratic polynomials). This provides a lower bound and a semialgebraic approximation.
- Nonlinear Templates: Inspired by static analysis, these are parametric families of sets used to approximate feasible regions or function properties. They help manage complexity by controlling the number of variables and constraints.
- Semialgebraic Lifting: A technique to transform semialgebraic optimization problems into polynomial optimization problems by introducing auxiliary "lifting" variables.
- Template Optimization Algorithm (
template_optim): An iterative algorithm that dynamically updates precision parameters (e.g., number of points for maxplus approximation, degree of polynomial approximation) and usestemplate_approxto refine bounds and approximations.
The novelty lies in the combination and adaptation of these techniques. Nonlinear templates are used to control the complexity of semialgebraic relaxations, offering a trade-off between the coarseness of maxplus approximations and the computational cost of high-degree SOS relaxations.
Datasets
The paper evaluates its method on:
- Global Optimization Literature: Examples like the Modified Schwefel Problem (H3, H6, MC, ML, SWF) are used to test the method's performance on standard benchmark problems.
- Flyspeck Project Inequalities: Several inequalities from the Flyspeck project are used as challenging test cases, particularly those involving transcendental functions and correlated variables.
No new datasets are introduced; rather, existing challenging problems are used for evaluation.
Key Insights and Ideas
- Bridging Precision and Scalability: The central idea is to combine the rigorous, precise bounds from SOS relaxations with the scalability of abstraction techniques like templates. This allows tackling problems that are too large for pure SOS or too complex for simple interval arithmetic.
- Template-Based Refinement: Nonlinear templates provide a structured way to approximate complex functions and feasible sets, allowing for controlled coarsening of approximations when direct SOS methods become too computationally expensive.
- Maxplus for Lower Bounds: Maxplus approximations are particularly useful for generating certified lower bounds of transcendental functions, which is a key requirement for proving inequalities.
- Handling Transcendental Functions: The method is designed to handle functions involving transcendental operations (like
arctan,sin,exp) by approximating them with semialgebraic functions. - Scalability through Approximation: By reducing the degree of polynomials or the number of lifting variables through approximations, the method can handle problems with more variables than traditional SOS methods.
Key Results
- The proposed nonlinear template method successfully certifies lower bounds for various global optimization problems and Flyspeck inequalities.
- Performance Comparison: The method demonstrates competitive or superior performance compared to interval arithmetic solvers (like
intsolver) and can handle problems with a moderate number of variables (10-100) where pure SOS methods would be intractable. - Efficiency Gains: For certain problems, using templates and approximations significantly reduces the number of lifting variables and computational time compared to standard semialgebraic optimization. For instance, Table 3 shows significant reductions in
Nliftingand time for Flyspeck inequalities. - Convergence Guarantees: The paper provides theoretical guarantees for the convergence of the approximations and the optimal values, under certain assumptions (e.g., Archimedean condition for quadratic modules).
Limitations and Future Work
- Approximation Coarseness: While templates improve scalability, they can lead to coarser approximations compared to high-degree SOS relaxations, potentially requiring more iterations or domain subdivisions to achieve a desired precision.
- Computational Cost: While more scalable than pure SOS, the method can still be computationally intensive, especially for very complex functions or when high precision is required. The time complexity can grow significantly with the relaxation order
k. - Future Work: The authors suggest extending the nonlinear template method to discrete-time optimal control problems, particularly the Mayer problem. This would involve applying templates in a forward fashion to analyze system dynamics. They also mention the potential for further research into improving the precision and efficiency of template generation and SOS relaxation.
Summary updated