Sparse noncommutative polynomial optimization

Igor Klep, Victor Magron, Janez PovhMath. Program 2022 · OpenReview

TL;DR

This paper introduces a new computational framework for optimizing polynomials with non-commuting variables, specifically when the problem exhibits sparsity. They develop a hierarchy of semidefinite programming (SDP) relaxations for eigenvalue and trace optimization problems, analogous to existing methods but adapted for non-commuting variables and sparsity. This allows for more efficient computation of lower bounds for these optimization problems, with applications in control theory and quantum information.

What Problem Does This Paper Address?

Polynomial optimization, the problem of finding the minimum or maximum value of a polynomial over a set defined by polynomial inequalities, is a fundamental problem in mathematics and computer science. When the variables don't commute (e.g., matrices), this problem becomes significantly harder. Existing methods for non-commuting variables, like Lasserre's hierarchy of SDP relaxations, can become computationally intractable very quickly due to the rapid growth in the size of the SDP problems. This paper tackles the challenge of making these non-commutative optimization problems more computationally tractable by exploiting "sparsity" in the input polynomials. Sparsity means that the polynomials involved only depend on a limited number of variables or combinations of variables, which is common in many real-world applications.

Methods

The core contribution of this paper is the development of a "sparse" version of the Lasserre hierarchy for non-commutative polynomial optimization. This involves:

  • Sparse Noncommutative Positivstellensatz: They generalize Putinar's Positivstellensatz (a key theorem in polynomial optimization) to the sparse non-commutative setting. This relies on sophisticated "amalgamation results" from operator algebra, a technique for combining different algebraic structures.
  • Sparse Gelfand-Naimark-Segal (GNS) Construction: The GNS construction is a standard tool for relating representations of algebraic structures to linear functionals. The authors adapt this construction to handle sparse non-commutative polynomials, enabling the extraction of optimal solutions (optimizers) under certain conditions (flatness and irreducibility).
  • Sparse Semidefinite Programming (SDP) Relaxations: They derive new hierarchies of SDP relaxations for both eigenvalue and trace optimization problems. These sparse relaxations are designed to be computationally less demanding than their dense counterparts by exploiting the sparsity structure. The size of the SDP problems grows much more slowly with the number of variables and the degree of the polynomials.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments with specific example polynomials, rather than using pre-existing datasets.

Key Insights and Ideas

  • Sparsity is Key for Tractability: The paper strongly demonstrates that exploiting sparsity is crucial for making non-commutative polynomial optimization computationally feasible. Without it, the problem quickly becomes intractable.
  • Amalgamation Theory as a Powerful Tool: The use of amalgamation results from operator algebra is a novel and powerful technique for constructing sparse representations and proving theoretical results in this domain.
  • GNS Construction for Optimizer Extraction: Adapting the GNS construction to the sparse non-commutative setting provides a concrete method for extracting solutions, which is a significant practical advancement.
  • No Sparse Analog for "Perfect" Positivstellensatz: The paper highlights that a direct sparse analog of the Helton-McCullough Sums of Squares theorem (which states that a positive polynomial is a sum of squares) does not exist in the sparse non-commutative setting, as demonstrated by an example. This implies that while sparsity helps with computation, it doesn't simplify all theoretical aspects.

Key Results

  • Converging Hierarchies of SDP Relaxations: The paper provides theoretical guarantees that their sparse SDP relaxations converge to the true optimal values for eigenvalue and trace optimization problems.
  • Computational Efficiency: Numerical experiments (Tables 1, 2, and 3) show that their sparse approach (NCeigMinSparse) significantly outperforms dense methods (NCeigMin) in terms of computation time and the size of the SDP problems solved, especially for larger problem instances. For example, in Table 1, for $n=24$, the sparse method solves the problem in 17.65 seconds, while the dense method takes 152.17 seconds.
  • Algorithm for Optimizer Extraction: They present algorithms (SparseGNS) for extracting optimizers, which are crucial for understanding the solutions to these optimization problems.

Limitations and Future Work

  • Flatness and Irreducibility Conditions: The extraction of optimizers relies on "flatness" and "irreducibility" conditions, which are not always guaranteed. The paper acknowledges this and suggests further research into these conditions.
  • Implementation Efficiency: While the sparse approach is computationally more efficient, the current implementation in Matlab is noted to be inefficient in constructing the SDP problem itself. Future work aims to interface with more efficient C libraries.
  • Generalizing to Other Structures: The authors suggest exploring how to exploit other properties of structured non-commutative polynomials, such as symmetry, beyond sparsity.
  • Alternative Representations: Investigating alternative representations of sparse positive polynomials, beyond sums of hermitian squares, is proposed as a future research direction.

Summary updated

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):822–843, 2006) and Waki et al. (SIAM J Optim 17(1):218–242, 2006). The Gelfand–Naimark–Segal 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 of noncommutative polynomials from the literature.
BibTeX
@inproceedings{klep2022sparse,
  author = {Igor Klep and Victor Magron and Janez Povh},
  title = {{Sparse noncommutative polynomial optimization}},
  booktitle = {Math. Program},
  year = {2022},
  url = {https://openreview.net/forum?id=7_2W5-GnCL},
}
Figure