Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints

We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems (QOPs) to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted to the intersection of the positive semidefinite cone and a polyhedral cone representing the algebraic properties of binary and box constraints as well as the sparsity structure of the objective polynomial. Our DNN relaxation serves as a variant of the standard Lasserre moment-SOS hierarchy for binary and box constrained POPs as the size of the cones is gradually increased to compute tighter lower bounds for their optimal values. A significant part of the paper is devoted to deriving and analyzing a class of polyhedral cones which strengthen the moment-SOS relaxation and to efficient computation of the metric projections onto these cones in the accelerated BP algorithm. Using the basic DNN relaxation framework, we also show why tight lower bounds of binary and box constrained QOPs were obtained numerically by their Lagrangian-DNN relaxation in the work by the authors in 2016. Numerical results on large scale POPs are provided to demonstrate the efficiency of the proposed method for attaining tight bounds.

Article

Download

View Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints