Exploiting term sparsity in noncommutative polynomial optimization

DOI10.1007/S10589-021-00301-7OpenAlexW3183816071MaRDI QIDQ2231045

Jie Wang, Victor Magron

Publication date: 29 September 2021

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.06956

zbMATH Keywords

eigenvalue optimizationsemidefinite relaxationstrace optimizationsum of Hermitian squaresterm sparsitynoncommutative polynomial optimization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Semialgebraic sets and related spaces (14P10) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Mathematical programming (90Cxx) Polynomial optimization (90C23)

Related Items (6)

Noncommutative Christoffel-Darboux kernels ⋮ Sparse noncommutative polynomial optimization ⋮ SONC optimization and exact nonnegativity certificates via second-order cone programming ⋮ A sublevel moment-SOS hierarchy for polynomial optimization ⋮ Exploiting sparsity in complex polynomial optimization ⋮ Dimension-free entanglement detection in multipartite Werner states

Uses Software

• SparsePOP
• Mosek
• ComputeTW
• Julia
• JuMP
• GitHub
• LightGraphs.jl
• TSSOS
• ChordalGraph
• SparseJSR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing the sum of many rational functions
• Handbook on semidefinite, conic and polynomial optimization
• Positive definite completions of partial Hermitian matrices
• Treewidth computations. I: Upper bounds
• Positive semidefinite matrices with a given sparsity pattern
• Extremal psd forms with few terms
• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Theory of operator algebras. III
• ``Positive noncommutative polynomials are sums of squares.
• The tracial moment problem and trace-optimization of polynomials
• Sparse noncommutative polynomial optimization
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Global Optimization with Polynomials and the Problem of Moments
• Optimization of Polynomials in Non-Commuting Variables
• Constrained Polynomial Optimization Problems with Noncommuting Variables
• Julia: A Fresh Approach to Numerical Computing
• Convergent Relaxations of Polynomial Optimization Problems with Noncommuting Variables
• Certified Roundoff Error Bounds Using Semidefinite Programming
• Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming
• Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
• A positivstellensatz for non-commutative polynomials
• Scalable Semidefinite Programming
• A New Sparse SOS Decomposition Algorithm Based on Term Sparsity
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
• 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

This page was built for publication: Exploiting term sparsity in noncommutative polynomial optimization