Semidefinite programming and sums of Hermitian squares of noncommutative polynomials
type: Item
instance of: scholarly article
title: Semidefinite programming and sums of Hermitian squares of noncommutative polynomials
zbMATH Open document ID: 1246.11092
author: Igor Klep
author: Janez Povh
published in: Journal of Pure and Applied Algebra
publication date: 2010-02-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11E25
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 08B20
Mathematics Subject Classification ID: 13J30
zbMATH DE Number: 5673198
zbMATH Keywords: sums of Hermitian squares
zbMATH Keywords: noncommutative polynomials
zbMATH Keywords: free semialgebraic geometry
zbMATH Keywords: semidefinite programming
zbMATH Keywords: Newton chip method
reviewed by: Luis David Garcia Puente
describes a project that uses: YALMIP
describes a project that uses: GloptiPoly
describes a project that uses: NCSOStools
describes a project that uses: SDPT3
describes a project that uses: Sostools
MaRDI profile type: Publication
full work available at URL: j.jpaa.2009.07.003
OpenAlex ID: W2065791599
Wikidata QID: Q114851521
cites work: ``Positive'' noncommutative polynomials are sums of squares.
cites work: Noncommutative sums of squares
cites work: Q3601985
cites work: Connes' embedding conjecture and sums of Hermitian squares
cites work: Sums of Hermitian squares and the BMV conjecture
cites work: Q4698624
cites work: Semidefinite programming relaxations for semialgebraic problems
cites work: Q3910639
cites work: Algorithms in real algebraic geometry
cites work: Handbook of semidefinite programming. Theory, algorithms, and applications
cites work: SOSTOOLS and Its Control Applications
cites work: An exact duality theory for semidefinite programming and its complexity implications
cites work: Robust convex optimization
cites work: Regularization Methods for Semidefinite Programming
cites work: A boundary point method to solve semidefinite programs
cites work: Extremal psd forms with few terms
cites work: Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
cites work: Semidefinite optimization
cites work: Q4400648
cites work: On the complexity of semidefinite programs
cites work: NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials
cites work: An algorithm for sums of squares of real polynomials
cites work: GloptiPoly 3: moments, optimization and semidefinite programming
cites work: Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
DOI: 10.1016/J.JPAA.2009.07.003
Recommended article: Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials
Recommended article: Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools
Recommended article: A note on Hermitian positive semidefinite matrix polynomials
Recommended article: Rational sums of hermitian squares of free noncommutative polynomials
Recommended article: Q4015912
Recommended article: Discrete Transforms, Semidefinite Programming, and Sum-of-Squares Representations of Nonnegative Polynomials
Recommended article: On matrix algebras associated to sum-of-squares semidefinite programs
Recommended article: Multihomogeneous nonnegative polynomials and sums of squares
Recommended article: Spectral factorizations and sums of squares representations via semidefinite programming
Recommended article: Q3601990
description: scientific article; zbMATH DE number 5673198