Iterative Valid Polynomial Inequality Generation in Polynomial Optimization
Miguel Anjos, Ecole Polytechnique de Montréal

Polynomial optimization problems are normally solved using hierarchies of convex relaxations. These schemes rapidly become computationally expensive, and are usually tractable only for problems of small sizes. We propose a novel dynamic scheme for generating valid polynomial inequalities for general polynomial optimization problems. These valid inequalities are then used to construct better approximations of the original problem. For the special case of binary polynomial problems, we prove that the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the problem. We also present examples illustrating the computational behaviour of the scheme and compare it to other methods in the literature. This is joint work with Bissan Ghaddar (U of Waterloo) and Juan Vera (Tilburg U).