Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleGlobal optimization of polynomials restricted to a smooth variety using sums of squares
Author(s) Aurélien Greuet, Feng Guo, Mohab Safey, Lihong Zhi
TypeArticle in Journal
AbstractLet 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 n f ( x ) . For A ∈ G L 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 풪 ⊂ G L n ( C ) such that for all A ∈ 풪 ∩ G L 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 〈 M i A 〉 , 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 .
KeywordsGlobal constrained optimization, Polynomials, Sum of squares, Polar varieties
URL http://www.sciencedirect.com/science/article/pii/S0747717111001957
JournalJournal of Symbolic Computation
Pages503 - 518
Translation No
Refereed No