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
- 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 sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Extremal psd forms with few terms
- Generalised absolute stability and sum of squares
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 753805 (Why is no real title available?)
- 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
(60)- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- 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
- Sparse noncommutative polynomial optimization
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- Exploiting term sparsity in noncommutative polynomial optimization
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- Nonnegative Polynomials and Circuit Polynomials
- Symmetry reduction in AM/GM-based optimization
- A new sparse SOS decomposition algorithm based on term sparsity
- scientific article; zbMATH DE number 7272387 (Why is no real title available?)
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- Convergent SDP-relaxations for polynomial optimization with sparsity
- A unified framework of SAGE and SONC polynomials and its duality theory
- Algebraic Perspectives on Signomial Optimization
- 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
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Global minimization of polynomial integral functionals
- Lower bounds of functions on finite abelian groups
- The moment-SOS hierarchy: applications and related topics
- Exploiting constant trace property in large-scale polynomial optimization
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- 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
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Convex hulls of monomial curves, and a sparse positivstellensatz
- The constant trace property in noncommutative optimization
- A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients
- A characterization for tightness of the sparse moment-SOS hierarchy
- Convergence rate for linear minimizer-estimators in the moment-sum-of-squares hierarchy
- Polynomial optimization over unions of sets
- On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem
- Solving low-rank semidefinite programs via manifold optimization
- Rank-one matrix completion via high-rank matrices in sum-of-squares relaxations
- Refined TSSOS
- Sparse polynomial optimization with unbounded sets
- Computer-assisted proofs for Lyapunov stability via sums of squares certificates and constructive analysis
- SPLD polynomial optimization and bounded degree SOS hierarchies
- Sparse polynomial matrix optimization
- An ideal-sparse generalized moment problem reformulation for completely positive tensor decomposition exploiting maximal cliques of multi-hypergraphs
- Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant
- Term-sparse polynomial optimization for the design of frame structures
- Sparse polynomial optimization with matrix constraints
- Cuts and semidefinite liftings for the complex cut polytope
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
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)
