Partitioning procedure for polynomial optimization

摘要

We consider the problem of finding the minimum of a real-valued multivariate polynomial function constrained in a compact set defined by polynomial inequalities and equalities. This problem, called polynomial optimization problem (POP), is generally non-convex and has been of growing interest to many researchers in recent years. Our goal is to tackle POPs using decomposition, based on a partitioning procedure. The problem manipulations are in line with the pattern used in the generalized Benders decomposition, namely projection followed by relaxation. Stengle's and Putinar's Positivstellensatze are employed to derive the feasibility and optimality constraints, respectively. We test the performance of the proposed partitioning procedure on a collection of benchmark problems and present the numerical results.