Algorithm 996: BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems With Binary, Box, and Complementarity Constraints
- 주제(키워드) 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
- 주제(기타) Computer Science, Software Engineering
- 주제(기타) Mathematics, Applied
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS
- 발행기관 ASSOC COMPUTING MACHINERY
- 발행년도 2019
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000161364
- 본문언어 영어
- Published As http://dx.doi.org/10.1145/3309988
초록/요약
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/sit/bbcpop1/.
more