Algorithm 996: BBCpop: A sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box, and complementarity constraints

Naoki Ito, Sunyoung Kim, Masakazu Kojima, Akiko Takeda, Kim Chuan Toh

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative 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 doubly nonnegative relaxation of the POP, and then solves the COP by applying the bisection and projection 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 from 5 to 8 with up to a few hundred variables. Numerical results on BBC-constrained POPs that arise from quadratic assignment problems are also reported. The software package BBCPOP is available at https://sites.google.com/site/bbcpop1/.

Original languageEnglish
Article number34
JournalACM Transactions on Mathematical Software
Volume45
Issue number3
DOIs
StatePublished - Aug 2019

Bibliographical note

Funding Information:
N. Ito was supported by Grant-in-Aid for JSPS Research Fellowship JP17J07365. S. Kim was supported by NRF 2017-R1A2B2005119. M. Kojima was supported by Grant-in-Aid for Scientific Research (A) 26242027. A. Takeda was supported by Grant-in-Aid for Scientific Research (C) 15K00031 and (B) 19H04069. K.-C. Toh was supported in part by the Ministry of Education, Singapore, Academic Research Fund under grant R-146-000-256-114. Authors’ addresses: N. Ito, Fast Retailing Co., LTD., Tokyo, 135-0063, Japan; email: [email protected]; S. Kim, Department of Mathematics, Ewha W. University, 52 Ewhayeodae-gil, Seoul, 03760, Korea; email: [email protected]; M. Kojima, Department of Industrial and Systems Engineering, Chuo University, Tokyo, 112-8551, Japan; email: kojima@ is.titech.ac.jp; A. Takeda, Department of Creative Informatics, Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 113-8656, Japan; email: [email protected]; K.-C. Toh, Department of Mathematics and Institute of Operations Research and Analytics, National University of Singapore, Singapore, 119076, Singapore; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2019 Association for Computing Machinery. 0098-3500/2019/07-ART34 $15.00 https://doi.org/10.1145/3309988

Publisher Copyright:
© 2019 Association for Computing Machinery.

Keywords

  • Bisection and projection methods
  • Box and complementarity constraints
  • Efficiency
  • Hierarchy of doubly nonnegative relaxations
  • High-degree polynomial optimization problems with binary
  • MATLAB software package
  • Sparsity
  • Tight lower bounds

Fingerprint

Dive into the research topics of 'Algorithm 996: BBCpop: A sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box, and complementarity constraints'. Together they form a unique fingerprint.

Cite this