Polynomial Optimization by Quadratization and Convexification
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A preconditioned iterative interior point approach to the conic bundle subproblemMathematical Programming, 2023
- Solving unconstrained 0-1 polynomial programs through quadratic convex reformulationJournal of Global Optimization, 2021
- Compact quadratizations for pseudo-Boolean functionsJournal of Combinatorial Optimization, 2019
- Linear and quadratic reformulations of nonlinear optimization problems in binary variables4OR, 2018
- Global solution of non-convex quadratically constrained quadratic programsOptimization Methods and Software, 2017
- Quadratic reformulations of nonlinear binary optimization problemsMathematical Programming, 2016
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimizationJournal of Global Optimization, 2016
- Quadratization of symmetric pseudo-Boolean functionsDiscrete Applied Mathematics, 2016
- Exact quadratic convex reformulations of mixed-integer quadratically constrained problemsMathematical Programming, 2015
- Transformation of General Binary MRF Minimization to the First-Order CaseIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010