Algorithm 996: BBCPOP. 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.
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan: Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures (2020)
- Ito, Naoki; Kim, Sunyoung; Kojima, Masakazu; Takeda, Akiko; Toh, Kim-Chuan: Algorithm 996: BBCPOP: a sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box, and complementarity constraints (2019)
- Oliveira, Danilo Elias; Wolkowicz, Henry; Xu, Yangyang: ADMM for the SDP relaxation of the QAP (2018)