Optimization Online


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

Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojimamasakazu***at***mac.com)
Kim-Chuan Toh(mattohkc***at***nus.edu.sg)

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


Download: [PDF]

Entry Submitted: 07/07/2016
Entry Accepted: 07/08/2016
Entry Last Modified: 07/07/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society