Exact Sums-of-Squares Certificates in Numeric Algebraic Geometry.

摘要

We consider the problem of finding the nearest polynomial/system with either a fixed or arbitrary root. Our distance measure to the nearest polynomial/system is the weighted Euclidean, one, or infinity coefficient vector norm. Although much work has already been done on this problem, we offer a new proof in the Euclidean norm case, which uses parameterized Lagrangian multipliers. We present formulas for when the root is real or complex, and when the function has real or complex coefficients. Our formulas also allow fixing selected coefficients of f to their input values and only deforming the other coefficients in f˜, thus preserving sparsity or monicity, for instance. We present an algorithm for computing the nearest polynomial with given linear equality and inequality coefficient constraints. Linear inequality constraints on the coefficients of f˜, for instance non-negativity (ci ≥ 0), can now be imposed via Karush-Kuhn-Tucker (KKT) conditions and the arising systems solved via linear programming, at least for a fixed real root. We further extend our algorithms to systems.;Furthermore, we consider the weighted infinity norm and one norm as the distance measure. We give explicit solutions for finding the nearest polynomial with a given root. The resulting functions are optimizable over the root in the unconstrained case. We also consider finding the nearest polynomial with linear inequality constraints on the coefficients. For a given root, this results in solving a linear program, due to Tchebycheff, and for an arbitrary root, this results in conducting a grid search.;In addition, we explore using sums-of-squares certificates to certify a lower bound for the distance to the nearest polynomial with a real root. Some polynomials that cannot be written as a sum-of-squares, such as a modified Motzkin polynomial, have a positive distance to the nearest polynomial with a real root and a sum-of-squares certificate for a positive lower bound on that distance. These sums-of-squares certificates offer an alternative proof that a polynomial has no real root and a deformation analysis for Seidenberg's problem.;Our last result is on a somewhat separate area of research than the rest of our results, approximate GCD. We generalize the univariate resultant to several polynomials.