TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
From MaRDI portal
Publication:5148403
DOI10.1137/19M1307871zbMath1506.90202arXiv1912.08899OpenAlexW3119965387MaRDI QIDQ5148403
Victor Magron, Jie Wang, 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/1912.08899
semidefinite programmingpolynomial optimizationsum of squaresmoment relaxationmoment-SOS hierarchyterm sparsity
Semidefinite programming (90C22) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Semialgebraic sets and related spaces (14P10) Polynomial optimization (90C23) Computational real algebraic geometry (14Q30)
Related Items
Algebraic Perspectives on Signomial Optimization, Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets, Sparse noncommutative polynomial optimization, Duality of sum of nonnegative circuit polynomials and optimal SONC bounds, Nonnegative Polynomials and Circuit Polynomials, Symmetry Reduction in AM/GM-Based Optimization, 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, Semidefinite Relaxation Methods for Tensor Absolute Value Equations, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization, Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming, 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, Invariants of SDP exactness in quadratic programming, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Exploiting term sparsity in noncommutative polynomial optimization, Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension, 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
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- Positive semidefinite matrices with a given sparsity pattern
- Extremal psd forms with few terms
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Sparsity in sums of squares of polynomials
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
- A bounded degree SOS hierarchy for polynomial optimization
- Generalised absolute stability and sum of squares
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Global Optimization with Polynomials and the Problem of Moments
- Relative Entropy Relaxations for Signomial Optimization
- Lower Bounds for Polynomials Using Geometric Programming
- Certified Roundoff Error Bounds Using Semidefinite Programming
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming
- Pre- and Post-Processing Sum-of-Squares Programs in Practice
- A New Sparse SOS Decomposition Algorithm Based on Term Sparsity
- Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- GloptiPoly
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- JuMP: A Modeling Language for Mathematical Optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity