Az ellipszoid algoritmus


1 Az ellipszoid algoritmus Csizmadia Zsolt Eötvös Loránd Tudományegyetem2 Bevezető Az ellipszoid módszert a nemline&aac...
Author:  Artúr Jónás

0 downloads 1 Views 258KB Size

Recommend Documents


EGYSZERŰSÍTETT ALGORITMUS AZ ELEMI BÁZISCSERE ELVÉGZÉSÉRE
1 Lipécz György* EGYSZERŰSÍTETT ALGORITMUS AZ ELEMI BÁZISCSERE ELVÉGZÉSÉRE AVAGY A SZÁMÍT...

Problémák, kérdések az algoritmus vizualizációval kapcsolatban
1 Problémák, kérdések az algoritmus vizualizációval kapcsolatban Bende Imre ELTE IK Absztrakt. Az algoritmus...

Matematika A1H - oktatási segédanyag. 1. Az euklideszi algoritmus az egész számokra
1 Budapesti Műszaki és Gazdaságtudományi Egyetem Gépészmérnöki Kar Energetika, Mechatronika és T...

EM-ALGORITMUS HIÁNYOS ADATRENDSZEREKRE
1 Süvítenek napjank, a forró sortüzek valamt mnden nap elmulasztunk. Robotolunk lélekszakadva, jóttevőn, s valam...

Algoritmus odesílání pacienta
1 Algoritmus odesílání pacienta s exacerbací CHOPN k hospitalizaci Ondřej Kudela Plicní klinika FNHK a LFHK UK2 AE ...

Subexponenciální algoritmus pro faktorizaci
1 Subexponenciální algoritmus pro faktorizaci 24. a 25. přednáška z kryptografie Alena Gollová SEF 1/372 Obsah 1 2 ...

Watkinsův algoritmus řádkového rozkladu
1 Watkinsův algoritmus řádkového rozkladu Josef Pelikán CGG MFF UK Praha 1 / 152 Watkinsův algoritmus nepotřebuje výstup...

8a.Objektové metody viditelnosti. Robertsův algoritmus
1 8a. OBJEKOVÉ MEODY VIDIELNOSI Cíl Po prostudování této kaptoly budete znát metody vdtelnost 3D objektů na ...

Az első program. 1. Első lépés A feladat Specifikáció Algoritmus Kód Második lépés
1 Az első program Tartalom 1. Első lépés A feladat Specifikáció Algoritmus Kód Második lépés A...

Gráfalgoritmusok Legrövidebb utak egy forrásból Dijkstra algoritmus Bellman-Ford algoritmus 31
1 Gráfalgoritmusok 2 1. Néhány probléma modellezése gráfokkal Útkeresés Minimális k&oum...



Az ellipszoid algoritmus

Csizmadia Zsolt

E¨otv¨os Lor´and Tudom´anyegyetem •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Bevezet˝o Az ellipszoid m´odszert a nemline´aris porgramoz´asra Shor [1970,0977] illetve Yudin e´ s Nemirovskiˆı [1976] feljlesztett´ek ki. Khachiyan [1979, 1980] megmutatta, hogy az algorimtus egy kiterjeszt´ese a line´aris programoz´asi feladatot polinom id˝oben megoldja. Az ellipszoid algoritmusnak szerepe a kombinatorikus optimaliz´al´as´aval, hogy seg´ıts´eg´evel j´op´ar algoritmus polinomi´alis fut´asideje bizony´ıthat´o. Bel´athat´o, hogy val´oj´aban a poli´eder teljes le´ır´as´ara nem is lesz sz¨uks´ege az ´ algoritmusnak, elegend˝o ha az ugynevezett szepar´al´ast el tudjuk v´egezni: ha adott a P ⊆ Rn poli´eder, illetve egy x vektor, akkor eld¨ontend˝o hogy x ∈ P teljes¨ul-e, illetve ha nem, megadand´o egy a P le´ır´as´aban szerepl˝o felt´etel, melyet az x megs´ert. Vagyis a szepar´al´as elegend˝o az ellipszoid algoritmus futtat´as´ahoz [2]. Gyakorlati szempontb´ol az ellipszoid algoritmus nem hat´ekony. Az algoritmus numerikusan instabil, e´ s a sz¨uks´eges iter´aci´ok sz´ama rendk´ıv¨ul nagy. A k¨ovetkez˝okben felt´etelezz¨uk hogy pontosan tudunk sz´amolni. A gyakorlatban ez a feltev´es kiv´althat´o, ha minden iter´aci´oban egy picit nagyobb epszilont tekint¨unk. •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Az ellipszoid tulajdons´ag 1. Defin´ıci´o. Legyen D ∈ Rn×n pozit´ıv definit m´atrix. Az

