Диссертация (1150610), страница 10
Текст из файла (страница 10)
Îòìåòèì, ÷òîf (xk ) = f (vk ):f (xk ) − f (vk ) =1 k(x − vk )T A(xk + vk ) + wT (xk − vk ) = 0.|{z}{z}|2k=u A=0m=0 ïî ëåììå 2.4Ïóñòü u∗ ∈ Ω, v∗ ∈ Ω⊥ , u∗ + v∗ = x∗ , òîãäà1f (xk ) − f (x∗ ) = f (vk ) − f (v∗ ) = (vk − v∗ )T A(vk + v∗ ) + wT (vk − v∗ ) ≤21 A(vk + v∗ ) + w ||vk − v∗ ||.2 ïîñëåäíåì âûðàæåíèè ëåâûé ñîìíîæèòåëü îãðàíè÷åí íà Q, â ñèëóâûáîðà γ âûïîëíÿåòñÿf (xk ) − f (x∗ ) ≤ γ||vk − v∗ ||.Äàëåå, ïðèìåíÿÿ Ëåììó 2.6 ê òî÷êàì xk − 21 ∇f (xk ) è x∗ − 12 ∇f (x∗ ) èó÷èòûâàÿ uk , u∗ ∈ Ω, vk , v∗ ∈ Ω⊥ ïîëó÷àåì691||vk+1 − v∗ || ≤ ||(I − A)(vk − v∗ )|| ≤2λ2 (A)1−||vk − v∗ ||.2Òàêèì îáðàçîìδ(xk − x∗ , Ω) ≤ q k ||x0 − x∗ ||èf (xk ) − f (x∗ ) ≤ γq k ||x0 − x∗ ||.Òåïåðü çàìåòèì ñëåäóþùåå: ðàç f (xk ) → f (x∗ ), òîP∞i+1i=0 ||xk− xi ||2 ≤P∞ii+1) = f (x0 ) − f (x∗ ).
Äëÿ ñõîäèìîñòè x äîñòàòî÷íîi=0 f (x ) − f (xP∞i+1ñõîäèìîñòè ðÿäà− xi ||, ÷òî â îáùåì ñëó÷àå íå ñëåäóåò èçi=0 ||xP∞ñõîäèìîñòè i=0 ||xi+1 − xi ||2 . Îäíàêî, â íàøåì ñëó÷àå ñõîäèìîñòü ýêñïîíåíöèàëüíàÿ, ÷òî ïîçâîëÿåò âûâåñòè ñõîäèìîñòü xk :||xk − xk+1 ||2 ≤ f (xk ) − f (xk+1 ) ≤ f (xk ) − f (x∗ ),ñëåäîâàòåëüíî||xk − xk+1 || ≤ q k/2pγ||x0 − x∗ ||,à çíà÷èò xk ñõîäèòñÿ.
Íå óìàëÿÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî xk → x∗ .Íàêîíåö âûâåäåì ñêîðîñòü ñõîäèìîñòè äëÿ xk :k∗||x − x || ≤∞Xi=0∞Xi=k||xi − xi+1 || ≤!q i/2 q k/2pγ||x0 − x∗ || =q k/2 pγ||x0 − x∗ ||.√1− qÇàìå÷àíèÿ. Äëÿ ïðîöåññà xk+1 = xk − 12 (Axk + w) ëåãêî ïîêàçàòü,÷òî u∗ = u0 = u1 = . .
., ÷òî îáëåã÷àåò äîêàçàòåëüñòâî, îäíàêî ïðè íà-ëè÷èè ïðîåêöèè ýòî ñâîéñòâî íå âûïîëíÿåòñÿ, äëÿ ÷åãî è ïîíàäîáèëàñüëåììà 2.6. Âåëè÷èíó λ2 (A) ïðèíÿòî íàçûâàòü ÷èñëîì Ôèäëåðà èëè àë70ãåáðàè÷åñêîé ñâÿçíîñòüþ, îíà âñåãäà ôèãóðèðóåò â êà÷åñòâå ïàðàìåòðàñêîðîñòè ñõîäèìîñòè ëàïëàñèàíîâûõ ñèñòåì. Îáùèé àíàëèç âåëè÷èíûλ2 (A) áûë ïîëó÷åí ñàìèì Ôèäëåðîì â ðàáîòàõ [60,61].  ðàáîòå [24] ïðîàíàëèçèðîâàíî àñèìïòîòè÷åñêîå ïîâåäåíèå âåëè÷èíû â çàâèñèìîñòè îòðàçìåðà ãðàôà (â õóäøåì ñëó÷àå). Ïóíêò 3 äàåò îöåíêó íà ðàññòîÿíèåäî áëèæàéøåé òî÷êè ìèíèìóìà, õîòü íåò íèêàêîé ãàðàíòèè, ÷òî ïîñëåäîâàòåëüíîñòü ñõîäèòñÿ èìåííî ê íåé.Òàê êàê óäàëîñü óñòàíîâèòü ýêñïîíåíöèàëüíóþ ñõîäèìîñòü äëÿ ||xk −x∗ || è ïðè ýòîì ðàçìåð øàãà ïîñòîÿíåí, òî áåç îñîáîãî òðóäà ìîæíî äîêàçàòü, ÷òî â ñëó÷àå, åñëè íà êàæäîé èòåðàöèè ïðîïóñêíûå ñïîñîáíîñòè íåìíîãî èçìåíÿþòñÿ, òî ||xk − x∗ || áóäåò ýêñïîíåíöèàëüíî ñõîäèòñÿ êíåêîòîðîìó øàðó c öåíòðîì â x∗ .
Ïóñòü ck âåêòîð ïðîïóñêíûõ ñïîñîáíîñòåé íà èòåðàöèè k , Qk = {x ∈ Rm | 0 ≤ xe ≤ cke }, fk (x) = 12 xT Ax+xT wk ,wk = B 0T bk , bk = B 00 c00k .  ýòèõ îáîçíà÷åíèÿõ ìû ïîëàãàåì, ÷òî â ñëó÷àåèçìåíåíèÿ ïðîïóñêíûõ ñïîñîáíîñòåé ïîñëåäîâàòåëüíîñòü îöåíîê ãåíåðèðóåòñÿ ïî ïðàâèëó(2.11)xk+1= PQk1kx − ∇fk (x ) ,2Îáîçíà÷èì òàêæå Q = ∪∞k=1 Qk .Ò å î ð å ì à2.5.Ïóñòü xk ïîñëåäîâàòåëüíîñòü, ãåíåðèðóåìàÿ ïîïðàâèëó (2.11) ñ ëþáûì íà÷àëüíûì ïðèáëèæåíèåì x0 ∈ Q0 , ïðè ýòîì||ck || ≤ σ , ||ck − ck−1 || ≤ β , γ = supx∈Q,k ||Ax + wk ||, q = 1 − λ2 (A)/2,0T 00B ||ν = β(1 + ||B(dλ2 (A)) ), òîãäà1.
Áëèæàéøàÿ ê xk òî÷êà ìèíèìóìà x∗k ôóíêöèè fk íàõîäèòñÿ íàðàññòîÿíèè íå áîëååqkν||x0 − x∗0 || −1−q+ν.1−q2. Áëèçîñòü çíà÷åíèÿ ôóíêöèè fk ê îïòèìàëüíîìó çíà÷åíèþ îöåíè71âàåòñÿ ñëåäóþùèì íåðàâåíñòâîìfk (x ) − fk (x ) ≤ γ q ||x0 − x∗0 || −k∗kkν1−qν+1−q.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ïðàêòè÷åñêè ïîâòîðÿåò òåîðåìó 2.4.åñëè îáîçíà÷èò x∗k , u∗k , v∗k òî÷êà ìèíèìóìà fk è å¼ ðàçëîæåíèå ïîΩ, Ω⊥ ñîîòâåòñòâåííî, òî âñå âûêëàäêè âïëîòü äîfk (xk ) − fk (x∗k ) ≤ γ||vk − v∗k ||èäåíòè÷íû. Äàëåå, èç-çà èçìåíåíèÿ ïðîïóñêíûõ ñïîñîáíîñòåé òî÷êà ìèíèìóìà ñäâèãàåòñÿ íå áîëåå, ÷åì íà β èç-çà èçìåíåíèÿ ìíîæåñòâà Qk , èíå áîëåå ÷åì íà ||B 0T B 00 ||β/λ2 (B 0T B 0 ) èç-çà èçìåíåíèÿ ôóíêöèè fk . Òàêèìîáðàçîì1||vk+1 − v∗k+1 || ≤ ||(I − A)(vk − v∗k )|| + ν ≤2q||vk − vk∗ || + ν.Âû÷òåì èç îáîèõ ÷àñòåéν(1−q)||vk+1 − v∗k+1 || −νν≤ q||vk − v∗k || + ν −=(1 − q)(1 − q)q ||vk − v∗k || −Òàêèì îáðàçîìν.(1 − q)||vk − v∗k || ≤ q k ||v0 − v∗0 || −δ vk , B v∗k ,v1−q≤ qkν1−q+ν,1−qν||x0 − x∗0 || −1−q.Òàê êàê ìíîæåñòâî Ωk = {x∗k + y | y ∈ Ω} ñîñòîèò òîëüêî èç òî÷åêìèíèìóìà fk , òî ðàññòîÿíèå äî áëèæàéøåé òî÷êè ìèíèìóìà è åñòü ||vk −v∗k ||.72Çàìå÷àíèå.
Êîíñòàíòà σ íèãäå â ÿâíîé ôîðìå íå èñïîëüçîâàëàñü âòåîðåìå, îäíàêî îò íåå çàâèñèò ðàçìåð ìíîæåñòâà Q, à çíà÷èò è êîíñòàíòàγ.2.2.4Ñõîäèìîñòü ðàíäîìèçèðîâàííîãî àëãîðèòìàÊàê óæå áûëî ñêàçàíî, ðàíäîìèçèðîâàííàÿ âåðñèÿ àëãîðèòìà ïðåäñòàâëÿåò ñïåöèàëüíûé âèä ðàíäîìèçèðîâàííîé ñòîõàñòè÷åñêîé àïïðîêñèìàöèè. Îáîçíà÷èì fk (x) = 12 xT B 0T B 0 x + xT B 0T bk , ∆k ðàíäîìèçèðîâàííîå ïðîáíîå âîçìóùåíèå íà èòåðàöèè k , îïðåäåëÿåìîå ïî ïðàâèëó(2.12)∆k = ±eim ñ.
â.pi,2ãäå eim m-ìåðíûé i-ûé îðò. Äàëåå, Ak = ∆k ∆Tk B 0T B 0 , A = EAi , wik =∆k ∆Tk B 0T bk , wk = Ewik , yk+ = fk (xk + α∆k ) + ξ2k è yk− = fk (xk − α∆k ) +ξ2k+1 çàøóìëåííûå èçìåðåíèÿ íà èòåðàöèè k , ïðè ýòîì ξ2k , ξ2k+1 ïîãðåøíîñòè, âîçíèêàþùèå ïðè èçìåðåíèè bk (êîòîðûé â ñâîþ î÷åðåäüçàâèñèò îò ïðîïóñêíûõ ñïîñîáíîñòåé), ξk ñëó÷àéíàÿ âåëè÷èíà, ðàñïðåäåëåíèå êîòîðîé íåèçâåñòî, Qk = {x ∈ Rm | 0 ≤ xe ≤ cke }.  ýòèõ îáîçíà÷åíèÿõ RandomizedArcBalancing ãåíåðèðóåò ïîñëåäîâàòåëüíîñòü îöåíîêïî ïðàâèëó(2.13)Ò å î ð å ì àxk+12.6.+−y−yk= PQk xk − ∆k k.4αÏóñòü xk ïîñëåäîâàòåëüíîñòü, ãåíåðèðóåìàÿïî ïðàâèëó (2.13) ñ ëþáûì íà÷àëüíûì ïðèáëèæåíèåì x0 ∈ Q0 , Eξk2 ,Eξ2k ξ2k+1 ≤ σ 2 , âûáîð ∆k íå çàâèñèò îò ξ2k è ξ2k+1 , ìíîæåñòâî ∪k Qkîãðàíè÷åíî è γ = supx∈Q,k ||Ax + wk ||, ||ck − ck+1 || ≤ β , λ2 (A) ìèíè- ìàëüíîå îòëè÷íîå îò íóëÿ ñîáñòâåííîå ÷èñëî ìàòðèöû A, q = 1 − λ2 2(A) ,α > 0, ν = β(1 +||B 0T B 00 ||λ2 (B 0T B 0 ) ),R=ν+√σ ,α73òîãäà1.
Åñëè x∗k ëþáàÿ òî÷êà ìèíèìóìà fk íà Qk , òîE dist(xk − x∗k , Ω) ≤ q k/2 (||x0 − x∗0 || − R) + R.2. Åñëè x∗k ëþáàÿ òî÷êà ìèíèìóìà fk íà Qk , òîE{fk (xk ) − fk (x∗k )} ≤ γ(q k/2 (||x0 − x∗0 || − R) + R).3. Åñëè ïîìåõè â èçìåðåíèÿõ îòñóòñòâóþò, à ïðîïóñêíûå ñïîñîáíîñòè íå èçìåíÿþòñÿ (ò.å. R = 0, Qk = Qk+1 , fk ≡ fk+1 ) è xkñõîäèòñÿ ê x∗ , òîE||xk − x∗ || ≤q k/4 pγ||x0 − x∗0 ||√41− qÄîêàçàòåëüñòâî. Âî ïåðâûõ îòìåòèì, ÷òî äëÿ ëþáîãî âîçìîæíîãî ∆kèìååò ìåñòî ||Ak || ≤ 2.
Íåïîñðåäñòâåííûì âû÷èñëåíèåì ïîëó÷àåì, ÷òîïðè âûáîðå äóãè l = (i, j) âûïîëíÿåòñÿ0T 0elm elTmB B x =X(h,j)∈E 0xh −X(j,h)∈E 0xh −X(h,i)∈E 0xh +Xxh .(i,h)∈E 0Êàæäàÿ êîìïîíåíòà âåêòîðà x ìîæåò âõîäèòü â ëþáóþ èç ýòèõ ñóìì, àçíà÷èò ëþáàÿ êîìïîíåíòà âõîäèò ñ êîýôôèöèåíòîì −2, −1, 0, 1 èëè 2, èç÷åãî è ñëåäóåò ||Ak || ≤ 2. Èç âûáîðà γ ñëåäóåòfk (xk ) − fk (x∗ ) ≤ γ||vk − v∗ ||,ãäå v è u ðàçëîæåíèÿ x ïî Ω⊥ , Ω. Èç ëåììû 2.4 ñëåäóåò, ÷òî ÿäðî A èB 0T B 0 ñîâïàäàåò.
Òàê êàê 0 4 Ak 4 2I , òîE{(I −AkAkAAk T) (I −)} 4 E{I −}=I− .2222Èç îïðåäåëåíèÿ ∆k ñëåäóåò, ÷òî E∆k = 0m , E∆Tk ∆ = 1, ∆k ∆Tk ∆k = ∆k ,74à çíà÷èò E∆k ∆Tk ∆k = 0m è, ñëåäîâàòåëüíî, E(ξ2k+1 − ξ2k )∆k Ak = 0.Òàêèì îáðàçîì, ïðèìåíÿÿ Ëåììó 2.6 äëÿ òî÷åê xk − ∆k (yk+ − yk− )/4α èx∗k ïîëó÷àåìE{||vk+1Akξ2k+1 − ξ2k 2)(vk − v∗ ) + ∆k|| } =− v || | x } ≤ E{||(I −24α∗k 2k(vk − v∗ )T E{(I −Ak TAk) (I −)}(vk − v∗ )+221Ak1TE{(ξ2k+1 − ξ2k )∆k (I −)}(vk − v∗k ) +E{∆Tk ∆k (ξ2k+1 − ξ2k )2 } ≤2α24αλ2 (A)σ2k∗ 21−||v − v || + ,2αà çíà÷èòE{||vk+1 − v∗k+1 || | xk } ≤ E{||vk+1 − v∗k || | xk } + ν ≤ 21λ(A)σ2(E{||vk+1 − v∗k ||2 | xk })1/2 + ν ≤ 1 −||vk − v∗k || + ν + √ .2αÎòñþäà âûâîäèìE{||vk − v∗k ||} − R ≤ q k/2 (||x0 − x∗0 || − R).Ïî âûáîðó γEfk (xk ) − fk (x∗k ) ≤ γE||vk − v∗k || ≤ γ(q k/2 (||x0 − x∗0 || − R) + R).Åñëè æå σ = 0, fk ≡ fk+1 , Qk = Qk+1 , òî R = 0, ìíîæåñòâî òî÷åêìèíèìóìà íå èçìåíÿåòñÿ, è ðàññòîÿíèå äî áëèæàéøåé òî÷êè ìèíèìóìàâ ñðåäíåì ñõîäèòñÿ ñ ýêñïîíåíöèàëüíîé ñêîðîñòüþ.Òàê êàê Qk ïðÿìîóãîëüíûé ïàðàëëåëåïèïåä, à íà îäíîì øàãå èçìåíåíèÿ âûïîëíÿþòñÿ òîëüêî ïî îäíîé êîîðäèíàòå, òî ñóùåñòâóåò òàêîé75íàáîð ñêàëÿðîâ 0 ≤ ϕk ≤ 1, ÷òî1212(2.14) xk+1 = xk + ϕk (xk − (Ak xk + wk )) − xk ) = xk − ϕk (Ak xk + wk ).Èç âûïóêëîñòè fk ñëåäóåòfk (xk+1 ) − fk (xk ) ≤fk (xk ) + ϕk1fk xk − (Ak xk + wk ) − fk (xk )− fk (xk ) =2(2.15)ϕk1 k kkkkfk x − (A x + w ) − fk (x ) .2Äàëåå, çàìåòèì, ÷òî fk (x) = 12 xT B 0T B 0 x+B 0T bk = 12 (||B 0 x+bk ||2 −||bk ||2 ). ñëó÷àå îòñóòñòâèÿ ïîìåõ (2.13) äåëàåò îïòèìàëüíûé øàã â âûáðàííîìíàïðàâëåíèè: âûáèðàåòñÿ äóãà e = (i, j) è óðàâíèâàåòñÿ çíà÷åíèÿ [B 0 xk +bk ]i è [B 0 xk + bk ]j , ïðè ýòîì ïðî÷èå êîîðäèíàòû âåêòîðà B 0 xk + bk íåèçìåíÿþòñÿ.
Èñïîëüçóÿ ýòîò ôàêò ìîæíî âû÷èñëèòü fk (xk+1 ) − fk (xk ).Äëÿ óäîáñòâà îáîçíà÷èì z = B 0 xk + bk , òîãäà21 k kzi + zjkkk−fk x − (A x + w ) − fk (x ) =22zi2 + zj22!=1− (zi − zj )2 .2Ñ äðóãîé ñòîðîíû111|| (Ak xk + wk )||2 = |[B 0 xk + bk ]i − [B 0 xk + b]j |2 = (zi − zj )2 ,222à çíà÷èòfk11xk − (Ai xk + wk ) − fk (xk ) = −|| (Ai xk + wk )||2 .2276Ñëåäîâàòåëüíî, â ñèëó (2.14) è (2.15) ïîëó÷àåì||xk+1 − xk ||2 ≤ fk (xk ) − fk (xk+1 ).Åñëè R = 0 è xk ñõîäèòñÿ ê x∗ , òîk∗E||x − x || ≤∞Xi=kq∞Xi/4i=kpiE||x − xγ||x0−i+1x∗0 |||| ≤∞Xi=kE(fk (xi ) − fk (x∗k )1/2 ≤q k/4 p=γ||x0 − x∗0 ||√41− qÇàìå÷àíèÿ. A = DB 0T B 0 , ãäå D = diag{p1 , .
. . , pm }. Äëÿ òîãî, ÷òîáûâûïîëíÿëîñü ||A|| ≤ 2 ãîäèòñÿ âûáîð pe = 1/(nd−i ), e = (i, j) èëè æåïðîñòî pe = 1/|E 0 |. Ïî ñðàâíåíèþ ñ ñèíõðîííîé âåðñèåé àëãîðèòìà ñõî-äèìîñòü ÷óòü áîëüøå, ÷åì â äâà ðàçà ìåäëåííåé, íî ïðè ýòîì íà îäíóèòåðàöèþ ãîðàçäî ìåíüøå äåéñòâèé. ïóíêòå 1 îöåíèâàåòñÿ ðàññòîÿíèå äî áëèæàéøåé òî÷êè ìèíèìóìà.
 ñëó÷àå îòñóòñòâèÿ ïîìåõ è èçìåíåíèÿ ôóíêöèé fk (ïðîïóñêíûõñïîñîáíîñòåé), òî R = 0 è èìååò ìåñòî ýêñïîíåíöèàëüíàÿ ñõîäèìîñòü êìíîæåñòâó òî÷åê ìèíèìóìà fk .  ïóíêòå 3 ìîæíî âûâåñòè ñõîäèìîñòüP∞ii+1ii+1 2E||x−x||,àòàêæåñõîäèìîñòüðÿäà|| äëÿi=0i=0 ||x − xëþáîé âîçìîæíîé ïîñëåäîâàòåëüíîñòè xk , ÷òî, òåì íå ìåíåå, íè÷åãî íåãîâîðèò î ñõîäèìîñòè xk .ðÿäàP∞2.2.5Èçâëå÷åíèå ðåøåíèÿ çàäà÷è îìàêñèìàëüíîì ïîòîêåÈç òåîðåì 2.4 è 2.6 ñëåäóåò, ÷òî îáà ðàññìàòðèâàåìûõ àëãîðèòìà ðåøàþò ñëåäóþùóþ çàäà÷ó îïòèìèçàöèè:(2.16)ìèíèìèçèðîâàòüïðè óñëîâèè1 T 0T 02x B B x+ xT B 0T b,0 ≤ x e ≤ ce , e ∈ E 0 .77Ïðè ýòîì, íà èñõîäíîì ãðàôå G ìû ïîëó÷àåì ïñåâäîïîòîê, óäîâëåòâîðÿþùèé ïðîïóñêíûì ñïîñîáíîñòÿì, â êîòîðîì íàñûùåíû âñå äóãè, èíöèäåíòíûå èñòîêó è ñòîêó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
