Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems

DOI10.1137/16M105544XzbMath1367.90080MaRDI QIDQ5737720

Akiko Takeda, Sunyoung Kim, Shinsaku Sakaue, N. Ito

Publication date: 30 May 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

chordal graphbinary polynomial optimization problemsbound for the exact SDP relaxationeven-degree binary polynomial optimization problemshierarchy of SDP relaxations

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Nonconvex programming, global optimization (90C26)

Related Items (7)

Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Binary quadratic optimization problems that are difficult to solve by conic relaxations ⋮ Unnamed Item ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Sum-of-squares hierarchies for binary polynomial optimization

Uses Software

• SDPA
• SeDuMi
• SDPT3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Approximation algorithms for discrete polynomial optimization
• On a conjecture concerning spanning tree invariants and loop systems
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Polynomially solvable cases for the maximum stable set problem
• On solving biquadratic optimization via semidefinite relaxation
• Global Optimization with Polynomials and the Problem of Moments
• A Semidefinite Relaxation Scheme for Multivariate Quartic Polynomial Optimization with Quadratic Constraints
• On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
• Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

This page was built for publication: Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems