Algorithm 996
From MaRDI portal
Abstract: 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/.
Recommendations
- Algorithm 950: Ncpol2sdpa -- sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables
- Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- \(\alpha BB\): A global optimization method for general constrained nonconvex problems
- Exploiting sparsity in SDP relaxation of polynomial optimization problems
- Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- Convergent SDP-relaxations for polynomial optimization with sparsity
Cites work
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3177945 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- A Copositive Programming Approach to Graph Partitioning
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A bounded degree SOS hierarchy for polynomial optimization
- A robust Lagrangian-DNN method for a class of quadratic optimization problems
- A unified formulation and fast accelerated proximal gradient method for classification
- ADMM for the SDP relaxation of the QAP
- Adaptive restart for accelerated gradient schemes
- An adaptive accelerated first-order method for convex optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
- Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- Greedy approximations for minimum submodular cover with submodular cost
- Handbook on semidefinite, conic and polynomial optimization
- Lagrangian-conic relaxations. I: A unified framework and its applications to quadratic optimization problems
- Lagrangian-conic relaxations. II: Applications to polynomial optimization problems
- Moments, positive polynomials and their applications
- Moreau's decomposition in Banach spaces
- On Lagrangian relaxation of quadratic matrix constraints
- Regularization methods for SDP relaxations in large-scale polynomial optimization
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite programming relaxations for the quadratic assignment problem
- Solving semidefinite-quadratic-linear programs using SDPT3
- Some applications of polynomial optimization in operations research and real-time decision making
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Submodular Function Minimization under Covering Constraints
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(10)- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- A regularization-patching dual quaternion optimization method for solving the hand-eye calibration problem
- Equivalent sufficient conditions for global optimality of quadratically constrained quadratic programs
- Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints
- BBCPOP
- A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems
- A Newton-bracketing method for a simple conic optimization problem
- Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures
- Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation
- ADMM for the SDP relaxation of the QAP
Describes a project that uses
Uses Software
This page was built for publication: Algorithm 996
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960955)
