Диссертация (1150610), страница 9
Текст из файла (страница 9)
Âåëè÷èíà [B T Bx](i,j) = [Bx]j − [Bx]i åñòü ðàçíèöàèçáûòêîâ âåðøèí i, j . Îòñþäà è íàçûâàíèå àëãîðèòìà: ôóíêöèÿ M oveP61Move(G,c,x, e)xe ← xe − 12 [B T Bx]e ;Functionififxe > ce thenxe ← ce ;xe < 0 thenxe ← 0;ArcBalancing(G, c, stopping criterion)x ← Initialize(G, c);while stopping criterion is not satised dopick e = (i, j) ∈ E : i, j 6= s, t;Move(G, c, x, e);Functionreturn x;ïûòàåòñÿ èçìåíèòü çíà÷åíèå ïîòîêà íà äóãå e òàêèì îáðàçîì, ÷òîáû ðàçíèöà ìåæäó èçáûòêàìè íà êîíöàõ äóãè áûëà ìèíèìàëüíîé âîçìîæíîéïðè óñëîâèè, ÷òî 0 ≤ xe ≤ ce . Ïðè ýòîì â çàâèñèìîñòè îò ñïîñîáà âûáîðàäóãè çàâèñèò ñõîäèìîñòü ôóíêöèè ArcBalancing . Îáû÷íî, âûáèðàþòñÿòîëüêî òå äóãè, äëÿ êîòîðûõ ôóíêöèÿ M ove èçìåíèò çíà÷åíèÿ ïîòîêà,îäíàêî æå, åñëè âûáèðàòü äóãè òàêèì îáðàçîì, à îñòàíàâëèâàòüñÿ â ñëó÷àå, êîãäà òàêèõ äóã íåòó, òî íåò íèêàêîé ãàðàíòèè, ÷òî ArcBalancingçàêîí÷èò ðàáîòó.RandomizedArcBalancing(G, c, stopping criterion)x ← Initialize(G, c);while stopping criterion is not satised dopick random e = (i, j) ∈ E 0 : i, j 6= s, t w.p.
pi ;Move(G, c, x, e);Algorithm 1:return x;Îäíà èç îñíîâíûõ èäåé, ïðåäëîæåííûõ â ýòîé ðàáîòå çàêëþ÷àåòñÿ âòîì, ÷òî ïðè ðàâíîìåðíîì âûáîðå äóã äëÿ îïåðàöèè M ove ïîëó÷àåòñÿ äîêàçàòü àñèìïòîòè÷åñêóþ ñõîäèìîñòü, ïðè ýòîì ìîæíî äîñòàòî÷íî ëåãêîèçâëå÷ü ìàêñèìàëüíûé ïîòîê / ìèíèìàëüíûé ðàçðåç èç ïðåäåëüíîãî ñî62Algorithm 2:ConcurrentArcBalancing(G, c, stopping criterion)x ← 0m ;while stopping criterion is not satised1x ← x − 2d(B 0T B 0 x + B 0T b);0for e ∈ E doif xe > ce thenxe ← ce ;ifdoxe < 0 thenxe ← 0;return x;ñòîÿíèÿ.
Äàëåå â ðàáîòå áóäóò ïðîàíàëèçèðîâàíû ñëåäóþùèå âàðèàíòûìåòîäà ArcBalancing :RandomizedArcBalancing è ConcurrentArcBalancing. îïèñàíèè ýòèõ ìåòîäîâ èñïîëüçóþòñÿ îáîçíà÷åíèÿ E 0 = {(i, j) ∈ E | i 6=+00s, j 6= t}, d−i = |{(i, j) ∈ E }|, di = |{(j, i) ∈ E }|, d > 0 íåêîòîðûé000ñêàëÿðíûé ïàðàìåòð," B# ìàòðèöà èíöèäåíòíîñòè ãðàôà G = hV, E i.c0, c0 ñîîòâåòñòâóåò äóãàì èç E 0 , c00 ñîîòâåòñòâóåòÏîëîæèì, ÷òî c =00c0äóãàì èç E \ E , b = B 00 c00 .2.2.2Ñõîäèìîñòü ìåòîäîâÄëÿ íà÷àëà îòìåòèì, ÷òî îáà ìåòîäà î÷åíü ñõîæè ñ ïðîåêòèâíûì ãðà-äèåíòíûì ñïóñêîì, áîëåå òîãî, åñëè îáîçíà÷èòü f (x) = d1 ( 12 xT B 0T B 0 x +xT B 0T b), ∇f (x) = d1 (B 0T B 0 x+B 0T b), òî àëãîðèòì ConcurrentArcBalancingâ òî÷íîñòè ÿâëÿåòñÿ ïðîåêòèâíûì ãðàäèåíòíûì ñïóñêîì äëÿ ôóíêöèè f .Îáùèé ìåòîä ïðîåêòèâíîãî ãðàäèåíòíîãî ñïóñêà áûë âïåðâûå ñôîðìóëèðîâàí â ðàáîòå [21].
Ìåòîä RandomizedArcBalancing îáíîâëÿåò ïîòîêïîõîæèì îáðàçîì: íà êàæäîì øàãå ñëó÷àéíûì îáðàçîì âûáèðàåòñÿ êîîðäèíàòà è äåëàåòñÿ øàã ãðàäèåíòíîãî ñïóñêà òîëüêî ïî ýòîé êîîðäèíàòå. Ïðåæäå, ÷åì ïåðåõîäèòü ê àíàëèçó ñõîäèìîñòè, âûïèøåì íåêîòîðûåêëþ÷åâûå ñâîéñòâà çàäà÷è.63Ë å ì ì à2.4.Åñëè D äèàãîíàëüíàÿ ìàòðèöà ñ íåîòðèöàòåëüíûìèýëåìåíòàìè, à B ∈ Rn×m ïðîèçâîëüíàÿ âåùåñòâåííàÿ ìàòðèöà, òîìàòðèöà DB T B èìååò òîëüêî âåùåñòâåííûå íåîòðèöàòåëüíûå ñîáñòâåííûå ÷èñëà. Áîëåå òîãî, åñëè âñå äèàãîíàëüíûå ýëåìåíòû D ñòðîãîïîëîæèòåëüíû, òîDB T Bx = 0m ⇔ Bx = 0n .Äîêàçàòåëüñòâî. Òàê êàê D äèàãîíàëüíàÿ ìàòðèöà ñ íåîòðèöàòåëüíûìè ýëåìåíòàìè, òî DB T B èìååò òîëüêî âåùåñòâåííûå ñîáñòâåííûå÷èñëà, äëÿ ìàòðèöû D äîïóñòèìî ðàçëîæåíèåD=√DT√D,√√√D = diag{ D11 , .
. . , Dmm }. Ñ äðóãîé ñòîðîíû, ó ìàòðèö DB T Bè BDB T îäèíàêîâûé íàáîð íåíóëåâûõ ñîáñòâåííûõ ÷èñåë:ãäåλx = DB T Bx ⇒ BDB T (Bx) = B(DB T Bx) = B(λx) = λ(Bx),à çíà÷èò, ïðè Bx 6= 0n λ ÿâëÿåòñÿ ñîáñòâåííûì ÷èñëîì BDB T . Åñëè æåBx = 0n , òî DB T Bx = 0m , à çíà÷èò λ = 0. Àíàëîãè÷íî â îáðàòíóþñòîðîíó:λxT = xT BDB T ⇒ (xT B)DB T B = (xBDB T )B = (λxT )B = λ(xT B),ïðè xT B 6= 0n λ ÿâëÿåòñÿ ñîáñòâåííûì ÷èñëîì DB T B , ïðè xT B = 0nxT BDB T = 0m , à çíà÷èò λ = 0.
 ñèëó√xT BDB T x = || DB T x||2 ≥ 0ïîëó÷àåì, ÷òî DB T B èìååò òîëüêî íåîòðèöàòåëüíûå ñîáñòâåííûå ÷èñëà.Íàêîíåö, åñëè âñå äèàãîíàëüíûå ýëåìåíòû D ñòðîãî ïîëîæèòåëüíû, òî64D îáðàòèìà, à çíà÷èòDB T Bx = 0m ⇒ 0 = xD−1 DB T Bx = ||Bx||2 ⇔ Bx = 0n .Ë å ì ì à2.5.Åñëè G0 ãðàô áåç ïåòåëü è êðàòíûõ äóã, Dee ≤+−0T 0max{1/2(d−i + dj ), 1/(ndi )} ïðè e = (i, j), òî σ(DB B ) ≤ 2.Äîêàçàòåëüñòâî.
