TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
From MaRDI portal
Publication:5148403
DOI10.1137/19M1307871zbMATH Open1506.90202arXiv1912.08899OpenAlexW3119965387MaRDI QIDQ5148403FDOQ5148403
Authors: Jie Wang, Victor Magron, Jean B. Lasserre 
Publication date: 4 February 2021
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1912.08899
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
polynomial optimizationsemidefinite programmingsum of squaresmoment relaxationmoment-SOS hierarchyterm sparsity
Semidefinite programming (90C22) Semialgebraic sets and related spaces (14P10) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Computational real algebraic geometry (14Q30) Polynomial optimization (90C23)
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- JuMP: a modeling language for mathematical optimization
- Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- Generalised absolute stability and sum of squares
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- Lower bounds for polynomials using geometric programming
- Pre- and Post-Processing Sum-of-Squares Programs in Practice
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Positive semidefinite matrices with a given sparsity pattern
- Title not available (Why is that?)
- Relative entropy relaxations for signomial optimization
- Extremal psd forms with few terms
- Sparsity in sums of squares of polynomials
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- A bounded degree SOS hierarchy for polynomial optimization
- Certified Roundoff Error Bounds Using Semidefinite Programming
- Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming
- Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
- A New Sparse SOS Decomposition Algorithm Based on Term Sparsity
- Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
Cited In (40)
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures
- A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Global minimization of polynomial integral functionals
- Title not available (Why is that?)
- Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming
- Lower bounds of functions on finite abelian groups
- Exploiting constant trace property in large-scale polynomial optimization
- Nonnegative Polynomials and Circuit Polynomials
- 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
- Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
- 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
- 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
- Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets
- Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- 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
- 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
- A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients
- The constant trace property in noncommutative optimization
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Symmetry Reduction in AM/GM-Based Optimization
- 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
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)
