doubly nonnegative relaxations

Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Various conic relaxations of quadratic optimization problems in nonnega- tive variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combi- natorial optimization problems can be expressed in several ways, each … Read more

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

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    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 … Read more