Semidefinite programming and sums of Hermitian squares of noncommutative polynomials
In this short and well-written paper, the authors present an algorithm for finding sums of Hermitian squares decompositions for polynomials in noncommuting variables. The algorithm is based on the author's ''Newton chip method'', a noncommutative analog of the classical Newton polytope method, and semidefinite programming. Let \(\mathbb{R}\left<\overline{X}\right> = \mathbb{R}\left<X_1,\dots, X_n\right>\) denote the algebra of polynomials in noncommuting variables \(X_1,\dots, X_n\) with real coefficients. The elements in this algebra are called NC polynomials. The algebra \(\mathbb{R}\left<\overline{X}\right> \) becomes a \(*\)-algebra with the involution \(*\) that fixes \(\mathbb{R}\cup \{\overline{X}\}\). Let \[ \mathrm{Sym} \mathbb{R}\left<\overline{X}\right> = \{f \in \mathbb{R}\left<\overline{X}\right> : f = f^{*} \}. \] An NC polynomial of the form \(g*g\) is called a \textit{Hermitian square} and the set of all sums of Hermitian squares is denoted by \(\Sigma^2\). Clearly, \(\Sigma^2 \subsetneq \mathrm{Sym} \mathbb{R}\left<\overline{X}\right> \). This article presents an effective \textit{tight} algorithm to compute a Hermitian squares decomposition of a particular symmetric NC polynomial in case this decomposition exists. The algorithm developed in this paper fills an important gap in the new and highly active area of free semialgebraic geometry.
scientific article; zbMATH DE number 5673198
scientific article