Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints

Sunyoung Kim, Masakazu Kojima, Kim Chuan Toh

Research output: Contribution to journalArticlepeer-review


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 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 Lasserre moment-SOS hierarchy of relaxations for binary and box constrained POPs when 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 to strengthen the DNN relaxation, and the design of efficient computation of the metric projections onto these cones in the accelerated BP algorithm. Numerical results on various POPs are available in Ito et al. (ACM Trans Math Softw 45, Article 34, 2019).

Original languageEnglish
Pages (from-to)761-787
Number of pages27
JournalMathematical Programming
Issue number2
StatePublished - Jun 2022

Bibliographical note

Publisher Copyright:
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.


  • A class of polyhedral cones
  • Computational efficiency and tight bounds
  • Doubly nonnegative relaxations
  • Polynomial optimization problems with nonnegative variables
  • The bisection and projection algorithm


Dive into the research topics of 'Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints'. Together they form a unique fingerprint.

Cite this