Optimization Online


Rational sums of hermitian squares of free noncommutative polynomials

Kristijan Cafuta(kristijan.cafuta***at***fe.uni-lj.si)
Igor Klep(igor.klep***at***fmf.uni-lj.si)
Janez Povh(janez.povh***at***fis.unm.si)

Abstract: In this paper we consider polynomials in noncommuting variables that admit sum of hermitian squares and commutators decompositions. We recall algorithms for finding decompositions of this type that are based on semidefinite programming. The main part of the article investigates how to find such decomposition with rational coefficients if the original polynomial has rational coefficients. We show that the numerical evidence, obtained by the Gram matrix method and semidefinite programming, which is usually an almost feasible point, can be frequently tweaked to obtain an exact certificate using rational numbers. In the presence of Slater points, the Peyrl-Parrilo rounding and projecting method applies. On the other hand, in the absence of strict feasibility, a variant of the facial reduction is proposed to reduce the size of the semidefinite program and to enforce the existence of Slater points. All these methods are implemented in our open source computer algebra package NCSOStools. Throughout the paper many worked out examples are presented to illustrate our results.

Keywords: sum of squares, semidefinite programming, noncommutative polynomial, Matlab toolbox, commutator, cyclic equivalence, free positivity, real algebraic geometry, Motzkin polynomial, Bessis-Moussa-Villani (BMV) conjecture, NCSOStools

Category 1: Optimization Software and Modeling Systems

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Global Optimization


Download: [PDF]

Entry Submitted: 08/02/2013
Entry Accepted: 08/02/2013
Entry Last Modified: 08/02/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society