Certification of real inequalities: templates and sums of squares

Victor Magron 1 Xavier Allamigeon 2, 3 Stéphane Gaubert 2, 3 Benjamin Werner 4
3 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We consider the problem of certifying lower bounds for real-valued multivariate transcendental functions. 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 polynomial optimization problems, which we solve by sparse sums of squares relaxations. In particular, we combine the ideas of the maxplus approximations (originally introduced in optimal control) and of the linear templates (originally introduced in static analysis by abstract interpretation). The nonlinear templates control the complexity of the semialgebraic relaxations at the price of coarsening the maxplus approximations. In that way, we arrive at a new—template based—certified global optimization method, which exploits both the precision of sums of squares relaxations and the scalability of abstraction methods. We analyze the performance of the method on problems from the global optimization literature, as well as medium-size inequalities issued from the Flyspeck project.
Type de document :
Article dans une revue
Mathematical Programming B, Springer, 2014, pp.30. 〈10.1007/s10107-014-0834-5〉
Liste complète des métadonnées

Contributeur : Xavier Allamigeon <>
Soumis le : mercredi 17 décembre 2014 - 15:54:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:34



Victor Magron, Xavier Allamigeon, Stéphane Gaubert, Benjamin Werner. Certification of real inequalities: templates and sums of squares. Mathematical Programming B, Springer, 2014, pp.30. 〈10.1007/s10107-014-0834-5〉. 〈hal-01096485〉



Consultations de la notice