Handelman rank of zero‐diagonal quadratic programs over a hypercube and its applications

It has been observed that the Handelman’s certificate of positivity of a polynomial over a compact polyhedron offers a hierarchical relaxation scheme for polynomial programs. The Handelman hierarchy seems particularly suitable for a class of combinatorial optimizations that are formulated as a zero‐diagonal quadratic program over a hypercube. In this paper, we present an error analysis of Handelman hierarchy applied to the special class of polynomial programs and its implications in the computation of the combinatorial optimization problems.