E(D, y) := {x ∈ Rn : (x − y)T D−1(x − y) ≤ 1} halmazt az y k¨oz´eppontu´ ellipszoidnak nevezz¨uk. 2. Tulajdons´ag. Legyen adott egy E(D, y) ellipszoid e´ s valamely d ∈ Rn vektor eset´en tekints¨uk a H = E(D, y)∩{x ∈ Rn : dT x ≤ dT y} f´elellipszoidot. Ekkor azt mondjuk hogy teljes¨ul az ellipszoid tulajdons´ag, ha ∃E 0 ellipszoid, melyre H ⊆ E 0 e´ s 1 vol(E 0) ≤ e− 2(n+1) < 1 vol(E)

Vegy¨uk e´ szre, hogy 1

lim e− 2(n+1) = 1

n→∞

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Az ellipszoid algoritmus Input: P< ⊆ E0 = E(D0 , x0 )

Begin t := 1, t∗ := d2(n + 1)(log V − log ν)e While (xt ∈ / P< )  T Legyen i : a(i) xt > bi d := a(i) , D := Dt 2 Dt+1 := n2n−1 D −

T

2 (Dd)(Dd) n+1 dT Dd 1 √ Dd n+1 dT Dd



xt+1 := xt − t := t + 1 If (t ≥ t∗ ) then STOP: P< u¨ res

Endif Endwhile xt bels˝o pont End Tegy¨uk fel, hogy teljes¨ul az ellipszoid tulajdons´ag. Megmutatjuk, hogy ekkor az algoritmus v´eges.

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Az ellipszoid tartalmazza a tartom´anyt 3. Lemma. Tegy¨uk fel hogy P< ⊆ E0 , teljes¨ul az ellipszoid tulajdons´ag, illetve hogy az algoritmus tˆ ≤ t∗ iter´aci´ot v´egez. Ekkor P< ⊆ Et b´armely t := 0, 1, . . . , tˆ eset´en. Bizony´ıt´as. Teljes indukci´oval bizony´ıtunk. t = 0 esete a lemma felt´etele, tegy¨uk fel hogy az a´ ll´ıt´ast t = 0, . . . , k eset´en m´ar igazoltuk. Legyen i az algoritmus a´ ltal a k -ik iter´aci´oban v´alasztott index,  (i) T azaz a xk > bi e´ s d := a(i). Ekkor

P< ⊆ Ek ∩ {x ∈ Rn : dT x ≤ dT xk } ⊆ {x ∈ Rn : dT x ≤ dT xk } ´ıgy az ellipszoid tulajdons´agot haszn´alva

P< ⊆ Ek ∩ {x ∈ Rn : dT x ≤ dT xk } = Hk ⊆ Ek+1  •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

L´ep´essz´am 4. T´etel. Tegy¨uk fel hogy P< ⊆ E0 , teljes¨ul az ellipszoid tulajdons´ag, adott a V, ν > 0 e´ s legyen t∗ := d2(n + 1)(log V − log ν)e. Ekkor az ellipszoid algoritmus a P< feladatot legfeljebb t∗ iter´aci´oban megoldja. Bizony´ıt´as. Megmutatjuk, hogy ha xt ∈ / P< az o¨ sszes t := 0, 1, . . . , t∗ eset´en akkor P< = ∅. Kisz´am´ıtjuk az Et∗ t´erfogat´at. Mivel 1 vol(Et+1) ≤ e− 2(n+1) vol(Et)

ez´ert

t∗ vol(Et∗ ) vol(E1) vol(Et∗ ) ≤ e− 2(n+1) = · ··· · vol(E0) vol(E0) vol(Et∗−1 )

vagyis ∗

t − 2(n+1)

vol(E ) ≤ vol(E0)e t∗

≤Ve

