Polynomial Optimization by Quadratization and Convexification

The question of minimizing a box-constrained polynomial (in mixed-integer variables) can easily and frequently emerge across many fields of science and engineering. This work explores the idea of solving this problem by reformulating the given polynomial as a quadratic function. Such reformulation induces a number of auxiliary variables that are intended to represent various (high-degree) monomials in the original variables. The interdependence of the artificial and the original variables is enforced through a hierarchical collection of non-convex quadratic constraints, referred to as a quadratization scheme. We thus obtain a quadratically-constrained quadratic program (QCQP) that is completely equivalent to the given polynomial program. This QCQP is still non-convex and N P-hard, but it can be relaxed into a convex quadratic program more easily than an arbitrary-degree polynomial. It is easier to convexify a quadratic function since its Hessian matrix does not vary with the point of evaluation as in the case of a higher-degree polynomial. The coefficients of the resulting convex quadratic program are obtained from the optimal dual values of the SDP (positive semi-definite) relaxation of the same QCQP program. We further integrate it into a spatial Branch-and-bound framework, in which each branching node reduces to a box that simply limits the domain of each variable. The Branch-and-bound is powered by the above convex quadratic program: the lower bound of each node is determined by solving this convex relaxation over the corresponding box, which is a very fast operation using modern Interior Point Methods solvers. Numerical results confirm the potential of the proposed ideas.