Trouve (1121214), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

We have the expansionXM (A n fgg; p [ Bg );M (A n fgg; [ Ac) 0prso that we obtain from Hn1 ?1 and Hn4 ?1 and lemma 3.5 that?C nfgg (g;cg )=Tk+1 nQk(42) fM (g n fgg; cg)M (A n fgg; [ Ac)gj;ng;k K1 e g= K1 e?He(A)=Tk+1 Qnk with Q 2 Dr (He (A); a1; b1):ALAIN TROUVE34Hence using again Hn1 ?1, we deduce from (41) and (42) that?He (A)=Tk+1 Qn with Q 2 D r (H (A); a ; b );M (A n fgg; [ Ac)j;ne2 2kg;k K2 eand then from Hn2nX?1k=mnP ( (A; m) > k; Xk = g j Xm = i )M (A n fgg; [ Ac)j;ng;k K3 Qm ;with Q 2 Dr (He (A); a3; b3). Applying Hn4 ?1 to M (A n fgg; [ Ac)j;ni;m we concludenally thatnrM (A; [ Ac)j;ni;m K4 Qm with Q 2 D (He (A); a4; b4):We can now prove Hn4 .

Let 0 2 M(A) such that i 2 0. If j 2 0 then CA (i; j ) = 0and the result has been proved above. Otherwise, considering the last visit of theMarkov chain in 0, we getM (A; [ B ) (I + M (A; 0))M (0; c0)(I + M (A n 0; [ Ac));j;m = 1 if i = j and m = n, otherwise its value is zero. Then ifwhere Ii;mfC (0; i2) + CA n0 (i2; j )g ^ C (0; j )C = i 2infAn20where C (0; i2) is the common value of C0 (i1; i2) for any i1 2 0, we deduce that?C=Tm+1 Qn with Q 2 Dr (H (A); a ; b ):M (A; [ B )j;ne5 5i;m K5 emSince one easily see that C CA (i; j ), the proof of Hn4 is completed.Consider the family (Fk )0kr of subsets of E , and the family (Hk )0kr of positivereal valued numbers dened by the following procedure: F0 = F (E ), H0 = +1.

for k 0,{ if Fk = E then the procedure stops and r = k{ otherwise, we dene Hk+1 = supfHe () j Fkc g and Fk+1 = f i 2E j He (i ) = Hk+1 g where i is the largest cycle in E such thati 2 F ().We can now establish the following theorem:OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A35Theorem 4.7. For each 0 k < r, then there exists a > 0; b 0 and K > 0 whichdepends only on E , q, and (and not on V ), such that for all i 2 Fk , all j 2 Fk+1 n Fkwe have(W (j )?W (i))+ =Tm+1 QnL(Fkc; Fkc)j;ni;m Kemlwith Q 2 D (Hk+1 ; a; b).Proof. We rst write the following expansionL(Fkc; Fkc+1)j;ni;mnX Xj 0 2j l=m+10j ;l P ( () > n j X = j 0 ):M (Fkc; j )i;mljNow dene i as the largest cycle in E n fj g which contains i.

We havej 0 ;l fM ( n F ; c )(I + M (F c ; ))gl;j 0M (Fkc; j )i;mik ik j i;m?Ci nFk (i;ci )=Tm+1 nQm; Kewith Q 2 Dr (Hk+1 ; a1; b1). HoweverC inFk (i; ci) C i nfig(i; c) = W (i) + He (i) ? W (i);so thatj 0 ;l Ke?[W (i )+He (i )?W (i)]=Tm+1 Qn :M (Fkc; j )i;mmWe should now study two cases.rst case: Assume that W (j ) W (i), then j 2= i otherwise j 2 F (i ) andj 2 Fk . Hence i i and W (i) + He (i) ? W (i) W (i ) + He (i ) ?W (i) = He (i ) Hk Hk+1 .second case: assume that W (j ) > W (i), then let +i be the smallest cycle such that fi; j g .

We have j +i otherwise i 2 j and W (j ) > W (i)leads to a contradiction. Hence W (i) + He (i) W (j ) + He(j ) so thatW (i) + He (i) ? W (i) Hk+1 + W (j ) ? W (i):From both previous cases, we getL(Fkc; Fk+1 n Fk )j;ni;m nnYX(1 ? ae?Hk+1 =Ts );e?[Hk+1+(Wj ?Wi )+]=Tm+1 Qlm(1 + b)l=m+1s=l+1with Q 2 Dr (Hk+1 ; a2; b2)For proving the result, it is sucient to show that there exists a0 > 0 and K 0 > 0ALAIN TROUVE36such thatLnm+1nXnnYYl0?H=Tsk+1=Qm)K(1 ? ae(1 ? a0e?Hk+1 =Tl ):def l=m+1 s=l+1l=m+2Noting a3 = inf fa; a2g, we get after an integration by partsLnm+1 nXl=m+1+ Sm+1where Sl =P1hh=l Qm .Sl(nYs=l+1nYs=m+1nY(1 ? a3e?Hk+1 =Ts ) ? (1 ? a3e?Hk+1=Ts ))s=l(1 ? a3e?Hk+1 =Ts );Since Sl (1 + b) Qlh?=1m+1 (1 ? a3e?Hk+1 =Th ), we getnXlY?1nY?H=T?H=Tk+1hk+1l (1 + b)(1 ? a3e)a3e(1 ? ae?Hk+1=Ts )l=m+1 h=m+1s=l+1nY(1 ? a3e?Hk+1 =Ts )+ (1 + b)s=m+1nnXYa3e?Hk+1 =Tl )(1 ? a3e?Hk+1=Tl ) 11?+ab (3 l=m+1l=m+1nY(1 ? a3e?Hk+1 =Ts ):+ (1 + b)s=m+1Since Pnl=m+1 a3e?Hk+1 =Tl 2 Qnl=m+1 (1 + (a3=2)e?Hk+1 =Tl ) and(1 + a3 e?Hk+1 =Tl )(1 ? a e?Hk+1 =Tl ) (1 ? a3 e?Hk+1 =Tl );Lnm+1322the result is proved.

Hence, the proof of the theorem is completed.5. Necessary and sufficient condition for convergenceWith this section, we start our study of the convergence properties of the G.S.A.As mentioned in the introduction, our approach will be based on the study on theprobability to be in a level set of the virtual energy W .Denition 5.1. Let > 0.

We denote E the subset of E dened byE = f i 2 E j W (i) min W + g:We give now a necessary and sucient condition on the decreasing cooling schedulefor which the mass in E vanishes when the number of steps increases:OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A37Theorem 5.2. Let q be an irreducible Markov kernel on E and let 2 [1; +1[. LetX be a G.S.A.

with parameter (q; ; P ) and let T be the underlying cooling schedule.Assume that T is decreasing (Tn Tn+1 ) and vanishes when n tends to innity.Then for all > 0,sup P ( Xn 2 E j X0 = i)n?!0 i!+1i2EwhereX ?? =Tne= +1;n0? = supf He () j 2 C (E ) and iinfW (i) min W + g:2Proof. The direct implication can be get from theorem 4.5. Let be a cycle includedin E and such that He () = ?.

Then, for all i 2 P ( Xn 2 j X0 = i ) P ( (; 0) = +1 j X0 = i )1Y c (1 ? de?He()=Tk ):k=0For the converse implication, we have to use the theorem 4.7. From the denition ofthe subsets Fk , we get that there exits k 2 N for which E E n Fk et Hk+1 = ?.Hence, denoting = inf fW (j )?W (i) j i 2 E nEand j 2 E g, we get the inequality:X X XP ( X n 2 E j X0 = i ) P ( Xm = i0 j X0 = i )L(E n Fk ; E n Fk )j;ni0 ;m0m<n i0 2Fk j 2EX ?=Tm+1 nQmKe0m<nwith Q 2 Dl (Hk+1; a; b).

Since (Tn)n2N is decreasing and converges to 0, there existsfor all > 0 an non negative integer M such that for all m M we have e?=Tm+1 =2: Therefore we havenX?1HoweverSincenX?1?=Tnm+1eQm =2Qnm =2:m=Mm=MMX?1e?=Tm+1 Qnm m=0lQ 2 D (Hk+1 ; a; b), weMX?1?1MX?1m=0Qnm get the upper boundQnm (1 + b)nY?1m=MMX?1?1Qnm:(1 ? ae??=Tm );ALAIN TROUVE38so that there exists N 2 N such that for all n N(1 + b)The proof is completed.nY?1m=M(1 ? ae??=Tm ) =2:6. Optimal convergence speed exponentIn this section, we study the optimal convergence speed of supi2E P ( XN 2 E j X0 =i ) for any > 0 (see denition 1.3).

We will consider triangular cooling schedulese.a. we free ourself from an unique cooling schedule for all the nite horizon N andwe allows us to dene for each nite horizon an adapted cooling schedule T N . Wewill established successively an upper and a lower bound for this convergence speed.6.1. Upper bound. In this part, we assume that the family (QT )T>0 in A(q; )satises the following additional condition:C1: There exists a set B of continuous real valued functions on [0; +1[ suchthat(1) For all f and g in B f +g 2B There exists A 0 such that one of the two following inequalitiesis true:{ f (x) g(x) for all x A.{ f (x) g(x) for all x A.(2) For all i; j 2 E , i 6= j , if q(i; j ) > 0, then there exist Aij > 0 and fij 2 Bsuch thatZQ (i; j ) = Aij exp( fij ) with = 1=T:0This extra condition is essentially a condition of monotony in a neighborhood of +1in which is satised by all the standard sequential or parallel annealing algorithms.For example, condition C1 holds ifXXk2Ij 2JQ (i; j ) = f ak ebk g=f cj edj g;where (ak )k2I , (bk )k2I , (cj )j2J and (dj )j2J are nite family of real numbers such thatdj 2J cj e j 6= 0 for all 0.POPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A39Theorem 6.1.

Consider a family (QT )T>0 in A(q; ) which satises C1. Let Xbe a G.S.A. with parameter (q; ; P ) where P = P(Q;T ;0 ) (see denition 1.3) andassume that the cooling schedule in decreasing (Tn Tn+1 ). Then there exists > 0independent of T and of the initial distribution 0 such thatP ( Xn = i ) jinf (j ) Tn (i);2E 0where T is the unique invariant probability measure of QT .Proof. Let us recall rst the well known explicit expression of the invariant probabilitymeasure given by the Wentzell and Freidlin A-graphs in [5]:X X YX YQT (u; v)g:QT (u; v)g=fT (i) = fj 2E g2G(fj g) u!v2gg2G(fig) u!v2gFrom now, we will use the variable = 1=T instead of T which seems to be moreappropriate for our proof. From C1, we get for each u; v 2 E , u 6= v, a continuousfunction fuv in B such that:ZQ (u; v) = Auv exp(Hence, if we note fg = Pu!v2g fuv , we getT (i) = fXg2G(fig)Ag exp(Z0fg )g=f0fuv ):X Xj 2E g2G(fj g)Ag exp(Z0fg )g:Now, considering c+ = Pu6=v fuv+ where fuv+ = fuv 1Ifuv 0 and dening feg = fg ? c+, wehave (i) = a (i)=Z ;whereZXXa (i) =Ag exp( feg ) and Z = a (i):g2G(fig)0i2EAn obvious computation shows that feg 0 so that a (i) is decreasing in for eachi 2 E .

Характеристики

Список файлов лекций