Global optimization of polynomials restricted to a smooth variety using sums of squares

2012 
Let f"1,...,f"p be in Q[X], where X=(X"1,...,X"n)^t, that generate a radical ideal and let V be their complex zero-set. Assume that V is smooth and equidimensional. Given f@?Q[X] bounded below, consider the optimization problem of computing f^@?=inf"x"@?"V"@?"R"^"nf(x). For A@?GL"n(C), we denote by f^A the polynomial f(AX) and by V^A the complex zero-set of f"1^A,...,f"p^A. We construct families of polynomials M"0^A,...,M"d^A in Q[X]: each M"i^A is related to the section of a linear subspace with the critical locus of a linear projection. We prove that there exists a non-empty Zariski-open set @?@?GL"n(C) such that for all A@?@?@?GL"n(Q), f(x) is positive for all x@?V@?R^n if and only if, f^A can be expressed as a sum of squares of polynomials on the truncated variety generated by the ideal , for 0@?i@?d. Hence, we can obtain algebraic certificates for lower bounds on f^@? using semi-definite programs. Some numerical experiments are given. We also discuss how to decrease the number of polynomials in M"i^A.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    39
    References
    21
    Citations
    NaN
    KQI
    []