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.
COBISS.SI-ID: 15438937
We show that when the feasible set of a quadratic problem consists of orthogonal matrices from R^{n×k}, then we can transform it into a semidefinite program in matrices of order kn which has the same optimal value. We show how to improve significantly using this result the well-known Donath-Hoffman eigenvalue lower bound for GPP by semidefinite programming. We also show that the copositive strengthening of the semidefinite lower bounds for graph partitionig quadratic assignment problem yields the exact values.
COBISS.SI-ID: 15143001
We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. We also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent.
COBISS.SI-ID: 1024132929
The package contains Matlab functions and procedures to handle NC polynomials and to check SOHS decompositions and positivity of such polynomials.
COBISS.SI-ID: 15233113
Several new methods to approximate the optimum of hard problems based on copositive and semidefinite programming are presented. All copositive results eventually rely on semidefinite programming.
COBISS.SI-ID: 15199833