Semidefinite programming and sums of hermitian squares of noncommutative polynomials

An algorithm for finding sums of hermitian squares decompositions for polynomials in noncommuting variables is presented. The algorithm is based on the “Newton chip method”, a noncommutative analog of the classical Newton polytope method, and semidefinite programming.