Constrained Eigenvalue and Trace-Optimization of Polynomials in Noncommuting Variables

Kristijan Çafuta, Igor Klep and Janez Povh^*

In the talk we present constrained eigenvalue and trace optimisation of non-commutative polynomials. We relate eigenvalue and trace positivity with sums of hermitian squares and weights and present how to find these decompositions by semidefinite programming. We study special cases when constrains define nc polydisc and nc cube and show that in this special case: (1) an nc polynomial has non-negative eigenvalues if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using a single semidefinite program (SDP) (3) the dual solution to this "single" SDP can be exploited to extract eigenvalue optimizers with an algorithm based on two ingredients: (i) solution to a truncated nc moment problem via flat extensions and (ii) Gelfand-Naimark-Segal (GNS) construction. The implementation of these procedures in our computer algebra system NCSOStools will be presented.

Mathematics Subject Classification: 90C22 13J30

Keywords: noncommutative polynomial; optimization; sum of squares; semidefinite programming; moment problem; Hankel matrix; flat extension; Matlab toolbox; real algebraic geometry; free positivity

Minisymposion: Algorithms Based on Semidefinite Optimization