zbMATH — the first resource for mathematics

Polyhedral approximation of multivariate polynomials using handelman’s theorem. (English) Zbl 06559857
Jobstmann, Barbara (ed.) et al., Verification, model checking, and abstract interpretation. 17th international conference, VMCAI 2016, St. Petersburg, FL, USA, January 17–19, 2016. Proceedings. Berlin: Springer (ISBN 978-3-662-49121-8/pbk; 978-3-662-49122-5/ebook). Lecture Notes in Computer Science 9583, 166-184 (2016).
Summary: Convex polyhedra are commonly used in the static analysis of programs to represent over-approximations of sets of reachable states of numerical program variables. When the analyzed programs contain nonlinear instructions, they do not directly map to standard polyhedral operations: some kind of linearization is needed. Convex polyhedra are also used in satisfiability modulo theory solvers which combine a propositional satisfiability solver with a fast emptiness check for polyhedra. Existing decision procedures become expensive when nonlinear constraints are involved: a fast procedure to ensure emptiness of systems of nonlinear constraints is needed. We present a new linearization algorithm based on Handelman’s representation of positive polynomials. Given a polyhedron and a polynomial (in)equality, we compute a polyhedron enclosing their intersection as the solution of a parametric linear programming problem. To get a scalable algorithm, we provide several heuristics that guide the construction of the Handelman’s representation. To ensure the correctness of our polyhedral approximation, our ocaml implementation generates certificates verified by a checker certified in coq.
For the entire collection see [Zbl 1329.68030].

68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: DOI