global optimization of polynomials using generalized critical values and sums of squares
Let &Xmacr; = [ X 1 , ..., X n ] and f ? R[&Xmacr;]. We consider the problem of computing the global infimum of f when f is bounded below. For A ? GL n (C), we denote by f A the polynomial f ( A &Xmacr;). Fix a number M ? R greater than inf x ?R n f ( x ). We prove that there exists a Zariski-closed subset A [equation] GL n (C) such that for all A ? GL n (Q) \ A, we have f A ? 0 on R n if and only if for all ? > 0, there exist sums of squares of polynomials s and t in R[&Xmacr;] and polynomials [Equation]. Hence we can formulate the original optimization problems as semidefinite programs which can be solved efficiently in Matlab. Some numerical experiments are given. We also discuss how to exploit the sparsity of SDP problems to overcome the ill-conditionedness of SDP problems when the infimum is not attained.
global optimization polynomials generalized critical values sum of squares semidefinite programing moment matrix