Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
DOI10.1137/16M105544XzbMATH Open1367.90080MaRDI QIDQ5737720FDOQ5737720
Authors: Shinsaku Sakaue, Akiko Takeda, Sunyoung Kim, N. Ito 
Publication date: 30 May 2017
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Recommendations
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- Semidefinite programming relaxations for linear semi-infinite polynomial programming
- Bilevel polynomial programs and semidefinite relaxation methods
- Semidefinite relaxations for semi-infinite polynomial programming
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- A semidefinite approach for truncated \(K\)-moment problems
- Solving polynomial least squares problems via semidefinite programming relaxations
- Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems
- Semidefinite programming in combinatorial and polynomial optimization
chordal graphbinary polynomial optimization problemsbound for the exact SDP relaxationeven-degree binary polynomial optimization problemshierarchy of SDP relaxations
Convex programming (90C25) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Solving semidefinite-quadratic-linear programs using SDPT3
- Graph theory
- Global optimization with polynomials and the problem of moments
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Title not available (Why is that?)
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- On a conjecture concerning spanning tree invariants and loop systems
- Approximation algorithms for discrete polynomial optimization
- A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints
- Polynomially solvable cases for the maximum stable set problem
- Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems
- On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
- Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
- On solving biquadratic optimization via semidefinite relaxation
Cited In (11)
- On the strength of recursive McCormick relaxations for binary polynomial optimization
- Title not available (Why is that?)
- Lower bounds of functions on finite abelian groups
- Binary quadratic optimization problems that are difficult to solve by conic relaxations
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- An exact Jacobian SDP relaxation for polynomial optimization
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
Uses Software
This page was built for publication: Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5737720)
