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)- A unified framework of SAGE and SONC polynomials and its duality theory
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- A new sparse SOS decomposition algorithm based on term sparsity
- Global minimization of polynomial integral functionals
- scientific article; zbMATH DE number 7272387 (Why is no real title available?)
- Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming
- Lower bounds of functions on finite abelian groups
- Nonnegative Polynomials and Circuit Polynomials
- Exploiting constant trace property in large-scale polynomial optimization
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- The moment-SOS hierarchy: applications and related topics
- Partial Lasserre relaxation for sparse Max-Cut
- Symmetry reduction in AM/GM-based optimization
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization
- Algebraic Perspectives on Signomial Optimization
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- Invariants of SDP exactness in quadratic programming
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- A hierarchy of spectral relaxations for polynomial optimization
- Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging scheduling
- Convergent SDP-relaxations for polynomial optimization with sparsity
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- 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
- A sublevel moment-SOS hierarchy for polynomial optimization
- Sparse noncommutative polynomial optimization
- Exploiting term sparsity in noncommutative polynomial optimization
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- Exploiting sparsity in complex polynomial optimization
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- Convex hulls of monomial curves, and a sparse positivstellensatz
- A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- The constant trace property in noncommutative optimization
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
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)
