Title | ||
---|---|---|
Global optimization of polynomials restricted to a smooth variety using sums of squares |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.jsc.2011.12.003 | J. Symb. Comput. |
Keywords | DocType | Volume |
complex zero-set,numerical experiment,radical ideal,linear projection,linear subspace,smooth variety,global optimization,algebraic certificate,lower bound,critical locus,non-empty Zariski-open set,polynomials M | Journal | 47 |
Issue | ISSN | Citations |
5 | 0747-7171 | 11 |
PageRank | References | Authors |
0.58 | 11 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Aurélien Greuet | 1 | 39 | 1.74 |
Feng Guo | 2 | 11 | 0.58 |
Mohab Safey El Din | 3 | 450 | 35.64 |
Lihong Zhi | 4 | 463 | 33.18 |