Eötvös Loránd Tudományegyetem
A lineáris programozási feladat optimális bázismegoldásának el®állítása polinom id®ben diplomamunka
Majoros Csilla
Témavezet®:
Illés Tibor egyetemi docens ELTE-TTK Operációkutatási Tanszék
Budapest, 2014.
Tartalomjegyzék
1. Bevezetés
3
2. Alapvet® eredmények áttekintése
6
2.1. Lineáris programozási alapfeladat . . . . . . . . . . . . . . . . . . . .
6
2.2. Lagrange-dualitás . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3. A Newton-módszer . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4. A barrier-módszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3. Útkövet® bels®pontos algoritmusok elmélete
12
3.1. Az analitikus centrum . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2. Newton módszer az LP -feladatra . . . . . . . . . . . . . . . . . . . .
13
3.3. Barrier módszer az LP -feladatra . . . . . . . . . . . . . . . . . . . . .
14
3.4. A centrális út . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.5. A Newton-lépés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.6. A centrális út környezetei
21
. . . . . . . . . . . . . . . . . . . . . . . .
4. Primál-duál útkövet® algoritmusok
23
4.1. A keretalgoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.2. Egy rövid lépéses algoritmus . . . . . . . . . . . . . . . . . . . . . . .
24
4.3. Egy hosszú lépéses algoritmus . . . . . . . . . . . . . . . . . . . . . .
28
4.4. Egy prediktor-korrektor algoritmus . . . . . . . . . . . . . . . . . . .
30
4.5. Pontos megoldás el®állítása
33
. . . . . . . . . . . . . . . . . . . . . . .
5. Duális módszerek
37
5.1. A szubgradiensek . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
5.2. A szubgradiens módszer . . . . . . . . . . . . . . . . . . . . . . . . .
38
5.3. A vágósíkos módszer . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.4. A volume algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
6. Optimális bázismegoldás el®állítása
49
6.1. A perturbált feladat . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
6.2. Kezd® bázis el®állítása . . . . . . . . . . . . . . . . . . . . . . . . . .
52
6.3. Primál fázis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
6.4. Duál fázis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
2
1.
Bevezetés
Jelenleg két népszer¶ megközelítés van a lineáris programozási feladat megoldására: a pivot algoritmusok és a bels®pontos algoritmusok. Mindkét típusnak számos variációja lett kifejlesztve az utóbbi évtizedekben. A szimplex módszernek megvan az a szép tulajdonsága, hogy ha a feladatnak van optimáis megoldása, akkor az algoritmus egy optimális bázismegoldást talál. Azonban jelenleg nem ismert polinomiális idej¶ pivot algoritmus. A szimplex módszerrel ellentétben a bels®pontos algoritmusok a megengedett tartomány belsejében lépkednek, a cél az optimális lap megközelítése. Azaz véges sok lépésben nem adnak egzakt optimális megoldást. Ye [10] javasolt egy eljárást, amit egy bels®pontos algoritmusba ágyazva pontos optimális megoldást állíthatunk el® polinom id®ben. Ez a megoldás azonban az optimális lap bels® pontja lesz, azaz több optimális megoldás létezése esetén nem lesz bázismegoldás. Számos esetben kívánatos, hogy az optimális megoldásunk bázismegoldás legyen: - Bázismegoldást használ a klasszikus és olcsó érzékenység vizsgálat. - Ha egymáshoz szorosan kapcsolódó feladat-sorozatunk van, akkor sok esetben az egyik optimális bázismegoldásából indítva néhány pivotlépéssel megkapjuk a következ® optimális bázismegoldását. - Egészérték¶ és vegyes programozási feladatok megoldási módszereinél is gyakran elengedhetetlen, hogy a relaxált feladat optimális bázismegoldása álljon rendelkezésre. Felvetült tehát a kérdés, hogyan lehetne polinom id®ben optimális bázismegoldást el®állítani. Erre a problémára az els® relaváns választ Megiddo [11] adta. Konstruktív módon bebizonyította, hogy ha adott egy optimális primál-duál megoldáspár, akkor er®sen polinomiális id®ben el® tudnuk állítani optimális bázismegoldást. Természetes volt Megiddo módszerét kombinálni a bels®pontos algoritmusokkal, és Ye [10] pontos megoldást el®állító kerekítési eljárásával. Ezt meg is tette Andersen és Ye [12], és egy elméleti és gyakorlati szempontból is jól m¶köd® algoritmust csináltak, ami polinomiális id®ben optimális bázismegoldást állít el®. Az eljárást röviden nevezzük BI -nek, azaz bázis identi kációnak. A BI eljárás nem csak a bels®pontos algoritmusokkal kombinálva használható, hanem más LP-megoldó módszerekkel is, amik nem feltétlenül adnak olyan precíz közelítést. A lényeg, hogy az primál és duál közelít® megoldást is gyártson. Megiddo [11] ugyanis azt is bebizonyította, hogy ha csak egy primál, vagy csak egy duál optimális megoldás áll a rendelkezésünkre, akkor optimális bázist csak abban az esetben tudunk találni er®sen polinomiális id®ben, ha az LP -feladat is megoldható er®sen polinomiális id®ben. A dolgozat célja, hogy ezt a folyamatot - közelít® megoldás el®állítása, bázis identi káció - kifejtse. Részletesen áttekintjük az útkövet® bels®pontos algoritmusok elméletét, a nemlineáris programozás eredményeib®l kiindulva. Majd megnézzük a Ye [10] által javasolt kerekítési eljárást, amivel egzakt, szigorúan komplementáris megoldáspárt állítunk el®. 3
A bels®pontos algoritmusok hátránya, hogy közeledve az optimális laphoz lelassul a folyamat, számítási nehézségek lépnek fel. Ezért miel®tt a BI -eljárást kifejtenénk, megnézünk néhány közelít® algoritmust, amik számításigénye (sok esetben) jóval kedvez®bb a bels®pontos algoritmusokénál. Az els® két vizsgált módszer csak duálközelít® megoldást állít el®, ezért ezekkel a BI-eljárás nem kombinálható. Francisco Barahona és Ranga Anbil [8] dolgozták ki az el®z®ek továbbfejlesztésével a volume algoritmust, ami a duál közelítéssel párhuzamosan a primál közelítést is végzi. Ez az algoritmus egy szemléletes tételen alapszik, ami a primál változókat bizonyos térfogatok arányaként fejezi ki. Ez a módszer kis számításigény¶, és kombinálva a BI eljárással sok esetben hatékonyan megkeres egy optimális bázist. Végül megnézzük a BI -eljárást, ami egy közelít® primál-duál megoldást adó algoritmussal kombinálva optimális bázismegoldást talál.
4
Köszönetnyilvánítás Ezúton is szeretnék köszönetet mondani Illés Tibor tanár úrnak a szakdolgozatomhoz nyújtott segítségéért, és azért, hogy a kurzusai során felkeltette az érdekl®désemet a téma iránt.
2.
Alapvet® eredmények áttekintése
2.1. Lineáris programozási alapfeladat A primál-duál lineáris optimalizálási feladatpár standard alakja a következ®:
(P )
max{bT y : AT y + s = c, s ≥ 0}.
(D) ahol A ∈ vektorok.
min{cT x : Ax = b, x ≥ 0},
Rm×n egy m-rangú mátrix;
b, c, x, y , s pedig megfelel® méret¶ valós
A vektorokat mindig oszlopvektornak képzeljük.
Jelölések FP , FD FP0 , FD0 FP∗ , FD∗ F , F 0, F ∗ p∗ = d∗ Sδ (x) Df ∇f , ∇2 f X e CP , CD , C n n ⊕, + xs
R R
a (P ), (D) feladatok megengedett megoldásai a (P ), (D) feladatok szigorúan megengedett megoldásai a (P ), (D) feladatok optimális megoldásai a megfelel® primál-duál megoldáspárok halmaza a primál és duál optimum értéke az x pont δ sugarú nyílt környezete az f : n → n függvény Jacobi-mátrixa az f : n → függvény gradiense és Hesse-mátrixa az a diagonális mátrix, amire Xii = xi , ahol x ∈ n a megfelel® méret¶ csupa 1 vektor a primál, duál és primál-duál centrális út a nemnegatív és pozitív ortáns n -ben két vektor komponensenkénti szorzata (= XSe)
R R
R R
R
R
2.1.1. Tétel (gyenge dualitás). Legyen x¯ ∈ FP és (¯y, s¯) ∈ FD . Ekkor cT x¯ ≥ bT y¯
és egyenl®ség pontosan akkor van, ha x¯T s¯ = 0.
Biz.:
triviális
2.1.2. Tétel (er®s dualitás). Ha a primál és duál feladatnak is van megengedett megoldása, akkor mindkett®nek van optimális megoldása is. Tetsz®leges x∗ , y ∗ optimális megoldásra cT x∗ = bT y ∗ . Tehát az x∗ primál, és (y ∗ , s∗ ) duál megengedett megoldások pontosan akkor optimálisak, ha (x∗ )T s∗ = 0. A nemnegativitási feltételek miatt ez pontosan azt jelenti, hogy x∗i s∗i = 0 minden i-re. Az optimális megoldások tehát pontosan a komplementárisak. 6
2.1. Def. Egy x∗ és (y∗ , s∗ ) optimális megoldáspárt er®sen komplementárisnak nevezünk, ha x∗ + y ∗ > 0. 2.1.3. Tétel (Goldman-Tucker). Ha a primál és duál feladatnak is van megengedett megoldása, akkor szigorúan komplementáris primál-duál optimális megoldáspár is létezik. Ha x∗ , (y ∗ , s∗ ) egy szigorúan komplementáris megoldáspár, akkor az általa meghatározott P ∗ := {j : x∗j > 0} és D∗ := {1, . . . , n} \ P ∗ partíció megegyezik minden egyes szigorúan komplementáris megoldás esetén.
2.2. Lagrange-dualitás A következ® ismeretekre a 5. fejezetben lesz majd szükség. Tekintsük a következ® optimalizálási feladatot
min f (x) h(x) = 0 x ∈ M, ahol f :
Rn → R, h : Rn → Rm adott függvények és M ⊆ Rn.
A feladathoz rendelt-Lagrange függvény:
L(x, π) = f (x) + π T h(x), és duális függvény
q(π) = inf L(x, π). x∈M
A feladat Lagrange-duálisa a következ® probléma: } max q(π) m π ∈
R
A q(π) értéke −∞ is lehet néhány µ-re. A duális feladat megoldása lényegében a következ® feltételes maximalizálási feladat megoldását jelenti: } max q(π) π ∈ D ahol D = {π|q(π) > −∞}. Nevezzük D-t a kiterjesztett érték¶ q függvény lényeges tartományának. Függetlenül a primál feladat költségfüggvényét®l és feltételeit®l, a duális feladat szép konvexitási tulajdonságokkal rendelkezik, ezt fejezi ki a következ® állítás.
2.2.1. Állítás. A duális függvény lényeges tartománya konvex halmaz, és q konkáv ezen a halmazon. Biz.:
Tetsz®leges x, π, π ¯ és α ∈ [0, 1] esetén
L(x, απ + (1 − α)¯ π ) = αL(x, π) + (1 − α)L(x, π ¯ ). 7
Mindkét oldal in mumát véve az M halmazon
inf L(x, απ + (1 − α)¯ π ) ≥ α inf L(x, π) + (1 − α) inf L(x, π ¯ ),
x∈M
vagyis
x∈M
x∈M
αq(απ + (1 − α)¯ π ) ≥ αq(π) + (1 − α)q(¯ π ).
Ebb®l látszik, hogy π, π ¯ ∈ D esetén απ + (1 − α)¯ π ∈ D, azaz D konvex halmaz. Továbbá az utolsó egyenl®tlenség épp q konkávitását mutatja. A duális függvény másik szép tulajdonságáról szól a következ® állítás.
2.2.2. Állítás. A duális függvény felülr®l féligfolytonos, azaz minden πk → π pontsorozatra lim sup q(π k ) ≤ q(π). k→∞
Biz.:
q(π k ) = inf L(z, π k ) ≤ L(x, π k ), z∈M
így
lim sup q(π k ) ≤ L(x, π),
∀x ∈ M,
∀x ∈ M.
k→∞
In mumot véve az M halmazon
lim sup q(π k ) ≤ inf L(x, π) = q(π), k→∞
x∈M
ami épp a bizonyítandó állítás.
2.2.1. Köv. A D tartomány zárt.
2.3. A Newton-módszer A Newton-módszer az alapja a leghatékonyabb algoritmusoknak a lineáris és nemlineáris programozás területén. A következ® fejezetben is erre fognak épülni az algoritmusaink. Névadója javasolta el®ször, 1669-ben, polinomok gyökének meghatározására. Az f (x) = x3 − 2x − 5 = 0 példán mutatta be az eljárást, az x0 = 2 pontból indulva. Tetsz®leges dierenciálható függvényre Raphson alkalmazta el®ször, 1690ben, ezért gyakran Newton-Raphson módszerként hivatkoznak rá. Az eljárás kvadratikus konvergenciáját a gyökök környezetében Fourier bizonyította 1818-ban, majd Cauchy terjesztette ki több dimenzióra 1829-ben. A többdimenziós eset konvergenciáját Fine bizonyította 1916-ban. A huszadik század folyamán végtelen dimenzióra és általános függvényterekre is továbbfejlesztették. B®vebben pl. Polyak [3] cikkéb®l tájékozódhatunk. Nézzük a következ® feladatot:
R
g: n→ g(x) = 0 x =? 8
Rn
A módszer egy olyan pontsorozatot fog generálni, ami a g függvény gyökéhez konvergál. Tegyük fel, hogy az x0 , x1 , . . . , xk pontokat már kiszámoltuk. A g(x)-et az xk körül az xk -beli els®rend¶ Taylor-polinomjával közelítjük:
g(x) ≈ g(xk ) + Dg(xk )(x − xk ) =: h(x) Az xk+1 pont a h(x) gyöke lesz:
h(x) = g(xk ) + Dg(xk )(x − xk ) = 0 xk+1 = xk − Dg(xk )−1 g(xk )
2.3.1. Tétel. (I.) Tegyük fel, hogy az x∗ gyöke a g-nek, a g folytonosan dierenciálható az x∗ környezetében és a Dg(x∗ ) Jacobi-mátrix reguláris. Ekkor ha a Newtonmódszert az x∗ -hoz elég közel indítjuk, akkor a Newton-lépések jól de niáltak lesznek, és a generált pontsorozat az x∗ -hoz konvergál. A konvergencia szuperlineáris. (II.) Tegyük fel, hogy az L > 0, M > 0, δ > 0 számokra és minden x, y ∈ Sδ (x∗ )-ra: ||Dg(x) − Dg(y)|| ≤ L||x − y||,
||(∇g(x))−1 || ≤ M.
Ekkor minden x0 ∈ Sδ (x∗ ) esetén: ||xk+1 − x∗ || ≤
Azaz ha
Biz.:
LM δ <1 2
LM k ||x − x∗ ||2 , 2
∀k = 0, 1, . . .
és x0 ∈ Sδ (x∗ ), akkor a konvergencia másodrend¶.
Lásd [2].
Newton-módszer minimalizálásra
R
R
f: n→ min f (x) =? Itt egy olyan pontsorozatot számolunk ki, ami egy lokális minimumhoz konvergál. Tegyük fel, hogy az x0 , x1 , . . . , xk pontokat már kiszámoltuk. Az f (x) függvényt az xk közelében becsülhetjük a csonkított Taylor-sorával:
1 f (x) ≈ f (xk ) + ∇f (xk )(x − xk ) + (x − xk )T ∇2 f (xk )(x − xk ) =: h(x) 2 Az f(x) helyett a h(x)-et minimalizáljuk:
∇h(x) = ∇f (xk ) + ∇2 f (xk )(x − xk ) = 0. A fenti egyenletb®l:
xk+1 = xk − ∇2 f (xk )−1 ∇f (xk ).
9
Megjegyzés: A Newton-módszer gyökkeresésre szélesebb körben alkalmazható. Az ott szerepl® g(x) függvény nem feltétlenül egy másik függvény gradiense. Egy folytonosan dierenciálható g : Rn → Rn függvény pontosan akkor egy h : Rn → R függvény gradiense, ha a Dg(x) mátrix szimmetrikus minden x-re. Ahhoz, hogy a lépés jól de niált legyen szükséges, hogy létezzen a Hesse-mátrix inverze. Ehhez tegyük fel, hogy az x∗ lokális minimumban a ∇2 f (x∗ ) mátrix pozitív de nit. Ekkor ha elég közel indítjuk az eljárást az x∗ -hoz, akkor a ∇2 f (xk ) is pozitív de nit lesz.
2.3.2. Tétel. Legyen f ∈ C 3 (Rn ), és tegyük fel, hogy az x∗ lokális minimumban a ∇2 f (x∗ ) Hesse-mátrix pozitív de nit. Ekkor ha a Newton-módszert az x∗ -hoz elég közel indítjuk, akkor a Newton-lépések jól de niáltak lesznek és a generált pontsorozat az x∗ -hoz konvergál. A konvergencia rendje legalább kett®. Biz.:
Lásd [1].
Ha a Hesse-mátrix nem jól-kondícionált (a legnagyobb és a legkisebb sajátérték hányadosa nagy), akkor a mátrix csak nehezen invertálható. A számításigény csökkentésére különféle technikákat dolgoztak ki. A [2]-ben találhatunk b®vebb ismertet®t.
2.4. A barrier-módszer A barrier-módszer a következ® típusú feladatokra alkalmazható:
min f (x) x∈S
R
R
ahol f : n → függvény, a megengedett S halmaz belseje nem üres, és S bármely pontjához van tetsz®legesen közeli bels® pont. A barrier módszer lényege, hogy a megengedett tartomány határán olyan gátat emel, ami megakadályozza, hogy a keres®eljárás elhagyja a tartományt. A B : int(S) →
R függvényt barrier függvénynek nevezzük, ha:
(1) B folytonos (2) B(x) ≥ 0 (3) B(x) → ∞, ha x az S határához tart
Példák:
S := {x ∈
Rn : gi(x) ≤ 0, i = 1, . . . , p}
B1 (x) := −
p ∑ i=1
B2 (x) := −
p ∑
1 , gi (x)
x ∈ int(S)
log(−gi (x)),
i=1
10
x ∈ int(S)
Nézzük k = 1, 2, . . . -re a következ® részfeladatokat:
min(f (x) + µk B(x)) x ∈ intS, ahol µk monoton fogyó nullsorozat. Legyen a megoldása xk .
Megjegyzés: Látszólag egy sereg, az eredetinél bonyolultabb, feltételes optimalizálási feladatot kaptunk. Viszont ezeknél a feladatoknál használhatóak lesznek a feltétel nélküli keresési eljárások, a megengedett tartományban maradást a barrier tag fogja biztosítani. 2.4.1. Tétel. A barrier módszer által generált {xk } sorozat tetsz®leges határpontja megoldása lesz az eredeti feladatnak. Biz.:
Lásd [2].
11
3.
Útkövet® bels®pontos algoritmusok elmélete
3.1. Az analitikus centrum Legyen az S halmaz a következ® módon megadva:
S = {x ∈ X ⊆
Rn : gj (x) ≥ 0, j = 1, . . . , m},
ahol a gj függvények folytonosak és int(S) ̸= ∅.
int(S)-en de niálunk egy potenciálfüggvényt: ψ(x) := −
m ∑
log gj (x).
j=1
Az S analitikus centruma az a pont(halmaz), ami minimalizálja a potenciálfüggvényt.
3.1. Példa. Legyen S ⊆ Rn a következ® egyenl®tlenségekkel megadva: xi ≥ 0 (1 − xi ) ≥ 0
i = 1, 2, . . . , n
Vagyis S = [0, 1]n , az egységkocka. ψ(x) = −
n ∑
log xj −
n ∑
j=1
log(1 − xj ),
j=1
Keressük meg a ψ(x) minimumát: (
) ∇ψ(x) j = − x1j +
1 1−xj
xj
= 0 = 12
Az analitikus centrum tehát az ( 12 , 12 , . . . , 12 ) pont, ami valóban a kocka geometriai középpontja.
3.2. Példa. Az analitikus centrum függ attól, hogyan adjuk meg a halmazt. Az S = [0, 1]n egységkockát a következ® egyenl®tlenségekkel is megadhatjuk: xi ≥ 0 (1 − xi )d ≥ 0
i = 1, 2, . . . , n
ahol a d tetsz®leges, egynél nagyobb szám. Ezekkel az egyenl®tlenségekkel kiszámolva 1 1 1 , d+1 , . . . , d+1 ) pontot kapjuk. Ez a pont nagy d esetén az analitikus centrumot, az ( d+1 sokkal közelebb van a kocka origó-beli csúcsához, mint a többihez.
12
Az analitikus centrumot felesleges egyenl®tlenségek hozzávétele is módosítja. Például ha ugyanazt az egyenl®tlenséget többször hozzávesszük. Az analitikus centrum értelmezését kiterjeszthetjük arra az esetre is, ha az int(S) = ∅. Nézzük a következ® speciális esetet:
S = {x ∈ X ⊆
Rn : x ≥ 0},
ahol az X egy a n altér. Tegyük fel, hogy az S korlátos (ekkor kompakt is). De niáljuk az S tartóját a következ®képpen:
σ(S) := {i : xi > 0 valamely x ∈ S esetén}. Az S analitikus centruma σ(S) = ∅ esetén a 0 vektor, különben pedig az az x ∈ S vektor, ami maximalizálja a ∏ xi i∈σ(S)
szorzatot. Ha σ(S) ̸= ∅, akkor az S kompaktsága miatt véges a maximum. Az S konvexitása miatt pedig lesz olyan x ∈ S vektor, amire xσ(S) > 0, azaz a maximum pozitív. A szorzat logaritmusa szigorúan konkáv, így a maximum értéke egyetlen S -beli pontban vétetik fel, az analitikus centrum ebben az esetben egyértelm¶.
3.3. Példa. Nézzük a primál-duál optimális lapot: ∗ Fx,s = {(x, s) ∈
Rn × Rn : Ax = b, AT y + s = c, cT x = p∗, x ≥ 0, s ≥ 0}
∗ Tegyük fel, hogy Fx,s ̸= ∅ és korlátos. Vezessük be a következ® indexhalmazokat:
P ∗ = {i : xi > 0, valamely x ∈ FP∗
esetén}
D∗ = {j : sj > 0, valamely (y, s) ∈ FD∗
esetén}
∗ ∗ ˙ ∗ indexhalmaz. Ekkor Fx,s Ekkor az Fx,s tartója a P ∗ ∪D analitikus centruma az az ∗ ∗ egyértelm¶ (x , s ) pont, ami maximalizálja a
∏
i∈P ∗
xi
∏
sj
j∈D∗
szorzatot. Ezt az eredményt és a P ∗ , D∗ halmazokat a kés®bbiekben még használni fogjuk.
3.2. Newton módszer az LP -feladatra Ahhoz, hogy megkapjunk egy optimális primál-duál megoldáspárt, "elég" megoldanunk a következ® rendszert:
Ax = b x ≥ 0, AT y + s = c s ≥ 0, OP T xs = 0. 13
Ugyanezt más formában felírva:
AT y + s − c 0 = 0 , Ax − b F0 (x, y, s) := Xs 0
x≥0 s≥0
Próbáljuk megoldani ezt a nemlineáris rendszert a Newton-módszerrel:
k xk+1 x y k+1 = y k − [DF0 (xk , y k , sk )]−1 F0 (xk , y k , sk ) sk+1 sk ahol
0 AT I DF0 = A 0 0 , S 0 X az F0 Jacobi-mátrixa. Legyen egy megoldás a p∗ := (x∗ , y ∗ , s∗ ). Az Xs = 0 feltétel miatt a p∗ a megengedett tartomány határán lesz, és ott sajnos nem garantálható a Jacobi-mátrix invertálhatósága. Így itt a Newton-módszer nem vezet eredményre.
3.3. Barrier módszer az LP -feladatra Tekintsük az LP -feladat standard alakját:
min cT x Ax = b (P ) x ≥ 0.
Tegyük fel, hogy FP0 ̸= ∅ és FP∗ korlátos. Legyen a barrierfüggvénnyel módosított célfüggvény a következ®:
fP (x; µ) := c x − µ T
n ∑
log xi ,
x ∈ FP0
i=1
Minden µ ≥ 0-ra a következ® barrier feladatot kapjuk:
min fP (x; µ) Ax = b BP (µ) x > 0 Világos, hogy µ = 0-ra az eredeti LP -feladatot kapjuk. Ha a µ → ∞, akkor a BP(µ) megoldásai az FP megengedett tartomány analitikus centrumához tartanak, hiszen ekkor a cT x elhanyagolható, a barrier rész pedig éppen az FP0 -hoz tartozó potenciálfüggvény. 14
A kés®bbiekben belátjuk majd, hogy minden µ > 0-ra egyértelm¶ x(µ) megoldása lesz a BP(µ) feladatnak. Az x(µ) pontok adják a primál centrális utat, ami µ → 0 esetén az optimális lap analitikus centrumához fog tartani. Tehát a primál centrális út az FP analitikus centrumától halad az FP∗ analitikus centruma felé. Most vizsgáljuk meg a duális feladatot:
max bT y AT y + s = c (D) s ≥ 0.
Alkalmazva a barrier-módszert, készítsük el a hozzá tartozó barrier-feladatot:
fD (y, s; µ) := bT y + µ
n ∑
log si ,
(y, s) ∈ FD0
i=1
max fd (y, s; µ) AT y + s = c BD(µ) s > 0 Tegyük fel, hogy FD0 ̸= ∅ és FD∗ korlátos. Ha a µ folytonosan halad a 0 felé, akkor a BD(µ) feladatok egyértelm¶ (y(µ), s(µ)) megoldásai egy utat de niálnak, amit duál centrális útnak nevezünk. Elmondhatjuk ugyanazt itt is, mint a primál esetben. A µ = 0-ra az eredeti feladatot kapjuk. Ha a µ → ∞, akkor az (y(µ), s(µ)) µ-centrumok az FD megengedett tartomány analitikus centrumához tartanak, míg µ → 0 esetén az FD0 duál optimális lap analitikus centrumához.
3.3.1. Tétel. Legyen µ > 0. Ekkor a következ® állítások ekvivalensek: (1) FP0 ̸= ∅ és FD0 ̸= ∅ (2) egyértelm¶en létezik megoldása a BP(µ) feladatnak (3) egyértelm¶en létezik megoldása a BD(µ) feladatnak (4) egyértelm¶en létezik megoldása a következ® rendszernek:
AT y + s − c 0 Ax − b 0 , Fµ (x, y, s) := = Xs − µe 0
Biz.: (2)⇔(4) Az fP
x≥0 s≥0
OP T (µ)
függvény gradiense:
∇fP (x; µ) = c − µX −1 e, és Hesse-mátrixa:
∇2 fP (x; µ) = µX −2 .
A Hesse mátrix pozitív de nit minden x ∈ FP0 pontban, azaz a függvény itt szigorúan konvex. 15
A BP (µ) tehát egy konvex programozási feladat. A megengedett tartomány minden pontja reguláris a rang(A) = m feltétel miatt. Így BP (µ) megoldása ekvivalens a hozzá tartozó KKT -rendszer megoldásával. A BP (µ) Lagrange-függvénye:
L(x, y) = c x − µ T
n ∑
log xi + y T (Ax − b),
i=1
a KKT -rendszer:
∇x L(x, y) = c − µX −1 e + y T A = 0 ∇y L(x, y) = Ax − b = 0
} (KKT )
Legyen s = µX −1 e, ekvivalensen Xs = µe. Azaz a KKT -rendszer ekvivalens az OP T (µ) rendszerrel.
(3)⇔(4) Az fD
függvény gradiense:
∇fD (y, s; µ) = (bT , eT S −1 ), és Hesse-mátrixa:
[ ∇ fD (y, s; µ) = 2
0 0 0 −µS −2
] .
A Hesse-mátrix negatív szemide nit minden (y, s) ∈ FD0 pontban, azaz a függvény itt konkáv. A BD(µ) is egy konvex programozási feladat. Minden megengedett megoldás reguláris pont lesz, a slack változók jelenléte miatt. Ezért a BD(µ) rendszer megoldása ekvivalens lesz a hozzá tartozó KKT-rendszer megoldásával. A BD(µ) Lagrange-függvénye: T
L(y, s, x) = y b + µ
n ∑
log si − (y T A + sT − cT )x,
i=1
a KKT -rendszer:
∇y,s L(y, s, x) = (bT − (Ax)T , µeS −1 − xT ) = 0 ∇x L(y, s, x) = −y T − sT + cT = 0
} (KKT ).
Azaz a BD(µ) feladathoz tartozó KKT -rendszer is éppen az OP T (µ) rendszer.
(4)⇒(1):
Az OP T (µ) megoldásai nyilván megengedett megoldások, és az Xs = µe feltétel miatt bels®pontok is.
3.4. A centrális út A következ®kben a bels®pont-feltételt végig feltesszük. Az ekkor minden 0 < µ < ∞ esetén egyértelm¶en létez® (x∗ (µ), y ∗ (µ), s∗ (µ)) megoldások folytonos útját primálduál centrális útnak nevezzük, C -vel jelöljük. A rang(A) = m feltétel miatt kölcsönösen egyértelm¶ megfeleltetés van az y és s között. Ez lehet®vé teszi, hogy az {(x(µ), s(µ)) : 0 < µ < ∞} utat tekintsük primál-duál centrális útnak. 16
3.4.1. Tétel. Tegyük fel, hogy F0 ̸= ∅. Ekkor: (1) Az {(x(µ), s(µ)) : 0 < µ ≤ µ0 } ponthalmaz korlátos minden 0 < µ0 < ∞ esetén. (2) µ→0 lim (x(µ), s(µ)) = (x∗ , s∗ ), ahol az (x∗ , s∗ ) egy szigorúan komplementáris meg∗ oldáspár, ami megegyezik a Fx,s optimális lap analitikus centrumával.
Biz.: (1) A(x(µ0 ) − x(µ)) = b − b = 0 és AT (y(µ0 ) − y(µ)) + (s(µ0 ) − s(µ)) = 0, azaz
(x(µ0 ) − x(µ)) ∈ N (A) és (s(µ0 ) − s(µ)) ∈ R(AT ),
ezért:
(x(µ0 ) − x(µ))T (s(µ0 ) − s(µ)) = 0
Kifejtve kapjuk: n ∑
(s(µ0 )i x(µ)i + x(µ0 )i s(µ)i ) = n(µ0 + µ) ≤ 2nµ0
i=1
Végigosztva µ0 -lal:
n ∑
(
i=1
x(µ)i s(µ)i + 0 x(µ )i s(µ0 )i
) ≤ 2n,
hiszen s(µ0 )i x(µ0 )i = µ0 minden i-re. Azaz x(µ) és s(µ) korlátosak.
(2)
Az (1)-es miatt az {(x(µ), s(µ)) : 0 < µ ≤ µ0 } halmaznak van legalább egy határpontja. Legyen az (x(0), s(0)) egy tetsz®leges határpont. Feltehet®, hogy (x(0), s(0)) = lim (x(µk ), s(µk )). k→∞
∗ I. (x(0), s(0)) ∈ Fx,s
Ez nyilvánvaló:
x(0)s(0) = lim (x(µk )s(µk )) = lim (µk e) = 0 k→∞
II.
(x(0), s(0))
Az
(1)-nél látottak alapján:
k→∞
szigorúan komplementáris megoldás (x(0) − x(µ))T (s(0) − s(µ)) = 0
Kifejtve:
n ∑
(s(0)i x(µ)i + x(0)i s(µ)i ) = µn
i=1
Másképpen:
∑ i:x(0)i >0
x(0)i
∑ s(µ)i x(µ)i + s(0)i =n µ µ i:s(0)i >0
17
Felhasználva, hogy µ = x(µ)i s(µ)i minden i-re:
∑ i:x(0)i >0
∑ s(0)i x(0)i + =n x(µ)i s(µ)i i:s(0)i >0
µ → 0 határátmenettel kapjuk: |σ(x(0))| + |σ(s(0))| = n,
II. III. a korábban de niált P ∗ és D∗ -re: amib®l következik
P ∗ ∩ D∗ = ∅, P ∗ ∪ D∗ = {1, 2, . . . , n}.
Az állítás második része következik abból, hogy létezik szigorúan komplementáris megoldás. Az els® rész bizonyításához indirekt tegyük fel, hogy i ∈ P ∗ ∩ D∗ . Azaz létezik x ∈ FP∗ , (y, s) ∈ FD∗ , amikre xi si > 0. Ez ellentmondás, hiszen az optimális megoldások pontosan a komplementárisak.
IV. az
(x(0), s(0))
megegyezik az
∗ Legyen (x∗ , s∗ ) ∈ Fx,s tetsz®leges. A
∗ Fx,s
analitikus centrumával
II.-nél látott módon, az
(x∗ − x(µ))T (s∗ − s(µ)) = 0 egyenletb®l kiindulva a következ® összefüggésre jutunk:
∑ x∗ ∑ s∗ i i + = n. x(0)i i∈D∗ s(0)i i∈P ∗ Mivel xi > 0 ∀i ∈ P ∗ és si > 0 ∀i ∈ D∗ , alkalmazhatjuk a számtani-mértani közép közti egyenl®tlenséget:
(
∏
x∗i
i∈P ∗
x(0)i
Így
∏ i∈D∗
s(0)i
∏ i∈P ∗
ebb®l következik
) n1
s∗i
x∗i
∏ i∈D∗
1 ≤ n
s∗i ≤
(
∑ x∗ ∑ s∗ i i + x(0)i i∈D∗ s(0)i i∈P ∗
∏ i∈P ∗
x(0)i
∏
) = 1.
s(0)i
i∈D∗
IV.
∗ lapnak egyértelm¶en létezik az analitikus centA korábbiakban láttuk, hogy az Fx,s ruma, így lim (x(µ), s(µ)) = (x(0), s(0)). µ→0
Az el®z® tétel alapján a primál-duál centrális út µ → 0 esetén az optimális lap analitikus centrumához konvergál, amennyiben ez a lap korlátos. Könnyen látható, hogy ha a Fx,s poliéder is korlátos, akkor a primál-duál centrális út µ → ∞ esetén a Fx,s analitikus centrumához konvergál. Ezeket az állításokat könnyen ellen®rizhetjük külön-külön a primál és a duál cent∗ -nak, ha x∗ rális utakra, ugyanis az (x∗ , s∗ ) pontosan akkor analitikus centruma Fx,s ∗ ∗ ∗ ∗ analitikus centruma FP -nak és (y , s ) analitikus centruma FD -nak. 18
Miért az analitikus jelz®? Vizsgáljuk az
(x(µ), s(µ)) :
R+ → Rn × Rn
függvényt. Az
AT y + s − c Ax − b Fµ (x, y, s) := Xs − µe
függvény folytonosan dierenciálható és hamarosan belátjuk, hogy a Jacobi-mátrixa nemszinguláris a bels® pontokban. Tudjuk, hogy:
Fµ (x(µ), y(µ), s(µ)) = 0 ∀µ > 0. Alkalmazva az implicitfüggvény-tételt kiderül, hogy a centrális út analitikus minden µ > 0 pontban. Mivel a centrális út konvergál µ → 0 esetén, kiterjeszthetjük az (x(µ), s(µ)) függvényt az ⊕ -ra: (x(0), s(0)) := lim (x(µ), s(µ)).
R
µ→0
A centrális út a µ = 0 pontban is analitikus lesz, ennek belátására viszont nem használhatjuk az implicitfüggvény-tételt a Jacobi-mátrix szingularitása miatt. A bizonyítás megtalálható [6]-ben.
3.5. A Newton-lépés Amint korábban láttuk az OP T rendszer megoldása az F megengedett megoldáshalmaz határán van. Ebben az esetben nem garantálható, hogy a DF0 Jacobi-mátrix invertálható, így itt nem m¶ködik a Newton-módszer. A relaxált OP T (µ) rendszer megoldásai azonban mindig bels® pontok.
3.5.1. Tétel. A
0 AT I DFµ (x, y, s) = A 0 0 , S 0 X
Jacobi-mátrix reguláris, ha x > 0 és s > 0 (azaz ha (x, y, s) ∈ F 0 ).
Biz.:
Azt vizsgáljuk, hogy lehet-e nemtriviális megoldása a (DFµ )z = 0 egyenletnek. Legyen z = (u, v, w) ∈ n × m × n . Kifejtve a homogén egyenletet: T u A v+w 0 = 0 Au DFµ (x, y, s) v = w Su + Xw 0
R
R
R
Ekkor
19
uT w = uT (−AT v) = −(Au)T v = 0. Az Su + Xw = 0 egyenletb®l A kett®t összerakva:
u = −S −1 Xw
0 = wT u = wT (−S −1 X)w.
A bels® pontokra a −S −1 X mátrix negatív de nit, így a w csak a 0 lehet. A 0 = Su + Xw = Su egyenletb®l kapjuk, hogy az u = 0, és a 0 = AT v + w = AT v egyenletb®l a rank(A) = m miatt a v = 0. Nincs nemtriviális megoldás, így a DFµ mátrix tényleg reguláris.
Így az OPT(µ) rendszer megoldására használhatjuk a Newton-módszert.
x+ x ∆x y + = y − ∆y s+ s ∆s ahol
(∆x, ∆y, ∆s) = DFµ (x, y, s)−1 Fµ (x, y, s),
azaz
DFµ (x, y, s)(∆x, ∆y, ∆s) = Fµ (x, y, s). De niáljuk a következ® maradékokat az (x, y, s) pontban:
rd := AT y + s + c rp := Ax − b rc := Xs − µe Ezekkel a jelölésekkel a (x, y, s)-beli Newton irány a következ® rendszer megoldása:
rd ∆x DFµ (x, y, s) ∆y = rp ∆s rc
A Jacobi-mátrixot beírva a következ®t kapjuk:
0 AT I ∆x rd A 0 0 ∆y = rp S 0 X rc ∆s
3.5.2. Tétel. Az el®z® rendszer megoldása a következ®: ∆y = (AXS −1 AT )−1 (rp − AS −1 (rc − Xrd )) ∆s = rd − AT ∆y ∆x = S −1 (rc − X∆s)
Biz.:
Ellen®rzés. 20
3.6. A centrális út környezetei Az N2 környezet Szeretnénk mérni, hogy egy (x, y, s) ∈ F 0 pont milyen messze van a centrális úttól. Ehhez vizsgáljuk az min ||Fµ (x, y, s)|| kifejezést. Az értéke pontosan akkor lesz 0, ha µ
az (x, s, y) pont a centrális úton van.
min ||Fµ (x, y, s)|| = min ||XSe − µe|| µ
µ
Az XSe vektor µe irányú mer®leges vetülete
min ||Fµ (x, y, s)|| = ||XSe − µ
xT s e, n
ezért
xT s xT s e|| = ||xs − e|| n n
. Legyen µ(x, s) =
xT s . n
Ekkor az (x, y, s)-hez legközelebbi centum a µ(x, s)-centrum.
Ezek alapján bevezetünk egy centralitási mértéket: xs δ2 (x, y, s) := − e µ(x, s) 2 A δ2 távolság segítségével értelmezhetjük a centrális út környezetét:
N2 (γ) := {(x, y, s) ∈ F 0 : δ2 (x, y, s) ≤ γ}. Könnyen látható, hogy ha 0 ≤ γ1 ≤ γ2 ≤ 1:
C = N2 (0) ⊆ N2 (θ1 ) ⊆ N2 (θ2 ) ⊆ N2 (1) ⊂ F 0 . A környezet szemléltetéséhez vezessük be a következ® függvényt:
ω:
Rn × Rm × Rn → Rn ,
ω(x, y, s) := xs
Az ω a C centrális utat a {µe : µ > 0} "átlós" félegyenesbe viszi. Használva az ω = ω(x, y, s) és µω = µ(x, s) jelölést:
(x, y, s) ∈ N2 (γ) ⇔ ||ω − µω e|| ≤ γµω ⇔ ||ω − µω e||2 ≤ γ 2 µ2ω . A jobboldali egyenl®tlenséget tovább alakítva kapjuk a
< ω, ω > − feltételt. Az Aγ := I −
( n + γ2 ) n2
n + γ2 < ω, eeT ω >≤ 0 n2
eeT mátrix segítségével a következ® egyszer¶ feltételt kapjuk: < ω, Aγ ω >≤ 0. 21
γ2 Az Aγ mátrixnak sajátvektora az e, a − sajátértékkel, és sajátvektora minden n u ⊥ e vektor is, az 1 sajátértékkel. Legyen v1 , . . . , vn−1 , vn ortonormált bázis, amire 1 vn = √ e. Ekkor minden ω vektrra: n ω=
n ∑
< ω, vi > vi =:
i=1
n ∑
λ i vi .
i=1
Ekkor:
< ω, Aγ ω >= λ21 + . . . , λ2n−1 −
γ2 2 λ . n n
Azaz
(x, y, s) ∈ N2 (γ) ⇔ λ21 + . . . , λ2n−1 ≤
γ2 2 λ . n n
Az N2 (γ) környezet ω -képe tehát egy körkúp, aminek szimmetriatengelye éppen a centrális út ω -képe.
Az N−∞ környezet Más centralitási mértéket kapunk, ha nem az euklideszi normát használjuk. Legyen:
xs δ∞ (x, y, s) = − e , µ(x, s) ∞
és
[ ]− xs δ−∞ (x, y, s) = − e , µ(x, s) ∞
− ahol [x]− i = 0, ha xi ≥ 0 és [x]i = xi , ha xi ≤ 0.
Az ebb®l származó környezetek:
N∞ (γ) := {(x, y, s) ∈ F 0 : δ∞ (x, y, s) ≤ γ}, N−∞ (γ) := {(x, y, s) ∈ F 0 : δ−∞ (x, y, s) ≤ γ}, valamely γ ∈ [0, 1]-re. Mi a kés®bbiek folyamán az N−∞ környezetet fogjuk használni. Világos, hogy ha 0 ≤ γ1 ≤ γ2 ≤ 1, akkor
C = N−∞ (0) ⊆ N−∞ (γ1 ) ⊆ N−∞ (γ2 ) ⊆ N−∞ (1) = F 0 .
3.6.1. Állítás. Biz.:
N2 (γ) ⊆ N∞ (γ) ⊆ N−∞ (γ).
minden i-re teljesül, hogy
|xi si − µ(x, s)| ≤ ||xs − µ(x, s)e||2 , ebb®l látszik az els® tartalmazás. A második tartalmazás triviális. 22
4.
Primál-duál útkövet® algoritmusok
Egy keretalgorimus három konkrét variációját nézzük meg: egy rövid lépéses, egy hosszú lépéses és egy prediktor-korrektor verziót.√A hosszú lépéses algoritmustól eltekintve a lehet® legjobb lépésszámot hozzák, O( nL) iterációval. A hosszú lépéses verzió elméleti lépésszámbecslése O(nL) iteráció, azonban a gyakorlatban hatékonyabb a rövid lépéses testvérénél. Ezt a jelenséget "az elmélet és a gyakorlat közti rés"-nek nevezik.
4.1. A keretalgoritmus Bels®pontos keretalgoritmus
Input
ϵ > 0 pontossági paraméter, (x0 , y 0 , s0 ) kezd® bels® pont
begin
(x, y, s) := (x0 , y 0 , s0 ). while nµ > ε do µ := µ(x, s) Oldjuk meg a következ® egyenletet 0 ∆x 0 AT I . A 0 0 ∆y = 0 XSe − σµe ∆s S 0 X Legyen (x, y, s) = (x, y, s) − α(∆x, ∆y, ∆s), ahol α ∈ (0, 1] egy olyan lépéshossz, amire (x, s) > 0, σ ∈ [0, 1] a centralizáló paraméter.
end end
A (∆x, ∆y, ∆s) egy Newton-lépést ad az (x(σµ), y(σµ), s(σµ)) ∈ C centrum felé. A σ paraméter arra szolgál, hogy egyensúlyt tartsunk a centrális út felé történ®, és a vele párhuzamos lépések között. Ha σ = 1, akkor a Newton-lépés épp azt a centrumot közelíti, amelyik a legközelebb van, azaz a centrális útra mer®legesen lépünk. Az ilyen lépést centralizáló lépésnek nevezik. A másik széls® eset, ha σ = 0. Ekkor egyenesen egy optimális pontot célozunk meg, azaz az optimális lap felé lépünk. Az ilyen lépést a n skálázási lépésnek nevezik. A σ és α választásától függ®en különböz® algoritmusokat kapunk. A következ® lemma mutatja, hogy a σ és az α függvényében mennyire csökken a µ. Használjuk a következ® jelöléseket:
(x+ , y + , s+ ) := (x, y, s) − α(∆x, ∆y, ∆s), µ+ := µ(x+ , s+ ).
23
4.1.1. Lemma. Az algoritmusban kiszámolt (∆x, ∆y, ∆s)-re fennállnak a következ®k: i) ∆xT ∆s = 0 ii) µ+ = (1 − α(1 − σ))µ
Biz.: i) Tudjuk, hogy A∆x = 0 A ∆y + ∆s = 0. T
(1) (2)
A (2)-est (∆x)T -tal szorozva kapjuk:
0 = ⟨∆x, AT ∆y⟩ + ⟨∆x, ∆s⟩ = ⟨A∆x, ∆y⟩ + ⟨∆x∆s⟩, így az (1) miatt ⟨∆x, ∆s⟩ = 0.
ii) Az S∆x + X∆s = XSe − σµe egyenletet komponensenként összegezve: ⟨s, ∆x⟩ + ⟨x, ∆s⟩ = ⟨x, s⟩ − σ⟨x, s⟩ = (1 − σ)⟨x, s⟩ . Ezek alapján:
nµ+ = ⟨x+ , s+ ⟩ = ⟨x, s⟩ − α(⟨s, ∆x⟩ + ⟨x, ∆s⟩) = (1 − α(1 − σ))⟨x, s⟩, amib®l következik
ii).
4.2. Egy rövid lépéses algoritmus Rövid lépéses algoritmusról beszélünk, ( ha a σ )a dimenziótól függ® konstans. A ν következ® algoritmusnál α = 1 és σ = 1 − √ . n
24
Rövid-lépéses algoritmus
Input
ϵ > 0 pontossági paraméter, γ és ν konstansok, amelyek kielégítik a következ®ket: √ 1 0≤γ< , 0 < ν < n, 2 ( γ2 + ν2 ν ) ≤ γ 1− √ 2(1 − γ) n
(3)
(x0 , y 0 , s0 ) ∈ N2 (γ).
begin
(x, y, s) := (x0 , y 0 , s0 ), µ := µ(x, s) while nµ > ε do Határozzuk meg azt az (x, y, s)-beli (∆x, ( ∆y, ∆s))Newton-irányt, ν ami a σµ-centrumot közelíti, ahol σ = 1 − √ . n Legyen (x, y, s) = (x, y, s) − (∆x, ∆y, ∆s) és µ := µ(x, s).
end end
4.2.1. Tétel. Legyenek γ és ν a (3) feltételeket kielégít® konstansok, és tegyük fel, hogy (x, y, s) ∈ N2 (γ). Ekkor: i) (x+ , y + , s+ ) ∈ N2 (γ) (
)
ii) µ+ = 1 − √νn µ
Biz.: i) A szakasz végén bizonyítjuk, a következ® lemmák felhasználásával. ii) A 4.1.1 lemma ii) részéb®l egyenesen következik. 4.2.1. Köv. Az algoritmus során nem lépünk ki az ráció után: ( )k µk =
ν 1− √ n
N2 (γ)
környezetb®l és a k. ite-
µ0
4.2.2. Tétel. Az algoritmus legfeljebb K = megoldást ad. Biz.:
⌈
log(nε−1 µ0 )
√
n ν
⌉
iteráció után ε-optimális
Az algoritmus leáll, ha nµk ≤ ε, belátjuk, hogy ez teljesül a k = K -ra:
[ log(nµK ) = log nµ0
(
ν 1− √ n
)K ]
(
ν = log(nµ0 ) + K log 1 − √ n
25
) ≤
[ √ ] ( ) ν n ν √ = log ε. ≤ log(nµ0 ) − K √ ≤ log(nµ0 ) − log(nµ0 ) − log ε ν n n Az els® egyenl®ség az el®z® következmény miatt áll fenn, míg az els® egyenl®tlenségnél azt a tényt használjuk, hogy log(1 − x) ≤ −x ha x < 1. A 4.2.1 tétel i) részének bizonyításához szükség van néhány segédállításra.
4.2.1. Lemma. Legyen u, v ∈ Rn két vektor, melyekre uT v ≥ 0. Ekkor ||uv|| ≥
Biz.:
√ 2−3 ||u + v||2 .
Bontsuk szét az I = {1, 2, . . . , n} indexhalmazt két részre:
P := {i ∈ I|ui vi ≥ 0},
M := {i ∈ I|ui vi < 0},
és egy T ⊆ I indexhalmazra legyen
zT =
∑
ui vi ei .
i∈T
Ekkor
||uv||2 = ||zP ||2 + ||zM ||2 ≤ ||zP ||21 + ||zM ||21 ∑ ≤ 2||zP ||21 = 2( i∈P ui vi )2 ∑ ≤ 2( i∈P 14 (ui + vi )2 )2 ∑ ≤ 2−3 ( ni=1 (ui + vi )2 )2 = 2−3 ||u + v||4 ,
Ami bizonyítja az állítást.
4.2.1. Megjegyzés. A 4.2.1 lemma egyenl®tlensége éles, például a következ® két vektor esetén egyenl®ség van: u := (r, −r, 0, . . . , 0) ∈ Rn és v := (r, r, 0, . . . , 0) ∈ Rn .
4.2.2. Lemma. Ha (x, y, s) ∈ N2 (γ), akkor min xi si ≥ (1 − γ)µ. i
Biz.:
Minden i indexre
µ − xi si ≤ |xi si − µ| ≤ ||xs − µe|| ≤ γµ, azaz (1 − γ)µ ≤ xi si .
4.2.3. Lemma. Ha (x, y, s) ∈ N2 (γ), akkor γ2 + ν2 ||∆x∆s|| ≤ √ µ. 23 (1 − γ) 26
Biz.:
Legyen D := X 2 S − 2 . A Newton-rendszer harmadik egyenletét (XS)− 2 -del szorozva a következ® egyenletet kapjuk: 1
1
1
D−1 ∆x + D∆s = (XS)− 2 (xs − σµe). 1
Ezt az egyenl®séget, és az 4.2.1 lemmát felhasználva
||∆x∆s|| = ||(D−1 ∆x)(D∆s)|| √ 2−3 ||D−1 ∆x + D∆s||2 ≤ √ 1 = 2−3 ||(XS)− 2 (xs − σµe)||2 ∑ 2 ∑ √ √ i = 1n (xi si − σµ)2 n (xi si − σµ) −3 −3 = 2 ≤ 2 i=1 xi si mini xi si 2 √ ||xs − σµe|| = 2−3 mini xi si
(4)
A számlálót kifejtve és felhasználva, hogy (x, y, s) ∈ N2 (γ) kapjuk:
||xs − σµe||2 = = = ≤
||(xs − µe) + (1 − σ)µe||2 ||xs − µe||2 + 2(1 − σ)µeT (xs − µe) + (1 − σ)2 µ2 eT e ||xs − µe||2 + 2(1 − σ)µ(eT (xs) − µeT e) + (1 − σ 2 )µ2 n γ 2 µ2 + (1 − σ)2 µ2 n
(5)
A (4) tört számlálóját az (5) alapján, a nevez®jét pedig a 4.2.2 lemma alapján becsülve a következ®t kapjuk
||∆x∆s|| ≤ ( amibe behelyettesítve a σ =
ν 1− √ n
γ 2 + n(1 − σ)2 √ µ, 23 (1 − γ)
) képletet, következik az állítás.
4.2.4. Lemma. Ha (x, y, s) ∈ N2 (γ), ekkor minden α ∈ [0, 1] lépéshosszra ||x+ s+ − µ+ e|| ≤ (1 − α)||xs − µe|| + α2 ||∆x∆s||.
Biz.:
A 4.1.1 lemma ii) állítása és egyszer¶ számítás alapján
x+ s+ − µe = (x − α∆x)(s − α∆s) − (1 − α(1 − σ))µe = xs − α(s∆x + x∆s) + α2 ∆x∆s − (1 − α(1 − σ))µe = xs − α(xs − σµe) + α2 ∆x∆s − (1 − α + ασ)µe = (1 − α)(xs − µe) + α2 ∆x∆s,
amib®l következik az állítás. 27
4.3. Egy hosszú lépéses algoritmus Hosszú-lépéses algoritmusokról beszélünk, ha a σ a dimenziótól független konstans. A következ® algoritmusban a σ -t minden iterációnál egy [σmin , σmax ] intervallumból választjuk. Az el®z® algoritmussal ellentétben itt a b®vebb N−∞ (γ) környezetet használjuk, ami a csaknem a teljes F 0 -at jelenti, ha a γ közel van az 1-hez. Az α lépéshosszt a lehet® legnagyobbnak választjuk, ügyelve arra, hogy ne lépjünk ki a N−∞ (γ) környezetb®l. Hosszú-lépéses algoritmus
Input
γ ∈ (0, 1), σmin , σmax : 0 < σmin ≤ σmax < 1, ϵ > 0 pontossági paraméter, (x0 , y 0 , s0 ) ∈ N−∞ (γ).
begin
(x, y, s) := (x0 , y 0 , s0 ). while nµ > ε do µ := µ(x, s) Válasszunk σ ∈ [σmin , σmax ]. Határozzuk meg azt a (x, y, s)-beli (∆x, ∆y, ∆s) Newton-irányt, ami a σµ-centrumot közelíti. Legyen α ∈ (0, 1] az a legnagyobb érték, amire (x+ , y + , s+ ) ∈ N−∞ (γ). Legyen (x, y, s) = (x+ , y + , s) .
end end
Ahhoz, hogy a lépésszámról mondani tudjunk valamit, találni kellene egy a 4.2.1 következményhez hasonló összefüggést a µk és µ0 között. Ehhez két lemmára van szükségünk.
4.3.1. Lemma. Ha (x, y, s) ∈ N−∞ (γ), akkor: ( 2 1) nµ(x, s). ||∆x∆s|| ≤ 2− 3 1 + γ
Biz.:
A 4.2.3 lemmánál látottak alapján, és felhasználva, hogy xi si ≥ γµ és xT s =
nµ ||∆x∆s|| ≤ = = = ≤
√ 1 2−3 ||(XS)− 2 (xs − σµe)||2 √ 1 1 2−3 ||(XS)− 2 e − σµ(XS)− 2 e|| √ n ) 2−3 (xT s − 2σµn + σ 2 µ2 γµ √ 2 2−3 nµ(1 − 2σ + σγ ) √ 2−3 nµ(1 + γ1 , )
ami bizonyítja az állítást. 28
A következ® lemma egy α ¯ alsó korlátot ad a lépéshosszakra.
4.3.2. Lemma. Ha (0, α ¯ ] esetén, ahol
(x, y, s) ∈ N−∞ (γ), α ¯=
Biz.:
akkor (x+ , y + , s+ ) ∈ N−∞ (γ) minden α ∈
√ 1−γ 8γσ . n(1 + γ)
Az el®z® lemma alapján minden i-re
) ( √ 1 |∆xi ∆si | ≤ ||∆x∆s|| ≤ 2−3 nµ 1 + . γ
Felhasználva az el®z® egyenl®tlenséget, a Newton rendszer harmadik egyenletét, és azt, hogy xi si ≥ γµ
x+ s+ = xs − α(s∆x + x∆s) + α2 ∆x∆s ≥ xs(1 − α) + ασµe − α2 |∆x∆s| ( ) √ 1 2 ≥ γµe(1 − α) + ασµe − α 2−3 nµ 1 + e γ
(6)
Az állítás belátásához azt kell igazolnunk, hogy x+ s+ ≥ γµ+ e. Felhasználva, hogy µ+ = (1 − α(1 − σ))µ és a (6) becslést könnyen ellen®rizhet® az állítás.
4.3.1. Tétel. Létezik ν > 0 az n-t®l független konstans, amire ( ν) k µk+1 ≤ 1 − µ n
k = 1, 2, 3, . . .
Biz.:
A 4.1.1 lemma alapján µk+1 = (1 − α(1 − σ))µk . Kihasználva, hogy α ≥ α ¯ minden iterációban: √ ( ) 8 1−γ k+1 µ ≤ 1− γ σ(1 − σ) µk . (7) n 1+γ A σ → σ(1 − σ) függvény szigorúan konkáv, így
σ(1 − σ) ≥ min{σmin (1 − σmin ), σmax (1 − σmax )} ∀σ ∈ [σmin , σmax ]. Ha a 2
ν = 23 γ
1−γ min{σmin (1 − σmin ), σmax (1 − σmax )} > 0 1+γ
értéket behelyettesítjük az (7) egyenl®tlenségbe, akkor megkapjuk a bizonyítandó állítást.
4.3.2. Tétel. A hosszú lépéses algoritmus legfeljebb után ε-optimális megoldást ad. Biz.:
K =
⌈
log(nε−1 µ0 ) nν
⌉
iteráció
A 4.2.2 tételhez hasonlóan bizonyítható, az el®z® lemma felhasználásával. 29
4.4. Egy prediktor-korrektor algoritmus Prediktor-korrektor algoritmus
Input
ϵ > 0 pontossági paraméter, (x0 , y 0 , s0 ) ∈ N2 (γ).
begin
(x, y, s) := (x0 , y 0 , s0 ), µ := µ(x, s). while nµ > ε do PREDIKTOR lépés Határozzuk meg azt az (x, y, s)-beli (∆x, ∆y, ∆s) Newton-irányt, ami a 0-centrumot közelíti Legyen α ∈ (0, 1] az a legnagyobb érték, amire (x+ , y + , s+ ) ∈ N2 (¯ γ)
.
Legyen (x, y, s) = (x+ , y + , s+ ) és µ := (1 − α)µ. KORREKTOR lépés Határozzuk meg azt az (x, y, s)-beli (∆x, ∆y, ∆s) Newton-irányt, ami a µ-centrumot közelíti Legyen (x, y, s) = (x, y, s) − (∆x, ∆y, ∆s)
end end
Az algoritmus m¶ködését igazolják a következ® lemmák. A prediktor lépést a γ = és γ¯ = 21 esetben vizsgáljuk.
1 4
4.4.1. Lemma. Tegyük fel, hogy (x, y, s) ∈ N2 ( 14 ), és legyen (∆x, ∆y, ∆s) a prediktor lépésben kiszámított Newton-irány. Ekkor (x+ , y + , s+ ) ∈ N2 ( 12 ) minden α ∈ [0, α ¯ ]-ra, ahol { } α ¯ := min
Biz.:
1 1 µ ,( )2 . 2 8||∆x∆s||
A rövid lépéses algoritmusnál látottak alapján
||x+ s+ − µ+ e|| ≤ (1 − α)||xs − µe|| + α2 ||∆x∆s|| µ ||∆x∆s|| ≤ (1 − α)||xs − µe|| + 8||∆x∆s|| 1 µ ≤ (1 − α)µ + 4 8 1 1 ≤ (1 − α)µ + (1 − α)µ 4 4 1 + = µ , 2 ami épp azt jelenti, hogy (x+ , y + , s+ ) ∈ N2 ( 12 ). 30
4.4.1. Köv. A prediktor lépés legalább α¯ nagyságú és µ+ ≤ (1 − α¯ )µ.
A korrektor lépést általánosabban, a γ := γ¯ 2 esetén vizsgáljuk. √
4.4.2. Lemma. Tegyük fel, hogy (x, y, s) ∈ N2 (¯γ ) valamilyen γ¯ ∈ (0, √8−1 ], és le8 + + + gyen (∆x, ∆y, ∆s) a korrektor lépésben kiszámított Newton-irány. Ekkor (x , y , s ) ∈ N2 (¯ γ 2 ) és µ+ = µ. Biz.:
A 4.1.1 lemmát felhasználva azonnal adódik, hogy µ+ = µ. A 4.2.4 lemmát felhasználva pedig ||x+ s+ − µ+ e|| ≤ γ¯ 2 µ = γ¯ 2 µ+ ,
ami épp azt jelenti, hogy (x+ , y + , s+ ) ∈ N2 (¯ γ 2 ).
A 4.4.1 következmény, és a az α ¯ de níciója miatt könnyen felírhatunk egy a 4.3.1 tétel állításához hasonló formulát:
4.4.1. Állítás. Ha ν ≤ 1 − √12 , akkor µk+2 ≤ (1 − √νn )2 µk .
Az el®z® állítás és a 4.2.2 tétel alapján könnyen bizonyíthatjuk a következ®t:
4.4.1. Tétel. A prediktor-korrektor algoritmus legfeljebb K = ráció után ε-optimális megoldást ad.
⌈
log(nε−1 µ0 )
√ ⌉ n ν
ite
Az algoritmusok összehasonlítása A hosszú-lépéses algoritmusok elméletei lépésszáma elmarad a másik két verzióétól, a gyakorlatban azonban a hosszú-lépéses algoritmusok gyakran jobban teljesítenek. Nézzünk meg egy példát az algoritmusok szemléltetésére!
4.1. Példa. Legyen A = (1, 1, 1), b = 1 és c = (−2, 1, −3)T . A következ® feladatpárt kapjuk: −2x1 + x2 − 3x3 → min x1 + x2 + x3 = 1 (P ) x ≥ 0 y → max y + s 1 = −2 y + s2 = 1 (D) y + s3 = −3 s ≥ 0
Az OPT(µ) rendszer a következ® lesz: x1 + x2 + x3 y + s1 y + s2 y + s3 xi si 31
= = = = =
1 −2 1 −3 µ
A rövid lépéses algoritmus m¶ködése
A hosszú lépéses algoritmus m¶ködése
A prediktor-korrektor algoritmus m¶ködése
4.5. Pontos megoldás el®állítása Az el®z® fejezetekben tárgyalt algoritmusok segítségével olyan primál-duál megengedett megoldáspárt kaphatunk, ami tetsz®legesen közel van az optimális megoldáspárhoz. Ebben a fejezetben azt tárgyaljuk, hogy hogyan juthatunk el egy pontos megoldásig. Elevenítsük fel a következ® indexhalmazokat:
P ∗ = {i : xi > 0, valamely u ∈ FP∗ esetén} D∗ = {i : si > 0, valamely (y, s) ∈ FD∗ esetén} Az eddig tárgyaltak alapján P ∗ ∩ D∗ = ∅, és FP ̸= ∅, FD ̸= ∅ esetén P ∗ ∪ D∗ = {1, . . . , n}. Legyen (xk , y k , sk ) valamelyik fenti algoritmus k. iterációjában kiszámolt pont. Ekkor
P k = P(xk , sk ) := {j ∈ {1, . . . , n} : xkj ≥ skj } Dk = D(xk , sk ) := {1 . . . , n} \ P k . Legyen
ξP = min∗ {max{xj : x ∈ FP∗ }}, j∈P
ξD = min∗ {max{sj : (y, s) ∈ FD∗ }}, j∈D
és legyen
ξ = min(1, ξP , ξD ). A ξ -t az LP feladat kondíciószámának nevezzük. Az LP feladat tárigényének fels® korlátja az
L(A, b, c) =
m ∑ n ∑ (
m n ) ∑ ( ) ∑ ( ) (log2 (|aij |+1)+1 + log2 (|bi |+1)+1 + log2 (|cj |+1)+1
i=1 j=1
i=1
j=1
érték.
4.5.1. Állítás. Ha a LP feladat adatai racionálisak, akkor ξ ≥ 2−L . Biz.: 4.5.1. Tétel. Származzon az {xk , sk } pontsorozat egy olyan bels®pontos ) ( √ algoritmus0 0 ból, ami az x = e, s = e bels® pontból indul, az iterációszáma O( n log nε µ0 ) és kielégíti a következ® feltételeket k+1 T k+1
(x
) s
≤ (x ) s
k T k
Ekkor: 33
és
(1) mini xki ski ≥Ω . (xk )T sk n
(8)
∀ k.
i) 0 < eT xk + eT sk ≤ 2n, ii)
xkj ≥ Ω
és skj ≥ Ω iii)
(ξ ) n
(ξ ) n
,
skj ≤
(xk )T sk ξ
∀k
és ∀j ∈ P ∗
,
xkj ≤
(xk )T sk ξ
∀k
és ∀j ∈ D∗ .
ha (xk )T sk ≤ O( ξn ), akkor 2
(ξ ) skj < Ω ∀j ∈ P ∗ n
így
és Dk = D∗ .
Pk = P∗
Biz.: i)
(xk − x0 ) ∈ N (A),
így
(ξ ) xkj < Ω ∀j ∈ D∗ , n
és
(sk − s0 ) ∈ R(AT ),
0 = (xk − x0 )T (sk − s0 ) = (xk − e)T (sk − e),
amib®l
eT xk + eT sk = n + (xk )T sk ≤ 2n.
ii) Tetsz®leges (x∗ , s∗ ) optimális megoldásra (xk − x∗ )T (sk − s∗ ) = 0, amib®l ∑
xkj s∗j +
j∈D∗
tovább alakítva
∑
skj x∗j = (xk )T sk ,
j∈P ∗
∑ s∗j xkj skj ∑ x∗j skj xkj + = 1. k (xk )T sk k (xk )T sk s x j j ∗ ∗ j∈D j∈P
Így minden j ∈ P ∗ és (x∗ , s∗ ) optimális megoldás esetén
skj x∗j ≤ (xk )T sk
és
x∗j skj xkj ≤ 1. xkj (xk )T sk
Adott j ∈ P ∗ esetén legyen x∗ = arg max{xj : x ∈ FP∗ }. Használva a fenti eredményt, a ξ de nícióját és a (8) feltételeket, a következ®t kapjuk
skj ξ ≤ skj x∗j < (xk )T sk amib®l következik j ∈ D∗
ii)
és
x∗j ξ (xk )T sk ≤ < ≤ O(n), xkj xkj xkj skj
minden j ∈ P ∗ . Az állítás hasonlóan bizonyítható minden
iii) Egyenesen következik a második állításból. ( )
√
4.5.1. Köv. A (P k , Dk ) partíció O( n log nξ ) iteráció után az optimális partíciót √ adja. Ha az LP feladat adatai racionálisak, akkor ez O( nL) iterációt jelent. 34
4.5.2. Köv. Ha (xk )T sk = µk → 0, akkor az x és s "kicsi" változói egyenletesen tartanak a 0-hoz, a "nagy" változói pedig egy egyenletes alsó korláttal el vannak szeparálva a 0-tól. Az (xk , sk ) pontsorozat tehát egy szigorúan komplementáris megoldáshoz tart. 4.5.1. Lemma. A bemutatott bels®pontos algoritmusok által generált pontsorozatra teljesülnek a (8) feltételek. Biz.: Az els® feltétel teljesülése nyilvánvaló a 4.2.1 és 4.3.1 tételekb®l. A rövid lépéses algoritmusnál minden el®állított (xk , y k , sk ) pont benne van az N2 (γ) környezetben valamilyen γ konstansra, ezért érvényes lesz a következ® minden i-re: xT s xT s xT s xT s − xi si ≤ xi si − e ≤ γ . ≤ xs − n n n n A hosszú lépéses algoritmusnál minden el®állított pont az N−∞ (γ) környezetben lesz, így ebben az esetben minden i-re:
xT s xT s xT s − xi si ≤ xi si − . ≤γ n n n Mindkét esetben következik az
mini xki ski 1−γ ≥ . k T k (x ) s n
Optimális megoldás el®állítása mer®leges vetítéssel Az optimális partíció segítségével a következ® módon tudjuk felírni az optimális lapokat:
FP∗ = {x : Ax = b, x ≥ 0, xj = 0 ∀j ∈ D∗ } FD∗ = {(y, s) : AT y + s = c, s ≥ 0, sj = 0 ∀j ∈ P ∗ } Ha a feltételek közül elhagyjuk a nemnegativitást, akkor a n altereket kapunk. A pontos megoldást úgy akarjuk el®állítani, hogy a közelít® megoldást mer®legesen vetítjük ezekbe az a n alterekbe. Ha elég közel voltunk az optimális halmazhoz, akkor a vetület optimális lesz. A algoritmusunk a következ® módon fog m¶ködni: 1. futtatjuk valamelyik útkövet® algoritmusunkat néhány iteráció erejéig, így kapjuk az (xk , y k , sk ) ∈ F 0 pontot 2. kiszámítjuk a P k és Dk indexhalmazokat, mint becslést az optimális partícióra
35
3. megoldjuk az
||x∗ − xk || → min Ax∗ = b x∗i = 0 i ∈ Dk
(9)
||y ∗ − y k || → min AT y ∗ + s∗ = c s∗i = 0 i ∈ P k
(10)
és
rendszereket 4. ha a megoldásokra x∗i > 0 i ∈ P k és s∗i > 0 i ∈ Dk , akkor (x∗ , y ∗ , s∗ ) optimális megoldás 5. ha a pozitivitási feltételek nem teljesülnek, akkor visszatérünk az útkövet® algoritmushoz, végzünk még egy iterációt Optimális megoldás vetítéssel
Input(xk , yk , sk ) ∈ F 0 begin
meghatározzuk a P k és Dk halmazokat megoldjuk a (9) és (10) rendszereket if (x∗i > 0 ha i ∈ P k és s∗i > 0 ha i ∈ Dk ) az (x∗ , y ∗ , s∗ ) optimális megoldás
else end
az útkövet® algoritmus folytatása
36
than
5.
Duális módszerek
A következ® fejezetek célja, hogy megismerjük a volume algoritmust, ami egy önmagában is érdekes, primál-duál közelít® megoldáspárt adó módszer. Kedvez® számításigény¶, és sok esetben hatékonyan alkalmazható az ismertetésre kerül® bázis identi kációs eljárással. Tekintsük a következ® lineáris programot
min cT x Ax = b Dx = e x ≥ 0,
R
R
R
R
R
ahol c ∈ n , A ∈ m×n , b ∈ m , D ∈ d×n , e ∈ d és rang(D) = d. Úgy tekintjük, hogy az Ax = b feltételek nehezen kezelhet®ek, a Dx = e feltételek könnyen. Ekkor lehetséges megközelítés, hogy a Lagrange-relaxációból származó duális feladatot oldjuk meg. Két kérdés megválaszolása áll el®ttünk: 1. hogyan oldjuk meg a nemdierenciálható duális feladatot 2. hogyan állítunk el® egy primál megoldást A feladathoz tartozó Lagrange-függvény
L(x, π) = cT x + π T (Ax − b). A duális függvény ekkor
q(π) = min L(x, π), ahol M = {x ∈
x∈M
R |Dx = e, x ≥ 0}. n
A duális feladat a következ®
maxm q(π).
π∈
R
Miel®tt folytatnánk a feladat megoldását, megnézzük a duális módszereket általánosabb szituációban.
5.1. A szubgradiensek 5.1. Def. Legyen q : Rm → R konkáv függvény. Azt monjuk, hogy a szubgradiense q-nak a π-ben, ha q(π ′ ) ≤ q(π) + (π ′ − π)T v,
∀π ′ ∈
v ∈
Rm
w ∈
Rm
Rm.
A π-beli szubgradiensek halmazát ∂q(π)-vel jelöljük.
5.2. Def. Legyen q : Rm → R konkáv függvény. Azt monjuk, hogy a ε-szubgradiense q -nak a p-ben, ha q(π ′ ) ≤ q(p) + (π ′ − p)T w,
∀π ′ ∈
A p-beli ε-szubgradiensek halmazát ∂ε q(p)-vel jelöljük. 37
Rm .
5.1.1. Megjegyzés. A ∂ε q(p) hamaz szép folytonossági tulajdonságokkal rendelkezik. Ha (εt , pt , wt ∈ ∂ε q(pt )) → (ϵ∗ , p∗ , w∗ ), akkor w∗ ∈ ∂ε q(p∗ ). ∗
t
A következ® feladatból indulunk ki
min f (x) h(x) = 0 x ∈ M.
A hozzá tartozó Lagrange-függvény
L(x, π) = f (x) + π T h(x), és duális függvény
q(π) = inf L(x, π). x∈M
Legyen
xπ = arg min L(x, π). x∈M
5.1.1. Állítás. A fenti jelölésekkel a π helyen. Biz.:
Minden π ′ ∈
h(xπ )
a szubgradiense a duális függvénynek a
Rm-re egyszer¶ számolással adódik:
q(π ′ ) =
inf L(x, π ′ ) ≤ L(xπ , π ′ ) =
x∈M
= f (xπ ) + (π ′ )T h(xπ ) = = f (xπ ) + π T h(xπ ) + (π ′ − π)T h(xπ ) = = q(π) + (π ′ − π)T h(xpi ). Két algoritmust fogunk tárgyalni, ami a szubgradienseket használja. Az els® a szubgradiens módszer, ami minden iterációban az éppen aktuális szubgradienset használja. A második pedig a vágósíkos módszer, ami minden iterációban a korábban kiszámolt összes szubgradienset használja.
5.2. A szubgradiens módszer A szubgradiens módszer nagyon hasonlít a dierenciálható függvények esetében használható gradiens-módszerre. Lényeges eltérés, hogy a lépéshossz el®re rögzített, nem alkalmaz egyenes menti keresést minden iterációban. A gradiens módszerrel ellentétben a célfüggvény értéke növekedhet egy-egy lépés után. Azonban a módszer el®nye, hogy jóval egyszer¶bb és szélesebb körben alkalmazható. A következ® típusú feladatra alkalmazzuk a módszert
max q(π) π ∈ X 38
R
R
ahol q : m → [−∞, ∞) egy felülr®l féligfolytonos, konkáv függvény, X ⊆ m konvex és zárt halmaz. Ezek a feltételek a korábbiak alapján fennállnak a Lagrangeduális feladat esetén. és q lényeges tartományának minden pontjában könnyen ki tudunk számolni egy szubgradienst. A feladatot a q függvény D lényeges tartománya alapján a következ® formában is felírhatjuk: max q(π) π ∈ X ∩D
Megjegyzések: 1. A feltételek miatt valójában a vetített szubgradiens algoritmusra lesz szükség. 2. Ha q valós érték¶ függvény, és X = ∅, akkor nem kell vetíteni. 3. Valós érték¶ konkáv függvény automatikusan folytonos, így ha nem engedünk meg kiterjesztett érték¶ függvényeket, akkor elég a konkávitást feltenni. 4. Euklideszi vetítés alapvet®en konvex és zárt halmazokra m¶ködik. A q konkávitása és felülr®l féligfolytonossága biztosítja, hogy a D konvex és zárt halmaz legyen. Az X -re vonatkozó feltételek miatt pedig az X ∩ D is konvez és zárt lesz, azaz lehet bele vetíteni. A módszer a következ® iteráció alapján m¶ködik
µk+1 := [µk + αk hk ]+ , ahol [·]+ jelöli a mer®leges vetítést a konvex és zárt M := X ∩ D halmazba és hk a q függvény π k -beli szubgradiense. Mivel a célfüggvény az iterációk során nem monoton növekv®, ezért minden lépésben számontartjuk az eddigi legjobb értéket
q∗k = max{q∗k−1 , q(π k )}. Az esetleges célfüggvény csökkenés ellenére az teszi a módszert használhatóvá, hogy elég kicsi lépéshossz esetén közelebb kerülünk az optimális megoldás halmazhoz. Err®l szól a következ® állítás.
5.2.1. Állítás. Ha πk nemoptimális, akkor minden π∗ optimális megoldásra ||π k+1 − π ∗ || < ||π k − π ∗ ||,
minden olyan αk lépéshosszra, amire 0 < αk <
Biz.:
2(q(π ∗ ) − q(π k )) . ||hk ||2
||π k+1 − π ∗ || = ||[π k + αk hk ]+ − π ∗ || ≤ ||π k + αk hk − π ∗ ||, 39
(11)
ahol az utolsó egyenl®tlenség azért áll fenn, mert π ∗ ∈ M és a vetítés az nem növeli a távolságot. Tovább becsüljük a jobb oldalt:
||π k + αk hk − π ∗ ||2 = ||π k − π ∗ ||2 − 2αk (π ∗ − π k )T hk + (αk )2 ||hk ||2 . Használva a
(π ∗ − π k )T hk ≥ q(π ∗ ) − q(π k )
szubgradiens egyenl®tlenséget:
||π k + αk hk − π ∗ ||2 ≤ ≤ ||π k − π ∗ ||2 − 2αk (q(π ∗ ) − q(π k )) + (αk )2 ||hk ||2 . (12) Legyen
γk =
αk ||hk ||2 . q(π ∗ ) − q(π k )
A γ k segítségével a következ® formára hozhatjuk a (12) egyenl®tlenséget:
||π k + αk hk − π ∗ ||2 ≤ ||π k − π ∗ ||2 −
γ k (2 − γ k )(q(π ∗ ) − q(π k ))2 ||hk ||2
(13)
Ha az αk lépéshossz kielégíti a tételben megadott feltételt, akkor 0 < γ k < 2 teljesül. Így a (13) egyenl®tlenség alapján
||π k + αk hk − π ∗ || ≤ ||π k − π ∗ ||,
amivel kész a bizonyítás.
Használatos lépéshosszak Konstans lépés. αk = h, függetlenül a k -tól. Konstans lépéshossz. αk = h/||g k ||. Ekkor ||µk+1 − µk || = h. Négyzetesen összegezhet®, de nem összegezhet®. Vagyis a következ®ket elégítik ki ∞ ∞ ∑ ∑ 2 αk < ∞, αk = ∞. Tipikus példa az αk =
k=1 a , ahol b+k
k=1
a > 0 és b ≥ 0.
Nem összegezhet®, de nullsorozat. Vagyis kielégítik a következ®ket
lim αk = 0,
k→∞
Tipikus példa az αk =
√a , k
∞ ∑
αk = ∞.
k=1
ahol a > 0.
A szubgradiens algoritmusok konvergencia viselkedése egyel®re nem jól megértett, annak ellenére, hogy számos konvergencia tétel kapcsolódik hozzájuk. Sok esetben nagyon hatékonyan m¶ködik, annak ellenére, hogy nincs elméleti konvergencia; máskor éppen az ellenkez®je történik. 40
5.3. A vágósíkos módszer
Tekintsük újra az el®z® feladatot
max q(π) π ∈ M.
}
A vágósíkos eljárás a k. iterációban a következ® részfeladatot oldja meg } max Qk (π) π ∈ M, ahol Qk a q lineáris approximációja, amit az addig generált π k pontok és hk szubgradiensek segítségével készítünk el a következ® módon
Qk (π) = min{q(π 0 ) + (π − π 0 )T g 0 , . . . , q(π k−1 ) + (π − π k−1 )T g k−1 }, és
π k = arg max Qk (π). π∈M
A következ® állítás az algoritmus konvergenciájáról szól.
41
5.3.1. Állítás. Tegyük fel, hogy a (hk ) szubgradiens sorozat korlátos. Ekkor a (πk ) sorozat tetsz®leges határpontja optimális megoldás lesz. Biz.:
A hk szubgradiense a q -nak a π k -ban, azaz
q(π) ≤ q(π i ) + (π − π i )T hk ,
∀π ∈ M,
így a Qk és π k de níciója alapján
Qk (π k ) ≥ Qk (π) ≥ q(π) ∀π ∈ M.
(14)
Tegyük fel, hogy a {π k }K részsorozat a π ¯ -hoz konvergál. Mivel az M zárt, π ¯ ∈ M. Felhasználva (14) és a Qk és π k de nícióját minden k és i < k esetén
q(π i ) + (π k − π i )T hi ≥ Qk (π k ) ≥ Qk (¯ π ) ≥ q(¯ π ).
(15)
Határértéket fogunk venni i → ∞, k → ∞, i ∈ K , k ∈ K esetén. Kihasználjuk a q felülr®l féligfolytonosságát:
lim sup q(π i ) ≤ q(¯ π ),
(16)
i→∞,i∈K
és a {hk } sorozat korlátosságát:
lim (π k − π i )T hk = 0. i → ∞, k → ∞, i ∈ K, k ∈ K
(17)
Felhasználva az (15), (16) és (17) sorokat
q(¯ π ) ≥ lim sup Qk (π k ) ≥ lim inf Qk (π k ) ≥ q(¯ π ), k→∞,k∈K
k→∞,k∈K
azaz
lim
k→∞,k∈K
Qk (π k ) = q(¯ π ).
Az utóbbi eredményt kombinálva az (14) sorral kapjuk
q(¯ π ) ≥ q(π), ami mutatja, hogy a π ¯ optimális megoldás.
42
∀π ∈ M,
5.4. A volume algoritmus
A szubgradiens algoritmus sok esetben jó közelítést ad a duál feladat megoldására, de primál megoldást nem állít el®. A volume algoritmus kiterjeszti a szubgradiens módszert, hogy orvosolja ezt a hiányosságot. Az algoritmus m¶ködése a következ® tételen alapszik:
5.4.1. Tétel. Tekintsük a következ® lineáris programot max z z + aTi π ≤ bi i = 1, . . . m
Ahol z ∈ R, π ∈ Rn−1 . A feladat duálisa a következ®
}
min λ y n ∑ λi = 1 T
i=1
n ∑
λi a i = 0 i=1 λ ≥ 0.
Legyen (z ∗ , π ∗ ) a primál feladat optimális megoldása, és tegyük fel, hogy a (z ∗ , π ∗ ) pontban az 1, 2, . . . , m′ egyenl®tlenségek aktívak. Legyen z¯ < z ∗ , és tegyük fel, hogy a következ® poliéder korlátos z + aTi π ≤ bi i = 1, . . . m′ z ≥ z¯. 43
}
P
Legyen γi az a térfogat, amit a z + aTi π ≤ bi lap és a z = z¯ hipersík határoz meg (ilyen térfogatok láthatóak az ábrán). Ekkor az optimális duális megoldás a következ® módon kapható meg: γi λi = ∑m′
j=1 γj
.
Biz.:
A tétel kimondása során de niált P poliéder egy teljes dimenziós politóp. Legyen F0 P -nek a z ≥ z¯ egyenl®tlenség által de niált lapja, Fi pedig a a z + aTi π ≤ bi által de niált. Gauss-Osztrogradszkij tétele szerint, ha P egy korlátos és zárt tartomány, aminek a határa egy szakaszonként folytonosan dierenciálható irányítható S felület, akkor tetsz®leges v vektorra ∫ v T n dS = 0, (18) S
ahol az n az S felület egységnormális mez®je. Ha alkalmazzuk a tételt a v = ej j = 1, 2, . . . , n esetben, akkor a következ®t kapjuk ∫ n dS = 0, S
ahol a jobb oldalon a csupa 0 vektor áll. A P politóp egységnormális mez®jét ismerjük, ez alapján átírva az utóbbi egyenletet ′
m ∑ i=1
δi
(1, ai ) − δ0 (1, 0, . . . , 0) = 0, ||(1, ai )||
ahol a δi jelöli az Fi lap területét. Átrendezve ′
(1, 0, . . . , 0) =
m ∑ i=1
δi (1, ai ). δ0 ||(1, ai )||
Ebb®l kiolvasható a duális feladat megoldása: δi , i = 1, . . . , m′ δ ||(1, a )|| 0 i λi = 0, különben.
δi , ahol C egy konstans. ||(1, ai )|| Ha δi = 0, akkor γi = 0, így feltehet®, hogy δi > 0. A Gauss-Osztrogradszkij tételt, vagyis a (18) formulát szeretnénk újra alkalmazni. Legyen Qi a konvex burka az Fi lapnak és a (¯ z , π ∗ ) pontnak. Ekkor vol(Qi ) = γi . Legyen F¯0 = F0 ∩ Qi . A Qi politóp F¯0 -tól és Fi -t®l különböz® lapjait olyan egyenl®tlenségek határozzák meg, ahol hiányzik a z , vagyis ezeknek a lapoknak a normálisa mer®leges a z tengelyre. A következ®kben belátjuk, hogy γi = C
Alkalmazzuk a 18 formulát a Qi politópra. Ha v = ei , akkor a v T n szorzat csak az Fi és az F¯0 lapok esetén ad 0-tól különböz® értéket. Ezt kihasználva
δi
(1, ai ) + Ai (1, 0, . . . , 0) = 0, ||(1, ai )|| 44
ahol Ai az F¯i lap területe. Ebb®l kapjuk:
Ai =
δi . ||(1, ai )||
Legyen h = z ∗ − z¯, ekkor a
γi = vol(Qi ) = Mivel δ0 =
∑
Ai h 1 δi = h . 2 2 ||(1, ai )||
Aj , felírhatjuk a következ®t: λi =
δi Ai γi =∑ =∑ , δ0 ||(1, ai )|| Aj γj
amivel készen vagyunk. Térjünk vissza a megoldandó feladathoz: min cT x min cT x Ax = b ⇐⇒ Ax = b Dx = e x ∈ M x ≥ 0,
A Lagrange-relaxáltját szeretnénk megoldani a volume-módszerrel. Minden olyan módszer, ami nemdierenciálható függvényt optimalizál, felhasznál egy orákulumot. Az orákulum egy adott π -re megadja a q(π) értéket, és ad egy π -beli szubgradienst. A mi esetünkben az orákulum feladata kiszámolni a
q(π) = min L(x, π) = min(cT x + π T (Ax − b)) x∈M
x∈M
(19)
értéket, és az
xπ = arg min L(x, π) x∈M
pontot. Korábban láttuk, hogy ekkor a v = h(xπ ) = Axπ −b vektor szubgradiense lesz a q -nak a π pontban, azaz a szubgradiens kiszámítása már nem id®igényes. Az 19 részfeladat megoldásának nehézsége az M halmazt de niáló feltételeken múlik. Minél könnyebb megoldani ezt a részfeladatot, annál jobban m¶ködik a duális megközelítés. A volume-algoritmus a következ® dolgokat generálja: πt alappontok π ˆk "stabil centrumok", ami a πt alappontok egy olyan részsorozata, ami elég jó el®rehaladást biztosít az optimalizálás során a következ® πt alappontot az aktuális stabil centrumból, és egy bizonyos wt irányú és st hosszúságú lépés alapján kapjuk
45
zt a primál megoldás approximációja, a korábbi primál pontok konvex kombinációjaként kapjuk, ugyanazokkal az együtthatókkal, amelyekkel a wt -t számítjuk a korábbi szubgradiensekb®l Volume-algoritmus
Input π0 ∈
Rn kezd® duális alappont.
Inicializálás
Megoldjuk a 19 részfeladatot, x0 ∈ arg min L(x, π0 ). v0 := Ax0 − b, z1 := x0 , w1 := v0 és π ˆ1 := π0 . k = t = 1 és T := ∅.
begin loop
Teszünk egy duális lépést: πt = π ˆk + st wt . Megoldjuk a 19 részfeladatot, xt ∈ arg min L(x, πt ). vt := Axt − b. if (q(πt ) > q(ˆπk ) és ⟨wt , vt ⟩) π ˆk+1 := πt , tk := t, T := T ∪ {tk }, k := k + 1. Kiszámítjuk az st+1 lépéshosszat. Adott 0 ≤ αt ≤ 1 paraméterre legyen
zt+1 = αt xt + (1 − αt )zt , wt+1 = αt vt + (1 − αt )wt , t := t + 1.
end end
U B − q(π )
t 5.4.1. Megjegyzés. A [8] cikkben az st = µ lépéshosszt javasolják, ahol ||wt ||2 U B egy fels® korlát az optimumra és µ ∈ (0, 2) egy paraméter, de más lehet®ségek is vannak.
Néhány összefüggés 5.4.1. Lemma. Legyen {zt }, {vt } és {wt } a volume-algoritmus által generált sorozat. Ekkor vt ∈ ∂q(πt ) és wt = Azt − b.
5.4.2. Lemma. Minden t ≥ 1 esetén vezettük be a következ® együtthatókat t ∏
µt,j := αt−j
(1 − αi ) j = 0, 1, . . . , t,
i=t−j+1
ahol α0 := 1 és if < i0 esetén
if ∏
(1 − αi ) := 1.
i=i0
46
Ekkor:
i) Minden j ≤ t esetén µt,j ≥ 0 és
t ∑
µt,j = 1.
j=0
ii) zt+1 =
t ∑
µt,j xt−j
j=0
és wt+1 =
t ∑
µt,j vt−j .
j=0
Biz.: i) Az αt ∈ [0, 1] miatt a µt,j nemnegativitása nyilvánvaló. Az összegük vizsgálatához t ∑
µt,j = αt 1 + αt−1 (1 − αt ) + αt−2 (q − αt )(1 − αt−1 + . . . )
j=0
= αt + (1 − αt )[αt−1 + (1 − αt−1 )(αt−2 + (1 − αt−2 )(. . . (1 − α2 )(α1 + 1 − α1 ) . . . ))] = αt + (1 − αt )[αt−1 + (1 − αt−1 )(αt−2 + (1 − αt−2 )1)] = αt + (1 − αt )[αt−1 + (1 − αt−1 )1] = 1
ii) Felhasználva az i) állítást és a zt+1 , wt+1 de nícióját indukcióval könnyen követ
kezik.
A következ® tétel arról szól, hogy a wt egy ε-szubgradiense a q függvénynek a pt pontban, ahol a pt -t a következ® rekurzív formulával kapjuk
p1 := π0 pt+1 := αt πt + (1 − αt )pt , vagy ekvivalensen
pt+1 :=
t ∑
µt,j πt−j .
j=0
5.4.2. Tétel.
ε1 := 0
és minden t ≥ 1 esetén legyen
εt = αt (1 − αt )⟨vt − wt , pt − πt ⟩ + (1 − αt )εt .
Ekkor
Biz.:
εt ≥ 0
és wt ∈ ∂εt q(pt ).
t = 1 esetén w1 = v0 = Ax0 − b ∈ ∂q(π0 ) = ∂ε1 q(π0 ) = ∂ε1 q(p1 )
Tegyük fel, hogy az állítás igaz a t ≥ 1 esetén. Ekkor kihasználva a wt ∈ ∂εt q(pt ) és vt ∈ ∂q (πt ) összefüggéseket minden π ′ ∈ m esetén
R
q(π ′ ) ≤ q(πt ) + (π ′ − πt )T vt q(π ′ ) ≤ q(pt ) + (π ′ − pt )T wt + εt 47
(20) (21)
Véve az αt · (20) + (1 − αt ) · (21) konvex kombinációt, és kihasználva a q konkávitását és a pt de nícióját, a következ®t állíthatjuk minden π ′ ∈ m esetén
R
q(π ′ ) ≤ q(pt+1 ) + ⟨wt+1 , π ′ ⟩ − ⟨αt vt , πt ⟩ − ⟨(1 − αt )wt , pt ⟩ + (1 − αt )εt . Az εt+1 de nícióját kihasználva a következ® alakra hozhatjuk
q(π ′ ) ≤ q(pt+1 ) + (π ′ − pt+1 )T wt+1 + εt+1 , ami éppen azt jelenti, hogy wt+1 ∈ ∂εt+1 q(pt+1 ), azaz az állítás örökl®dik. Kihasználva a vt ∈ ∂q(πt ) és wt ∈ ∂εt q(pt ) tényeket, a következ® becslést kapjuk
εt+1 ≥ −αt (1 − αt )εt + (1 − αt )εt = (1 − αt )2 εt , azaz az εt ≥ 0 is teljesül.
48
6.
Optimális bázismegoldás el®állítása
Ebben a fejezetben egy bázis identi kációs eljárást (röviden BIP ) tekintünk át, Megiddo [11] algoritmusára támaszkodva, ami er®sen polinomiális id®ben állít el® egy optimális bázismegoldást, egy adott primál-duál komplementáris megoldáspárból indulva. A BIP olyan LP megoldó módszerekkel együtt alkalmazható, ami egyszerre állít el® primál és duál közelít® megoldást. Egy (xk , sk ) jó közelít® megoldáspár "kevéssé" sérti csak a komplementaritási feltételeket. A BIP a következ® módon m¶ködik: 1. Perturbáljuk az LP -feladatot, megkapva az LP k feladatot, majd kerekítjük az (xk , sk ) közelít® megoldást, hogy az LP k -nak komplementáris megoldáspárja legyen. 2. A perturbált feladatra alkalmazzuk Megiddo algoritmusát: (a) Keresünk egy kezd® bázist. (b) Pivotálással eljutunk egy primál optimális bázishoz. (c) További pivotálással eljutunk egy optimális bázishoz, Bk -hoz. (d) Ellen®rizzük, hogy a Bk bázis optimális-e az eredeti LP -feladatra. Azt reméljük, hogy ha a k. iterációban kapott (xk , sk ) pont elég közel van az optimális laphoz, akkor az LP k probléma B k optimális bázisa egyben az eredeti LP -feladat optimális bázisa is.
6.1. A perturbált feladat Jelöljük (B, N )-nel a változók felbontását bázis és nem bázis változókra, legyenek AB és AN az A mátrix megfelel® részmátrixai. A B pontosan akkor optimális bázis, ha AB nemszinguláris, xB = A−1 B b ≥ 0, és
y = A−T B cB ,
sN = cN − ATN y ≥ 0.
Ha az LP -feladat megengedett és korlátos, akkor létezik optimális bázismegoldása. Egy bázismegoldás primál degenerált, ha az xB -nek van 0 komponense, duál degenerált, ha az sN -nek van 0 komponense. Tegyük fel, hogy egy primál-duál közelít® megoldást adó algoritmus generálja az (xk , y k , sk ) pontsorozatot és a (P k , Dk ) partíciósorozatot.
min(ck )T x Ax = bk , (LP k ) x ≥ 0, ahol
bk = P k xkP k ,
ckP k = (P k )T y k , 49
ckDk = (Dk )T y k + skDk .
6.1.1. Állítás. Az x = (xkP , 0) és (y, s) = (yk , (0, skD táris megoldása az LP k feladatnak. k
Biz.:
k
))
egy szigorúan komplemen
Ellen®rzés.
Bázis identi káció bels®pontos algoritmus segítségével Az LP k feladatra a P k , Dk adja az optimális partíciót, így a 4.5.1 tétel alapján bizonyos számú iteráció után az LP k és LP feladatokra megegyezik az optimális partíció. Tegyük fel, hogy a k -ra már (P k , Dk ) = (P ∗ , D∗ ). Felhasználva a 4.5.1 tételt kapjuk:
||bk − b|| = ||Dk xkDk || = ||
∑
skj aj || ≤
j∈Dk
(xk )T sk ∑ (xk )T sk ||xj || ≤ η, ξ n k
(22)
j∈D
és
||ck − c|| = ||skP k || ≤
(xk )T sk (xk )T sk √ ||e|| = n, ξ ξ
(23)
amib®l látszik, hogy (xk )T sk → 0 esetén bk → b és ck → c. Továbbá ha
{ ( ξ2 ) } ξ −t nη (x ) s ≤ min O ,2 , n k T k
akkor
(P k , Dk ) = (P ∗ , D∗ ),
||bk − b|| ≤ 2−t ,
||ck − c|| ≤ 2−t .
6.1.1. Megjegyzés. Ha általában tekintünk egy LP (A, b, c) feladatot, és egy LP (A, bk , ck ) feladatrendszert, amire bk → b és ck → c, akkor nem mondhatjuk el, hogy elég nagy k -ra meg fog egyezni az LP és LP k optimális partíciója. √
6.1.1. Tétel. Tegyük fel, hogy az (xk , yk , sk ) pontsorozat egy O( nL)-es bels®pontos algoritmusból származik. Legyen B az LP k feladat optimális bázisa. Ekkor létezik 0 < t¯ < ∞, amire (xk )T sk < 2−t¯ esetén B az eredeti LP feladat optimális bázisa is. Ha az LP -feladat racionális, akkor t¯ ≤ O(L). Biz.:
Legyen B tetsz®leges bázisa az A mátrixnak, amire AB x ¯B = b és ATB y¯ = cB . Legyen τB az x ¯B és s¯ = c − AT y¯ legkisebb pozitív abszolút érték¶ komponense. Legyen τ = min{1, min(τB )}. Ekkor a τ > 0, mert az A mátrixnak véges sok B
bázisa van. Legyen ζ = max{1, max{||A−1 B ||}}. Ha az LP (A, b, c) feladat adatai B
racionálisak, akkor τ ≤ 2−L és ζ ≤ 2L . El®ször a következ® lemmát bizonyítjuk.
6.1.1. Lemma. Legyen B optimális bázisa az LP (A, bk , ck ) feladatnak, ahol ||bk − τ . Ekkor B az LP (A, b, c) feladat optimális bázisa is, azaz a b|| < τζ és ||ck − c|| < ηζ B -hez tartozó x¯B és s¯ nemnegatív.
50
Biz.:
Legyen az LP k feladat B -hez tartozó primál és duál optimális bázimegoldása és (¯ y k , s¯k ). Tegyük fel, hogy az x¯B -nek van negatív komponense, az i. komponens. Ekkor a τ de níciója miatt x ¯i ≤ −τ . Tudjuk, hogy
x¯kB
k x¯kB − x¯B = A−1 B (b − b),
azaz
−1 k k ||¯ xkB − x¯B || = ||A−1 B (b − b)|| ≤ ||AB || · ||b − b||.
A legutóbbi egyenl®tlenségb®l k |¯ xki − x¯i | ≤ ||A−1 B || · ||b − b|| < τ,
azaz
x¯ki < τ + x¯i ≤ τ − τ = 0,
ami ellentmond annak, hogy x ¯kB ≥ 0. Az s¯B nemnegativitása hasonlóan jön ki. Tegyük fel, hogy s¯j negatív. Ekkor s¯j ≤ −τ is teljesül.
−1 k T k |¯ skj − s¯j | = |aTj (¯ y k − y¯)| ≤ |aTj A−T B (cB − cB )| ≤ ||aj || · ||AB || · ||c − c|| < τ,
azaz
s¯kj < τ + s¯j ≤ τ − τ = 0,
ami szintén ellentmondás. A tétel belátásához úgy kell megválasztanunk a t¯-t, hogy
(P k , Dk ) = (P ∗ , D∗ ) és
||bk − b|| <
τ , ζ
||ck − c|| <
τ . ηζ
A (22) és (23) sorok alapján ez teljesül, ha
2
−t¯
{ ( ξ 2 ) ξτ } ≤ min O , . n nηζ
Ha az LP (A, b, c) feladat adatai racionálisak, akkor t¯ ≤ O(L).
6.1.1. Köv. Származzon az {xk , sk } pontsorozat egy olyan bels®pontos algoritmus√ 0 0 ból, ami az x = e, s = e bels® pontból√ indul, az iterációszáma O( nL) és kielégíti a (8) feltételeket. Ekkor legfeljebb O( nL) iteráció után az LP k feladat optimális bázisa megegyezik az eredeti LP feladat optimális bázisával.
51
Bázis identi káció A következ® részben megnézzük Megiddo [11] algoritmusát, ami az LP (A, bk , ck ) feladat optimális bázisát állítja el®, az ismert komplementáris megoldáspárból. A korábbi eredményeket felhasználva, a következ®ket tesszük fel az LP k feladatról: (1) A P k , Dk optimális partíció ismert. (2) Ismert az x ˜ primál optimális megoldás, amire A˜ x = bk , x˜Dk = 0 és x˜P k > 0. (3) Ismert az (˜ y , s˜) duális optimális megoldás, amire AT y˜ + s˜ = ck , s˜Dk > 0 és s˜P k = 0. Az egyszer¶ség kedvéért a következ®kben elhagyjuk a k indexet. Legyen a (B, N ) a változók tetsz®leges bázis-nembázis partíciója. Ekkor
x˜B = A−1 ˜N ). B (b − AN x Az (˜ xB , x˜N ) megoldást primál szuper-bázismegoldásnak nevezhetjük, hiszen vannak olyan nembázis váltózói amik nem nullák. Ha xi > 0 egy i ∈ N indexre, akkor az i egy primál szuper-bázisváltozó. Hasonlóan ha si > 0 egy i ∈ B indexre, akkor az i egy duális szuper-bázisváltozó. A cél a szuper-bázisváltozók kiküszöbölése. El®ször azonban szükségünk van egy kezd® bázisra.
6.2. Kezd® bázis el®állítása Legyen az [A1 , A2 , A3 ] az A mátrix következ® indexhalmazokhoz tartozó partíciója:
I1 = {i|˜ xi > 0, s˜i = 0} I2 = {i|˜ xi = 0, s˜i = 0} I3 = {i|˜ xi = 0, s˜i > 0} Kezd® bázis keresés
Input
A = [A1 , A2 , A3 ] mátrix a fenti partícióval, A ∈
Output
Rm×n, rang(A) = m.
AB kezd® bázis.
begin
A′ := [ ], AB := [ ], i := 1. while rang(AB ) < m do A′ := A′ ∪ Ai . while rang(AB ) < rang(A′ ) do Keresünk egy aj A′ -beli oszlopot, ami független a AB -t®l. AB := AB ∪ aj .
end
i := i + 1.
end end
52
Ha a AB -hez az algoritmus sorrendjében vesszük hozzá az oszlopokat, akkor nyilvánvalóan egy olyan kezd® bázist kapunk, amiben minimális a szuper-bázisváltozók száma. Ha a primál és duál szuper-bázisváltozókat x ˜+ ˜+ B jelöli, akkor a következ® N és s formájú kezd® pivottáblát kapjuk: Kezd® bázis struktúra
x˜+ B
x˜+ N
x˜0B
x˜0N
x˜0B
x˜0N
s˜0B
s˜0N
s˜0B
s˜0N
s˜+ B
s˜+ N
I 0 0
∗ 0 0
0 I 0
∗ ∗ 0
0 0 I
∗ ∗ ∗
Miel®tt folytatnánk a bázis identi káció folyamatát, fel kell elevenítenünk a bázistáblák egy fontos tulajdonságát. Az aktuális B bázishoz tartozó bázistábla a következ® módon néz ki:
B
B
N
I
A−1 B AN
Legyen a tábla i ∈ B , j ∈ N indexekhez tartozó eleme a tij . De niálunk két típusú vektort: minden i ∈ B -re a t(i) vektort és minden j ∈ N -re a tj vektort.
(i)
tk
tik 1 = 0
ha k ∈ N ha k = i különben
és
tkj −1 (tj )k = 0
6.2.1. Tétel. Biz.:
tj ⊥ t(i)
ha k ∈ B ha k = j különben
minden i ∈ B, j ∈ N esetén.
Könnyen adódik a vektorok de níciójából:
t(i)
B N i j = 0 . . . 0 1 0 . . . 0 ∗ · · · ∗ tij ∗ · · · ∗
tj = ∗ · · · ∗ tij ∗ · · · ∗ 0 . . . 0 −1 0 . . . 0 53
6.3. Primál fázis Az algoritmus a korábban el®állított kezd® bázisból indul. A primál szuper-bázisváltozókat úgy lehet eltüntetni, ha nullára csökkentjük az értéküket, vagy bevisszük ®ket a bázisba. Ezt végzi el a következ® algoritmus. Megiddo - primál fázis
Input
(˜ x, y˜, s˜) komplementáris megoldáspár, AB kezd® bázis.
Output
AB∗ primál optimális bázis, és a hozzá tartozó xP bázismegoldás.
begin
xP := x˜, B∗ := B , N ∗ := N . J + := {j ∈ N ∗ |0 < xPj }. while |J + | > 0 do Legyen j ∈ J + . Készítsük el a tj vektort. α := min P
x :=
for each k ∈ arg min i if (k ∈ B∗ ) end
{ xP i
|tji |
{ xP
} : tji < 0 ,
i
|tji | xP + αtj . }
: tji < 0
do
Pivotálás a (k, q) pozícióban, amire a tkq ̸= 0.
J + := J + − j.
end end
6.3.1. Tétel. A primál fázis er®sen polinomiális id®ben el®állít egy primál bázismegoldás.
xP
optimális
Biz.:
Az algoritmus minden iterációjában J + számossága legalább eggyel csökken. Így a pivotlépések száma legfeljebb a kiinduló megoldás szuper-bázisváltozóinak száma, ami azt jelenti, hogy az algoritmus er®sen polinomiális. Az (xP , s) megengedett, és komplementáris megoldáspárból indul az algoritmus. Belátjuk, hogy ez végig fennmarad, amivel az optimalitás bizonyítást nyer.
Megengedettség:
Az 6.2.1 tétel alapján a tj vektor mer®leges az A mátrix sorterére. Ezt felhasználva:
A(xP + αtj ) = AxP + αAtj = b + 0 = b A hányadosteszt miatt pedig 0 ≤ xP + αtj is teljesül.
Komplementaritás:
Azt kell belátni, hogy a tj ⊥ s. Ez a tj de níciója, és a kezd® bázishoz tartozó bázistábla alapján könnyen látható. Mivel a j primál szuperbázisváltozó, ezért a tj vektor kizárólag az x ˜+ N -nek megfelel® oszlopokból készülhet. 54
A tj nemnulla elemei a kezd® bázis struktúrából leolvashatóan az s˜0B résznek felelnek meg. A kezd® bázisnak megfelel® strutúra az algoritmus során végig fennáll. A végén nem lesz primál szuper-bázisváltozó, azaz primál bázismegoldást kapunk.
6.3.1. Megjegyzés. A primál fázis során, ha a kezd® bázis duál megengedett, akkor az algoritmus során végig az marad.
6.4. Duál fázis Megiddo - duál fázis
Input
(˜ x, y˜, s˜) komplementáris megoldáspár, AB kezd® bázis.
Output
AB∗ duál optimális bázis, és a hozzá tartozó (y D , sD ) bázismegoldás.
begin
sD := s˜, y D := y˜, B ∗ := B, N ∗ := N . J + := {j ∈ B ∗ |0 < sD j }. while |J + | > 0 do Legyen j ∈ J + . Keressük meg azt az i-t, amire (A−1 B∗ A)ij = 1. Készítsük el a t(i) vektort. α := min
{ sD
j (i) tj
sD − αt(i) y D + αA−T B ∗ ei .
sD := y D :=
for each k ∈ arg min j if end
} (i) : sD > 0, t > 0 , j
{ sD
j (i) tj
:
sD j
> 0, t
(i)
} >0
(24)
do
(k ∈ / B∗ ) Pivotálás a (k, q) pozícióban, amire a tkq ̸= 0.
J + := J + − j.
end end
6.4.1. Tétel. A duál fázis er®sen polinomiális id®ben el®állít egy (yD , sD ) optimális duális bázismegoldást. Biz.:
Csakúgy, mint a primál fázisnál, a J + elemszáma minden iteráció után legalább eggyel csökken, azaz az algoritmus er®sen polinomiális, legfeljebb |J + | pivotlépéssel. Belátjuk, hogy az (y D , sD ) végig megengedett megoldás és az (x, sD ) végig komplementáris, amivel az otimalitás bizonyítást nyer. 55
Megengedettség: pésben.
Az sD nemnegativitását a hányadosteszt biztosítja minden lé-
T (i) D (i) T −T (i) AT (y D +α(A−T = c+α((A−1 B∗ A) ei −t ) = c B∗ )ei )+(s −αt ) = c+α(A AB∗ )ei −αt T Az utolsó egyenl®ségnél kihasználtuk, hogy t(i) = (A−1 B∗ A) ei .
Komplementaritás:
A komplementaritáshoz azt kell látni, hogy t(i) ⊥ x, ami a kezd® bázis struktúrából kiolvasható.
Mivel a végén nem marad duális szuper-bázisváltozó, ezért a kapott megoldás bázismegoldás.
6.4.1. Megjegyzés. A duál fázis során, ha a kezd® bázis primál megengedett, akkor az algoritmus során végig az marad. A primál és duál fázisok egymástól függetlenek, bármelyikkel lehet kezdeni. Összességében egy optimális bázis eléréséig legfeljebb annyi pivotiterációra van szükség, mint amennyi a primál és duál szuper-bázisváltozók összáma a kezd® bázisra vonatkozóan.
56
Hivatkozások [1] David G. Luenberg, Yinyu Ye: 2008. [2] Dimitri P. Bertsekas:
Linear and Nonlinear Programming, Springer,
Nonlinear programming, Athena Scienti c, 1999.
[3] B. T. Polyak: Newton's method and its use in optimization, European Journal of Operational Research, 181: 1086-1096, 2007. [4] R. D. C. Monteiro, I. Adler: Interior path following primal-dual algorithms. Part I: Linear Programming, Mathematical Programming, 44: 27-41, 1989. [5] Julia Vogt: Primal-Dual Path-Following Methods for Linear Optimization, Diploma Thesis, University of Konstanz, 2008. [6] Margaréta Halická: Two simple proofs for analyticity of the central linear programming, Operation Research Letters 28: 9-19, 2001. [7] S. Mizuno, M. J. Todd, and Y. Ye:
path in
On adaptive-step primal-dual interior-
point algorithms for linear programming, Mathematics of Operations Research, Vol. 18, No. 4, 964-981, 1993.
[8] Francisco Barahona, Ranga Anbil: The Volume Algorithm: producing primal solutions with a subgradient method, Mathematical Programming, 87: 385-399, 2000. [9] L. Bahiense, N. Maculan, C. Sagastizábal: The volume algorithm revisited: relation with bundle methods, Mathematical Programming, 94: 41-69, 2002. [10] Y. Ye: On the nite convergence of interior-point algorithms for linear programming, Mathematical Programming, 57: 325-335, 1992. [11] N. Megiddo: On nding primalComputing, 3(1): 63-65, 1991.
and dual-optimal bases, ORSA Journal on
[12] Erling D. Andersen, Yinyu Ye: Combining interior-point and pivoting algorithms for linear programming, Management Science, 42:1719-1731, 1996.
On exploiting problem structure in a basis identi cation procedure for linear programming, Technical report, Odense University, Den-
[13] Erling D. Andersen: mark, 1996.
57