Äëÿ e = (i, j) îáîçíà÷èì de = dij = Dee , dij = 0ïðè (i, j) ∈/ E 0 . Òàê êàê ó ìàòðèö DB 0T B 0 è B 0 DB 0T îäèíàêîâûé íà-áîð íåíóëåâûõ ñîáñòâåííûõ ÷èñåë, òî ó íèõ ðàâåí ñïåêòðàëüíûé ðàäèóñ.Íåïîñðåäñòâåííûì âû÷èñëåíèåì ïîëó÷àåì, ÷òî([B 0 DB 0T ]ij =−(dij + dji ),i 6= j,Pk6=i dik + dki , i = j.+Åñëè dij ≤ 1/2(d−i + dj ), òîXj6=i(dij + dji ) ≤X(i,j)∈EX(i,j)∈EX11+++ ≤2(d−2(d−i + dj )j + di )00(j,i)∈EX 11+≤ 1.2d−2d+ii00(j,i)∈EÏîñëåäíåå íåðàâåíñòâî îáðàùàåòñÿ â ðàâåíñòâî, åñëè îáå ñóììû ñîäåðæàò õîòÿ áû îäíî ñëàãàåìîå. Åñëè æå de ≤ 1/(nd−i ), òîXj6=i(dij + dji ) ≤X(i,j)∈EX 11 d+1+ i ≤ 1.− +− ≤nnndindj00(j,i)∈EÊàê è äëÿ ïðåäûäóùåãî ñëó÷àÿ â ïðåäïîñëåäíåì íåðàâåíñòâå âûïîëíÿåòñÿ ðàâåíñòâî, åñëè ñîîòâåòñòâóþùèå ñóììû ñîäåðæàò õîòÿ áû îäíîñëàãàåìîå.
 ïîñëåäíåì íåðàâåíñòâå ìû âîñïîëüçîâàëèñü òåì, ÷òî â ãðàôå áåç ïåòåëü è êðàòíûõ äóã ∀i : d+i ≤ n − 1. Íàêîíåö â ñèëó êðèòåðèÿÃåðøãîðèíà ìû ïîëó÷àåì, ÷òî âñå ñîáñòâåííûå ÷èñëà ìàòðèöû B 0 DB 0T65óäîâëåòâîðÿþò |λ − maxiP≤ maxiñëåäóåò |λ − 1| ≤ 1, à çíà÷èò σ(B B D) ≤ 2.j6=i (dij + dji )|0T 0Pj6=i (dij+ dji ) èç ÷åãîÇàìåòèì, ÷òî â Ëåììå 2.5 òàêàÿ æå îöåíêà íà ñïåêòðàëüíûé ðàäèóñïîëó÷àåòñÿ, åñëè âûïîëíÿåòñÿ de ≤ 1/(nd+j ).
Äàëåå, äëÿ âûâîäà îñíîâíûõðåçóëüòàòîâ íàì ïîíàäîáèòñÿ ñëåäóþùàÿ ëåììà î åâêëèäîâîé ïðîåêöèèíà ìíîãîãðàííèêè.Ë å ì ì à2.6.Ïóñòü Q = {x ∈ Rn | Ax ≤ d}, ñòðîêè ìàòðèöûA ëèáî îðîòîãàíàëüíû, ëèáî ñîíàïðàâëåíû, PQ (x) = argminy∈Q ||x −y||, b1 , . . . , bn íåêîòîðûé îðòîãîíàëüíûé áàçèñ, x, y ∈ Rn , α1 , . .
. , αnè β1 , . . . , βn ðàçëîæåíèÿ x, y ïî áàçèñó b, α10 , . . . , αn0 è β10 , . . . , βn0 ðàçëîæåíèÿ PQ (x), PQ (y) ïî áàçèñó b, òîãäà|αi0 − βi0 | ≤ |αi − βi |, 1 ≤ i ≤ n.Äîêàçàòåëüñòâî. Âî-ïåðâûõ, îòìåòèì, ÷òî PQ ïðåäñòàâëÿåòñÿ â âèäåêîìïîçèöèè ïðîåêöèé PQ1 ◦ . . . ◦ PQm , ãäå Qi = {x ∈ Rn | Ai x ≤ di },ïîýòîìó äîñòàòî÷íî äîêàçàòü óêàçàííîå ñâîéñòâî äëÿ ïîëóïðîñòðàíñòâà.Ïóñòü Q = {x ∈ Rn | aT x ≤ d}. Ðàññìîòðèì íåêîòîðûé îðòîãîíàëüíûéáàçèñ, ñîäåðæàùèé âåêòîð a: a = a1 , a2 , .
. . , an , g1 , . . . , gn è h1 , . . . , hn ðàçëîæåíèÿ x, y ïî ýòîìó áàçèñó. Î÷åâèäíûì îáðàçîì, ðàçëîæåíèå ïîýòîìó áàçèñó äëÿ PQ (x), PQ (y) çàäàåòñÿ ôîðìóëàìè(g10= mindg1 , ||a||2,dh1 , ||a||2,gi0 = gi , i > 1,è(h01= minh0i = hi , i > 1,èç ÷åãî ñëåäóåò(|g10 − h01 | ≤ |g1 − h1 |,gi0 − h0i = gi − hi , i > 1.66Òàê êàê b îðòîãîíàëüíûé áàçèñ, òî2Tαi ||bi || = x bi =nXgj aTj bi .j=1Îñòàëüíûå êîýôôèöèåíòû ïîëó÷àþòñÿ àíàëîãè÷íûì îáðàçîì, íàêîíåö nn |g 0 − h0 ||aT b |XX1 111 i0 T0 T 00=gab−hab≤|αi − βi | =iijjjj||bi ||2 ||bi ||2j=1|g1 − h1 ||aT1 bi |||bi ||2j=1nnXX1 TT gj aj bi −hj aj bi = |αi − βi |.=||bi ||2 j=1j=1Äàëåå ìû âîñïîëüçóåìñÿ ñëåäóþùèì î÷åâèäíûì ñëåäñòâèåì ýòîé ëåììû: åñëè M ëèíåéíîå ïîäïðîñòðàíñòâî Rn , x = ux + vx , y = uy + vy ,PQ (x) = u0x + vx0 , PQ (y) = u0y + vy0 , ux , uy , u0x , u0y ∈ M , vx , vy , vx0 , vy0 ∈ M ⊥ ,òî||u0x − u0y || ≤ ||ux − uy ||,||vx0 − vy0 || ≤ ||vx − vy ||.2.2.3Ñõîäèìîñòü ñèíõðîííîãî àëãîðèòìàÁóäåì ñ÷èòàòü, ÷òî ìàòðèöà || d1 B 0T B|| ≤ 2 (ïàðàìåòð d ìîæíî âû-áèðàòü êàê óãîäíî, ïî ýòîìó äîñòàòî÷íî ëåãêî ãàðàíòèðîâàòü ýòî ñâîéñòâî âûáðàâ d èñïîëüçóÿ, íàïðèìåð, Ëåììó (2.5)).
Êàê è ðàíüøå, îáîçíà÷èì f (x) = d1 ( 12 xT B 0T B 0 x + xT B 0T b), ∇f (x) = d1 (B 0T B 0 x + B 0T b). ÌåòîäConcurrentArcBalancing ãåíåðèðóåò ïîñëåäîâàòåëüíîñòü {xk }∞k=0 ïî ïðàâèëó(2.10)xk+11kk= PQ x − ∇f (x ) ,267ïðè ýòîì íà÷àëüíîå ïðèáëèæåíèå âûáèðàåòñÿ êàê x0 = 0m .
Åñëè áûìàòðèöà B 0T B 0 áûëà ñòðîãî ïîëîæèòåëüíî îïðåäåëåííîé, òî ìîæíî áûëî áû âûâåñòè ýêñïîíåíöèàëüíóþ ñõîäèìîñòü èç ðåçóëüòàòîâ [21]. Ê ñîæàëåíèþ ýòî ïðîèñõîäèò òîëüêî â ñëó÷àå, åñëè G0 íå ñîäåðæèò öèêëîâ(áåç ó÷åòà îðèåíòàöèè). Òåì íå ìåíåå äëÿ êâàäðàòè÷íûõ ôóíêöèé òàêæåìîæíî äîêàçàòü ýêñïîíåíöèàëüíóþ ñõîäèìîñòü. Îáîçíà÷èì A = d1 B 0T B 0 ,w = d1 B 0T b.Ò å î ð å ì à2.4.Ïóñòü xk ïîñëåäîâàòåëüíîñòü, ãåíåðèðóåìàÿ ïîïðàâèëó (2.10) ñ ëþáûì íà÷àëüíûì ïðèáëèæåíèåì x0 ∈ Q, ||A|| ≤ 2,γ = maxx∈Q ||Ax + w||, λ2 (A) ìèíèìàëüíîå îòëè÷íîå îò íóëÿ ñîáñòâåííîå ÷èñëî ìàòðèöû A, q = 1 − λ2 2(A) , òîãäà1.
Ïîñëåäîâàòåëüíîñòü xk ñõîäèòñÿ ê íåêîòîðîé òî÷êå ìèíèìóìàx∗ f íà Q, ïðè÷åìq k/2 pγ||x0 − x∗ ||.||x − x || ≤√1− qk∗2. f (xk ) óáûâàåò, ïðè÷åìf (xk ) − f (x∗ ) ≤ γq k ||x0 − x∗ ||.3. Åñëè Ω ÿäðî A, ò.å. Ω = {y ∈ Rm | Ay = 0m }, òîδ(xk − x∗ , Ω) ≤ q k ||x0 − x∗ ||,ãäå δ(·, ·) åâêëèäîâà ìåòðèêà.Äîêàçàòåëüñòâî.11f (xk+1 ) − f (xk ) = xk+1T Axk+1 + wT xk+1 − xkT Axk − wT xk =221 k+1(x− xk )T A(xk+1 − xk ) + (Axk + w)T (xk+1 − xk ) ≤268(Axk + w)T (xk+1 − xk ) + ||xk+1 − xk ||2 =1||xk+1 − xk ||2 − 2(xk − (Axk + w) − xk+1 )T (xk+1 − xk ) − 2(xk+1 − xk )T (xk+12−xk ) ≤ −||xk+1 − xk ||2 . ïîñëåäíåì ðàâåíñòâå èñïîëüçîâàëîñü ñâîéñòâî ïðîåêöèè ∀x ∈ Rn , y ∈Q : (x−PQ (x))T (y−PQ (x)) ≤ 0.
Òàêèì îáðàçîì f (xk ) óáûâàåò. Òàê êàê fîãðàíè÷åíà ñíèçó, òî ñóùåñòâóåò ïðåäåë f (xk ), à çíà÷èò ||xk+1 −xk ||2 → 0.Ïóñòü x∗ ëþáàÿ òî÷êà ìèíèìóìà f íà Q, òîãäà ïîâòîðèâ àíàëîãè÷íîåðàññóæäåíèå äëÿ x∗ è x0 = PQ (x − 21 ∇f (x∗ )) ïîëó÷àåì0 ≤ f (x0 ) − f (x∗ ) ≤ −||x∗ − x0 ||2 ⇒ x∗ = x0 .Äàëåå, ðàññìîòðèì ïîñëåäîâàòåëüíîñòè uk ∈ Ω, vk ∈ Ω⊥ : xk = uk +vk (ýòè ïîñëåäîâàòåëüíîñòè çàäàþòñÿ îäíîçíà÷íî ïî xk ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
