Optimization Online


BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

Naoki Ito (naoki_ito***at***mist.i.u-tokyo.ac.jp)
Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (kojimamasakazu***at***mac.com)
Akiko Takeda (atakeda***at***ism.ac.jp)
Kim-Chuan Toh (mattohkc***at***nus.edu.sg)

Abstract: The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a DNN relaxation of the POP, and then solves the COP by applying the bisection and projection (BP) method. The COP is expressed with a linear objective function and constraints described as a single hyperplane and two cones, which are the Cartesian product of positive semidefinite cones and a polyhedral cone induced from the BBC constraints. BBCPOP aims to compute a tight lower bound for the optimal value of a large-scale POP in the class that is beyond the comfort zone of existing software packages. The robustness, reliability and efficiency of BBCPOP are demonstrated in comparison to the state-of-the-art software SDP package SDPNAL+ on randomly generated sparse POPs of degree 2 and 3 with up to a few thousands variables, and ones of degree 4, 5, 6. and 8 with up to a few hundred variables. Comparison with other BBC POPs that arise from combinatorial optimization problems such as quadratic assignment problems are also reported. The software package BBCPOP is available at https://sites.google.com/site/bbcpop1/.

Keywords: MATLAB software package, High-degree polynomial optimization problems with binary, box and complementarity constraints, Hierarchy of doubly nonnegative relaxations, Sparsity, Bisection and projection methods, Tight lower bounds, Efficiency.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Category 3: Global Optimization

Citation: arXiv:1804.00761

Download: [PDF]

Entry Submitted: 04/02/2018
Entry Accepted: 04/02/2018
Entry Last Modified: 04/03/2018

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