Approximate GCDs of polynomials and sparse SOS relaxations

The problem of computing approximate GCDs of several polynomials with real or complex coefficients can be formulated as computing the minimal perturbation such that the perturbed polynomials have an exact GCD of given degree. We present algorithms based on SOS (Sums Of Squares) relaxations for solving the involved polynomial or rational function optimization problems with or without constraints.