2018/04/02 by Naoki Ito, Ito, Naoki, Sunyoung Kim +7 · 2 citations
Computer Science · Mathematics · #90C20 #90C22 #90C25 #90C26 #Advanced Optimization Algorithms Research #Algorithm #Arithmetic #Binary number #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #FOS: Mathematics #Mathematical optimization #Mathematics #Monomial #Monotone polygon #Optimization and Control (math.OC) #Polynomial and algebraic computation #Quadratic programming #Software #Solver #math.OC #msc:90C20 #msc:90C22 #msc:90C25 #msc:90C26
paper · pdf · doi:10.48550/arxiv.1804.00761
published in arXiv (Cornell University) (Cornell University) · 28 pages, 4 figures
arxiv created 2018/04/02 · openalex publication_date 2018/04/02 · arxiv updated 2018/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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/.