V −log ν) − 2(n+1)(log 2(n+1)

V

= V e− log ν = ν

Azonban a feltev´esek szerint vol(P> ) > v, illeve a 3. lemma alapj´an P< ⊆ Et∗ vagyis vol(P< ) ≤ vol(Et∗ ) = ν. Ellentmond´as.  A tov´abbiakban r´at´er¨unk az ellipszoid tulajdons´ag teljes¨ul´es´enek a bizony´ıt´as´ara. •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Affin transzform´aci´ok 5. Defin´ıci´o. Legyen A ∈ Rn×n , b ∈ Rn e´ s TA (x) := Ax + b. Ekkor TA : Rn → R affin transzform´aci´o. 6. Lemma. Ha L ⊆ L0 ⊆ Rn akkor TA (L) ⊆ TA (L0 ) ⊆ Rn 7. Lemma. Ha L ⊆ Rn L konvex, akkor vol(TA (L)) = |det(A)| vol(L). Bizony´ıt´as. Anal´ızisb˝ol volt. Ha m´asnem t´egl´akra. De L konvex, tudod ilyenekkel k¨ozel´ıteni.  8. Lemma. Legyen E = E(D, y ˜) ahol D = QT Q. Legyen tov´abb´a T (x) = (QT )−1x − (QT )−1y ˜ egy affin traszform´aci´o. Ekkor T (E) = S n, ahol S n az n dimenzi´os egys´egg¨omb. Bizony´ıt´as.

 T −1 T −1 T (E) = ξ : ξ = (Q ) (x − y ˜), ahol (x − y ˜) D (x − y ˜) ≤ 1  = ξ : (QT ξ)T D−1(QT ξ) ≤ 1   = ξ : ξ T QD−1QT ξ ≤ 1 = ξ : ξ T ξ ≤ 1 = S n.  •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Rot´aci´os lemma 9. Defin´ıci´o. A TQ affin transzform´aci´ot rot´aci´onak nevezz¨uk, ha QT Q = I . 10. Lemma. Legyen d ∈ Rn \ {0} tetsz˝oleges. Ekkor ∃Q2 ∈ Rn×n rot´aci´o, hogy Q2 d = − kdk e1 . Bizony´ıt´as. Vagyis minden vektor beforgathat´o ak´armilyen ir´anyba.



11. Lemma. Legyen Q1 ∈ Rn×n , d ∈ Rn tetsz˝oleges, QT1 Q1 = D := Dt , Q2 rot´aci´o melyre Q2 Q1 d = − kQ1 dk e1 e´ s Q = Q2 Q1 . (Et = (D, xt ), D = Dt ) Legyen tov´abb´a T (x) = (QT )−1 (x − xt )

e´ s ξ := T (x) vagyis ξ = QT 1. kQdk =

p

−1

x − QT

−1

xt . Ekkor

dT Qd

2. QD−1 QT = I 3. (QT )−1 D = Q 4. T (Et ) = T (E(D, xt )) = ξ : ξ T ξ ≤ 1 

5. T



x : dT x ≤ dT xt

6. T (xt+1 ) =





= {ξ : ξ1 ≥ 0}

1 n+1 e1

 7. T (Et+1 ) = ξ : ξ −

e1 n+1



n2 n2 −1

I−

2 T n+1 e1 e1

−1

ξ−

e1 n+1



 ≤1

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Rot´aci´os lemma bizony´ıt´as Bizony´ıt´as. 1.

q q √ T kQdk = kQ2 Q1 dk = (Q2 Q1 d) (Q2 Q1 d) = dT QT1 QT2 Q2 Q1 d = dT Dd

2. QD

−1

T

Q = Q2 Q1



QT1 Q1

−1

QT1 QT2 = I

3. K¨ovetkezik az el˝oz˝ob˝ol. 4.

n o T −1 T −1 T (E) = ξ : ξ = (Q ) (x − y ˜), ahol (x − y ˜) D (x − y ˜) ≤ 1 n o n   o (2) n o T T T −1 T T −1 T = ξ : (Q ξ) D (Q ξ) ≤ 1 = ξ : ξ QD Q ξ ≤ 1 = ξ : ξ ξ ≤ 1

5. T

n o n o n o x : dT x ≤ dT xt = ξ : dT QT ξ ≤ 0 = ξ : (Q2 Q1 d)T ξ ≤ 0 n o = ξ : − kQ1 dk eT1 ξ ≤ 0 = {ξ : ξ1 ≥ 0}

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Rot´aci´os lemma bizony´ıt´as ... 6.  T (xt+1 ) = T

     −1 1 Dd Dd 1 T √ √ xt − = Q − xt xt − n + 1 dT Dd n + 1 dT Dd    −1  T −1 Dd Q Dd 1 1 √ √ = QT =− − n + 1 dT Dd n+1 dT Dd 1 − kQdk 1 1 Qd (3) =− e1 = e1 =− n + 1 kQdk n + 1 kQdk n+1

7. Jel¨olje ξt+1 := T (xt+1 ), azaz xt+1 − xt = QT ξt+1 . Ekkor o n −1 T T (Et+1 ) = ξ : Q ξ = x − xt , (x − xt+1 )Dt+1 (x − xt+1 ) ≤ 1 n o −1 (QT (ξ − ξt+1 )) ≤ 1 = ξ : (QT (ξ − ξt+1 ))T Dt+1

mivel QT ξ = x − xt e´ s QT ξt+1 = xt+1 − xt ´ıgy QT (ξ − ξt+1 ) = x − xt − xt+1 + xt = x − xt+1

e´ s

−1 T T (Et+1 ) = {ξ : (ξ − ξt+1 )T QDt+1 Q (ξ − ξt+1 ) ≤ 1}

−1 T ´ıgy mivel QDt+1 Q = ((QT )−1 Dt+1 Q)−1

T (Et+1 ) = {ξ : (ξ − ξt+1 )T ((QT )−1 Dt+1 Q)−1 (ξ − ξt+1 ) ≤ 1} •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Rot´aci´os lemma bizony´ıt´as ... Felhaszn´alva, hogy Dt+1

n2 = 2 n −1



2 (Dt d)(Dt d)T Dt − n+1 dT Dt d



kapjuk, hogy T −1

(Q )

−1

Dt+1 Q

  n2 2 (Dt d)(Dt d)T = (Q ) Dt − Q−1 n2 − 1 n+1 dT D t d   2 (QT )−1 (Dt d)(Dt d)T Q−1 n2 T −1 −1 (Q ) Dt Q − = 2 n −1 n+1 dT Dt d   n2 2 (Qd)(Qd)T (3) = 2 I− n −1 n + 1 dT Dt d   2 n2 T I− e1 e1 = 2 n −1 n+1 T −1

Vagyis haszn´alva (6)-ot ad´odik hogy ( T (Et+1 ) =

ξ:



e1 ξ− n+1



n2 n2 − 1



2 I− e1 eT2 n+1

−1 

e1 ξ− n+1



) ≤1 

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

¨ az ellipszoid tulajdons´ag, vagyis 12. Lemma. Legyen n ≥ 3. Ekkor teljesul 1. Dt+1 ∈ P D 2.

vol(Et+1 ) vol(Et )

1

≤ e− 2(n+1)

3. Ht = Et ∩ {x ∈ Rn : dT x ≤ dT xt } ⊆ Et+1 Bizony´ıt´as. 1. Az el˝oz˝o lemma 7. pontja szerint Dt+1 = QT ∆Q ahol ∆ = diagon´alis m´atrix ha n ≥ 3.

n2 n2 −1

I−

2 T n+1 e1 e2



∈ PD

1

2

x Dt+1 x = x Q ∆Qx = x Q ∆ ∆ Qx = ∆ Qx > 0 T

T

T

T

1 2

T

1 2

2. s     1 p vol E ∆, e vol(Et+1 ) vol(T (Et+1 )) (4) n2 2 n+1 1 T = = = det(∆) = det I− e1 e1 vol(Et ) vol(T (Et )) vol (S n ) n2 − 1 n+1 s s  n n−1 n2 n2 n−1 n2 n − 1 = = n2 − 1 n+1 n2 − 1 n2 − 1 n + 1 s s  n−1  2  n−1  2 2 n n 1 1 = 1+ 2 1− = n2 − 1 n+1 n −1 n+1

Felhaszn´alva hogy 1 + α ≤ eα kapjuk, hogy vol(Et+1 ) ≤ vol(Et )

r



e

1 n2 −1

n−1 

1 − n+1

e

2

q =

1

2

1

e n+1 e− n+1 = e− 2(n+1)

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Ellipszoid tulajdons´ag bizony´ıt´as ... 1 3. T (Et+1 ) = E ∆, n+1 e1 , ahol ∆ =



( T (Et+1 ) =

ahol

 ξ−

ξ:

 −1



n2 n2 −1

  =  

I−

2 T n+1 e1 e2



T



1 e1 n+1

(n+1)2 n2

0

0

n2 −1 n2

.. . 0

...

e´ s T (Ht ) = ξ : ξ T ξ ≤ 1 e´ s ξ1 ≥ 0 . 

∆−1 ξ −

...

... 0

0

1 e1 n+1





) ≤1



..  .  

∈R 0 

n×n

n2 −1 n2

pozit´ıv definit diagon´alis m´atrix.

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Ellipszoid tulajdons´ag bizony´ıt´as ... 

1 ξ− e1 n+1

T

−1





1 ξ− e1 n+1



(n + 1)2 = n2 = = =

azaz

n2

n −1X

n2 n2 − 1 n2 n2



i=2 n X

ξi2 +

i=1

(n + 1)2 n2

n

2 +

n2 − 1 X 2 ξi n2 i=2

ξ12 −

2ξ1 (n + 1) (n + 1)2 1 + 2 2 n n (n + 1)2

ξi2 +

2(n + 1) 2 2(n + 1) 1 ξ1 − ξ1 + 2 2 2 n n n

ξi2 +

2(n + 1) 1 + ξ1 (ξ1 − 1) 2 n n2

i=1

n −1X

n2

1 ξ1 − n+1

) n n2 − 1 X 2 1 2(n + 1) ξ: ξ1 (ξ1 − 1) ≤ 1 ξi + 2 + n2 n n2

