Sparse Noncommutative Polynomial Optimization

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.

37 pages, 3 figures, 3 tables

References in corpus (4)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• 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