Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph

DOI10.1137/21M140345XzbMath1487.05259arXiv2103.01574OpenAlexW3134280401MaRDI QIDQ5072588

Luis Felipe Vargas, Monique Laurent

Publication date: 29 April 2022

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

Full work available at URL: https://arxiv.org/abs/2103.01574

zbMATH Keywords

semidefinite programmingcopositive programmingfinite convergencepolynomial optimizationLasserre hierarchystable set problemsum-of-squares polynomialMotzkin-Straus formulationstandard quadratic programming\(\alpha\)-critical graph

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Sums of squares and representations by other particular quadratic forms (11E25) Combinatorial optimization (90C27) Graph theory (05C99)

Related Items

On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices, A Sum of Squares Characterization of Perfect Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimality conditions and finite convergence of Lasserre's hierarchy
• An improved semidefinite programming hierarchy for testing entanglement
• Kneser's conjecture, chromatic number, and homotopy
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• A quantitative Pólya's theorem with zeros
• Matching theory
• The \(K\)-moment problem for compact semi-algebraic sets
• Evolution towards the maximum clique
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Uniform denominators in Hilbert's seventeenth problem
• On the exactness of Lasserre relaxations and pure states over real closed fields
• Complexity aspects of local minima and related notions
• On the tightness of SDP relaxations of QCQPs
• On standard quadratic programs with exact and inexact doubly nonnegative relaxations
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• Tight relaxations for polynomial optimization and Lagrange multiplier expressions
• Representations of non-negative polynomials having finitely many zeros
• Distinguished representations of non-negative polynomials
• Sums of squares on real algebraic surfaces
• A review on algorithms for maximum clique problems
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Polynomial Optimization with Real Varieties
• On the Lasserre Hierarchy of Semidefinite Programming Relaxations of Convex Polynomial Optimization Problems
• Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
• Convexity in SemiAlgebraic Geometry and Polynomial Optimization
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• Continuous Characterizations of the Maximum Clique Problem
• Optimization of Polynomial Functions
• On the Exactness of Lasserre Relaxations for Compact Convex Basic Closed Semialgebraic Sets
• On the uniqueness of solutions to linear programs
• On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
• Reducibility among Combinatorial Problems
• Fast Cluster Detection in Networks by First Order Optimization
• A General Regularized Continuous Formulation for the Maximum Clique Problem
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• LMI Approximations for Cones of Positive Semidefinite Forms
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• On copositive programming and standard quadratic optimization problems