Certification of real inequalities: Templates and sums of squares
File(s)1403.5899v2.pdf (774.62 KB)
Accepted version
Author(s)
Magron, V
Allamigeon, X
Gaubert, S
Werner, B
Type
Journal Article
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.
Date Issued
2014-11-12
Date Acceptance
2014-10-24
Citation
Mathematical Programming, 2014, 151 (2), pp.477-506
ISSN
1436-4646
Publisher
Springer
Start Page
477
End Page
506
Journal / Book Title
Mathematical Programming
Volume
151
Issue
2
Copyright Statement
© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. The final publication is available at Springer via https://dx.doi.org/10.1007/s10107-014-0834-5
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Software Engineering
Operations Research & Management Science
Mathematics, Applied
Computer Science
Mathematics
Polynomial optimization problems
Semidefinite programming
Semialgebraic relaxations
Maxplus approximation
Nonlinear template method
Certified global optimization
Global optimization
Publication Status
Published