Formal Proofs for Global Optimization -- Templates and Sums of Squares

Abstract : The aim of this work is to certify lower bounds for real-valued multivariate functions, defined by semialgebraic or transcendental expressions and to prove their correctness by checking the certificates in the Coq proof system. The application range for such a tool is widespread; for instance Hales' proof of Kepler's conjecture involves thousands of nonlinear inequalities. The functions we are dealing with are nonlinear and involve semialgebraic operations as well as some transcendental functions like cos, arctan, exp, etc. Our general framework is to use different approximation methods to relax the original problem into a semialgebraic optimization problem. It leads to polynomial optimization problems which we solve by sparse sums of squares relaxations. First, we implement a classical scheme in global optimization. Namely, we approximate univariate transcendental functions with best uniform degree-d polynomial estimators. Then, we present an alternative method, which consists in bounding some of the constituents of the nonlinear function by suprema or infima of quadratic polynomials (max-plus approximation method, initially introduced in optimal control) with a carefully chosen curvature. Finally, we improve this approximation algorithm, by combining the ideas of the maxplus estimators and of the linear template method developed by Manna et al. (in static analysis). The nonlinear templates control the complexity of the semialgebraic estimators at the price of coarsening the maxplus approximations. In that way, we arrive at a new - template based - global optimization method, which exploits both the precision of sums of squares/SDP relaxations and the scalability of abstraction methods. We successfully implemented these approximation methods in a software package named NLCertify. This tool interleaves semialgebraic approximations with sums of squares witnesses to form certificates. It is interfaced with Coq and thus benefits from the trusted arithmetic available inside the proof assistant. This feature is used to produce, from the certificates, both valid underestimators and lower bounds for each approximated constituent. We illustrate the efficiency of NLCertify with various examples from the global optimization literature, as well as tight inequalities issued from the Flyspeck project.
Complete list of metadatas

Cited literature [93 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00917779
Contributor : Victor Magron <>
Submitted on : Thursday, December 12, 2013 - 1:54:44 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on : Friday, March 14, 2014 - 11:10:18 AM

Identifiers

  • HAL Id : pastel-00917779, version 1

Citation

Victor Magron. Formal Proofs for Global Optimization -- Templates and Sums of Squares. Optimization and Control [math.OC]. Ecole Polytechnique X, 2013. English. ⟨pastel-00917779⟩

Share

Metrics

Record views

586

Files downloads

479