TY - JOUR
T1 - Algorithm 996
T2 - BBCpop: A sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box, and complementarity constraints
AU - Ito, Naoki
AU - Kim, Sunyoung
AU - Kojima, Masakazu
AU - Takeda, Akiko
AU - Toh, Kim Chuan
N1 - 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: naoki.b.ito@fastretailing.com; S. Kim, Department of Mathematics, Ewha W. University, 52 Ewhayeodae-gil, Seoul, 03760, Korea; email: skim@ewha.ac.kr; 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: takeda@mist.i.u-tokyo.ac.jp; K.-C. Toh, Department of Mathematics and Institute of Operations Research and Analytics, National University of Singapore, Singapore, 119076, Singapore; email: mattohkc@nus.edu.sg. 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 permissions@acm.org. © 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.
PY - 2019/8
Y1 - 2019/8
N2 - 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/.
AB - 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/.
KW - Bisection and projection methods
KW - Box and complementarity constraints
KW - Efficiency
KW - Hierarchy of doubly nonnegative relaxations
KW - High-degree polynomial optimization problems with binary
KW - MATLAB software package
KW - Sparsity
KW - Tight lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85071177304&partnerID=8YFLogxK
U2 - 10.1145/3309988
DO - 10.1145/3309988
M3 - Article
AN - SCOPUS:85071177304
SN - 0098-3500
VL - 45
JO - ACM Transactions on Mathematical Software
JF - ACM Transactions on Mathematical Software
IS - 3
M1 - 34
ER -