Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints
Abstract: We propose doubly nonnegative (DNN) relaxations for polynomial optimization problems (POPs) with binary and box constraints to find tight lower bounds for their optimal values using a bisection and projection (BP) method. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems (QOPs) to POPs. We show how the dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which the BP algorithm can be applied. To compute the metric projection efficiently in the BP method, we introduce a class of polyhedral cones as a basic framework for various DNN relaxations. Moreover, we prove using the basic framework why the tight lower bounds of QOPs were obtained numerically by the Lagrangian-DNN relaxation of QOPs in the work by the authors in 2016. Preliminary numerical results on randomly generated POPs with binary and boxed constraints and the maximum complete satisfiability problems are provided to demonstrate the numerical efficiency of the proposed method for attaining tight bounds.
Keywords: Polynomial optimization problems with nonnegative variables, doubly nonnegative relaxations, a class of polyhedral cones, the bisection and projection algorithm.
Category 1: Linear, Cone and Semidefinite Programming
Entry Submitted: 07/07/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|