Optimaliz´ al´ asi elj´ ar´ asok MSc hallgat´ ok sz´ am´ ara
1. El˝oad´as: Az alapfeladat El˝oad´o: Hajnal P´eter
2015. tavasz
Az optimaliz´al´as a matematika legk¨ ul¨onf´el´ebb ter¨ uleteinek tal´alkoz´asi pontja, ez´ert p´eld´aul a folytonoss´ag fogalm´ara ´ep¨ ul˝o analitikus meggondol´asok ´es diszkr´et matematikai m´odszerek egyar´ant r´eszei az optimaliz´al´asi appar´atusnak. Heterog´en jelleg´et jelzi, hogy a megannyi term´eszettudom´anyos, k¨ozgazdas´agi ´es informatikai alkalmaz´as, melyek alapj´at optimaliz´al´asi eredm´enyek k´epezik. Az optimaliz´al´as ter¨ ult´en el´ert ´att¨or´esek – a sz´elesk¨or˝ u alL.V. Kantorovics kalmaz´ asnak k¨osz¨onhet˝oen – komoly tudom´anyos elismer´essel (1912-1986) j´arnak. Kantorovics (szovjet matematikus) az optim´alis er˝oforr´as-allok´aci´oval kapcsolatos eredm´enyei´ert k¨ozgazdas´agi Nobel-d´ıjat kapott 1975-ben.1
1. Az optimaliz´ al´ as alapfeladata ´ es alapfogalmai Ebben a pontban megfogalmazzuk az optimaliz´al´as alapfeladat´at ´es bevezetj¨ uk az alapvet˝o fogalmakat, elnevez´eseket. Legyen c : dom (c) ⊆ Rn → R egy adott n-v´altoz´os val´os f¨ uggv´eny (n ∈ N), melyet c´ elf¨ uggv´ enynek nevez¨ unk. A dom (c) ´ertelmez´esi tartom´any egy ´altal´anos elem´ere az x = (x1 , . . . , xn )T jel¨ol´est haszn´aljuk2 . Az optimaliz´al´as alapfeladata a c c´elf¨ uggv´eny minimaliz´al´asa, el˝ore kiszabott felt´etelek mellett. Erre a tov´abbiakban az al´abbi r¨ovid´ıtett ´ır´asm´odot haszn´aljuk: Minimaliz´aljuk felt´eve, hogy
c(x)-et x ∈ F,
ahol x ∈ dom (c) ´es F ⊆ Rn a felt´etelek ´altal meghat´arozott tartom´any. Maguk a kik¨ot´esek elt´er˝o eredet˝ uek lehetnek: formaliz´alhatnak matematikai felt´eteleket vagy sz´armazhatnak fizikai, gazdas´agi k´enyszerekb˝ol. A felt´etelek el˝o´ır´as´ara is t¨obbf´ele lehet˝os´eg l´etezik. Itt kett˝o megad´asi m´odot eml´ıt¨ unk: • Implicit felt´ etelek. Adott x ∈ Rn elemr˝ol egy algoritmus/or´akulum/szubrutin eld¨onti, hogy teljes´ıti-e a felt´eteleket: x ⇒ ALGORITMUS ⇒ j´o/rossz (∈ F /6∈ F ) • Explicit felt´ etelek. V´eges sok egyenlet ´es/vagy egyenl˝otlens´eg ´ırja le a felt´etelt: ( fi (x) ≤ 0, i ∈ [k] := {1, 2, . . . , k}, (1.1) gj (x) = 0, j ∈ [ℓ], 1 2
http://www.nobelprize.org/nobel prizes/economics/laureates/1975/ FIGYELEM! Az el˝ oad´ as sor´an mindv´egig oszlopvektorokkal dolgozunk.
1-1
ahol teh´at fi (i ∈ [k]) ´es gj (j ∈ [ℓ]) szint´en n-v´altoz´os val´os f¨ uggv´enyek. Ekkor F a fenti rendszer megold´ashalmaza. Megjegyz´ es. A gyakorlati alkalmaz´asokban megjelen˝o c´elf¨ uggv´enyek nagyon sok” ” v´altoz´ot´ol f¨ ugghetnek: n ´ert´eke az ezres, s˝ot a milli´os nagys´agrendet is el´erheti. Az optimaliz´ al´ asi feladat ´ ertelmez´ esi tartom´ anya a c´elf¨ uggv´eny ´es a felt´etelek ´ertelmez´esi tartom´any´anak metszete. Ez az (1.1) explicit felt´etelek eset´en a D := dom (c) ∩
\ k
i=1
dom (fi ) ∩
\ ℓ
dom (gj )
j=1
halmaz, amely teh´at azon x-eket tartalmazza, amelyekre mind a c´elf¨ uggv´eny, mind pedig a felt´etelek ´ertelmezettek. Lehets´ eges/megengedett megold´ asoknak azon x ∈ D vektorokat nevezz¨ uk, amelyek eleget tesznek a krit´eriumoknak is, azaz x ∈ F . Ezen x-ek halmaz´at L jel¨oli. Teh´at L := D ∩ F , amely (1.1) explicit felt´etelek eset´en L = {x ∈ D : fi (x) ≤ 0, gj (x) = 0, i ∈ [k], j ∈ [ℓ]}. A feladathoz tartoz´o optim´ alis ´ ert´ ek p∗ = inf c(x) ∈ R ∪ {−∞} ∪ {∞}, x∈L
ahol az infimum ∞, ha a lehets´eges megold´asok halmaza u ¨ res ´es −∞, ha a c c´elf¨ uggv´eny a lehets´eges megold´asokon tetsz˝olegesen kicsi ´ert´eket is felvesz. Egy x∗ ∈ L vektor optim´ alis hely, ha ott a c´elf¨ uggv´eny felveszi az optim´alis ´ert´eket c(x∗ ) = p∗ . Az xl vektor lok´ alis optimum, ha annak egy k¨ornyezet´enek minden pontj´aban c legal´abb akkora, mint az xl helyen: ∃ ε > 0, ∀ x : kx − xl k2 < ε eset´en3
c(xl ) ≤ c(x).
Azt mondjuk, hogy x0 egy ε-k¨ ozel´ıt˝ o megold´ as (ε > 0), ha c(x0 ) ≤ p∗ + ε. Egy x0 vektor ε -approxim´ aci´ os megold´ as (ε > 0), ha c(x0 ) ≤ (1 + ε)p∗ . Megjegyz´ es. Az ε-approxim´aci´os megold´as fenti defin´ıci´oj´aba bele´ertj¨ uk, hogy az ∗ optim´alis ´ert´ek pozit´ıv, p > 0. A negat´ıv optim´alis ´ert´ek˝ u feladatokban az c(x0 ) ≤ ∗ (1 − ε)p felt´etelt kell tenn¨ unk. 3
k k2 az Rn -en ´ertelmezett euklid´eszi norma, k k2 : Rn → [0, ∞),
y 7→ kyk2 :=
1-2
q
y12 + · · · + yn2 .
2. Optimaliz´ al´ asi probl´ em´ ak ´ atfogalmaz´ asa Egy meg´ertett optimaliz´al´asi probl´ema eset´en t¨obb lehet˝os´eg van annak formaliz´al´as´ara. M´ask´eppen fogalmazva egy formaliz´alt optimaliz´al´asi probl´ema gyakran ´atfogalmazhat´o u ´ gy, hogy ugyanazt a probl´em´at ´ırja le. Sokf´ele helyzetben ezek az ´at´ır´asok az eredetivel ekvivalensek. M´askor azonban ugyaznazon probl´ema kiss´e elt´er˝o alakjai k¨ozt l´enyeges k¨ ul¨onbs´eg lehet. Ekvivalens ´atalak´ıt´as alatt olyan form´alis ´atlalak´ıt´ast ´ert¨ unk, hogy b´armelyik feladat optim´alis ´ert´eke/helye a m´asik feladat optim´alis ´ert´eke/helye alapj´an k¨onnyen megadhat´o. Most (a teljess´eg ig´enye n´elk¨ ul) n´eh´any lehet˝os´eg´et megeml´ıt¨ unk. 1. Min/max csere: Maximaliz´aljuk felt´eve, hogy
c(x)-et x∈F
≡
Minimaliz´aljuk felt´eve, hogy
−c(x)-et x∈F
A minimaliz´al´asi probl´ema egy optim´alis pontja egyben a maximaliz´al´asi probl´em´anak is optim´alis pontja. Ha a mimimaliz´al´asi probl´ema optim´alis ´ert´ek´et ismerj¨ uk, akkor annak ellentettje lesz a maximaliz´al´asi probl´ema optim´alis ´ert´eke. 2. A felt´ etelek ekvivalens ´ at´ır´ asa: A k¨oz´episkol´aban m´ar l´attunk formul´ak/egyenl˝otlens´egek/egyenl˝os´egek ekvivalens ´atalak´ıt´asait. A felt´eteleinkn´el ezeket term´eszetesen felhaszn´alhatjuk. x1 ≤ 0 ⇐⇒ x1 ≤ 0. +1
x22
(x1 + x2 )2 ≤ 0 ⇐⇒ (x1 + x2 )2 = 0 ⇐⇒ x1 + x2 = 0. 3. Slack v´ altoz´ ok, egyenl˝ otlens´ egek helyettes´ıt´ ese el˝ ojelfelt´ etelekkel: Minimaliz´aljuk felt´eve, hogy
Minimaliz´aljuk felt´eve, hogy
c(x)-et fi (x) ≤ 0 gi (x) = 0 ≡
c(x)-et fi (x) + si = 0 gi (x) = 0 si ≥ 0
4. A line´ aris egyenl˝ os´ egek kik¨ usz¨ ob¨ ol´ ese: Az Ax = b line´aris egyenl˝os´egrendszer megold´asa alap algebra tananyag. Az ´altal´anos megold´as x = x0 +F y alakban ´ırhat´o, ahol x0 egy tetsz˝oleges megold´as, m´ıg F oszlopai az Ax = 0 egyenletrendszer ´altal le´ırt alt´er egy gener´al´o rendszere. Ha F -nek s oszlopa van, akkor y ∈ Rs . x0 ´es F meghat´aroz´asa hat´ekonyan megtehet˝o. Minimaliz´aljuk felt´eve, hogy
c(x)-et fi (x) ≤ 0 Ax = b
Minimaliz´aljuk felt´eve, hogy ≡
c(x0 + F y)-et fi (x0 + F y) ≤ 0
5. A c´ elf¨ uggv´ eny helyettes´ıt´ ese egy monoton f¨ uggv´ enybe: Legyen m : R → R egy szigor´ uan monoton f¨ uggv´eny range c-n (a c´elf¨ uggv´eny ´altal felvett ´ert´ekek halmaz´an). Ekkor 1-3
Minimaliz´aljuk felt´eve, hogy
c(x)-et x∈F
Minimaliz´aljuk felt´eve, hogy
≡
m(c(x))-et x∈F
1. P´ elda. Minimaliz´aljuk felt´eve, hogy
kxk2 -et x∈F
≡
Minimaliz´aljuk felt´eve, hogy
kxk22 -et x∈F
Fenti esetben range c = R≥0 , ahol az m(x) = x2 f¨ uggv´eny monoton. Minim´alis v´altoztat´ast eszk¨oz¨olt¨ unk, de az u ´ j c´elf¨ uggv´eny differenci´alhat´o. L´atni fogjuk, hogy egy ilyen kis” el˝ony nagyon jelent˝os lehet. ” Egy ¨osszetettebb p´elda. 2. P´ elda. Minimaliz´aljuk
Maximaliz´aljuk x1 x2 + x2 x3 + x3 x1 -et. felt´eve, hogy x1 + x2 + x3 = 100, felt´eve, hogy x1 , x2 , x3 > 0. ≡
q
x21 +x22 +x23 -et. 3 x1 +x2 +x3 = 100 , 3 3
x1 , x2 , x3 > 0.
A k´et felt´etelrendszer nyilv´an ekvivalens. uggv´eny: c1 (x1 , x2 , x3 ) = q A k´et c´elf¨ 2 2 2 x1 +x2 +x3 x1 x2 + x2 x3 + x3 x1 , illetve c2 (x1 , x2 , x3 ) = . A kapcsolat nyilv´anval´o (a 3 felt´etelek teljes¨ ul´ese eset´en): 3c22 + 2c1 = (x1 + x2 + x3 )2 = 1002. c1 maximaliz´al´as´a helyett ´att´ep rhet¨ unk 1002 − 2c1 = 3c22 minimaliz´al´as´ara. Majd uan monoton f¨ uggv´enyt (az u ´ j c´elf¨ uggv´eny itt alkalmazhatjuk az m(x) = x3 szigor´ ´ ´altal felvett nemnegat´ıv ´ert´ekek halmaz´an) az aktu´alis c´elf¨ uggv´enyre. Igy a fenti m´asodik alakot kapjuk. Az u ´ j alak el˝onye nyilv´anval´o. A n´egyzetes k¨ozepet kell minimaliz´alni adott sz´amtani k¨oz´ep ´ert´ek eset´en. A sz´amtani ´es n´egyzetes k¨oz´ep k¨oz¨otti egyenl˝otlens´eg alapj´an elemi matematik´aval megv´alaszolhat´o az optimaliz´al´asi k´erd´es.
3. P´ eld´ ak optimaliz´ al´ asi feladatokra Az el˝oad´assorozatban t¨obbsz¨or l´atni fogunk olyan feladatot, amely formaliz´al´asa okozza a legt¨obb probl´em´at. Gyakran a form´alis le´ır´ashoz sz¨ uks´egesek a matematikai ¨otletek, az optimaliz´al´asi algoritmus m´ar k´eszen v´ar (az u ¨ gyesen megfogalmazott feladatn´al). Az al´abbiakban n´eh´any bevezet˝o p´eld´at mutatunk az alapfogalmakra, illetve elemi formaliz´al´asi tr¨ ukk¨okre. 3. P´ elda. Minimaliz´aljuk felt´eve, hogy 1-4
1 -et x x ≥ 0.
A c´elf¨ uggv´eny a c(x) = x−1 line´aris t¨ortf¨ uggv´eny, melynek ´ertelmez´esi tartom´anya dom (c) = R \ {0}. Az explicit felt´etelt egyetlen egyenl˝otlens´eg adja, nevezetesen f1 (x) = −x ≤ 0, ez´ert k = 1, ℓ = 0. Mivel dom (f1 ) = R, ´ıgy a feladat ´ertelmez´esi tartom´anya D = R \ {0}. Ebb˝ol l´athat´o, hogy a lehets´eges megold´asok halmaza az L = R>0 := (0, ∞) =]0.∞[ ny´ılt intervallum. Mivel az x ∈ L megengedett megold´asokon felvett f¨ uggv´eny´ert´ekek infimuma z´er´o, ez´ert p∗ = 0. Azonban nem l´etezik olyan x ∈ L, amelyen c felveszi ezt az ´ert´eket, teh´at optim´alis hely nincs. Megjegyezz¨ uk, hogy b´armely ε > 0 eset´en az x0 ≥ ε−1 sz´amok ε-k¨ozel´ıt˝o megold´asok, viszont ε-approxim´al´o megold´asok nem l´eteznek. 4. P´ elda. Minimaliz´aljuk
x log x-et
Most nincsenek felt´etelek kiszabva, azaz F = ∅. Ilyenkor azt mondjuk, hogy egy glob´alis optimaliz´al´asi probl´em´at tekint¨ unk. A c´elf¨ uggv´eny differenci´alhat´o ´ertelmez´esi tartom´any´an. Az optimaliz´al´as a calculus kurzus standard r´esze. A c(x) = x log x egyv´altoz´os c´elf¨ uggv´eny ´ertelmez´esi tartom´anya dom (c) = R>0 . Mivel felt´etel nincs, ez´ert L = D = dom (c) = R>0 . Az optim´alis ´ert´eket p´eld´aul elemi f¨ uggv´enydiszkusszi´ot elv´egezve ´allap´ıthatjuk meg. Eredm´eny¨ ul 1 p∗ = − e ad´odik. Az optim´alis ´ert´eket az 1 x∗ = . e optim´alis helyen ´eri el c. u s´ık mely pontj´anak minim´alis az orig´ot´ ol 5. P´ elda. Az x1 + x2 + x3 = 100 egyenlet˝ m´ert t´avols´aga? q Vegy¨ uk ´eszre, hogy a t´avols´ag helyett ´ırhatjuk t´avols´ag 13 -szeres´et is. A formaliz´al´as (egy kor´abbi p´eld´aval megegyez˝oen): q x21 +x22 +x23 Minimaliz´aljuk -et 3 x1 +x2 +x3 3
= 100 , 3 x1 , x2 , x3 > 0.
felt´eve, hogy
1-5
A sz´amtani ´es a n´egyzetes k¨ozepek k¨oz¨otti egyenl˝otlens´eget haszn´aljuk fel az optim´alis ´ert´ek becsl´es´ere: r r 1 x21 + x22 + x23 x1 + x2 + x3 100 c(x) = ≥ = . 3 3 3 3 Azaz
√ 100 3 . 3 (´es csak ekkor). Teh´at a feladat Tov´abb´a a korl´at el´erhet˝o, ha x1 = x2 = x3 = 100 3 egyetlen optim´alis helye 100 100 100 ∗ x = . , , 3 3 3 p∗ ≥
Tov´abb´a optim´alis ´ert´eke
p∗ = c(x∗ ) =
√ 100 3 . 3
6. P´ elda. Mekkora a legnagyobb felsz´ın˝ u (t´eglatest alak´ u) doboz, amelyet egy 400 cm-es madzaggal ´at tudunk k¨otni (a mell´ekelt ´abr´anak megfelel˝o m´odon)?
x3
x2 x1
1. ´abra. A formaliz´al´as nyilv´anval´o: Maximaliz´aljuk felt´eve, hogy
2x1 x2 + 2x2 x3 + 2x3 x1 -et 4x1 + 4x2 + 4x3 = 400, x1 , x2 , x3 > 0.
A kor´abbiak alapj´an ez ekvivalens feladat az el˝oz˝ovel. Az ekvivalencia u ´ jb´oli meggondol´asa adja, hogy az optim´alis hely azonos az el˝oz˝o feladat optim´alis hely´evel. 100 100 100 ∗ . , , x = 3 3 3 Ebb˝ol az eredeti feladat optim´alis ´ert´eke p∗ = c(x∗ ) =
20 000 . 3
7. P´ elda. Tegy¨ uk fel, hogy a lehet˝o legnagyobb t´eglalap alak´ u tartom´anyt szeretn´ek beker´ıteni 100 m hossz´ u ker´ıt´essel u ´gy, hogy a ter¨ ulet egyik oldal´at egy fal k´epezi. 1-6
x2
x1
2. ´abra. Ez a probl´ema a k¨ovetkez˝ok´eppen ´ırhat´o le optimaliz´al´asi feladatk´ent: Maximaliz´aljuk felt´eve, hogy
x1 x2 -t x1 + 2x2 = 100, x1 , x2 ≥ 0.
Nyilv´anval´o, hogy a c(x1 , x2 ) = x1 x2 c´elf¨ uggv´eny az eg´esz R2 s´ıkon ´ertelmezett ´es f1 (x1 , x2 ) = −x1 , f2 (x1 , x2 ) = −x2 , g1 (x1 , x2 ) = x1 + 2x2 − 100, ez´ert D = R2 ´es L = R≥0 × R≥0 . Alkalmazva a sz´amtani ´es m´ertani k¨ozepek k¨oz¨otti egyenl˝otlens´eget ´es a felt´eteleket figyelembe v´eve 50 =
x1 + 2x2 p ≥ x1 (2x2 ) 2
(≥ 0)
ad´odik, melyb˝ol n´egyzetre emel´essel kapjuk, hogy
2500 ≥ 2x1 x2 = 2c(x1 , x2 ), vagyis a c´elf¨ uggv´eny fel¨ ulr˝ol korl´atos: c(x1 , x2 ) ≤ 1250. Mivel x∗ = (50, 25) ∈ L egy lehets´eges megold´as, ahol c el´eri ezt a korl´atot, ´ıgy p∗ = 1250. 8. P´ elda. Tegy¨ uk fel, hogy egy lovas egy egyenesen halad´o foly´o egyik oldal´an tal´alhat´ o A pontb´ ol az ugyanazon oldalon l´ev˝o B pontba szeretne eljutni, de k¨ozben a lov´at is meg szeretn´e itatni. Melyik a legr¨ovidebb ilyen u ´t? B
,
B A
3. ´abra. A feladattal m´ar ´altal´anos iskol´aban tal´alkozhattunk geometria ´or´an. Legyen t azon foly´opart egyenese, amelyik oldalon lovasunk van. Legyen M az itat´as pontja. Tetsz˝oleges lehets´eges megold´as eset´en a lovas p´aly´aj´anak AM szakasz´at meghagyva, 1-7
majd a k´es˝obbi szakaszt t-re t¨ ukr¨ozve egy olyan p´aly´at kapunk, ami A-b˝ol, B ′ -be vezet (B ′ a B pont t¨ uk¨ork´epe t-re). A m´odos´ıtott p´alya hossza a tetsz˝olegesen v´alasztott lehets´eges megold´as hossza/k¨olts´ege. A m´odos´ıtott p´aly´ak k¨oz¨ott nyilv´an az AB ′ szakasz bej´ar´asa az optim´alis. Azaz t ´es az AB ′ szakasz M metsz´espontja az optim´alis itat´o hely”. Ide A-b´ol egyenes u ´ ton ´erkezve, majd B-be ugyancsak ” egyenes ment´en haladva lesz legr¨ovidebb a p´aly´aja a feladatbeli lovasnak. A formaliz´alt optimaliz´al´asi feladatot t¨obbf´elek´eppen is fel´ırhatjuk. Egy lehet˝os´eg, ha der´eksz¨og˝ u koordin´at´akat vezet¨ unk be (p´eld´aul a lovas fel˝oli foly´opart az x tengely). Feladatunk azon M(x∗ , 0) pont keres´ese, amelyre az AM, MB szakaszok hossz´anak ¨osszege minim´alis. Hiszen nyilv´anval´o, hogy ha A ´es M vagy M ´es B pontok k¨oz¨ott nem egyenes szakaszon mozog a lovas, akkor p´aly´aja nem optim´alis. Teh´at adott A(a1 , a2 ) ´es B(b1 , b2 ) eset´en a feladat az al´abbi m´odon fogalmazhat´o meg: p p Minimaliz´aljuk (a1 − x)2 + a22 + (b1 − x)2 + b22 -et. 9. P´ elda. A 100 pont´ u 3-r´eszes egyszer˝ u gr´afok k¨oz¨ ul melyeknek maxim´alis az ´elsz´ama? Ezzel a feladattal Kombinatorika kurzuson a Tur´an-t´etel kapcs´an tal´alkoztunk. Ha a h´arom r´esz m´eret´et rendre x1 , x2 ´es x3 jel¨oli ´es ´el¨ unk a term´eszetes ´eszrev´etellel, hogy teljes 3-r´eszes gr´afok k¨oz¨ott keress¨ uk az optim´alist, akkor a feladat a k¨ovetkez˝o: Maximaliz´aljuk felt´eve, hogy
x1 x2 + x2 x3 + x3 x1 -et x1 + x2 + x3 = 100, x1 , x2 , x3 > 0, x1 , x2 , x3 ∈ Z.
Mivel F egy nem¨ ures v´eges halmaz, ´ıgy a lehets´eges megold´asok k¨oz¨ott biztosan ∗ l´etezik x optim´alis hely, p∗ ∈ R optim´alis ´ert´ekkel. A felt´etelb˝ol az is l´athat´o, hogy ha (x1 , x2 , x3 ) egy lehets´eges megold´as, akkor p´eld´aul (x1 − 1, x2 + 1, x3 ) is lehets´eges megold´as (felt´eve, hogy x1 > 1). Ha x1 ≥ x2 + 2, akkor az ut´obbi helyen nagyobb a c´elf¨ uggv´eny, mint az el˝obbin. Ez azt is jelenti, hogy az optim´alis helyen |x∗i − x∗j | ≤ 1 minden i, j ∈ {1, 2, 3} eset´en. H´arom ilyen lehets´eges megold´as van, ahol a c´elf¨ uggv´eny k¨oz¨os ´ert´eket vesz fel. ´Igy az optim´alis helyek a (34, 33, 33), (33, 34, 33), (33, 33, 34) pontok. Az optim´alis ´ert´ek p∗ = 3333. Megjegyz´ es. A fenti feladat NEM ekvivalens a kor´abbi p´eld´aink egyik´evel sem. Ezt jelzi az optim´alis helyek ´es a lehets´eges megold´asok halmaz´anak elt´er´ese, melynek oka a felt´etelek l´enyeges” k¨ ul¨onb¨oz˝os´ege: most kiz´ar´olag eg´esz koordin´at´aj´ u helyek ” j¨ohetnek sz´oba. A folytonos” feladatban (2. p´elda, 6. p´elda) az optim´alis ´ert´ek 3 333 13 , nagyobb ” a mostanin´al. Ez term´eszetes: a folytonos versenyben” t¨obb r´esztvev˝o” van, a ” ” maximum ´ert´eke legal´abb annyi mint ahol csak eg´esz ´ert´ek´ u versenyz˝ok” indultak. ” ⋆
⋆
1-8
⋆
10. P´ elda. Legyen d, n ∈ N ´es ℓ1 (x), . . . , ℓn (x) : Rd → R adott line´aris f¨ uggv´enyek. Hat´arozzuk meg a c(x) = max1≤i≤n ℓi (x) f¨ uggv´eny minimum´at. Teh´at a formaliz´alt feladat: Minimaliz´aljuk
c(x)-et
A feladat glob´alis (nincsenek felt´etelek). A mell´ekelt ´abra a d = 1, n = 5 eset egy ´altal´anos konfigur´aci´oj´at szeml´elteti. M´ar ez a speci´alis v´alaszt´as is h˝ u k´epet ad a c´elf¨ uggv´enyr˝ol. c line´aris f¨ uggv´enyek maximuma szakaszonk´ent” line´aris ” f¨ uggv´eny. Ez d > 1 eset´en azt jelenti, hogy c ´ertelmez´esi tartom´anya felbonthat´o olyan ¨osszef¨ ugg˝o r´eszekre, melyeken c line´aris.
c(x)
4. ´abra. Az el˝oz˝ovel ekvivalens optimaliz´al´asi feladatban az m sz´amot minimaliz´aljuk u ´ gy, hogy az ottani c´elf¨ uggv´eny defin´ıci´oj´at (maximalit´as´at) be´ep´ıtj¨ uk a felt´etelekbe. Minimaliz´aljuk felt´eve, hogy
m-et l1 (x) ≤ m, .. . ln (x) ≤ m,
ahol (x, m) ∈ Rd × R. Egy optimaliz´al´asi feladat ezen form´aja ismer˝os lehet az oper´aci´okutat´as kurzusr´ol. 11. P´ elda (Line´ aris programoz´ as, LP). Legyen A ∈ Rm×n adott m´atrix, b ∈ Rm , c ∈ Rn r¨ogz´ıtett vektorok ´es x ∈ Rn az ismeretlen vektor. A feladat: Minimaliz´aljuk felt´eve, hogy
cT x-et Ax 4 b,
ahol Ax 4 b az al´abbi, m line´aris egyenl˝otlens´egb˝ol ´all´o rendszert jel¨oli (Ax)j ≤ bj
(j = 1, . . . , m).
Az (LP) feladatokat az Oper´aci´okutat´as kurzuson r´eszletesen t´argyaltuk. Megjegyezz¨ uk, hogy aqz LP feladat nagyon j´ol vizsg´alt, sok gyakorlatban ´es elm´eletben is j´onak tartott algoritmus l´etezik r´a. Ha egy probl´em´at LP feladatk´ent fogalmazunk meg, akkor a nehez´en t´ ul vagyunk (ak´ar k¨oz´episkol´aban, ha egyenletmegold´as sor´an m´asodfok´ u egyenletre reduk´altuk munk´ankat). Valamelyik ´altal´anos LP algoritmussal fejezz¨ uk be munk´ankat (ilyenek nyilv´anos forr´ask´oddal is k¨onnyen el´erhet˝oek). 1-9
12. P´ elda. Az LP probl´em´at tekintj¨ uk, amelyben a line´aris c´elf¨ uggv´eny (cT x) c vektora val´osz´ın˝ us´egi v´altoz´o. Feltessz¨ uk, hogy v´arhat´o ´ert´eke, c = E[c] ismert, tov´abb´ a a felt´etelek m´ar nem f¨ uggnek a v´eletlent˝ol. Minimaliz´aljuk a c´elf¨ uggv´eny ´ert´ek´enek v´arhat´o ´ert´ek´et. A v´arhat´o ´ert´ek linearit´asa alapj´an E[cT x] = (E[c])T x egy LP feladat marad optimaliz´al´asi k´erd´es¨ unk: Minimaliz´aljuk felt´eve, hogy
(E[c])T x Ax 4 b.
13. P´ elda (Polit´ opok Csebisev-k¨ oz´ eppontja). A P = {x ∈ Rn : aTi x ≤ b, i = 1, . . . , k} alak´ u ponthalmazokat poli´edereknek nevezz¨ uk. Ha a P poli´eder korl´atos (amikor is kompakt: korl´atos ´es z´art), akkor polit´opnak nevezz¨ uk. Fontos probl´ema, hogy m´erj¨ uk P egy pontja milyen m´elyen van P belsej´eben. Illetve fontos k´erd´es: Melyek P legbels˝o pontjai? Igaz´ ab´ol az is k¨ozponti probl´ema, hogy P-r˝ol d¨onts¨ uk el, hogy u ¨res-e. Sokf´ele megold´as/v´alasz van. Mi egy, Csebisev nev´ehez f˝ uz¨ott, megold´asr´ol besz´el¨ unk. Defin´ıci´ o. B(c, r) = {x ∈ Rn : |x − c|2 ≤ r 2 } a c k¨oz´eppont´ u r sugar´ u g¨omb. A p ∈ P pont Csebisev m´elys´ege M(p) = sup{r : B(p, r) ⊂ P}. c a P polit´op egy Csebisev k¨oz´eppontja, ha M(c) = sup M(p). p∈P
Az alapprobl´ema: Adott P eset´en keress¨ unk egy Csebisev k¨oz´eppontot. A feladat els˝o r´an´ezesre nem line´aris. N´emi ¨otlettel azonban LP feladatk´ent fogalmazhatjuk meg. N´emi geometriai ismeretre lesz sz¨ uks´eg¨ unk. Defin´ıci´ o. Egy hipers´ık Rn -ben: H = {x : aT x = b} alak´ u ponthalmaz. r pont pontosan akkor esik H-ra, ha a− b = 0. Egy p pont el˝ojeles t´avols´aga H-t´ol b aT p− . |a| |a| Az el˝ojeles t´avols´ag abszol´ ut´ert´eke a t´avols´ag, el˝ojele a hipers´ık azon oldal´at ´ırja le, ahov´a pontunk esik. K´etf´ele el˝ojeles t´avols´ag l´etezik. A fenti az, amelyik az {x : aT x > b} f´elt´erben pozit´ıv, a komplementer (nyilt) f´elt´erben negat´ıv. A Csebisev-k¨oz´eppont probl´em´aja ekvivalens a k¨ovetkez˝ovel: Maximaliz´aljuk felt´eve, hogy
r aTi x + |ai |r ≤ bi , r≥0
1-10
i = 1, . . . , k
Els˝o t´ıpus´ u felt´etel¨ unk ekvivalens azzal, hogy r≤
aT i x |ai |
+r ≤
b , |ai |
azaz
aT b − i x. |ai | |ai |
A jobb oldalon egy el˝ojeles t´avols´ag szerepel, amit u ´ gy v´alasztottunk, hogy az ai x < b f´elterekben legyen pozit´ıv. Az ´atfogalmazott optimaliz´al´asi feladat egy LP feladat. ⋆
⋆
⋆
A k¨ovetkez˝o probl´em´aval ´es megold´asi m´odszereivel a numerikus anal´ızis t´argyk¨or´eben tal´alkozhattunk. 14. P´ elda (A legkisebb n´ egyzetek probl´ em´ aja). A probl´ema Minimaliz´aljuk
kc − Axk
Minimaliz´aljuk
kc − Axk2
illetve
ahol x ∈ Rn , A ∈ Rk×n val´os m´atrix ´es c ∈ Rk . Ez egy felt´etel n´elk¨ uli optimaliz´al´asi feladat. Alap line´aris algebrai, geometriai ismeretek alapj´an egyszer˝ uen kezelhet˝o. 15. P´ elda. Adott egy m´er´essorozat (pl. egy k´ıs´erleti laborat´orium k¨ ul¨onb¨oz˝o id˝opontokban vett m´er´esei, vagy egy meteorol´ogiai ´allom´as k¨ ul¨onb¨oz˝o helyeken m´ert adatai), ahol t1 , t2 , . . . tN ´es p1 , p2 , . . . , pN jel¨oli rendre a m´er´esi id˝oket/helyeket illetve a m´ert param´etereket. Keres¨ unk egy ”alacsony”, d-fok´ u polinomot, ami j´o ”hipot´ezis” p v´altoz´asaira (vagyis j´ol ”illeszthet˝o” a diszkr´et id˝o-m´ert param´eter grafikonra). Legyen p(x) = xd xd + · · · + x1 x + x0
azaz p = (p1 , . . . , pN )T m´ert vektor eset´en az
d−1 T xd (td1 , . . . , tdN )T + xd−1 (td−1 1 , . . . , tN ) + . . .
vektor L2 -ben m´ert p-t˝ol vett t´avols´ag´at kell minimaliz´alni. A probl´ema a legkisebb n´egyzetek probl´em´aj´ara vezet˝odik vissza. A legkisebb n´egyzetek probl´em´aj´aban kvadratikus forma a c´elf¨ uggv´eny. szemben LP-vel, ahol line´aris f¨ uggv´eny. Az al´abbiakban a k´et probl´em´anak k¨oz¨os ´altal´anos´ıt´as´at vizsg´aljuk. ⋆
⋆
⋆
16. P´ elda (Kvadratikus programoz´ as, QP). Adottak az A ∈ Rn×n szimmetrikus m×n ´es C ∈ R m´atrixok, valamint a b ∈ Rn , d ∈ Rm vektorok. A feladat: 1-11
xT Ax + bT x-et Cx 4 d.
Minimaliz´aljuk felt´eve, hogy
A QP alapfeladat felt´etelrendszere line´aris. A c´elf¨ uggv´eny azonban j´oval ´altal´anosabb. Megjegyezz¨ uk, hogy a QP alapfeladata is kezelhet˝o (hat´ekony algoritmus ismert r´a) ha a ce’lfu;ggve’ny konvex (azaz A poziti’v szemidefinit). Ha egy probl´em´at ilyen (konvex QP) alakra hozunk, akkor k´eszen vagyunk”. ” 17. P´ elda (Sztochasztikus LP). Az LP probl´em´at tekintj¨ uk, amelyben a line´aris T c´elf¨ uggv´eny (c x) c vektora val´osz´ın˝ us´egi v´altoz´o. Feltessz¨ uk, hogy v´arhat´o ´ert´eke, c = E[c], kovarianciam´atrixa Σ = E[(c − c)(c − c)T ] ismert. Tov´abb´a a felt´etelek m´ ar nem f¨ uggnek a v´eletlent˝ol. L´attuk, ha csak a c´elf¨ uggv´eny ´ert´ek´enek v´arhat´o ´ert´ek´et (E[cT x] = (E[c])T x) minimaliz´aljuk, akkor egy LP feladathoz jutunk. Ekkor azonban a kock´azatot” nem ” vett¨ uk figyelembe. Megszokott a k¨ovetkez˝o v´altozat vizsg´alata: E[cT x] + γ Var[cT x] Ax b Dx = e
Minimaliz´aljuk felt´eve, hogy
ahol γ ∈ R>0 egy az alkalmaz´ashoz v´alasztott param´eter. Egyszer˝ u ´atlak´ıt´asokkal Var[cT x] = E[(cT x − E[cT x])2 ] = E[(cT x − (E[c])T x)2 ] = E[((cT − E[c]T )x)2 ] = xT E[(c − E[c])(cT − E[c]T )]x = xT Σx. A k´erd´es konvex QP alakja m´ar l´athat´o. 18. P´ elda. Hat´arozzuk meg az n-dimenzi´os euklid´eszi t´er k´et adott polit´opj´anak t´avols´ag´at! Mivel a polit´opok line´aris egyenl˝otlens´egrendszerek megold´ashalmazak´ent ´allnak el˝o, ez´ert mindk´et polit´opnak megfelel egy egyenl˝otlens´egrendszer: P1 = {x ∈ Rn : C1 x1 4 d1 } ´es P2 = {y ∈ Rn : C2 x2 4 d2 }. Ezek t´avols´aga d(P1 , P2 ) = inf{d(x1 , x2 ) : x1 ∈ P1 , x2 ∈ P2 }, ahol d(x1 , x2 ) = kx1 − x2 k2 . A t´avols´agn´egyzetet tekintve ekvivalens optimaliz´al´asi feladatot nyer¨ unk: Minimaliz´aljuk felt´eve, hogy
1-12
kx1 − x2 k22 -et C1 x1 4 d1 , C2 x2 4 d2 .
Blokkm´atrixos ´ır´asm´odot haszn´alva megmutatjuk, hogy ez egy konvex QP feladat. Ehhez tekints¨ uk a d1 , d2 , x1 , x2 ∈ Rn vektorokb´ol ´es C1 , C2 ∈ Rn×n m´atrixokb´ol k´epzett C1 0 x1 d1 2n ∈ R2n×2n ∈R , C= , x= d= 0 C2 x2 d2 vektorokat ´es m´atrixot, ahol teh´at 0 az n × n-es nullm´atrixot jel¨oli. Ha az n × n-es egys´egm´atrixb´ol k´epezz¨ uk m´eg, az I −I ∈ R2n×2n A= −I I
m´atrixot, akkor feladatunk a konvex QP alapfeladat´anak alakj´at ¨olti (M, N = 2n ´es b = 0 ∈ R2n ). A r´eszletek kidolgoz´as´at az Olvas´ora b´ızzuk. A fentiek alapj´an k´et polit´op t´avols´ag´anak meghat´aroz´asa hat´ekonyan elv´egezhet˝o. ⋆
⋆
⋆
Ism´et ny´ uljunk” bele az LP alapfeladatba. Most a felt´etelrendszert m´odos´ıtsuk. ” A felt´etelek k¨oz´e tegy¨ uk be azt, hogy versenyz˝o” vektoraink koordin´at´ai legyenek ” eg´eszek. 19. P´ elda (Eg´ esz ´ ert´ ek˝ u programoz´ as, IP). Az alapfeladat: Minimaliz´aljuk felt´eve, hogy
cT x-et Ax 4 b, x ∈ Zd .
Lehet, hogy ez a m´odos´ıt´as ´artatlanabbnak” t˝ unik, mint a c´elf¨ uggv´eny m´odos´ıt´asa, ” m´egis a kapott probl´ema neh´ez. Ez az ´altal´anos forma k´epes N P -teljes probl´em´ak ´ formaliz´al´as´ara. Altal´ anos, hat´ekony megold´asa nem v´arhat´o. 20. P´ elda. Adott egy G egyszer˝ u gr´af. Hat´arozzuk meg ω(G) = max{|K| : K ⊂ V (G) klikk} ´ert´ek´et. Egye tetsz˝oleges U cs´ ucshalmaz le´ırhat´o {0, 1}V ⊂ RV -beli χU karakterisztikus vektor´aval. U elemsz´ama ´eppen 1T χU , ahol 1 ∈ RV azon vektor, amely minden komponense 1. {0, 1}V elemeit a 0 ≤ xv ≤ 1, xv ∈ Z tetsz˝oleges v cs´ ucsra tett felt´etelekkel ´ırhatjuk le. Egy 0-1 vektor akkor lesz klikk karakterisztikus vektora, ha tetsz˝oleges ¨ossze nemk¨oz¨ott u ´es v cs´ ucsra legfeljebb egy esik bele. Azaz minden uv 6∈ E(G), u 6= v cs´ ucsok eset´en xu + xv ≤ 1. A j´ol ismerten N P -neh´ez klikk probl´ema megfogalmazhat´o mint egy IP probl´ema: Maximaliz´aljuk felt´eve, hogy
1T x-et, 0 ≤ xv ≤ 1, xv ∈ Z minden v cs´ ucsra xu + xv ≤ 1 tetsz˝oleges uv 6∈ E(G), u 6= v cs´ ucsok eset´en.
A tov´abbiakban egy speci´alis IP probl´em´akat mutatunk be, ahol m´egis lehets´eges a hat´ekony kezel´es. 1-13
21. P´ elda. Adott G gr´af ´elei k¨oz¨otti maxim´alis p´aros´ıt´ast keress¨ uk. A feladat formaliz´al´asa: 1T x-et (ahol 1T = (1, . . . , 1), x ∈ RE(G) ) x p´aros´ıt´as karakterisztikus vektora.
Maximaliz´aljuk felt´eve, hogy
A felt´etelt algebraiz´alva az al´abbi ekvivalens optimaliz´al´asi feladatot kapjuk: Maximaliz´aljuk felt´eve, hogy
1T x-et (ahol x ∈ RE(G) ) 0 ≤ xe ≤ 1, xe ∈ Z P xe ≤ 1 minden v cs´ ucsra.
e:vIe
Azaz egy IP feladatot l´atunk. Az xe ∈ Z felt´etel elhagy´as´at LP relax´ aci´ onak nevezz¨ uk. Ezzel a versenyt megnyitjuk” a nem eg´esz koordin´at´aj´ u versenyz˝ok” fel´e ” ” is. Term´eszetesen a maximaliz´al´asi feladat optim´alis ´ert´eke megn˝ohet. A relax´alt feladat egy kezelhet˝o probl´ema/LP feladat: Maximaliz´aljuk felt´eve, hogy
1T x-et 0 ≤ xe ≤ 1, P xe ≤ 1 minden v cs´ ucsra.
e:v I e
T´ etel. Ha G p´aros, akkor a ν ∗ optim´alis ´ert´ekre ν ∗ = ν(G). Azaz LP relax´aci´oval nyert feladat ekvivalens az eredetivel. Probl´em´ank kezdeti alakj´at is ´at´ırhatjuk LP alakba. Eredetileg v´eges sok verseny” z˝onk” volt, a p´aros´ıt´asok karakterisztikus vektorai. Ezt a versenyz˝ohalmazt helyettes´ıtve a konvex burkukkal egy ekvivalens probl´em´at kapunk (c´elf¨ uggv´eny¨ unk line´aris!): Maximaliz´aljuk felt´eve, hogy
1T x x ∈ conv{χM : M p´aros´ıt´as}
A felt´etel egy polit´opot ´ır le. Ez le´ırhat´o v´eges sok f´elt´er metszetek´ent, azaz algebrailag egy v´eges line´aris egyenl˝otlens´egrendszer megold´ashalmaza. A fentiek alapj´an p´aros gr´afok eset´en ez az egyenl˝otlens´egrendszer sz´epen fel´ırhat´o. A nem p´aros gr´afok eset´et a k´es˝obbiekben vizsg´aljuk meg jobban. ⋆
⋆
⋆
V´eg¨ ul egy N P -neh´ez probl´em´at formaliz´alunk/algebraiz´alunk. Az eredm´eny alakja egy QP alapfeladat. Az N P -neh´ezs´eg/kezelhetetlens´eg azonban azt sugallja, hogy a konvex QP kis m´odos´ıt´asai m´ar kezelhetetlen probl´em´ak lehetnek. 22. P´ elda. Adott egy G gr´af. Hat´arozzuk meg a klikk param´eter´et (ω(G)-t), azaz a legnagyobb klikk m´eret´et. L´attuk, hogy a k´erd´es egy IP probl´emak´ent is megfogalmazhat´o. Az al´abbi t´etel egy t´avolr´ol sem nyilv´anval´o, m´asik formaliz´al´as´at adja ω(G) meghat´aroz´as´anak. T´ etel. Legyen A a G gr´af szomsz´eds´agi m´atrixa ´es tekints¨ uk az al´abbi feladatot: 1-14
xT Ax-et x < 0, 1T x = 1.
Maximaliz´aljuk felt´eve, hogy
Ekkor p∗ = 1 −
1 . ω(G)
Bizony´ıt´ as. (1) Legyen K egy optim´alis (maxim´alis elemsz´am´ u) klikk. Ekkor az xK = (0, . . . , 0,
1 1 , . . . , , 0, . . . , 0) |ω {z ω} K
lehets´eges helyen c ´ert´eke c(xK ) = xTK AxK = (2) Tekints¨ uk az
1 1 ω(ω − 1) = 1 − . 2 ω ω
v1 vk n1 nk x= ∈ L ∩ QV (G) ,..., N N
vektort, ahol teh´at k = |V (G)| ´es az n1 , . . . , nk ∈ N sz´amok az N ∈ N sz´am e egy part´ıci´oj´at adj´ak. Ezek ut´an a G gr´afhoz rendelj¨ unk egy G-mal jel¨olt gr´afot a k¨ovetkez˝o m´odon: • A G gr´af vi pontj´anak egy ni pontb´ol ´all´o ´elmentes Vi f¨ uggetlen ponthalmaz e felel meg G-ban (i = 1, . . . , k).
• Ha a vi , vj ∈ V (G) pontok szomsz´edosak, akkor a megfelel˝o Vi , Vj cs´ ucshalmazok k¨ozt egy Kni ,nj teljes p´aros gr´afot tesz¨ unk (minden lehets´eges kereszt´elt beh´ uzunk). • Ha a vi , vj ∈ V (G) pontokat nem k¨oti ¨ossze ´el, akkor a megfelel˝o Vi , Vj cs´ ucshalmazok k¨oz¨ott nincs ´el. e pontjainak sz´ama A defini´aci´o alapj´an G e = |V (G)|
k X
e ´elsz´ama A konstrukci´o alapj´an G e = |E(G)|
X
{vi ,vj }∈E(G)
vi = N
i=1
1 ni nj = N 2 2
k X ni i=1
X
vi vj ∈E(G)
N
=N
ni nj N2 T N2 = x Ax = c(x). NN 2 2
e legnagyobb klikkje ω(G) m´eret˝ G u. A Tur´an-t´etelt alkalmazva ´elsz´ama legfeljebb az ω(G) oszt´aly´ u/N pont´ u Tur´an-gr´af ´elsz´ama: e ≤ |E(TN,ω(G) )| ≤ |E(G)|
2 2 N ω(G) N 1 = 1− . 2 ω(G) ω(G) 2 1-15
A fentiek ¨osszegz´ese ut´an kapjuk, hogy c(x) =
2 e ≤1− 1 , |E(G)| 2 N ω(G)
ha x ∈ L∩QV (G) . Ez egy s˝ ur˝ u halmaz L-ben, a c´elf¨ uggv´eny folytonos, ami bizony´ıtja 1 . a hi´anyz´o egyenl˝otlens´eget. Vagyis p∗ = 1 − ω(G) A t´etel ´altal adott formaliz´al´asban egy kvadratikus alakot kell minimaliz´alni. A konvex QP alapfeladat felt´etelei k¨oz¨ ul csak” a kvadratikus alak m´atrix´anak pozit´ıv ” szemidefinits´ege hi´anyzik. Ezen felt´etel elhagy´asa olyan alakot eredm´enyez, ami k´epes rem´enytelen optimaliz´al´asi feladatok formaliz´al´as´ara.
1-16
