Sparse Noncommutative Polynomial Optimization
arXiv:1909.00569 · doi:10.1007/s10107-020-01610-1
Abstract
This article focuses on optimization of polynomials in noncommuting variables, while taking into account sparsity in the input data. A converging hierarchy of semidefinite relaxations for eigenvalue and trace optimization is provided. This hierarchy is a noncommutative analogue of results due to Lasserre [SIAM J. Optim. 17(3) (2006), pp. 822--843] and Waki et al. [SIAM J. Optim. 17(1) (2006), pp. 218--242]. The Gelfand-Naimark-Segal (GNS) construction is applied to extract optimizers if flatness and irreducibility conditions are satisfied. Among the main techniques used are amalgamation results from operator algebra. The theoretical results are utilized to compute lower bounds on minimal eigenvalue and trace of noncommutative polynomials from the literature.
arXiv comment37 pages, 3 figures, 3 tables
References in corpus (13)
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Convergent relaxations of polynomial optimization problems with non-commuting variables
- Approximate volume and integration for basic semi-algebraic sets
- Quantum Bounds on Bell inequalities
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Algorithm 950: Ncpol2sdpa---Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables
- Exploiting symmetries in SDP-relaxations for polynomial optimization
- Equivalent forms of the Bessis-Moussa-Villani conjecture
- The convex Positivstellensatz in a free algebra
- The A-truncated K-moment problem
- Sums of hermitian squares and the BMV conjecture
- TSSOS: A Moment-SOS hierarchy that exploits term sparsity
- Application of Polynomial Optimization to Electricity Transmission Networks
Cited by in corpus (9)
- Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
- Dimension-free entanglement detection in multipartite Werner states
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- State polynomials: positivity, optimization and nonlinear Bell inequalities
- Fairness in Forecasting and Learning Linear Dynamical Systems
- SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions
- Exploiting term sparsity in Noncommutative Polynomial Optimization
- Learning of Linear Dynamical Systems as a Non-Commutative Polynomial Optimization Problem
- Quantum Optimal Control via Magnus Expansion and Non-Commutative Polynomial Optimization