TIGHT RELAXATIONS FOR POLYNOMIAL OPTIMIZATION AND LAGRANGE MULTIPLIER EXPRESSIONS 7 1 JIAWANGNIE 0 2 Abstract. Thispaperproposestightsemidefiniterelaxationsforpolynomial n optimization. Theoptimalityconditionsareinvestigated. Weshowthatgener- a allyLagrangemultiplierscanbeexpressedaspolynomialfunctionsindecision J variables over the set of critical points. The polynomial expressions can be 6 determined by linear equations. Based on these expressions, new Lasserre typesemidefiniterelaxationsareconstructedforsolvingpolynomialoptimiza- ] tion. Weshowthatthehierarchyofnewrelaxationshasfiniteconvergence,or C equivalently, thenewrelaxationsaretightforafiniterelaxationorder. O . h t a 1. Introduction m A general class of optimization problems is [ 1 fmin :=min f(x) v (1.1) s.t. ci(x)=0(i ),  ∈E 9 c (x) 0(j ),  j 4 ≥ ∈I 5 wheref andallci,cj arepolynomialsinx:=(x1,...,xn),therealdecisionvariable. 1 The and aretwodisjointfiniteindexsetsofconstrainingpolynomials. Lasserre’s 0 relaxEationsI[16] are generally used for solving (1.1) globally, i.e., to find the global . 1 minimum value f and minimizer(s) if any. The convergence of Lasserre’s relax- min 0 ations is related to optimality conditions. 7 1 1.1. Optimality conditions. A general introduction of optimality conditions in : v nonlinearprogrammingcanbe foundin[1,Section3.3]. Letube alocalminimizer i of (1.1). Denote the index set of active constraints X r (1.2) J(u) := i ci(u)=0 . a { ∈E ∪I | } Iftheconstraint qualification condition (CQC)holdsatu,i.e.,thegradients c (u) i ∇ (i J(u)) are linearly independent ( denotes the gradient), then there exist ∈ ∇ Lagrange multipliers λ (i ) satisfying i ∈E ∪I (1.3) f(u)= λ c (u), i i ∇ ∇ i ∈XE∪I (1.4) c (u)=0(i ), λ c (u)=0(j ), i j j ∈E ∈I (1.5) c (u) 0(j ), λ 0(j ). j j ≥ ∈I ≥ ∈I 2010 Mathematics Subject Classification. 65K05,90C22,90C26. Keywordsandphrases. Lagrangemultiplier,Lasserrerelaxation,tightrelaxation,polynomial optimization,criticalpoint. 1 2 JIAWANGNIE Thesecondequationin(1.4)iscalledthecomplementaritycondition. Ifλ +c (u)> j j 0 for all j , the strict complementarity condition (SCC) is said to hold. For the ∈I λ ’s satisfying (1.3)-(1.5), the associated Lagrange function is i L(x):=f(x) λ c (x). i i − i ∈XE∪I Under the constraint qualification condition, the second order necessary condition (SONC) holds at u, i.e., ( 2 denotes the Hessian) ∇ (1.6) vT 2L(u) v 0 for all v c (u) . i ⊥ ∇ ≥ ∈ ∇ (cid:16) (cid:17) i∈\J(u) Here, c (u) is the orthogonalcomplement of c (u). If it further holds that i ⊥ i ∇ ∇ (1.7) vT 2L(u) v >0 for all 0=v ci(u)⊥, ∇ 6 ∇ (cid:16) (cid:17) i∈\J(u) then the second order sufficient condition (SOSC) is said to hold. If the con- straint qualification condition holds at u, then (1.3), (1.4) and (1.6) are necessary conditionsforu to be alocalminimizer. If(1.3),(1.4), (1.7)andthe strictcomple- mentarity condition hold, then u is a strict local minimizer. 1.2. Some existing work. Under the archimedeancondition(see 2), the hierar- § chy of Lasserre’s relaxations converges asymptotically [16]. Moreover, in addition to the archimedeanness,if the constraintqualification,strict complementarity,and secondordersufficientconditionsholdateveryglobalminimizer,thentheLasserre’s hierarchyconvergesinfinitelymanysteps[31]. Forconvexpolynomialoptimization, the Lasserre’s hierarchy has finite convergence under the strict convexity or sos- convexity condition [7, 19]. For unconstrained polynomial optimization, the stan- dardsumofsquaresrelaxationwasproposedin[33]. Whentheequalityconstraints define a finite set, the Lasserre’s hierarchy also has finite convergence,as shown in [17, 23, 29]. Recently, a bounded degree hierarchy of relaxations was proposed for polynomial optimization [22]. General introductions to polynomial optimization and moment problems can be found in the books and surveys [20, 21, 24, 25, 37]. Lasserre’s relaxations provide lower bounds for the minimum value. There also exist methods that compute upper bounds [8, 18]. A convergence rate analysis for such upper bounds is given in [9, 10]. When a polynomial optimization problem does not have minimizers (i.e., the infimum is not achievable), there are relaxation methods for computing the infimum [36, 40]. A new type of Lasserre relaxations, based on Jacobian representations, were recently proposed in [28]. The hierarchy of such relaxations always has finite con- vergence, when the feasible sets are nonsingular. When there are only equality constraints c (x)= =c (x)=0, the method needs the maximal minors of the 1 m ··· matrix f(x) c (x) c (x) . 1 m ∇ ∇ ··· ∇ When there are inequal(cid:2)ity constraints, it requires to e(cid:3)numerate all possibilities of active constraints. The method in [28] is expensive when there are a lot of constraints. For unconstrained optimization, it is reduced to the gradient sum of squares relaxations in [26]. TIGHT RELAXATIONS AND LAGRANGE MULTIPLIER EXPRESSIONS 3 1.3. New contributions. When Lasserre’s relaxations are used to solve polyno- mial optimization, the following issues are of concerns: The convergence depends on the archimedean condition (see 2), which is • § satisfied only if the feasible set is compact. If the set is noncompact, how can we get convergentrelaxations? The cost of Lasserre’s relaxations depends significantly on the relaxation • order. For a fixed order, can we construct tighter relaxations than the standard ones? When the convergence of Lasserre’s relaxations is slow, can we construct • new relaxations whose convergence is faster? Whenthe optimality conditionsfailto hold,the Lasserre’shierarchymight • not have finite convergence. Can we construct a new hierarchy of stronger relaxations that also has finite convergence for such cases? This paperdiscussesthe aboveissues. We constructtighter relaxationsby using optimality conditions. In (1.3)-(1.4), under the constraint qualification condition, the Lagrange multipliers λ are uniquely determined by u. Note that (u,λ) is a i solution to the polynomial system in (x,λ): (1.8) λ c (x)= f(x), c (x)=λ c (x)=0(i ,j ). i i i j j ∇ ∇ ∈E ∈I i ∈XE∪I Apointxsatisfying(1.8)iscalledacritical point,andsuch(x,λ)iscalledacritical pair. In(1.8),oncexisknown,λcanbedeterminedbylinearequations. Generally, the value of x is not known. One can try to express λ as a rational function in x. Suppose = 1,...,m and denote E ∪I { } G(x):= c (x) c (x) . 1 m ∇ ··· ∇ When m n and rankG(x)=m(cid:2), we can get the rationa(cid:3)l expression ≤ (1.9) λ= G(x)TG(x) −1G(x)T f(x). ∇ Typically, the matrix inverse(cid:0) G(x)TG(x(cid:1)) −1 is expensive for usage. The denom- inator det G(x)TG(x) is typically a high degree polynomial. When m > n, (cid:0) (cid:1) G(x)TG(x) is always singular and we cannot express λ as in (1.9). (cid:0) (cid:1) Do there exist polynomials p (i ) such that each i ∈E ∪I (1.10) λ =p (x) i i for all (x,λ) satisfying (1.8)? If they exist, then we can do: The polynomial system (1.8) can be simplified to • (1.11) p (x) c (x)= f(x), c (x)=p (x)c (x)=0(i ,j ). i i i j j ∇ ∇ ∈E ∈I i ∈XE∪I For each j , the sign condition λ 0 is equivalent to j • ∈I ≥ (1.12) p (x) 0. j ≥ The new conditions (1.11) and (1.12) only use the decision variable x, but not λ. They can be used to construct tighter relaxations for solving (1.1). When do there exist polynomials p satisfying (1.10)? If they exist, how can we i compute them? How can we use them to construct tighter relaxations? Do the new relaxations have advantages over the old ones? These questions are the main topics of this paper. Our major results are: 4 JIAWANGNIE We show that the polynomials p satisfying (1.10) exist for nonsingular i • constraints. Moreover,they can be determined by linear equations. Using the new conditions (1.11)-(1.12), we can construct tight relaxations • for solving (1.1). To be more precise, we construct a hierarchy of new relaxations, which has finite convergence. This is true even if the feasible set is noncompact and/or the optimality conditions fail to hold. Foreveryrelaxationorder,thenewrelaxationsaretighterthanthestandard • ones in the prior work. The paper is organized as follows. Section 2 reviews some basics in polynomial optimization. Section3constructsnew relaxationsandprovestheirtightness. Sec- tion4characterizeswhenthepolynomialsp ’ssatisfying(1.10)existandshowshow i to determine them, for polyhedral constraints. Section 5 discusses the case of gen- eral nonlinear constraints. Section 6 gives examples of using the new relaxations. Section 7 discusses some related issues. 2. Preliminaries Notation The symbol N (resp., R, C) denotes the set of nonnegative integral (resp., real, complex) numbers. The symbol R[x]:=R[x ,...,x ] denotes the ring 1 n of polynomials in x:=(x ,...,x ) with real coefficients. The R[x] stands for the 1 n d set of real polynomials with degrees d. Denote ≤ Nn := α:=(α ,...,α ) Nn α :=α + +α d . d { 1 n ∈ || | 1 ··· n ≤ } For a polynomial p, deg(p) denotes its total degree. For t R, t denotes the ∈ ⌈ ⌉ smallest integer t. For an integer k > 0, denote [k] := 1,2,...,k . For x = ≥ { } (x ,...,x ) and α=(α ,...,α ), denote 1 n 1 n xα := xα1 xαn, [x] := 1 x x x2 x x xd T . 1 ··· n d 1 ··· n 1 1 2 ··· n The superscript T denotes the tra(cid:2)nspose of a matrix/vector. The e de(cid:3)notes the i ith standard unit vector, while e denotes the vector of all ones. The I denotes m the m-by-m identity matrix. By writing X 0 (resp., X 0), we mean that X (cid:23) ≻ is a symmetric positive semidefinite (resp., positive definite) matrix. For matrices X ,...,X , diag(X ,...,X ) denotes the block diagonal matrix whose diagonal 1 r 1 r blocks are X ,...,X . In particular, for a vector a, diag(a) denotes the diagonal 1 r matrix whose diagonal entry vector is a. For a function f in x, f denotes the xi partial derivative of f with respect to x . i We review some basics in computational algebra and polynomial optimization. They could be found in [4, 20, 21, 24, 25]. An ideal I of R[x] is a subset such that I R[x] I and I +I I. For a tuple h = (h ,...,h ) of polynomials, Ideal(h) 1 m · ⊆ ⊆ denotes the smallest ideal containing all h , which is the set i h R[x]+ +h R[x]. 1 m · ··· · The 2kth truncation of Ideal(h) is the set Ideal(h) := h R[x] + +h R[x] . 2k 1· 2k−deg(h1) ··· m· 2k−deg(hm) For an ideal I, its complex and real varieties are respectively defined as C(I):= v Cn p(v)=0 p I , R(I):= C(I) Rn. V { ∈ | ∀ ∈ } V V ∩ TIGHT RELAXATIONS AND LAGRANGE MULTIPLIER EXPRESSIONS 5 Apolynomialσ issaidtobe asumofsquares(SOS)ifσ =s2+ +s2 forsome polynomials s ,...,s R[x]. The set of all SOS polynomials1in·x··is dkenoted as 1 k ∈ Σ[x]. For a degree d, denote the truncation Σ[x] :=Σ[x] R[x] . d d ∩ For a tuple g =(g ,...,g ), its quadratic module is the set 1 t Qmod(g):=Σ[x]+g Σ[x]+ +g Σ[x]. 1 t · ··· · The 2kth truncation of Qmod(g) is the set Qmod(g) := Σ[x] +g Σ[x] + +g Σ[x] . 2k 2k 1· 2k−deg(g1) ··· t· 2k−deg(gt) For convenience of notation, we denote IQ(h,g) := Idea(h)+Qmod(g), (2.1) IQ(h,g) := Idea(h) +Qmod(g) . 2k 2k 2k (cid:26) The set IQ(h,g) is said to be archimedean if there exists p IQ(h,g) such that ∈ p(x) 0 defines a compact set. If IQ(h,g) is archimedean, then the set ≥ K := x Rn h(x)=0, g(x) 0 { ∈ | ≥ } mustbecompact. Conversely,ifK iscompact,say,K B(0,R)(the ballcentered ⊆ at 0 with radius R), then IQ(h,(g,R2 xTx)) is always archimedean and h = − 0, (g,R2 xTx) 0 give the same set K. − ≥ Theorem 2.1 (Putinar, [34]). Let h,g be tuples of polynomials in R[x]. Let K be as above. Assume IQ(h,g) is archimedean. If a polynomial f R[x] is positive on ∈ K, then f IQ(h,g). ∈ Interestingly, if f is only nonnegative on K but some standard optimality con- ditions hold, then we still have f IQ(h,g) [31]. Let RNnd be the space of real se∈quences indexed by α Nn. A vector in RNnd is ∈ d called a truncated multi-sequence (tms) of degree d. A tms y := (yα)α Nn defines the Riesz functional R acting on R[x] as ∈ d y d (2.2) Ry(cid:16) X fαxα(cid:17):= X fαyα. α∈Nn α∈Nn d d For f R[x]d and y RNnd, we denote ∈ ∈ (2.3) f,y :=R (f). y h i Let q R[x]2k. The kth localizing matrix of q, generated by a tms y RNn2k, is the ∈ ∈ symmetric matrix L(k)(y) such that q (2.4) vec(a )T L(k)(y) vec(a )=R (qa a ) 1 q 2 y 1 2 for all a ,a R[x] (cid:16). (The v(cid:17)ec(a ) denotes the coefficient vector of a .) 1 2 k deg(q)/2 i i ∈ −⌈ ⌉ When q =1 (the constant one polynomial), L(k)(y) is called a moment matrix and q we denote (2.5) M (y):=L(k)(y). k 1 The columns and rows of L(k)(y), as well as M (y), are indexed by α Nn with q k ∈ 2α +deg(q) 2k. When q =(q ,...,q ) is a tuple of polynomials, we define 1 r | | ≤ (2.6) L(k)(y) := diag L(k)(y),...,L(k)(y) , q q1 qr (cid:16) (cid:17) 6 JIAWANGNIE a block diagonal matrix. For the polynomial tuples h,g as above, the set (2.7) S(h,g)2k := y ∈RN2nk L(hk)(y)=0, L(gk)(y)(cid:23)0 is a spectrahedralcone in RNn2nk. The set(cid:12)(cid:12)(cid:12)IQ(h,g)2k is also a conveox cone in R[x]2k. The dual cone of IQ(h,g) is precisely S(h,g) [21, 24, 32]. This is because for 2k 2k all p IQ(h,g) and for all y S(h,g) , we have p,y 0. 2k 2k ∈ ∈ h i≥ 3. The construction of tight relaxations Consider the polynomial optimization problem (1.1). Let λ:=(λ ) i i ∈E∪I be the vector of Lagrange multipliers. Denote the set c (x)=λ c (x)=0 (i ,j ) i j j (3.1) := (x,λ) Rn RE∪I f(x)= λ ∈cE(x)∈I . K ( ∈ × (cid:12) ∇ i∇ i ) (cid:12)(cid:12) i∈PE∪I Each point in is called a critical pai(cid:12)r. The projection K (cid:12) (3.2) := u (u,λ) c K { | ∈K} is the set of real critical points for (1.1). To construct tight relaxations for solving (1.1), we need the following assumption for Lagrange multipliers. Assumption 3.1. For each i , there exists a polynomial p R[x] such that i ∈E∪I ∈ for all (x,λ) it holds that ∈K λ = p (x). i i Assumption 3.1 is generally satisfied. For the following cases, we can express λ as a polynomial function in x explicitly. (Simplex)Forthesimplex eTx 1=0, x 0,...,x 0 ,itcorresponds 1 n • { − ≥ ≥ } to that = 0 , = [n], c (x) = eTx 1, c (x) = x (j [n]). The 0 j j E { } I − ∈ Lagrange multipliers can be expressed as (3.3) λ =xT f(x), λ =f xT f(x) (j [n]). 0 ∇ j xj − ∇ ∈ (Hypercube) For the hypercube [ 1,1]n, it corresponds to that = , • − E ∅ =[n] and each c (x)=1 x2. We can show that I j − j 1 (3.4) λ = x f (j [n]). j −2 j xj ∈ (Ballorsphere)Theconstraintis1 xTx=0or1 xTx 0. Itcorresponds • − − ≥ to that = 1 and c =1 xTx. We have 1 E ∪I { } − 1 (3.5) λ = xT f(x). 1 −2 ∇ (Triangular constraints) Suppose = 1,...,m and each • E ∪I { } c (x) =τ x +q (x ,...,x ) i i i i i+1 n for some polynomials q R[x ,...,x ] and scalars τ = 0. The matrix i i+1 n i ∈ 6 T(x),consistingofthefirstmrowsof[ c (x),..., c (x)],isaninvertible 1 m ∇ ∇ lower triangular matrix with constant diagonal entries. Then, λ=T(x)−1· fx1 ··· fxm T . Note that the inverse T(x)−1 i(cid:2)s also a matrix(cid:3)polynomial. TIGHT RELAXATIONS AND LAGRANGE MULTIPLIER EXPRESSIONS 7 For more general constraints, we can also express λ as a polynomial function in x on the set . This will be discussed in 4 and 5. c K § § For the polynomials p as in Assumption 3.1, denote i (3.6) φ := f p c , p c , ψ := p . ∇ − i∇ i j j j j j ∈I ∈I (cid:16) i∈XE∪I (cid:0) (cid:1) (cid:17) (cid:0) (cid:1) When the minimum value f of (1.1) is achieved at a critical point, (1.1) is min equivalent to the problem f :=min f(x) c (3.7) s.t. c (x)=0, c (x) 0,  eq in ≥ φ(x)=0, ψ(x) 0.  ≥ We can apply Lasserre relaxations to solve it. For an integer k > 0 (called the  relaxation order), the kth order Lasserre’s relaxation for (3.7) is f :=min f,y k′ h i s.t. 1,y =1,M (y) 0 k (3.8)  Lh(k)(iy)=0, L(k)((cid:23)y) 0,  Lc(keq)(y)=0, L(ckin)(y) (cid:23)0, y RNn2k. φ ψ (cid:23) ∈ Since x0 = 1 (the constant one polynomial), the condition 1,y = 1 means that h i (y) =1. Its dual optimization problem is 0 f := max γ (3.9) k s.t. f γ IQ(c ,c ) +IQ(φ,ψ) . eq in 2k 2k (cid:26) − ∈ We refer to 2 for the notation used in (3.8)-(3.9). They are equivalent to some § semidefinite programs (SDPs), so they can be solved by SDP solvers (e.g., SeDuMi [38]). For k =1,2, , we get a hierarchy of Lasserre relaxations. In (3.8)-(3.9), if ··· we removethe usageof φand ψ, they are reducedto standardLasserrerelaxations in [16]. So, (3.8)-(3.9) are stronger relaxations. By the construction of φ as in (3.6), Assumption 3.1 implies that = u Rn : c (u)=0, φ(u)=0 . c eq K { ∈ } By Lemma 3.3 of [6], f achieves only finitely many values on , say, c K (3.10) v < <v . 1 N ··· A point u may not be feasible for (3.7), i.e., c (u) 0 or ψ(u) 0). In c in ∈ K 6≥ 6≥ applications,weare ofteninterestedin the optimal value f of(3.7). When (3.7) is c infeasible, by convention, we set f = + . c ∞ When the optimal value f of (1.1) is achieved at a critical point, f = f . min c min This is the case if the feasible set is compact (or f is coercive) and the constraint qualification condition holds. As in [16], one can show that (3.11) f f f k ≤ k′ ≤ c for all k. Moreover, f and f are both monotonically increasing. If for some { k} { k′} order k it occurs that fk =fk′ =fc, then the kth order Lasserre’s relaxation is said to be tight (or exact). 8 JIAWANGNIE 3.1. Tightness of the relaxations. Letc ,ψ, ,f be asabove. We referto 2 in c c K § for the notation Qmod. We begin with a general assumption. Assumption 3.2. There exists ρ Qmod(c ,ψ) such that if u and f(u) < in c ∈ ∈ K f , then ρ(u)<0. c In Assumption 3.2, the hypersurface ρ(x)=0 separates feasible and nonfeasible critical points. Clearly, if u is a feasible point for (3.7), then c (u) 0 and c in ∈ K ≥ ψ(u) 0, and hence ρ(u) 0. Assumption 3.2 generally holds. For instance, it is ≥ ≥ satisfied for the following general cases. a) When there are no inequality constraints, c and ψ are empty tuples. in Then, Qmod(c ,ψ)=Σ[x] and Assumption 3.2 is satisfied for ρ=0. in b) Suppose the set is finite, say, = u ,...,u , and c c 1 D K K { } f(u ),...,f(u )<f f(u ),...,f(u ). 1 t 1 c t D − ≤ Let ℓ ,...,ℓ be real interpolating polynomials such that ℓ (u ) = 1 for 1 D i j i=j andℓ (u )=0fori=j. Foreachi=1,...,t,theremustexistj i j i 6 ∈I such that c (u )<0. Then, the polynomial ji i 1 (3.12) ρ:= − c (x)ℓ (x)2+ ℓ (x)2 c (u ) ji i i i<t ji i i t X X≥ satisfies Assumption 3.2. c) For each x with f(x) = v < f , at least one of the constraints c (x) i c j ≥ 0,p (x) 0(j ) is violated. Suppose for each critical value v < f , j i c ≥ ∈ I there exists g c ,p such that i j j j ∈{ } ∈I g <0 on f(x)=v . i c i K ∩{ } Letϕ ,...,ϕ berealunivariatepolynomialssuchthatϕ (v )=0fori=j 1 N i j 6 and ϕ (v )=1 for i=j. Suppose v =f . Then, the polynomial i j t c 2 2 (3.13) ρ:= g (x) ϕ (f(x)) + ϕ (f(x)) i i i i<t i t X (cid:0) (cid:1) X≥ (cid:0) (cid:1) satisfies Assumption 3.2. We refer to 2 for the archimedean condition and the notation IQ(h,g) as in § (2.1). The following is about the convergence of relaxations (3.8)-(3.9). Theorem 3.3. Suppose = and Assumption 3.1 holds. If c K 6 ∅ i) IQ(c ,c )+IQ(φ,ψ) is archimedean, or eq in ii) IQ(c ,c ) is archimedean, or eq in iii) Assumption 3.2 holds, then f =f =f for all k sufficiently large. Therefore, if the minimum value f k k′ c min of (1.1) is achieved at a critical point, then f = f = f for all k big enough if k k′ min one of the conditions i)-iii) is satisfied. Remark: InTheorem3.3,theconclusionholdsifoneofconditionsi)-iii)issatisfied. Theconditionii)isonlyaboutconstrainingpolynomialsof(1.1). Itcanbe checked without usage of φ,ψ. Also note that the condition ii) implies the condition i). Proof of Theorem 3.3. Clearly, every point in the complex variety := x Cn c (x)=0,φ(x)=0 1 eq K { ∈ | } TIGHT RELAXATIONS AND LAGRANGE MULTIPLIER EXPRESSIONS 9 is a complex critical point. By Lemma 3.3 of [6], the objective f achieves finitely many real values on = Rn, say, they are v < <v . Up to the shifting c 1 1 N K K ∩ ··· of a constant in f, we can further assume that f = 0. Clearly, f equals one of c c v ,...,v , say v =f =0. 1 N t c Case I: Assume the set IQ(c ,c )+IQ(φ,ψ) is archimedean. Let eq in I := Ideal(c ,φ), eq thecriticalideal. Notethat 1 = C(I). Thevariety C(I)isaunionofirreducible subvarieties, say, V ,...,V .KIf V V Rn = , then f isVa real constant on V , which 1 ℓ i i ∩ 6 ∅ equals one of v ,...,v . This can be implied by Lemma 3.3 of [6] and Lemma 3.2 1 N of [28]. Denote the subvarieties of C(I): V T := f(x)=v (i=t,...,N). i 1 i K ∩{ } Let T be the union of irreducible subvarieties V , such that either V Rn = t 1 i i − ∩ ∅ or f v on V with v <v =f . Then, it holds that j i j t c ≡ C(I)=Tt 1 Tt TN. V − ∪ ∪···∪ BytheprimarydecompositionofI [11,39],thereexistidealsI ,I ,...,I R[x] t 1 t N − ⊆ such that I =I I I t 1 t N − ∩ ∩ ··· ∩ and Ti = C(Ii) for all i=t 1,t,...,N. Denote the semialgebraic set V − (3.14) S := x Rn c (x) 0, ψ(x) 0 . in { ∈ | ≥ ≥ } For i = t 1, we have R(It 1) S = , because v1,...,vt 1 < fc and − V − ∩ ∅ − w ,...,w are not real. By the Positivstellensatz [2, Corollary 4.1.8], there exists 1 M p0 Preord(cin,ψ)1 satisfying2+p0 It 1. Note that1+p0 >0 on R(It 1) S. ∈ ∈ − V − ∩ The set I +Qmod(c ,ψ) is archimedean, because I I and t 1 in t 1 − ⊆ − IQ(c ,c )+IQ(φ,ψ) I +Qmod(c ,ψ). eq in t 1 in ⊆ − By Theorem 2.1, we have p :=1+p I +Qmod(c ,ψ). 1 0 t 1 in ∈ − Then 1+p I . There exists p Qmod(c ,ψ) such that 1 t 1 2 in ∈ − ∈ 1 p p mod I . 1 2 t 1 − ≡ ≡ − Since f =(f/4+1)2 1 (f/4 1)2, we have − · − f σ := (f/4+1)2+p (f/4 1)2 mod I . t 1 2 t 1 ≡ − − − So, when k is big enough(cid:8), we have σt 1 Qmod(cin(cid:9),ψ)2k. − ∈ Fori=t,vt =0andf(x)vanisheson C(It). ByHilbert’sStrongNullstellensatz V [4], there exists an integer mt >0 such that fmt It. Hence, ∈ st(ǫ):=√ǫ 1+ǫ−1f 1/2 √ǫmt−1 1/2 ǫ−jfj mod It. ≡ j j=0 (cid:18) (cid:19) (cid:0) (cid:1) X Let σ (ǫ)=s (ǫ)2. Then f +ǫ σ (ǫ) I and t t t t − ∈ mt−2 f +ǫ σ (ǫ) = b (ǫ)fmt+j t j − j=0 X 1Itisthepreorderingof(cin,ψ);see§7.1. 10 JIAWANGNIE for some real numbers bj(ǫ). Note that fmt+j It for all j N. ∈ ∈ Foreachi=t+1,...,N,vi >0andf(x)/vi 1vanisheson C(Ii). ByHilbert’s Strong Nullstellensatz [4], there exists 0<mi −N such that (fV/vi 1)mi Ii. So, ∈ − ∈ 1/2 s := √v 1 + f/v 1 i i i − ≡ √vi(cid:16) mj=i0−(cid:0)1 1/j2 (f/(cid:1)v(cid:17)i−1)j mod Ii. Let σ =s2, then f σ IP. (cid:0) (cid:1) i i − i ∈ i Note that C(Ii) C(Ij) = for all i = j. By Lemma 3.3 of [28], there exist a ,...,a VR[x] s∩uVch that ∅ 6 t 1 N − ∈ a2 + +a2 1 I, a I . t−1 ··· N − ∈ i ∈ j i6=j∈{t\−1,...,N} For ǫ>0, denote the polynomial σ := σ (ǫ)a2+ (σ +ǫ)a2, ǫ t t j j t6=j∈{Xt−1,...,N} then f +ǫ σ = (f σ )a2+(f +ǫ σ (ǫ))a2 − ǫ t=i t 1,...,N − i i − t t +(f6 +∈{ǫ)−(1 a2} a2 ). P − t−1−···− N For each i=t, f σ I , so i i 6 − ∈ N (f σ )a2 I =I. − i i ∈ j j=t 1 \− Hence, there exists k >0 such that 1 (f σ )a2 I (t=i t 1,...,N ). − i i ∈ 2k1 6 ∈{ − } Since f +ǫ σ (ǫ) I , we also have t t − ∈ N (f +ǫ σ (ǫ))a2 I =I. − t t ∈ j j=t 1 \− Moreover, mt−2 (f +ǫ σ (ǫ))a2 = b (ǫ)fmt+ja2. − t t j t j=0 X Each fmt+ja2t ∈I, since fmt+j ∈It. So, there exists k2 >0 such that for all ǫ>0 (f +ǫ σ (ǫ))a2 I . − t t ∈ 2k2 Since 1 a2 a2 I, there also exists k >0 such that for all ǫ>0 − t−1−···− N ∈ 3 (f +ǫ)(1 a2 a2 ) I . − t−1−···− N ∈ 2k3 Hence, if k max k ,k ,k , then we have ∗ 1 2 3 ≥ { } f(x)+ǫ σǫ I2k∗ − ∈ for all ǫ > 0. By the construction, the degrees of all σ and a are independent of i i ǫ. So, σǫ Qmod(cin,ψ)2k∗ for all ǫ>0 if k∗ is big enough. Note that ∈ I2k∗ +Qmod(cin,ψ)2k∗ =IQ(ceq,cin)2k∗ +IQ(φ,ψ)2k∗.