Izvorni znanstveni članak

OPTIMIZATION AND APPROXIMATION OF NC POLYNOMIALS WITH SUMS OF SQUARES

Kristijan Cafuta ; Faculty of Electrical Engineering, University of Ljubljana, Slovenia
Igor Klep ; Faculty of Science, University of Ljubljana, Slovenia

Sažetak

In this paper we study eigenvalue optimization of non-commutative polynomials. That is, we compute the smallest or biggest eigenvalue a non-commutative polynomial can attain. Our algorithm is based on sums of hermittian squares. To test for exactness, the solutions of the dual SDP are investigated. When we consider the eigenvalue lower bounds we can show that attainability of the optimal value on the dual side implies that the eigenvalue bound is attained. We also show how to extract global eigenvalue optimizers with a procedure based on two ingredients:
- the first is the solution to the truncated (tracial) moment problem;
- the second is the Gelfand-Naimark-Segal (GNS) construction.
The implementation of these procedures in our computer algebra system NC-SOStools is presented and several examples pertaining to matrix inequalities are given to illustrate the results.

Ključne riječi

noncommutative polynomial; sum of squares; semidefnite programming; trace optimization; eigenvalue optimization; free positivity

Hrčak ID:

93436

URI

https://hrcak.srce.hr/93436

Datum izdavanja:

22.12.2010.

Posjeta: 792 *