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 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.

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: 12/06/2017

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