TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
From MaRDI portal
Publication:5148403
Abstract: This paper is concerned with polynomial optimization problems. We show how to exploit term (or monomial) sparsity of the input polynomials to obtain a new converging hierarchy of semidefinite programming relaxations. The novelty (and distinguishing feature) of such relaxations is to involve block-diagonal matrices obtained in an iterative procedure performing completion of the connected components of certain adjacency graphs. The graphs are related to the terms arising in the original data and not to the links between variables. Our theoretical framework is then applied to compute lower bounds for polynomial optimization problems either randomly generated or coming from the networked systems literature.
Recommendations
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- A new sparse SOS decomposition algorithm based on term sparsity
- SOS tensor decomposition: theory and applications
- scientific article; zbMATH DE number 1532350
- scientific article; zbMATH DE number 7272387
- scientific article; zbMATH DE number 2080210
- Designing Structured Sparse Dictionaries for Sparse Representation Modeling
Cites work
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 753805 (Why is no real title available?)
- A bounded degree SOS hierarchy for polynomial optimization
- A new sparse SOS decomposition algorithm based on term sparsity
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- Certified roundoff error bounds using semidefinite programming
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Extremal psd forms with few terms
- Generalised absolute stability and sum of squares
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming
- JuMP: a modeling language for mathematical optimization
- Lower bounds for polynomials using geometric programming
- Positive semidefinite matrices with a given sparsity pattern
- Pre- and Post-Processing Sum-of-Squares Programs in Practice
- Relative entropy relaxations for signomial optimization
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Sparsity in sums of squares of polynomials
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Sums of squares, moment matrices and optimization over polynomials
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(44)- Lower bounds of functions on finite abelian groups
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- scientific article; zbMATH DE number 7272387 (Why is no real title available?)
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- Global minimization of polynomial integral functionals
- Invariants of SDP exactness in quadratic programming
- Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming
- Exploiting term sparsity in noncommutative polynomial optimization
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- A hierarchy of spectral relaxations for polynomial optimization
- Sparse noncommutative polynomial optimization
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- A unified framework of SAGE and SONC polynomials and its duality theory
- Nonnegative Polynomials and Circuit Polynomials
- Exploiting constant trace property in large-scale polynomial optimization
- Convex hulls of monomial curves, and a sparse positivstellensatz
- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- Exploiting sparsity in complex polynomial optimization
- The moment-SOS hierarchy: applications and related topics
- Convergent SDP-relaxations for polynomial optimization with sparsity
- Algebraic Perspectives on Signomial Optimization
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- A sublevel moment-SOS hierarchy for polynomial optimization
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization
- Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging scheduling
- A new sparse SOS decomposition algorithm based on term sparsity
- Symmetry reduction in AM/GM-based optimization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients
- Partial Lasserre relaxation for sparse Max-Cut
- The constant trace property in noncommutative optimization
Describes a project that uses
Uses Software
This page was built for publication: TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5148403)
