Convergent relaxations of polynomial optimization problems with noncommuting variables
From MaRDI portal
Publication:3083282
DOI10.1137/090760155zbMATH Open1228.90073arXiv0903.4368OpenAlexW3105661328MaRDI QIDQ3083282FDOQ3083282
Authors: Stefano Pironio, Miguel Navascués, A. Acín 
Publication date: 21 March 2011
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: We consider optimization problems with polynomial inequality constraints in non-commuting variables. These non-commuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.
Full work available at URL: https://arxiv.org/abs/0903.4368
Recommendations
- SDP relaxations for non-commutative polynomial optimization
- Algorithm 950: Ncpol2sdpa -- sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables
- Sparse noncommutative polynomial optimization
- Constrained polynomial optimization problems with noncommuting variables
- Optimization of polynomials in non-commuting variables
Semidefinite programming (90C22) General mathematical topics and methods in quantum theory (81Q99) Mathematical programming (90C99)
Cited In (55)
- Noncommutative polynomials nonnegative on a variety intersect a convex set
- The tracial Hahn-Banach theorem, polar duals, matrix convex sets, and projections of free spectrahedra
- The tracial moment problem and trace-optimization of polynomials
- Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools
- Matrix convex hulls of free semialgebraic sets
- Limitations of semidefinite programs for separable states and entangled games
- Maximizing concave piecewise affine functions on the unitary group
- Algorithm 950: Ncpol2sdpa -- sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables
- NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials
- Minimizer Extraction in Polynomial Optimization Is Robust
- Quantum bilinear optimization
- Nonnegative Polynomial Optimization over Unit Spheres and Convex Programming Relaxations
- A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming
- On characterising assemblages in Einstein–Podolsky–Rosen scenarios
- Device-independent bit commitment based on the CHSH inequality
- Constrained trace-optimization of polynomials in freely noncommuting variables
- Optimization over trace polynomials
- Using complete measurement statistics for optimal device-independent randomness evaluation
- Convergent Relaxations of Polynomial Matrix Inequalities and Static Output Feedback
- Noncommutative polynomials describing convex sets
- Positive maps and trace polynomials from the symmetric group
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- A convergent inflation hierarchy for quantum causal structures
- Global completability with applications to self-consistent quantum tomography
- SDP relaxations for non-commutative polynomial optimization
- The convex Positivstellensatz in a free algebra
- Convexity and semidefinite programming in dimension-free matrix unknowns
- A physical approach to Tsirelson's problem
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Reinhardt free spectrahedra
- Semidefinite programming hierarchies for constrained bilinear optimization
- A combinatorial approach to nonlocality and contextuality
- The weirdness theorem and the origin of quantum paradoxes
- Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials
- Lower bounds for ground states of condensed matter systems
- Operator Positivstellensätze for noncommutative polynomials positive on matrix convex sets
- Sparse noncommutative polynomial optimization
- Canonical primal-dual algorithm for solving fourth-order polynomial minimization problems
- Information-causality and extremal tripartite correlations
- Exploiting term sparsity in noncommutative polynomial optimization
- On matrix algebras associated to sum-of-squares semidefinite programs
- Constrained polynomial optimization problems with noncommuting variables
- Noncommutative Christoffel-Darboux kernels
- Randomness in post-selected events
- Can you compute the operator norm?
- A paradox in bosonic energy computations via semidefinite programming relaxations
- Semi-definite programming and quantum information
- State polynomials: positivity, optimization and nonlinear Bell inequalities
- Real algebraic geometry with a view toward Koopman operator methods. Abstracts from the workshop held March 12--17, 2023
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- Matrix extreme points and free extreme points of free spectrahedra
- The inflation hierarchy and the polarization hierarchy are complete for the quantum bilocal scenario
- The constant trace property in noncommutative optimization
- Free extreme points span generalized free spectrahedra given by compact coefficients
- Entropy constraints for ground energy optimization
Uses Software
This page was built for publication: Convergent relaxations of polynomial optimization problems with noncommuting variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083282)
