Iterative Valid Polynomial Inequalities Generation for Polynomial Programing

Polynomial Programs are ussually solved by using hierarchies of convex relaxations. This scheme rapidly becomes computationally expensive and is often tractable only for problems of small sizes. We propose an iterative scheme that improves an initial relaxation without incurring exponential growth in size. The key ingredient is a dynamic scheme for generating valid polynomial inequalities for general polynomial programs. These valid inequalities are then used to construct better approximations of the original problem. As a result, the proposed scheme is in principle scalable to large general combinatorial optimization problems.

Joint work with Bissan Ghaddar and Miguel Anjos