( T (Et+1 ) =

i=1

Ha ξ ∈ T (Ht ) akkor n

1 2(n + 1) n2 − 1 1 2(n + 1) n2 − 1 X 2 ξ + + ξ (ξ − 1) ≤ + 2+ ξ1 (ξ1 − 1) 1 1 i 2 2 2 2 n n n n n n2 i=1

=1+

2(n + 1) ξ1 (ξ1 − 1) n2

Mivel 0 ≤ ξ1 ≤ 1, ez´ert ξ1 (ξ1 − 1) ≤ 0 e´ s ´ıgy ξ1 (ξ1 − 1) ≤ 0 azaz ξ ∈ T (Et+1 ). Megmutattuk hogy T (Ht ) ⊆ T (Et+1 ), de T bijekt´ıv l´ev´en k´eszen vagyunk. 

A tov´abbiakban megmutatjuk hogyan lehet minden LP feladatot egy, az algoritmus felt´eteleinek megfelel˝o megengedetts´egi feladatt´a alak´ıtani. •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Becsl´es a determin´ansra 13. Lemma. Legyen A ∈ Rm×n , I ∈ Rm×m , b ∈ Rm , I egys´egm´atrix. Legyen B ∈ Rm×m az (A, I, b) r´eszm´atrixa. Ekkor |det(B)| < 2L /n

ahol  L= 1 + log2 n + log2 m + 

m X n X

(1 + log2 (1 + |aij |)) +

i=1 j=1

m X



(1 + log2 (1 + |bi |))   j=1

az adatok t´arol´asi ig´enye. Bizony´ıt´as. X |det(B)| = (−1)σ(π) α1π(1) . . . αmπ(m) π∈Sm X  α1π(1) + · · · + αnπ(n) ≤ ≤

π∈Sm m Y m Y

(|αij | + 1)

i=1 j=1

≤ <

m Y n Y

(|aij | + 1)

i=1 j=1 2L 2L

nm

<

m Y

(|bi | + 1)

i=1

n  •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

B´azismegold´asok becsl´ese 14. Lemma. Tekints¨uk az Ax ≤ b, x ≥ 0 megengedetts´egi feladatot, ahol A ∈ Zm×n, b ∈ Zm. Ekkor b´armely x ¯ b´azis megold´asa a megengedetts´egi feladatnak olyan, hogy k¯ xk < 2L. Bizony´ıt´as. Ha x ¯j 6= 0 akkor a Cramer-szab´aly szerint

|det Bj | 2L |¯ xj | = < |det Bj | < |det B| n mivel det B > 0 vagyis det B ≥ 1 l´ev´en eg´esz, e´ s ´ıgy

k¯ xk < 2L 

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Poli´eder t´erfogat´anak becsl´ese 15. Lemma. Legyen P = {x ∈ Rm : Ax ≤ b, x ≥ 0}, ahol A ∈ Zm×n , b ∈ Zm ahol int(P ) 6= 0. Ekkor vol(P ) ≥ 2−(n+1)L .

Bizony´ıt´as. Legyen x ¯ ∈ intP , illetve x ˆ ∈ P b´azismegold´as. Ekkor |ˆ xj | <

2L n

illetve ∃δ hogy B(¯ x, δ) ⊂ P. Mivel P konvex, ´ıgy tetsz˝oleges x ∈ P eset´en a conv(x, B(¯ x, δ)) k´up is P -ben van, ´ıgy a   P˜ =

x ∈ Rn : Ax ≤ b, x ≥ 0, x ≤

2L e n

(1)

poli´eder m´ar korl´atos e´ s tov´abbra is van bels˝o pontja. Mivel P˜ korl´atos, ´ıgy el˝oa´ ll mint extrem´alis pontjainak a konvex burka. Mivel P˜ -nak bels˝o pontja, ´ıgy teljes dimenzi´os, ez´ert kiv´alaszthat´o {v0 , . . . , vn } ⊂ P˜ extrem´alis pontjai, melyek affin f¨uggetlenek, vagyis a ∆v = conv{v0 , . . . , vn } ⊂ P˜

egy n dimenzi´os szimplex. Felhaszn´alva hogy az n dimenzi´os egys´egszimplex t´erfogata a 7. lemm´at ad´odik, hogy  1 1 1 ... vol(∆v ) = det v n! 0 v1 . . .

1 vn

1 n!

illetve



•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Bizony´ıt´as ... e´ s felf´ujt poli´eder Legyen vi = udii ahol ui ∈ Zn , di ∈ Z e´ s i ∈ {0, . . . , n} felhaszn´alva, hogy a vi pontok egyben b´azismegold´asai a P˜ poli´edernek, ´ıgy a Cramer szab´aly miatt racion´alisak. e´ s egyben |vi | = udii < 2L −L . Amennyiben u = 0 akkor d v´ o ilyennek. Ezt i i alaszthat´ n , vagyis ha ui 6= 0 akkor di > n2 felhaszn´alva ad´odik, hogy  1 1 do d1 . . . vol(∆v ) = det u0 u1 . . . n! d0 d1 . . . dn

dn un



2−(n+1)L nn+1 ≥ ≥ ≥ 2−(n+1)L n!d0 d1 . . . dn n! 1

Mivel ∆v ⊂ P˜ ez´ert

vol(E0 ∩ P ) ≥ vol(P˜ ) ≥ vol(∆v ) ≥ 2−(n+1)L 

A k¨ovetkez˝okben megkonstru´alunk egy u´ j poli´edert az eredetib˝ol, melynek m´ar van bels˝o pontja, de egy megengedett megold´as´ab´ol meghat´arozhat´o az erdeti egy megengedett megold´asa. Legyen A ∈ Zm×n e´ s b ∈ Zm . P1 := {x ∈ Rn : Ax ≤ b}

e´ s P2 := {x ∈ Rn : 2L (a(i) )T x < 2L bi + 1}

(2)

Az egyszer˝ubb jel¨ol´es kedv´ee´ rt legyen Θi (x) := (a(i) )T x−bi minden i ∈ {1, . . . , m} eset´en. Vagyis (a(i) )T x ≤ bi ⇐⇒ Θi (x) ≤ 0. •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Technikai seg´edlemma 16. Lemma. Legyen x0 ∈ Rn tetsz˝oleges pont. Ekkor ∃¯ x ∈ Rn : Θi (¯ x) ≤ max{0, Θi (x0 )} ∀i

e´ s ha J¯ := {i : Θi (¯ x) ≥ 0} akkor a(j) =

X

λi a(i)

i∈J¯

minden j eset´en megoldhat´o. Bizony´ıt´as. Feltehet˝o, hogy {i : Θi (x0 ) ≥ 0} = {1, . . . , k}. Az els˝o felt´etelt teljes´ıt˝o vektor mindenk´eppen van, l´ev´en maha az x0 ilyen. Tekints¨uk az {a(1) , . . . , a(k) } sorvektorokat, e´ s tegy¨uk fel hogy nem fesz´ıtik ki az A m´atrix sorter´et. Feltehet˝o, hogy a(k+1) ∈ / L {a(1) , . . . , a(k) } . A k¨ovetkez˝o egyenletrendszer  

(i)

a

a(k+1)

T T

y = 0 i = 1, . . . , k y=1

megoldhat´o, legyen y0 egy megold´as. Legyen 



(k+1)

λ0 := max λ : λ a

T

0



y0 + Θi (x ) ≤ 0, i = k + 1, . . . , m •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Technikai seg´edlemma bizony´ıt´as ...  (k+1) T

Mivel a

y0 = 1 e´ s Θi(x0) < 0 i = k + 1, . . . , m ez´ert  (k+1) T λ0 a y0 + Θi(x0) ≤ 0

miatt λ0 ≤ −Θk+1 (x0 ). Mivel Θi (x0 ) < 0 ez´ert λ0 > 0 e´ s ´ıgy 0 < λ0 ≤ −Θk+1(x0) ad´odik. Legyen

x1 = x0 + λ0y0 e´ s ´ıgy 1

0

 (i) T

Θi(x ) = Θi(x ) + λ0 a

y0 = Θi(x0) i = {1, . . . , k}

e´ s Θi (x1 ) ≤ 0 i = k +1, . . . , m eset´en. A λ0 defin´ıci´oja miatt viszont legal´abb egy esetben nulla a Θi (x1 ) e´ rt´eke az i ∈ {k + 1, . . . , m} halmazon, azaz J¯ elemsz´am´at n¨ovelt¨uk legal´abb eggyel. Ha x1 nem megfelel˝o, iter´aljuk az elj´ar´ast.  •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

A felf´ujt poli´elder ekvivalenci´aja 17. T´etel. P1 6= ∅ ⇐⇒ P2 6= ∅. Tov´abb´a b´armely x ∈ P2 vektorb´ol polinom id˝oben konstru´alhat´o y ∈ P1 vektor. Bizony´ıt´as. P1 ⊂ P2 nyilv´anval´o, azaz P1 6= ∅ ⇒ P2 6= ∅. Teh´at a megford´ıt´as´at igazoljuk. Legyen x0 ∈ P2 e´ s x0 ∈ / P1 . Ekkor az x0 -b´ol konstu´alunk egy x ˆ ∈ P1 vektort. x0 ∈ P2 ⇒ Θi (x0 ) < 2−L i = 1, . . . , m

¯ 0 ) = {i : Θi (x0 ) ≥ 0} = {1, . . . , k} e´ s ´ıgy Θi (x0 ) < 0 ha i = k + 1, . . . , m. Feltehet˝o hogy J(x ¯ x) = Felhaszn´alva az el˝oz˝o lemm´at, legyen x ¯ olyan, hogy Θi (¯ x) ≤ max(0, Θi (x0 )) e´ s {a(i) : i ∈ J(¯ (i) ¯ {i : Θi (¯ x) ≥ 0}} kifesz´ıti az A m´atrix sorter´et. Keress¨uk meg az {a : i ∈ J(¯ x)} vektorrendszer ¯ maxim´alis f¨uggetlen r´esz´et, legyen ez I. Ekkor a J(¯ x) defin´ıc´oja e´ s a f¨uggetlens´eg miatt |I| ≤ m − 1 ≤ n − 1. Oldjuk meg az 

a(i)

T

x = bi i ∈ I

(3)

ˆ megold´asa egyben a P1 megold´asa is. rendszert. Megmutatjuk hogy a 3 rendszer b´armely x Legyen l ∈ {1, . . . , m}. Ekkor az X (i) (l) a

=

λi a

i∈I

rendszer megoldhat´o az I konstrukci´oja miatt. Mivel az {a(i) : i ∈ I} rendszer line´arisan f¨uggetlen, ´ıgy a megold´as egy´ertelm˝u. Legyen λi = ddi ahol di , d ∈ Z. A d > 0 egy esetleges −1 -el val´o szorz´as a´ r´an feltehet˝o (Cramer szab´aly: λi racion´alis). •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

A felf´ujt poli´elder ekvivalenci´aja bizony´ıt´as ... A kor´abbiak alapj´an d, di <

2L n

´Igy d



(l)

a

T

 x ˆ − bl

X

=

 T X ˆ − dbl = di bi − dbl di a(i) x i∈I

i∈I

tov´abb´a X

di bi − dbl =

i∈I

X

di



(i)

a

T

    T (l) x ¯ − Θl (¯ x) x ¯ − Θi (¯ x) − d a

i∈I



 =

X



di a(i)

T



x ¯ − d a(l)

T

x ¯ + dΘl (¯ x) −

6i∈I

X

di Θi (¯ x)

i∈I

|

{z

}

=0

Felhaszn´alva, hogy i ∈ {1, . . . , m} eset´en 0 ≤ Θi (¯ x) ≤ 2−L dΘl (¯ x) −

X

di Θi (¯ x) ≤ d2−L −

X

di Θi (¯ x)

i∈I

i∈I

<

2L n

2−L +

X i∈I

|di | Θi (¯ x) <

1 X 2L −L 1 |I| |I| + 1 n + 2 = + = ≤ =1 n n n n n n i∈I

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

A felf´ujt poli´elder ekvivalenci´aja bizony´ıt´as ... Teh´at

P

i∈I

di bi − dbl < 1 eg´esz, ´ıgy sz¨uks´egszer˝uen d



(l)

a

T

azaz 

a(l)

 x ˆ − bl

T

≤0

x ˆ ≤ bl

Mivel ez tetsz˝oleges l indexre teljes¨ul, az a´ ll´ıt´ast igazoltuk.



•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

LPb˝ol megengedetts´egi feladat H´atra van m´eg megmutatnunk, hogyan lehet egy LP feladatot megengedetts´egi feladatt´a alak´ıtani. Megjegyzend˝o, hogy az ellipszoid algoritmus k¨ozvetlen¨ul is m´odos´ıthat´o olym´odon, hogy line´aris c´elf¨ugv´eny eset´en k¨ozel´ıt˝o megold´ast keressen [1]. Tekints¨uk a szok´asos prim´al-du´al feladatp´art. T

 

min c x Ax ≥ b (P )  x ≥ 0

T

 

max b y AT y ≤ c (D)  y ≥ 0

Az LP feladat megold´asa ekvivalens a fenti feldatp´ar megold´as´aval, ´ıgy a

 Ax ≥ b, x ≥ 0  T T A y ≤ c , y ≥ 0 optimalit´asi krit´eriumok  T T c x ≤ b y

(4)

rendszerrel is. Legyen tov´abb´a A ∈ Zm×n , b ∈ Zm e´ s c ∈ Zn . A fenti op¯ ≤b ¯ form´ara alak´ıthat´o, timalit´asi krit´eriumok seg´ıts´eg´evel az LP feladat Ax ¯ ≤b ¯ + 2−L¯ rendszerre pedig alkalmazhat´o az ellipszoid m´odszer. e´ s az Ax •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

L´ep´essz´am megint ¨ Osszefoglal´ as´ul k´esz´ıts¨uk el a kapott l´ep´essz´ambecsl´est a bizony´ıtott alakra. Legyen teh´at adott az LP feladat, e´ s hozzuk egy megengedetts´egi feladat alakj´ara, ´ıgy kapjuk a P0 poli´edert. Sz´am´ıtsuk ki a feladat le´ır´as´ahoz sz¨uks´eges bithosszt: 



m X n X

 L0 :=  1 + log2 n + log2 m + 2  i=1

(1 + log2 (1 + |aij |)) +

j=1



m X

(1 + log2 (1 + |bi |))   j=1

Ezt a feladatot m´eg korl´atoss´a tessz¨uk 1 e´ s be´agyazzuk hogy legyen bels˝o pontja 2. Ez az el˝obbi esetben a jobboldal, m´ıg ut´obbi esetben a felt´eteli m´atrix e´ s a jobboldal eset´en jelent egy 2L0 -os t¨obbletvektort, illetve szorz´ast. Az ´ıgy modos´ıtott feladat le´ır´as´ahoz sz¨uks´eges 



m X n X

 L :=  1 + log2 n + log2 m + 2  i=1 L'

(1 + log2 (1 + |aij | 2L0 )) +

j=1

m X

 



(1 + log2 (1 + |bi | + 2L0 2L0 ))   j=1

2L20

Ezen le´ır´as seg´ıts´eg´evel a bels˝o t´erfogat becsl´ese: ν := 2−2(n+1)L

A kezdeti k¨or´e ´ırt ellipszoid t´erfogatbecsl´ese: velhaszn´alva az extrem´alis pontokra kapott k¯ xk < 2L becsl´est V ≤ cn 2nL

Illetve a teljes l´ep´essz´am: d2(n + 1)(log V − log ν)e = d2(n + 1)(log cn + nL + 2(n + 1)L)e •First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Pontos e´ s k¨ozel´ıt˝o aritmetika

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

K¨osz¨on¨om a figyelmet Hivatkoz´asok [1] George L. Nemhauser, Larence A. Wolsey, Integer and Combinatorical Optimization, Wiley-Interscience, Jhon Wiley & Sons, Inc, 1998? [2] Manfred Padberg, Linear Optimization and Extensions, Springer

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 TIXPDF.COM - All rights reserved.