Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
From MaRDI portal
Publication:5148406
DOI10.1137/20M1323564zbMath1457.90106arXiv2003.03210MaRDI QIDQ5148406
Jie Wang, Victor Magron, Jean-Bernard Lasserre
Publication date: 4 February 2021
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.03210
Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Semialgebraic sets and related spaces (14P10) Coloring of graphs and hypergraphs (05C15)
Related Items
Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients, Algebraic Perspectives on Signomial Optimization, Sparse noncommutative polynomial optimization, Nonnegative Polynomials and Circuit Polynomials, A tighter relaxation for the relative pose problem between cameras, Symmetry Reduction in AM/GM-Based Optimization, Optimization on the Euclidean Unit Sphere, SONC optimization and exact nonnegativity certificates via second-order cone programming, Partial Lasserre relaxation for sparse Max-Cut, A hierarchy of spectral relaxations for polynomial optimization, Sparse polynomial optimisation for neural network verification, A new global algorithm for max-cut problem with chordal sparsity, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization, Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Exploiting term sparsity in noncommutative polynomial optimization, TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity, Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures, A sublevel moment-SOS hierarchy for polynomial optimization, Decomposed structured subsets for semidefinite and sum-of-squares optimization, Exploiting sparsity in complex polynomial optimization, Finding unstable periodic orbits: a hybrid approach with polynomial optimization, A unified framework of SAGE and SONC polynomials and its duality theory
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Minimal triangulations of graphs: a survey
- Extremal psd forms with few terms
- Sparse noncommutative polynomial optimization
- Incidence matrices and interval graphs
- A bounded degree SOS hierarchy for polynomial optimization
- Global Optimization with Polynomials and the Problem of Moments
- Certified Roundoff Error Bounds Using Semidefinite Programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- A New Sparse SOS Decomposition Algorithm Based on Term Sparsity
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- GloptiPoly
- Algorithm 837
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- JuMP: A Modeling Language for Mathematical Optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
