´ OKUTAT ´ ´ II. OPERACI AS Programtervez˝ o matematikusok sz´ am´ ara Verzi´ o: 2004. ´ aprilis 1.
Kov´ acs Margit docens ELTE TTK Oper´ aci´ okutat´ asi Tansz´ ek
Tartalomjegyz´ ek 1. Fu enyek ¨ ggv´
3
2. Fu enyek optimalit´ asa ¨ ggv´ 2.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 6
3. Konvex halmazok 3.1. M˝ uveletek konvex halmazokkal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 7 10
4. Konvex fu enyek ¨ ggv´ 4.1. Konvex f¨ uggv´enyek karakteriz´ aci´oi . . . . 4.2. Konvex f¨ uggv´enyek f¨ uggv´enyei . . . . . . 4.3. Konvex f¨ uggv´enyekkel defini´ alt halmazok 4.4. Feladatok . . . . . . . . . . . . . . . . . .
. . . .
12 12 14 15 17
5. Felt´ eteles sz´ els˝ o´ ert´ ekprobl´ em´ ak 5.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19 20
6. Lagrange multiplik´ atorok m´ odszere 6.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21 24
7. Optimalit´ asi krit´ eriumok 7.1. Sz¨ uks´eges felt´etelek differenci´ alis alakban . . 7.2. Feladatok . . . . . . . . . . . . . . . . . . . . 7.3. Konvex MP feladatok optimalit´asi krit´eriumai 7.4. Feladatok . . . . . . . . . . . . . . . . . . . . 7.5. Megengedett ir´ anyok m´ odszere . . . . . . . . 7.6. Feladatok . . . . . . . . . . . . . . . . . . . . 7.7. Nyeregpontfelt´etelek . . . . . . . . . . . . . . 7.8. Feladatok . . . . . . . . . . . . . . . . . . . .
. . . . . . . .
25 25 29 31 33 34 35 36 39
8. A line´ aris komplementarit´ asi feladat megold´ asa 8.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40 49
9. Kvadratikus programoz´ as 9.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51 54
10.Hiperbolikus programoz´ as 10.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55 57
11.Egyv´ altoz´ os unimod´ alis fu enyek ¨ ggv´ 11.1. Intervallumfelez´esi elj´ ar´ as . . . . . 11.2. Aranymetsz´es m´ odszere . . . . . . 11.3. Feladatok . . . . . . . . . . . . . .
58 58 59 61
12. Egyv´ altoz´ os fu enyek ¨ ggv´ 12.1. T¨ or¨ ottvonal m´ odszer ´ 12.2. Erint˝ o m´odszer . . . . 12.3. Feladatok . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . . . . . . . . . . . . . . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
. . . .
. . . . . . . .
minimaliz´ al´ asa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
minimaliz´ al´ asa: t¨ or¨ ottvonal ´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
´ erint˝ o m´ odszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62 63 64 66
1. Fu enyek ¨ ggv´ Jel¨olje D(f ) ⊆ Rn az f f¨ uggv´eny ´ ertelmez´ esi tartom´ any´at, azaz legyen D(f ) = {u ∈ Rn : −∞ < f (u) < ∞}.
1.1. Defin´ıci´ o. Az U ⊂ Rn -en ´ertelmezett f (u) f¨ uggv´eny epigr´ afj´ anak az epi f = {(u, η) ∈ Rn+1 : u ∈ U, η ≥ f (u)} halmazt nevezz¨ uk.
1.2. Defin´ıci´ o. Az U ⊂ Rn -en ´ertelmezett f (u) f¨ uggv´eny als´ o n´ıv´ ohalmaz´ anak (r¨ oviden n´ıv´ ohalmaz´ anak) az Lf (c) = {u ∈ D(f ) : f (u) ≤ c}, c ∈ R halmazt nevezz¨ uk.
2. Fu enyek optimalit´ asa ¨ ggv´ 2.1. Defin´ıci´ o. u∗ ∈ U lok´ alis minimumpontja az f : D(f ) → R f¨ uggv´enynek az U ⊆ D(f ) halmazon, ha ∃Oδ (u∗ ) k¨ ornyezete u ´gy, hogy f (u) ≥ f (u∗ ) ∀u ∈ U ∩ Oδ (u∗ ).
(2.1)
Ha (2.1) teljes¨ ul ∀u ∈ U , akkor u∗ glob´ alis minimumpont.
2.1. T´ etel. Legyen f : D(f ) → R, u∗ ∈ U ⊆ D(f ) ⊆ Rn ´es f ∈ C 1 (U ∩ Oε (u∗ )) (folytonosan differenci´ alhat´ o). Akkor hf 0 (u∗ ), u − u∗ i ≥ 0
∀u ∈ U ∩ Oε (u∗ )
(2.2)
sz¨ uks´eges felt´etele annak, hogy u∗ lok´ alis minimumpont legyen. Ha Oε (u∗ ) ⊆ U , akkor a sz¨ uks´eges felt´etelaz f 0 (u∗ ) = 0 alakot o ¨lti. Bizony´ıt´ as. Legyen u ∈ U ∩ Oε (u∗ ) ´es α ∈ [0, 1]. Akkor f (u∗ + α(u − u∗ )) − f (u∗ ) = αhf 0 (u∗ ), u − u∗ i + o(α) ≥ 0. Inn´et o(α) ≥ 0 ∀α ∈ (0, 1). α α ↓ 0-val kapjuk a (2.2) egyenl˝ otlens´eget. Ha Oε (u∗ ) ⊆ U , akkor ∀v ∈ Rn -hez ∃ε0 > 0 u ´gy, hogy u = u∗ + εv ∈ Oε (u∗ ) ∀ε : |ε| < ε0 , ez´ert hf 0 (u∗ ), u − u∗ i +
hf 0 (u∗ ), u∗ + εv − u∗ i ≥ 0 ∀ε : |ε| < ε0 , v ∈ Rn . Inn´et εhf 0 (u∗ ), vi ≥ 0 ∀ε : |ε| < ε0 , v ∈ Rn , vagyis hf 0 (u∗ ), vi = 0 ∀v ∈ Rn , ami csak f 0 (u∗ ) = 0 mellett teljes¨ ul.
3
2.2. Defin´ıci´ o. Az {uk } ⊂ U az f : D(f ) → R f¨ uggv´eny minimaliz´ al´ o sorozata az U ⊆ D(f ) halmazon, ha lim f (uk ) = f∗ = inf f (u). u∈U
k→∞
2.3. Defin´ıci´ o. Az U∗ = {u ∈ U ⊆ D(f ) : f (u) = f∗ = inf f (v)} v∈U
az f : D(f ) → R f¨ uggv´eny minimumhalmaza az U ⊆ D(f ) halmazon.
2.2. T´ etel. (Weierstrass t´ etele) Legyen az f (u) f¨ uggv´eny folytonos a kompakt U ⊂ D(f ) halmazon. Akkor 1. f∗ = inf f (u) > −∞; u∈U
2. U∗ = {u ∈ U : f (u) = f∗ } = 6 ∅ kompakt; 3. f (u) minden minimaliz´ al´ o sorozata U -n tart U∗ -hoz. Bizony´ıt´ as. Legyen {uk } ⊂ U minimaliz´ al´ o sorozat, azaz lim f (uk ) = f∗ . Mivel U kompakt, {uk } sorozatnak k→∞
van legal´abb egy torl´ od´ asi pontja, ´es minden torl´od´asi pontja U -ban van. Legyen u∗ ∈ U egy torl´od´asi pont. {uk }-b´ ol kiv´ alaszthat´ o egy konvergens r´eszsorozat: {ukm }, ukm → u∗ , ha m → ∞. Kihaszn´alva f (u) folytonoss´ ag´ at ´es f∗ definici´oj´at: f∗ ≤ f (u∗ ) = lim inf f (ukm ) = lim f (uk ) = f∗ , m→∞
k→∞
k¨ovetkez´esk´eppen f (u∗ ) = f∗ . Ebb˝ ol k¨ ovetkezik, hogy f∗ > −∞, U∗ 6= ∅ ´es minden minimaliz´al´o sorozat valamennyi torl´ od´ asi pontja U∗ -beli. Legyen {vk } ⊂ U∗ . Mivel U kompakt ´es {vk } ⊂ U , ez´ert kiv´alaszthat´o bel˝ole konvergens r´eszsorozat {vkm } → v∗ ∈ U . A {vk } sorozat minimaliz´al´o f (u)-ra, mivel f (vk ) = f∗ , ez´ert minden torl´od´asi pontja, ´ıgy v∗ is U∗ -beli, azaz U∗ z´art. Teh´at U∗ egy kompakt halmaz z´art r´eszhalmaza, ´ıgy ˝o maga is kompakt. Legyen {uk } egy minimaliz´ al´ o sorozat. ρ(uk , U∗ ) = inf ρ(uk , u) ≥ 0 =⇒ lim inf ρ(uk , U∗ ) ≥ 0. u∈U∗
k→∞
Legyen lim sup ρ(uk , U∗ ) = lim ρ(ukm , U∗ ) = a ≤ ∞. k→∞
m→∞
U kompakts´ aga miatt kiv´ alaszthat´o az {ukm } sorozatb´ol egy u∗ ponthoz konverg´al´o r´eszsorozat. Az ´altal´anoss´ ag megszor´ıt´ asa n´elk¨ ul feltehet˝o, hogy ez a r´eszsorozat maga az {ukm } r´eszsorozat. A ρ(u, U∗ ) f¨ uggv´eny folytonos, ´ıgy lim ρ(ukm , U∗ ) = ρ(u∗ , U∗ ) = a.
m→∞
Minthogy u∗ egy minimaliz´ al´ o sorozat torl´od´asi pontja, a kor´abbiak szerint u∗ ∈ U∗ , azaz ρ(u∗ , U∗ ) = a = 0. Ez´ert 0 ≤ lim inf ρ(uk , U∗ ) ≤ lim sup ρ(uk , U∗ ) = 0. k→∞
k→∞
Ez azt jelenti, hogy b´ armely minimaliz´ al´o sorozat tart U∗ -hoz.
4
2.3. T´ etel. Legyen f (u) folytonos a z´ art, nem u abb´ a valamilyen ¨res U ⊂ D(f ) halmazon, tov´ v ∈ U -ra Lf (f (v)) = {u ∈ U : f (u) ≤ f (v)} legyen korl´ atos. Akkor f∗ > −∞, U∗ 6= ∅ kompakt ´es f (u) minden minimaliz´ al´ o {uk } ⊂ Lf (f (v)) sorozatra {uk } → U∗ . Bizony´ıt´ as. Mivel f (u) > f (v), ha u ∈ U \ Lf (f (v)), f (u) ≤ f (v), ha u ∈ Lf (f (v)), a f (u) f¨ uggv´eny nem veheti fel az infimum´at az U \ Lf (f (v)) halmazon. Ez´ert el´eg a vizsg´alatot az Lf (f (v)) halmazra szor´ıtani. A f folytonoss´ aga miatt Lf (f (v)) z´ art, a felt´etel szerint korl´atos, teh´at kompakt. A Weierstrass t´etelb˝ol ez´ert k¨ ovetkezik a t´etel minden ´all´ıt´asa.
2.4. T´ etel. Legyen U ⊂ D(f ) nem u art halmaz, f (u) folytonos U -n, ´es tegy¨ uk fel, hogy ¨res, z´ lim f (uk ) = +∞
k→∞
minden olyan {uk } ⊂ U sorozatra, amelyre lim k uk k= ∞ teljes¨ ul. k→∞
Akkor f∗ > −∞, U∗ 6= ∅ kompakt halmaz ´es minden minimaliz´ al´ o sorozat tart U∗ -hoz. Bizony´ıt´ as. Ha U korl´ atos, akkor Weierstrass t´etele alapj´an igaz az ´all´ıt´as. Tegy¨ uk fel, hogy U nem korl´ atos. Akkor l´etezik legal´abb egy {uk } ⊂ U sorozat, melyre lim k uk k= +∞.
k→∞
Akkor a felt´etel szerint lim f (uk ) = +∞.
k→∞
V´alasszunk tetsz˝ oleges olyan v ∈ U pontot, melyre f (v) > f∗ . Tekints¨ uk az Lf (f (v)) = {u ∈ U : f (u) ≤ f (v)} szinthalmazt. Lf (f (v)) korl´ atos, mert ha nem lenne az, akkor l´etezne {wk } ⊂ Lf (f (v)) sorozat, amelyikre lim k wk k= +∞ ´es erre a sorozatra lim f (wk ) = +∞, ami ellentmond annak, hogy k→∞
k→∞
f (wk ) ≤ f (v) < +∞. Lf (f (u)) korl´ atoss´ aga miatt a t´etel valamennyi ´all´ıt´asa k¨ovetkezik az 2.3. T´etelb˝ol.
5
2.1. Feladatok 2.1.1. Feladat. Minimaliz´ al´ o sorozat-e 1.) az f (x) =
x2 , (x ∈ R) f¨ uggv´enyre az xk = k, k = 1, 2, . . . sorozat? 1 + x4
2.) az f (u) =
||u|| , (u ∈ Rn ) f¨ uggv´enyre az uk = k · 1 sorozat, ahol a 1 = (1, 1, . . . , 1)? 1 + ||u||2
2.1.2. Feladat. Indokolja meg, fog-e minden U -beli minimaliz´ al´ o sorozat konverg´ alni az f (u) f¨ uggv´eny U -beli minimumhely´ehez konverg´ alni, ha 1.) U = Rn ´es f (u) = ||u||2 ? 2.) U = {u = (x, y) ∈ R2 : x + 3y ≤ 1, x ≥ 0, y ≥ 0} ´es f (u) = x + y? 3.) U = {u = (x, y) ∈ R2 : 2x + y ≥ 3, x ≥ 0, y ≥ 0} ´es f (u) = x + 2y? 2.1.3. Feladat. Felveszi-e az f (u) f¨ uggv´eny a minimum´ at az U halmazon, ha 1.) U = {u ∈ R : 1 ≤ u ≤ ∞ ´es f (u) =
u2 ? 1 + u4
2.) U = Rn ´es f (u) = ||u||3 ? 3.) U = {u = (x, y) ∈ R2 : x ≥ 0, y ≥ 0} ´es f (u) = x + y1 ? 4.) U = {u = (x, y) ∈ R2 : |x| ≤ 1, 0 ≤ y ≤ 1} ´es f (u) = x + y1 ?
6
3. Konvex halmazok 3.1. Defin´ıci´ o. U ⊂ Rn konvex, ha ∀u, v ∈ U, α ∈ [0, 1] eset´en: αu + (1 − α)v ∈ U
3.1. M˝ uveletek konvex halmazokkal
3.1.1. Defin´ıci´ o. • Halmazok ¨ osszege: Ai ⊂ Rn , i = 1, . . . , m eset´en A=
m P
Ai = {a ∈ Rn : a =
i=1
m P
ai , ai ∈ Ai }.
i=1
• Halmazok k¨ ul¨ onbs´ege: A, B ⊂ Rn eset´en C = A − B = {c ∈ Rn : c = a − b, a ∈ A, b ∈ B}. • Halmazok skal´ arszorosa: A ⊂ Rn , λ ∈ R eset´en B = λA = {b ∈ Rn : b = λa, a ∈ A}. • Halmazok Descartes szorzata: Ai ⊂ Rni , i = 1, . . . , m eset´en m
A = A1 × . . . × Am =
× Ai =
i=1
{a = (a1 , . . . , am ) ∈ Rn1 +...+nm : ai ∈ Ai , i = 1, . . . , m}. ´ Megjegyz´ es. Altal´ aban A + A 6= 2A ´es A − A 6= {0}, de 2A ⊂ A + A ´es {0} ⊂ A − A.
3.1.1. T´ etel. Ha Ai , i = 1, . . . , m, A, B az Rn konvex halmazai, akkor 1) A =
m P
Ai , 2) C = A − B, 3) B = λA, λ ∈ R
i=1
is konvex. Bizony´ıt´ as.
1.
a, b ∈ A =⇒ a ∈
m P
b=
i=1 m P
ai ,
ai ∈ Ai
bi ,
bi ∈ Ai
i=1
=⇒ αa + (1 − α)b =
m P i=1
(αai + (1 − α)bi ) ∈ A. | {z } ∈Ai
7
c1 , c2 ∈ C =⇒ c1 = a1 − b1 , a1 ∈ A, b1 ∈ B c2 = a2 − b2 , a2 ∈ A, b2 ∈ B
2.
=⇒ αc1 + (1 − α)c2
= α(a1 − b1 ) + (1 − α)(a2 − b2 ) = (αa1 + (1 − α)a2 ) − (αb1 + (1 − α)b2 ) ∈ C. | {z } | {z } ∈A
∈B
a, b ∈ B =⇒ a = λa0 , b = λb0 , a0 , b0 ∈ A
3.
=⇒ αa + (1 − α)b = λ(αa0 + (1 − α)b0 ) ∈ B. | {z } ∈A
m
3.1.2. T´ etel. Ha Ai ⊂ Rni , i = 1, . . . , m, konvex halmazok akkor A =
× Ai is konvex.
i=1
Bizony´ıt´ as. m
a, b ∈
× Ai =⇒
i=1
a = (a1 , . . . , am ), b = (b1 , . . . , bm ), bi ∈ Ai , i = 1, . . . , m =⇒ m
λa + (1 − λ)b = (λa1 + (1 − λ)b1 , . . . , λam + (1 − λ)bm ) ∈ × Ai . {z } | {z } | i=1 ∈A1
∈Am
3.1.3. T´ etel. Ha Ai ⊂ Rn , i = 1, . . . , m, konvex halmazok, akkor a C =
m T
Ai halmaz is konvex.
i=1
Bizony´ıt´ as. a, b ∈ C =⇒ a, b ∈ Ai ∀i = 1, . . . , m =⇒ αa + (1 − α)b ∈ Ai ∀i = 1, . . . , m =⇒ αa + (1 − α)b ∈
m T
Ai = C.
i=1
3.1.2. Defin´ıci´ o. Az {u1 , . . . , um } ⊂ U pontrendszer konvex kombin´ aci´ oja az u = ahol αi ≥ 0 (i = 1, . . . , m) ´es
m P
m P
αi ui pont,
i=1
αi = 1.
i=1
3.1.4. T´ etel. Az U ⊆ Rn halmaz akkor ´es csak akkor konvex, ha tartalmazza b´ armely v´eges sz´ am´ u elem´enek konvex kombin´ aci´ oj´ at.
8
Bizony´ıt´ as. El´egs´egess´eg. Ha U tartalmazza b´ armely v´eges sz´am´ u elem´enek konvex kombin´aci´oj´at, akkor b´armely k´et elem´enek konvex kombin´ aci´ oj´ at is tartalmazza, ´ıgy defin´ıci´o szerint konvex. Sz¨ uks´egess´eg. Teljes indukci´ oval bizony´ıtunk. Mivel U konvex, tartalmazza b´ armely k´et elem´enek konvex kombin´aci´oj´at. Tegy¨ uk fel, hogy U tartalmazza b´ armely m − 1 elem´enek konvex kombin´aci´oj´at. Legyen u=
m P
αi ui , 0 ≤ αi ≤ 1,
i=1
m P
αi = 1.
i=1
Ha valamelyik αi = 0, akkor u el˝ o´ all a t¨ obbi, (m − 1) sz´am´ u uj (j 6= i) konvex kombin´aci´ojak´ent, ´ıgy u ∈ U . Legyen 0 < αi < 1 (i = 1, . . . , m) ´es vezess¨ uk be a βi = 1 −αiα (i = 1, . . . , m−1) v´altoz´okat. m m−1 m−1 P P Nyilv´anval´ oan 0 < βi < 1 (i = 1, . . . , m) ´es βi = 1, tov´abb´a v = βi ui ∈ U . i=1
i=1
Mivel u = (1 − αm )v + αm um , ´ıgy u ∈ U .
3.1.3. Defin´ıci´ o. Az U -t tartalmaz´ o konvex halmazok metszete az U konvex burka. Jele: co U . Nyilv´anval´ oan co U a legsz˝ ukebb U -t tartalmaz´o konvex halmaz.
3.1.5. T´ etel. U konvex burka a v´eges sok U -beli elem konvex kombin´ aci´ ojak´ent el˝ o´ all´ o pontok halmaza. Bizony´ıt´ as. Legyen W az U -beli elemek v´egeselem˝ u konvex kombin´aci´oinak a halmaza. Nyilv´anval´oan U ⊆ W . Mivel U ⊆ co U ´es co U konvex, ´ıgy tartalmazza a co U -beli elemek v´eges elemsz´am´ u konvex kombin´aci´oit, ´ıgy az U -beliek´et is, azaz co U ⊇ W . M´asr´eszt, W konvex. Ugyanis, ha u=
p P
αi ui , ui ∈ W, 0 ≤ αi ≤ 1 (i = 1, . . . , p),
i=1
p P
αi = 1
i=1
´es v=
q P
βi vi , vi ∈ W, 0 ≤ βi ≤ 1 (i = 1, . . . , q),
i=1
q P
βi = 1,
i=1
akkor vα = αu + (1 − α)v =
p P
q P ααi ui + (1 − α)βi vi ; |{z} {z } i=1 i=1 | ≥0
p P i=1
ααi +
q P
≥0
(1 − α)βi = 1,
i=1
´ıgy vα konvex kombin´ aci´ oja p + q sz´am´ u elemnek, azaz vα ∈ W . Mivel co U a legsz˝ ukebb U -t tartalmaz´ o konvex halmaz, ez´ert co U ⊆ W .
9
3.2. Feladatok 3.2.1. Feladat. (Carath` eodory t´ etele) Legyen U ⊆ Rn , konvex halmaz, U 6= ∅. Jel¨ olje co U az U halmaz konvex burk´ at. Bizony´ıtsuk be, hogy ∀u ∈ co U el˝ o´ all´ıthat´ o n + 1-n´el nem t¨ obb U -beli pont konvex kombin´ aci´ ojak´ent. Bizony´ ıt´ as. m P
Legyen u ∈ co U . Mivel co U konvex, ´ıgy u =
αi ui , ahol
i=1
m P
αi = 1 ´ es αi > 0, ui ∈ U (i = 1, . . . , m). (Az αi -k
i=1
pozitivit´ as´ anak felt´ etelez´ ese jogos, mert u el˝ o´ all´ıt´ as´ aban a 0 egy¨ utthat´ oj´ u tagok elhagy´ asa cs¨ okkenti az el˝ o´ all´ıt´ o pontok sz´ am´ at.) Ha m ≤ n + 1, akkor a t´ etel ´ all´ıt´ asa nyilv´ an teljes¨ ul. Legyen m > n + 1. Vegy¨ uk az ui ∈ R
n+1
,
ui = (ui , 1) m P
pontokat. Mivel m > n + 1, ezek line´ arisan ¨ osszef¨ ugg˝ ok. K¨ ovetkez´ esk´ eppen ∃γi (i = 1, . . . , m), melyre
|γi | 6= 0 ´ es
i=1 m P
γi ui = 0, vagyis
i=1 m P
γi u i
=
0
=
0.
i=1 m P
γi
i=1
Inn´ et u=
m P
αi ui =
i=1
m P
αi ui − t
i=1
m P
γi u i =
i=1
m P
(αi − tγi )ui .
i=1
| {z } =0
m P
Ha t el´ eg kis pozit´ıv sz´ am, akkor αi − tγi ≥ 0. Mivel
|γi | 6= 0, de
i=1
m P
γi = 0, ez´ ert ∃γi > 0.
i=1
Jel¨ olje t=
αs αi = min . γi >0 γi γs
Inn´ et αi − tγi ≥ 0 (i = 1, . . . , m) , mik¨ ozben m P αs − tγs = 0 ´ es (αi − tγi ) = 1, i=1
´ıgy u =
m P
(αi − tγi )ui , azaz az u-t el˝ o´ all´ıt´ o pontok sz´ ama eggyel cs¨ okkent. Ez a cs¨ okkent´ es mindaddig folytathat´ o az
i=1,i6=s
el˝ obbiek szerint am´ıg az {ui } vektorrendszer line´ aris ¨ osszef¨ ugg˝ os´ ege meg nem sz˝ unik, azaz az el˝ o´ all´ıt´ o komponensek sz´ ama legfeljebb n + 1 nem lesz.
3.2.2. Feladat. Legyenek U, V ⊆ Rn nem¨ ures halmazok. Mutassuk meg, hogy co (U ∩ V ) ⊆ (co U ) ∩ (co V ). Mutassunk p´eld´ at, amikor szigor´ u tartalmaz´ as teljes¨ ul. 3.2.3. Feladat. Jel¨ olje int U ´es U az U ⊆ Rn konvex halmaz belsej´et ill. lez´ artj´ at. Legyen u ∈ int U ´es v ∈ U . Mutassuk meg, hogy w = αu + (1 − α)v ∈ int U minden α ∈ (0, 1] eset´en. 3.2.4. Feladat. Mutassuk meg, hogy int U ´es U konvex halmazok, ha U ⊆ Rn konvex. 3.2.5. Feladat. Konvexek-e az al´ abbi halmazok (haszn´ alhatja a k¨ ovetkez˝ o fejezet eredm´enyeit is): 1.) U = {u = (x, y) ∈ R2 : x2 + 3y 2 ≤ 8, 3x − 7y ≥ 1, x3 + 2x2 + y 2 + y ≤ 7, x, y ≥ 0}; 2.) U = {u = (x, y, z) ∈ R3 : x2 + y 2 ≤ z}; 10
3.) U = {u = (x, y, z) ∈ R3 : x + y < 3, −x + y + z ≤ 5, x, y, z ≥ 0}; 4.) U = {u = (x, y, z) ∈ R3 : x2 + y 2 + z 2 ≤ 4, x + y + z = 1}; 5.) U = {u = (x, y) ∈ R2 : 0 ≤ x ≤ 2, (x − 3)2 + (y − 2)2 ≤ 2, 2y + x ≥ 3, x − (y − 3)2 ≥ 3}; 6.) U = {u = (x, y) ∈ R2 : 0 ≤ x ≤ 2, (x − 1)2 + (y − 2)2 ≤ 2, y − x ≤ 1, (x − 1)2 + y ≤ 1}; 7.) U = {u = (x, y) ∈ R2 : 0 ≤ x ≤ 2π, y ≥ 0, y − sin(x) ≤ 0, y + (x − 1)2 ≤ 2}; 8.) U = {(x, y, z) ∈ R3 : 8x + y + 2z ≥ 7, x2 + 3y 2 + 7z ≤ 10, 2 (x + 1)−2 + 3y 2 + e−2z ≥ 0, x, y, z ≥ 0}; 9.) U = {u = (x, y) ∈ R2 : 0 ≤ x ≤ 1, y ≥ 0, x2 + y 2 ≤ 2, 1 ≤ 1, y− x x + 3y ≤ 3}? 3.2.6. Feladat. Mi a 3.2.5. Feladatban defini´ alt halmazok belseje, lez´ artja, hat´ ara?
11
4. Konvex fu enyek ¨ ggv´ 4.1. Defin´ıci´ o. Az f : Rn → R f¨ uggv´eny konvex a konvex U ⊂ D(f ) halmazon, ha ∀u, v ∈ U ´es λ ∈ [0, 1] eset´en f (λu + (1 − λ)v) ≤ λf (u) + (1 − λ)f (v).
(4.1)
Az f (u) f¨ uggv´eny szigor´ uan konvex, ha a (4.1)-ben az egyenl˝ os´eg csak λ = 0 ´es λ = 1 eset´en ´ all fenn, azaz f (λu + (1 − λ)v) < λf (u) + (1 − λ)f (v) ∀λ ∈ (0, 1). f (u) konk´ av, ha −f (u) konvex.
4.1. Konvex fu enyek karakteriz´ aci´ oi ¨ ggv´ 4.1.1. T´ etel. (Jensen egyenl˝ otlens´ eg) Ha az f : Rn → R f¨ uggv´eny konvex a konvex U ⊂ D(f ) m P halmazon, akkor ∀ui ∈ U, λi ≥ 0, i = 1, . . . , m ´es λi = 1 eset´en i=1
f(
m P
λi u i ) ≤
i=1
m P
λi f (ui ).
i=1
Bizony´ıt´ as. U konvexit´ asa miatt
m P
λi ui ∈ U . Teljes indukci´oval a bizony´ıt´as trivi´alis.
i=1
4.1.2. T´ etel. Legyen f ∈ C 1 (U ) (egyszer folytonosan differenci´ alhat´ o) a konvex U ⊂ D(f ) halmazon. f (u) konvex ⇐⇒ f (u) ≥ f (v) + hf 0 (v), u − vi
∀u, v ∈ U.
(4.1)
Bizony´ıt´ as. Sz¨ uks´egess´eg. f (u) konvex =⇒ f (v + α(u − v)) − f (v) ≤ α[f (u) − f (v)] ∀u, v ∈ U ´es α > 0. A Lagrange k¨ oz´ep´ert´ekt´etel szerint: αhf 0 (v + ϑα(u − v)), u − vi ≤ α[f (u) − f (v)]
(4.2)
∀u, v ∈ U ´es valamilyen ϑ ∈ [0, 1] eset´en. Az α > 0-val osztva ´es α → 0 eset´en (4.2)-b´ol kapjuk, hogy hf 0 (v), u − vi ≤ f (u) − f (v). El´egs´egess´eg. Tegy¨ uk fel, hogy teljes¨ ul a (4.1) felt´etel. Legyen u, v ∈ U ´es uα = αu + (1 − α)v. Akkor f (u) − f (uα ) ≥ f (v) − f (uα ) ≥
hf 0 (uα ), u − uα i hf 0 (uα ), v − uα i.
Itt az els˝o egyenl˝ otlens´eget α-val, a m´ asodikat 1−α-val szorozva ´es a k´et egyenl˝otlens´eget ¨osszeadva kapjuk, hogy αf (u) + (1 − α)f (v) − f (uα ) ≥ hf 0 (uα ), αu + (1 − α)v − uα i = 0. | {z } =0
12
4.1.3. T´ etel. Legyen f (u) ∈ C 1 (U ) (egyszer folytonosan differenci´ alhat´ o) az U ⊂ D(f ) konvex halmazon. f (u) konvex U -n ⇐⇒ hf 0 (u) − f 0 (v), u − vi ≥ 0
∀u, v ∈ U.
(4.3)
Bizony´ıt´ as. Sz¨ uks´egess´eg. Ha f (u) konvex, akkor a 4.1.2.T´etel alapj´an f (u) − f (v) ≥ hf 0 (v), u − vi, f (v) − f (u) ≥ hf 0 (u), v − ui. A k´et egyenl˝ otlens´eget ¨ osszeadva: 0 ≥ hf 0 (v) − f 0 (u), u − vi. El´egs´egess´eg. αf (u) + (1 − α)f (v) − f (αu + (1 − α)v) = α[f (u) − f (αu + (1 − α)v)] + (1 − α)[f (v) − f (αu + (1 − α)v)] Z 1 =α hf 0 (αu + (1 − α)v + t(u − αu − (1 − α)v)), u − αu − (1 − α)vidt+ 0 1
Z
hf 0 (αu + (1 − α)v + t(v − αu − (1 − α)v)), v − αu − (1 − α)vidt
+(1 − α) 0
Z
1
hf 0 (αu + (1 − α)v + t(1 − α)(u − v)) | {z }
= α(1 − α) 0
=z1
−f 0 (αu + (1 − α)v + tα(v − u)), u − vidt | {z } =z2
Z
1
= α(1 − α) 0
1 hf 0 (z1 ) − f 0 (z2 ), z1 − z2 i dt ≥ 0. | {z }t ≥0
4.1.4. T´ etel. Legyen f (u) ∈ C 2 (U ) (k´etszer folytonosan differenci´ alhat´ o) a ny´ılt konvex U ⊂ Rn halmazon. f (u) konvex U -n ⇐⇒ hf 00 (u)ξ, ξi ≥ 0
∀u ∈ U, ∀ξ ∈ Rn .
(4.4)
Bizony´ıt´ as. Sz¨ uks´egess´eg. Legyen u ∈ U ´es v´ alasszunk tetsz˝oleges ξ ∈ Rn vektort. U ny´ılts´aga miatt ∃ε0 > 0 u ´gy, hogy ∀ε : |ε| < ε0 eset´en u + εξ ∈ U . A 4.1.3. T´etel szerint hf 0 (u + εξ) − f 0 (u), εξi ≥ 0. A Lagrange k¨ oz´ep´ert´ekt´etelt alkalmazva: hf 00 (u + ϑεξ)ξ, ξiε2 ≥ 0, azaz hf 00 (u + ϑεξ)ξ, ξi ≥ 0 ∀0 ≤ ϑ ≤ 1 ´es ∀ε : |ε| ≤ ε0 . 13
Mivel f 00 (u) folytonos, ε ↓ 0-val kapjuk a t´etel ´all´ıt´as´at. El´egs´egess´eg. Legyen u, v ∈ U, α ∈ [0, 1], ξ = u − v. A Lagrange k¨oz´ep´ert´ekt´etel szerint ∃ϑ ∈ [0, 1], hogy hf 0 (u) − f 0 (v), u − vi = hf 00 (v + ϑ(u − v))(u − v), u − vi = hf 00 (v + ϑξ)ξ, ξi ≥ 0 a t´etel felt´etele miatt, ami a 4.1.3 T´etel szerint biztos´ıtja f konvexit´as´at.
4.2. Konvex fu enyek fu enyei ¨ ggv´ ¨ ggv´
4.2.1. T´ etel. Legyenek az fi (u), i = 1, . . . , m, konvexek a konvex U ⊂ a f (u) =
n T
D(fi ) halmazon. Akkor
i=1
m P
αi fi (u) f¨ uggv´eny is konvex U -n minden αi ≥ 0, i = 1, . . . , m, eset´en.
i=1
Bizony´ıt´ as. Legyen u, v ∈ U, β ∈ [0, 1]. m m P P f (βu + (1 − β)v) = αi fi (βu + (1 − β)v) ≤ αi [βfi (u) + (1 − β)fi (v)] i=1
=β
m P
i=1
αi fi (u) + (1 − β)
i=1
m P
αi fi (v) = βf (u) + (1 − β)f (v).
i=1
4.2.2. T´ etel. Legyenek az fi (u), i = 1, . . . , m, konvexek a konvex U ⊂
m T
D(fi ) halmazon. Akkor
i=1
az f (u) =
sup
fi (u) f¨ uggv´eny is konvex U -n.
i=1,...,m
Bizony´ıt´ as. Legyen u, v ∈ U, β ∈ [0, 1] ´es uβ = βu + (1 − β)v. Ekkor ∀ε > 0-hoz ∃i = i(ε, β) ∈ {1, . . . , m} u ´gy, hogy f (uβ ) ≤ fi (uβ ) + ε ≤ βfi (u) + (1 − β)fi (v) + ε, ∀ε > 0. ε → 0 -val kapjuk a t´etel ´ all´ıt´ as´ at.
4.2.2.1. K¨ ovetkezm´ eny. g + (u) = max(g(u), 0) konvex, ha g(u) konvex. Bizony´ıt´ as. Trivi´alis. 4.2.3. T´ etel. Ha ϕ(t) monoton n¨ ov˝ o konvex f¨ uggv´eny az [a, b] ⊂ R intervallumon ´es a g(u) f¨ uggv´eny konvex a konvex U ⊂ D(f ) halmazon, tov´ abb´ a ∀u ∈ U : g(u) ∈ [a, b], akkor az f (u) = ϕ(g(u)) f¨ uggv´eny is konvex U -n. Bizony´ıt´ as. Legyen u, v ∈ U, ´es β ∈ [0, 1]. f (βu + (1 − β)v)
= ϕ(g(βu + (1 − β)v)) ≤ ϕ(βg(u) + (1 − β)g(v)) ≤ βϕ(g(u)) + (1 − β)ϕ(g(v)).
14
4.2.3.1. K¨ ovetkezm´ eny. Ha g(u) konvex f¨ uggv´eny a konvex U ⊂ D(g) halmazon, akkor az f (u) = g p (u), p ≥ 1, f (u) = (max(0, g(u)))p = g + (u)p , p ≥ 1, 1 f (u) = − , ha g(u) < 0 ∀u ∈ U, g(u) 1 f (u) = max(0, ln )p , ha g(u) < 0 ∀u ∈ U, p ≥ 1 −g(u) f¨ uggv´enyek is konvexek U -n. Bizony´ıt´ as. Trivi´alis.
4.3. Konvex fu enyekkel defini´ alt halmazok ¨ ggv´
4.3.1. T´ etel. A konvex D(f ) ⊆ Rn halmazon ´ertelmezett f (u) f¨ uggv´eny akkor ´es csak akkor konvex, ha epi f konvex. Bizony´ıt´ as. Sz¨ uks´egess´eg. Legyen z1 = (u1 , η1 ) ∈ epi f,
z2 = (u2 , η2 ) ∈ epi f,
´es zα = (αu1 + (1 − α)u2 , αη1 + (1 − α)η2 ). | {z } =uα ∈U
f (u) konvexit´ asa miatt f (uα ) ≤ αf (u1 ) + (1 − α)f (u2 ) ≤ αη1 + (1 − α)η2 , k¨ovetkez´esk´eppen zα ∈ epi f . El´egs´egess´eg. Legyen u1 , u2 ∈ U, z1 = (u1 , f (u1 )) ∈ epi f, z2 = (u2 , f (u2 )) ∈ epi f. Az U halmaz ´es az epi f konvexit´ asa miatt zα = (αu1 + (1 − α)u2 , αf (u1 ) + (1 − α)f (u2 )) ∈ epi f, k¨ovetkez´esk´eppen αu1 + (1 − α)u2 ∈ U, ´es αf (u1 ) + (1 − α)f (u2 ) ≥ f (αu1 + (1 − α)u2 ).
4.3.2. T´ etel. Legyen f (u) konvex a konvex U ⊂ D(f ) halmazon. Akkor az M (c) = {u ∈ U : f (u) ≤ c} szinthalmaz is konvex ∀c ∈ R.
15
Bizony´ıt´ as. Legyen c ∈ R. u, v ∈ M (c) =⇒ f (u) ≤ c ´es f (v) ≤ c =⇒ f (αu + (1 − α)v) ≤ αf (u) + (1 − α)f (v) ≤ c ∀α ∈ [0, 1] =⇒ αu + (1 − α)v ∈ M (c).
4.3.3. T´ etel. Legyen U0 ⊆
m T
D(gi ) konvex ´es legyenek a gi (u), i = 1, . . . , m f¨ uggv´enyek konvexek
i=1
U0 -n, tov´ abb´ a legyenek a hi (u); i = m+1, . . . , s f¨ uggv´enyek line´ arisak, azaz hi (u) = hai , ui−bi , i = m + 1, . . . , s. Akkor az U = {u ∈ U0 : gi (u) ≤ 0, i = 1, . . . , m, hi (u) = 0, i = m + 1, . . . , s} halmaz is konvex. Bizony´ıt´ as. s T U= Ui , ahol i=1
Ui Ui
= {u ∈ U0 : gi (u) ≤ 0}, i = 1, . . . , m, = {u ∈ U0 : hi (u) = 0}, i = m + 1, . . . , s.
A 4.3.2. T´etel alapj´ an az Ui , i = 1, . . . , m halmazok konvexek. Az Ui , i = m + 1, . . . , s halmazok alterek, ´ıgy szint´en konvexek. A 3.1.1. T´etel szerint a konvex halmazok metszete is konvex.
16
4.4. Feladatok 4.4.1. Feladat. Konvexek-e az al´ abbi f¨ uggv´enyek: 1.) f : Rn → R, f (u) =k u k, 2.) f : R2 → Rn , f (u1 , u2 ) = u21 + 2u1 u2 − 10u1 + 5u2 , 3.) f : R2 → Rn , f (u1 , u2 ) = u1 e−(u1 +u2 ) . 4.4.2. Feladat. Konvexek-e az al´ abbi f f¨ uggv´enyek az adott U halmazon? √ 1.) f : U → R, f (u) = − u, U = {u ∈ R : u ≥ 0}, 1 , 0))p , p ≥ 1, 20 − (u21 + u42 ) U = {u = (u1 , u2 ) ∈ R2 : u21 + u42 < 20},
2.) f : U → R, f (u1 , u2 ) = (max(ln
3.) f : R2 → R, f (u1 , u2 ) = 2(u2 − u21 )2 − 10, U = {(u1 , u2 ) : −1 ≤ u1 ≤ 1, −1 ≤ u2 ≤ 1}. 4.4.3. Feladat. Legyen g : Rn → R konvex f¨ uggv´eny. Mutassuk meg, hogy az 1.) f (u) = max(g(u), 0), U = Rn ; 2.) f (u) = − 1 , U = {u ∈ Rn : g(u) ≤ 0} g(u) f¨ uggv´enyek is konvexek az adott U halmazon. 4.4.4. Feladat. Hat´ arozza meg az al´ abbi f¨ uggv´enyek konvexit´ asi ´es konk´ avit´ asi tartom´ anyait: 1.) f (x, y) = sin(x + y + z), (x, y, z) ∈ R3 ; 2.) f (x, y) = sin(x2 + y 2 ), (x, y) ∈ R2 ; 3.) f (x, y, z) = sin(x2 + y 2 + z 2 ), (x, y, z) ∈ R3 ; 4.4.5. Feladat. Tegy¨ uk fel, hogy az f : Rn → R f¨ uggv´eny olyan, hogy |f (u)| konvex. Mutassuk meg, hogy az U = {u ∈ Rn : f (u) = 0} halmaz konvex. 4.4.6. Feladat. Mutassuk meg, hogy minden ui R, λi ≥ 0(i = 1, . . . , m),
m P
λi = 1 eset´en
i=1 m P
λi ui ≤ ln
m P
i=1
λi e
ui
!
i=1
4.4.7. Feladat. Mutassa meg, hogy minden ui > 0, λi ≥ 0 (i = 1, . . . , m),
m P
λi = 1 eset´en
i=1
m P i=1
m P λi λi u i ui ≥ 1! i=1
4.4.8. Feladat. Mutassa meg, hogy minden ui > 0, λi ≥ 0 (i = 1, . . . , m),
m P i=1
m P i=1
λi u i
≥
m Y
uλi i !
i
17
λi = 1 eset´en
4.4.9. Feladat. Igazolja, hogy minden n term´eszetes sz´ amra 1+e
1 n
n P i=1
xi
≤
n Y
1
(1 + exi ) n !
i=1
4.4.10. Feladat. Igazolja, hogy ln(1 + e
x2 +y 2 4
)≤
y2 x2 1 1 ln(1 + e 2 ) + ln(1 + e 2 )! 2 2
4.4.11. Feladat. Igazolja, hogy minden n term´eszetes sz´ amra v u n n q X u 1X 2 ≤ t1 + 1 ( x ) 1 + x2i ! i n i=1 n2 i=1
18
5. Felt´ eteles sz´ els˝ o´ ert´ ekprobl´ em´ ak Legyen f : Rn → R. Legyenek tov´ abb´ a az Ui ⊂ Rn , i = 0, . . . , m + 1, halmazok olyanok, hogy int Ui 6= ∅ ∀i = 0, . . . , m ´es int Um+1 = ∅, ahol int U = {u ∈ U : ∃Oε (u) ⊂ U k¨ ornyezet} m+1 T Jel¨olje U = Ui . i=0
uk az Az ´altal´ anos felt´eteles sz´els˝ o´ert´ekprobl´ema: Keress¨ f∗ = inf f (u)
(5.1)
u∈U
f¨ uggv´eny´ert´eket, ´es az azt realiz´ al´ o u∗ ∈ U pontot (ha egy´altal´an ilyen l´etezik). m+1 T Az U = Ui halmazt a (5.1) probl´ema megengedett tartom´any´anak nevezz¨ uk. i=0
5.1. T´ etel. u∗ ∈ U∗ ⇐⇒
m+1 T
Ui = U ∩ U−1 = ∅, ahol U−1 = {u ∈ Rn : f (u) < f (u∗ )}.
i=−1
Bizony´ıt´ as. Sz¨ uks´egess´eg. Tegy¨ uk fel, hogy ∃v ∈
m+1 T
Ui . Mivel v ∈ U−1 , ´ıgy f (v) < f (u∗ ), azaz u∗ nem
i=−1
minimumpont, ami ellentmond´ as. m+1 T Ui = ∅. Akkor ∀u ∈ U eset´en u 6∈ U−1 , azaz f (u) ≥ f (u∗ ), azaz u∗ El´egs´egess´eg. Legyen i=−1
minimumpont. Speci´alisan matematikai programoz´ asi feladatnak nevezz¨ uk a (5.1) probl´em´at, ha a korl´atoz´o felt´etelek a k¨ ovetkez˝ o alak´ u halmazokkal adottak: •
Ui = {u ∈ Rn : gi (u) ≤ 0} (i = 1, . . . , m), egyenl˝ otlens´eg t´ıpus´ u felt´etelek, ahol gi ∈ F(Rn ) (i = 1, . . . , m);
•
Vi = {u ∈ Rn : gi (u) = 0} (i = 1, . . . , s), egyenl˝ os´eg tipus´ u felt´etelek, ahol gi ∈ F(Rn ) (i = 1, . . . , s);
•
U0 ⊂ Rn ,
int U0 6= ∅.
Nyilv´anval´ oan int Vi = ∅, ´ıgy Um+1 =
s T
Vi vehet˝o.
i=1
U0 -k´ent azokat a felt´eteleket vessz¨ uk, amiknek egyszer˝ u strukt´ ur´aja van (pl. valamely ort´ans, speci´alis k´ up stb.). Megengedj¨ uk, hogy b´ armelyik t´ıpus´ u felt´etel elmaradjon. uk, ha a korl´atoA matematikai programoz´ asi feladatot konvex programoz´asi feladatnak nevezz¨ z´o U ⊆ Rn halmaz konvex ´es a minimaliz´aland´o f f¨ uggv´eny konvex U -n. Nyilv´anval´ o, hogy ha a minimaliz´ aland´o f f¨ uggv´eny ´es a nemline´aris egyenl˝otlens´eg t´ıpus´ u felt´eteleket ad´ o gi f¨ uggv´enyek konvexek, az egyenl˝os´eg t´ıpus´ u felt´etelekat ad´o gi f¨ uggv´enyek pedig line´arisak, akkor az optimaliz´ al´ asi feladat konvex programoz´asi feladat.
19
5.1. Feladatok 5.1.1. Feladat. Irja fel az al´ abbi feladatok modellj´et nemline´ aris programoz´ asi feladattal: 1.) Melyik az az egys´egsugar´ u k¨ orbe ´ırt h´ aromsz¨ og, melynek olalainak a n´egyzet¨ osszege maxim´ alis? 2.) Hat´ arozza meg az U = {u = (x, y) ∈ R2 : 2x + y ≤ 4, x + y ≤ 1} halmaznak a (2, 0) ponthoz legk¨ ozelebbi nemnegat´ıv koordin´ at´ aj´ u pontj´ at! 3.) Hat´ arozza meg az U = {u = (x, y) ∈ R2 : x − 2y ≤ 6, −2x + y ≤ 6} halmaznak a (1, 3) ponthoz legk¨ ozelebbi nemnegat´ıv koordin´ at´ aj´ u pontj´ at! 4.) Legyenek α, β, γ egy h´ aromsz¨ og sz¨ ogei. Igazolja a k¨ ovetkez˝ o egyenl˝ otlens´eget: sin
α β γ 1 sin sin ≤ ! 2 2 2 8
5.) Igazolja, hogy ln(1 + e
x2 +y 2 4
)≤
y2 x2 1 1 ln(1 + e 2 ) + ln(1 + e 2 )! 2 2
6.) Igazolja, hogy minden n term´eszetes sz´ amra v u n q n X u 1X 2 ≤ t1 + 1 ( x ) 1 + x2i ! i n i=1 n2 i=1 7.) Igazolja, hogy minden n term´eszetes sz´ am ´es α > 0 eset´en n P
(2i − 1)α ≥ nα+1 !
i=1
5.1.2. Feladat. Konvex programoz´ asi feladatok-e az al´ abbi probl´em´ ak: 1.) 2 xy 150 y+ xy x, y x+
→
min
≤
1
≥
0
2.) x + xy y + sin xy x, y
→ min ≤ 1 ≥ 0
3.) x+y x2 + y x, y
→ min = 5 ≥ 0
20
6. Lagrange multiplik´ atorok m´ odszere Ha csak egyenl˝ os´eg t´ıpus´ u felt´etelek szerepelnek, azaz ha f, gi ∈ C 1 (Rn ), (i = 1, . . . , m), akkor az f∗ = inf f (u)
(6.1)
U = {u ∈ Rn : gi (u) = 0 (i = 1, . . . , s)},
(6.2)
u∈U
feladatra az optimalit´ as sz¨ uks´eges felt´etel´et a klasszikus anal´ızisb˝ol ismert Lagrange multiplik´atororok t´etele adja. A t´etel egyszer˝ ubb kezel´ese ´erdek´eben vezess¨ unk be n´eh´any fogalmat.
6.1. Defin´ıci´ o. F : Rn → Rs f¨ uggv´eny vektorf¨ uggv´eny, ha F = (f1 , . . . , fs ) ´es fi : Rn → R (i = 1, . . . , s). Az F vektorf¨ uggv´eny ´ertelmez´esi tartom´ anya D(f ) =
s T
D(fi ).
i=1
6.2. Defin´ıci´ o. Az F = (f1 , . . . , fs ) : Rn → Rs vektorf¨ uggv´eny folytonos az u ∈ Rn pontban, ha ott minden fi (i = 1, . . . , s) f¨ uggv´eny folytonos.
6.3. Defin´ıci´ o. Legyen u = (v, w) ∈ Rm × Rn−m . Az F = (f1 , . . . , fs ) : Rm × Rn−m → Rs vektorf¨ uggv´eny [ folytonosan ] differenci´ alhat´ o az u ∈ Rm , ill. a v ∈ Rn−m v´ altoz´ oja szerint, ha minden fi (i = 1, . . . , s) [ folytonosan ] differenci´ alhat´ o u, ill. v szerint. Az fi (u, v) f¨ uggv´enyek u ∈ Rm , ill.v ∈ Rn−m , v´ altoz´ oja szerinti gradienseib˝ ol, mint sorvektorokb´ ol all´ ´ o (s × m), ill. (s × (n − m)) m´ atrixot jel¨ olj¨ uk Fu0 (u, v)-vel ill. Fv0 (u, v)-vel. Megjegyz´es: A deriv´ altakn´ al csak akkor jelezz¨ uk als´o indexkent, hogy melyik v´altoz´o szerinti parci´alis deriv´ altr´ ol van sz´ o, ha az csak egy r´eszvektora a f¨ uggv´eny v´altoz´o-vektor´anak. A vektorf¨ uggv´enyekkel a feladat a k¨ ovetkez˝o alakot ¨olti: f∗ = inf f (u)
(6.3)
U = {u ∈ Rn : G(u) = 0,
(6.4)
u∈U
ahol G : Rn → Rs , G = (g1 , . . . , gs ) ∈ C 1 (Rn ) vektorf¨ uggv´eny. A k¨ovetkez˝ o k´et, a klasszikus anal´ızisb˝ol ugyancsak j´ol ismert t´etelre sz¨ uks´eg¨ unk lesz a bizony´ıt´ashoz, ezeket eml´ekeztet˝ ou ul k¨oz¨olj¨ uk. ¨l bizony´ıt´as n´elk¨
6.1. T´ etel. (Implicit-fu eny t´ etel) Legyen U ⊆ Rn , V ⊆ Rm , F : U × V → Rn , (u0 , v0 ) ∈ ¨ ggv´ U × V ´es teljes¨ uljenek az al´ abbi felt´etelek: 1.) F folytonos az (u0 , v0 ) pontban; 2.) F (u0 , v0 ) = 0; 3.) l´etezik az (u0 , v0 ) ∈ U × V pontnak olyan Oε ((u0 , v0 )) ⊆ U × V k¨ ornyezete, hogy ∀(u, v) ∈ Oε ((u, v)) pontban F folytonosan differenci´ alhat´ o u szerint ´es Fu0 (u0 , v0 ) nem szingul´ aris.
21
Akkor az F (u, v) = 0 egyenlet az (u0 , v0 ) pont valamely k¨ ornyezet´eben megoldhat´ o, azaz l´eteznek olyan δ1 , δ2 > 0 sz´ amok, ´es egy, az Oδ1 (v0 ) k¨ ornyezetben ´ertelmezett ´es a v0 pontban folytonos ϕ = (ϕ1 , . . . , ϕn ) : Rm → Rn vektorf¨ uggv´eny, hogy minden olyan (u, v) eset´en, melyre v ∈ Oδ1 (v0 ) ´es u = ϕ(v), teljes¨ ul az F (u, v) = 0 egyenlet, ´es megford´ıtva, minden olyan (u, v) eset´en, melyre F (u, v) = 0, u ∈ Oδ1 (u0 ) ´es v ∈ Oδ2 (v0 ), fenn´ all az u = ϕ(v) ¨ osszef¨ ugg´es. Ha F v szerint is folytonosan differenci´ alhat´ o az Oε ((u0 , v0 )) k¨ ornyezetben, akkor a ϕ vektorf¨ uggv´eny differenci´ alhat´ o a v0 pontban ´es −1
ϕ0 (v0 ) = − [Fu0 (u0 , v0 )]
Fv0 (u0 , v0 ).
6.2. T´ etel. Legyen F : Rn → Rn vektorf¨ uggv´eny folytonosan differenci´ alhat´ o az u0 ∈ Rn pont Oδ (u0 ) k¨ ornyezet´eben ´es tegy¨ uk fel, hogy Fu0 (u0 ) nem szingul´ aris. Ha F (u0 ) = b0 , akkor b´ armely el´eg kis δ > 0-hoz ∃ε > 0, hogy ∀b ∈ Oε (b0 ) eset´en az F (u) = b egyenletnek pontosan egy u = ϕ(b) ∈ Oδ (u0 ) megold´ asa van ´es ϕ folytonosan differenci´ alhat´ o az Oδ (b0 ) k¨ ornyezetben. A (6.3)-(6.4) feladatra a k¨ ovetkez˝ o optimalit´asi krit´eriumot adhatjuk meg:
6.3. T´ etel. (Lagrange multiplik´ atorok t´ etele) Tegy¨ uk fel, hogy a (6.1)-(6.2) feladatban a G0 (u∗ ) m´ atrix rangja s, azaz az u∗ pontban a gi f¨ uggv´enyek gradiensvektorai line´ arisan f¨ uggetlenek. Ahhoz, hogy u∗ ∈ U∗ = {u ∈ U : f (u) = f∗ } legyen, sz¨ uks´eges, hogy l´etezzen olyan λ∗ = (λ∗1 , . . . , λ∗s ) ∈ Rs vektor u ´gy, hogy az (u∗ , λ∗ ) vektorp´ ar el´eg´ıtse ki a f 0 (u) +
s P i=1
λi gi0 (u) = 0,
gi (u) = 0
(6.5)
(i = 1, . . . , s),
(6.6)
vagy vektoralakban f 0 (u) + G0T (u)λ = 0,
(6.7)
G(u) = 0
(6.8)
egyenletrendszert, ahol G0T a G0 m´ atrix transzpon´ altj´ at jel¨ oli.. Bizony´ıt´ as. Legyen u∗ ∈ U∗ minimumpont. Ha s = n, akkor a 6.2. T´etel szerint az U halmaz egyetlen u∗ ponb´ol ´all ´es G0 (u∗ ) nem szingularit´ asa miatt ebben a pontban −1 0 λ = − G0T (u∗ ) f (u∗ ) kiel´eg´ıti a (6.7) felt´etelt. Legyen s < n. Particion´ aljuk az u vektorok koordin´at´ait u = (v, w), v ∈ Rs , w ∈ Rn−s alakban u ´gy, hogy az u∗ = (v∗ , w∗ ) pontban a G0 (u∗ ) = [G0v (v∗ , w∗ ) G0w (v∗ , w∗ )] m´atrixban a 0 Gv (v∗ , w∗ ) (s × s) alm´ atrix nem szingul´ aris. Mivel u∗ ∈ U , ´ıgy G(u∗ ) = G(v∗ , w∗ ) = 0. Az implicit-f¨ uggv´eny t´etel szerint a w∗ pont l´etezik olyan ϕ(w) differenci´ alhat´ o f¨ uggv´eny, melyre v∗ = ϕ(w∗ );
G(ϕ(w∗ ), w∗ ) = 0 22
´es −1
ϕ0 (w) = − [G0v (ϕ(w), w)]
G0w (ϕ(w), w).
(6.9)
Legyen w ∈ Oδ (w∗ ). Mivel itt G(ϕ(w), w) = 0, ez´ert u = (ϕ(w), w) ∈ U . ´Igy f (ϕ(w∗ ), w∗ ) = f (v∗ , w∗ ) = f (u∗ ) ≤ f (u) = f (ϕ(w), w). K¨ovetkez´esk´eppen az f (ϕ(w), w) = h(w) f¨ uggv´enynek a w = w∗ pontban lok´alis minimuma van. Az optimalit´ as sz¨ uks´eges felt´etele szerint h0 (w∗ ) = 0. Az ¨osszetett f¨ uggv´eny differenci´al´asi szab´alya szerint h0 (w∗ ) = ϕ0T (w∗ )fv0 (ϕ(w∗ ), w∗ ) + fw0 (ϕ(w∗ ), w∗ ). Figyelembe v´eve (6.9)-t ´es a ϕ(w∗ ) = v∗ ¨osszef¨ ugg´est azt kapjuk, hogy −1 0 h0 (w∗ ) = −G0 w (v∗ , w∗ )T G0v (v∗ , w∗ )T fv (v∗ , w∗ ) + fw0 (v∗ , w∗ ) = 0.
(6.10)
Jel¨olje −1 0 λ∗ = − G0v (v∗ , w∗ )T fv (v∗ , w∗ ). A (6.10) ´es (6.11) ¨ osszef¨ ugg´esek a 0 − Gv (v∗ , w∗ )T λ∗ + fv0 (v∗ , w∗ ) − G0w (v∗ , w∗ )T λ∗ + fw0 (v∗ , w∗ )
(6.11)
= 0 = 0
rendszert adj´ ak, ami ekvivalens a G0 (u∗ )T λ∗ + f 0 (u∗ ) = 0 egyenlettel, ami azt jelenti, hogy az (u∗ , λ∗ ) vektorp´ar kiel´eg´ıti a t´etel ´all´ıt´as´at. Vegy¨ uk ´eszre, hogy a t´etelben szerepl˝o (6.5) egyenl˝os´eg a L(u, λ) = f (u) +
s X
gi (u)
i=1
Lagrange fu eny seg´ıts´eg´evel ¨ ggv´ L0u (u∗ , λ∗ ) = 0 alakot ¨olti.
23
6.1. Feladatok 6.1.1. Feladat. Oldja meg Lagrange multiplik´ atorok m´ odszer´evel a k¨ ovetkez˝ o feladatokat: 1.)
−2x2 + 4xy + y 2 → min . x2 + y 2 = 1
2.)
1 → min . x2 + y 2 + z 2 x2 + 2y 2 + 3z 2 = 0 x+y+z =0
3.)
1 (x2 + y 2 + z 2 ) → min . 2 z − xy = 5
6.1.2. Feladat. Keress¨ uk meg a minimum´ at ´es a maximum´ at az f (x, y, z) = 2x2 + 5y 2 + 11z 2 + 20xy − 4xz + 16yz f¨ uggv´enynek az egys´egg¨ omb fel¨ ulet´en? 6.1.3. Feladat. Hat´ arozza meg az orig´ onak az z − xy = 5 fel¨ ulett˝ ol val´ o t´ avols´ ag´ at. 6.1.4. Feladat. Hat´ arozza meg az (1, 2, 1) pontnak az 2x − y + z = 4 s´ıkt´ ol val´ o t´ avols´ ag´ at. 6.1.5. Feladat. Legyenek α, β, γ egy h´ aromsz¨ og sz¨ ogei. A Lagrange multiplik´ atorok m´ odszere seg´ıts´eg´evel igazolja a k¨ ovetkez˝ o egyenl˝ otlens´egeket: 1.) sin α + sin β + sin γ ≤
√ 3 3 2 ;
2.) cos α + cos β + cos γ ≤ 3 2; 3.) sin α2 sin β2 sin γ2 ≤ 18 . 6.1.6. Feladat. ´ Irjon az egys´egk¨ orbe olyan h´ aromsz¨ oget, melynek oldalainak n´egyzet¨ osszege maxim´ alis. Oldja meg a feladatot a Lagrange multiplik´ atorok m´ odszer´evel. 6.1.7. Feladat. A 5.1.1. Feladat melyik r´eszfeladata oldhat´ o meg Lagrange multiplik´ atorok m´ odszer´ebel? Oldja meg a feladatokat!
24
7. Optimalit´ asi krit´ eriumok 7.1. Szu eges felt´ etelek differenci´ alis alakban ¨ ks´ Tekints¨ uk az f (u) → min
(7.1)
u∈U
feladatot, ahol U = {u ∈ Rn : gi (u) ≤ 0 (i ∈ I), gj (u) = haj , ui − bj ≤ 0 (j ∈ J1 ), gj (u) = haj , ui − bj = 0 (j ∈ J2 )},
(7.2)
ahol f, gi (i ∈ I) ∈ C 1 (Rn ), aj ∈ Rn , bj ∈ R (j ∈ J1 ∪ J2 ), I, J1 ´es J2 v´eges indexhalmazok. Megengedett, hogy az I, J1 , J2 indexhalmazok b´armelyike u u ¨res legyen, azaz valamelyik t´ıpus´ korl´atoz´o felt´etel hi´ anya. Ha mindh´ arom indexhalmaz u uli, azaz Rn -en t¨or¨res akkor felt´etel n´elk¨ t´en˝o mimimaliz´ al´ asr´ ol van sz´o. Az U halmaz el˝ o´ all´ıthat´ o U = U1 ∩ U2 ∩ U3 alakban, ahol U1 U2 U3
= {u ∈ Rn : gi (u) ≤ 0, i ∈ I}, = {u ∈ Rn : gi (u) = haj , ui − bj ≤ 0, j ∈ J1 }, = {u ∈ Rn : gi (u) = haj , ui − bj = 0, j ∈ J2 }.
7.1.1. Defin´ıci´ o. 0 6= s ∈ Rn megengedett ir´ anya az U halmaznak az u ∈ U pontb´ ol, ha ∃ε0 > 0 konstans, hogy u + εs ∈ U ∀ε ∈ [0, ε0 ]. Legyen int U 6= ∅ azaz ∃u ∈ U , hogy annak valamely ny´ılt Oδ (u) k¨ornyezet´ere Oδ (u) ⊂ U . Nyilv´anval´ o, ekkor ∀s ∈ Rn megengedett ir´any az u ∈ int U pontb´ol. Legyen ri U 6= ∅, azaz ha H a legsz˝ ukebb U -t tartalmaz´o affin halmaz, akkor ∃u ∈ U , hogy annak valamely ny´ılt Oδ (u) k¨ ornyezet´ere Oδ (u) ∩ H ⊂ U . Nyilv´anval´oan ekkor H ⊆ U3 ´es ∀s ∈ H megengedett ir´ any az u ∈ ri U pontb´ ol.
7.1.2. Defin´ıci´ o. A gi (u) ≤ 0 (i ∈ I ∪ J1 ) felt´etel akt´ıv az u ∈ U pontban, ha gi (u) = 0 (i ∈ I ∪ J1 ). (Az egyenl˝ os´egt´ıpus´ u felt´etelek konstrukci´ ojukb´ ol ad´ od´ oan mindig akt´ıvak). Az u-beli akt´ıv felt´etelek indexhalmaz´ at jel¨ olje I(u) ∪ J1 (u) ∪ J2 , ahol I(u) J1 (u)
= {i ∈ I : gi (u) = 0} = {j ∈ J1 : haj , ui − bj = 0}.
7.1.1. T´ etel. Ha 0 6= s ∈ Rn megengedett ir´ anya az U halmaznak az u ∈ U pontb´ ol, akkor ∃σ ≥ 0 konstans, hogy (s, σ) ∈ Rn+1 kiel´eg´ıti a hgi0 (u), si + σ ≤ 0 (i ∈ I(u)) haj , si ≤ 0 (j ∈ J1 (u)) haj , si = 0 (j ∈ J2 )
(7.3) (7.4) (7.5)
redszert. Ha a (7.3)-(7.5) rendszernek (s, σ), s 6= 0, σ > 0 megold´ asa, akkor s megengedett ir´ any az u pontb´ ol. 25
Bizony´ıt´ as. Sz¨ uks´egess´eg. Legyen s ∈ Rn egy megengedett ir´any az u ∈ U pontb´ol. A (7.5) felt´etel teljes¨ ul´ese sz¨ uks´eges, mert ha s ∈ Rn egy megengedett ir´any az u ∈ U pontb´ol, akkor ∀j ∈ J2 eset´en ∀ε ∈ [0, ε0 ]-re haj , u + εsi = bj ⇐⇒ haj , ui − bj +εhaj , si = 0, | {z } =0
ahonnan k¨ ovetkezik (7.5). ´Igy ha a (7.3)-(7.5) rendszernek (7.5) teljes¨ ul´ese mellett nem lenne a k´ıv´ant tulajdons´ag´ u megold´asa, akkor ∀0 6= s ∈ Rn ´es σ ≥ 0 eset´en vagy hgi0 (u), si + σ > 0, valamely i ∈ I(u)-ra, vagy haj , si > 0 valamely j ∈ J1 (u)-ra. Az el˝ obbi esetben σ = 0-val hgi0 (u), si > 0. Minthogy
o(ε) ε → 0, ha ε → 0, ´ıgy
gi (u + εs) = g(u) +ε hgi0 (u), si +o(ε) > 0. |{z} | {z } =0
>0
A m´asodik esetben haj , u + εsi = haj , ui +ε haj , si > 0. | {z } | {z } =0
>0
Vagyis azt kapjuk, hogy s egyik esetben sem lenne megengedett ir´any, ami ellentmond´as. El´egs´egess´eg. Legyen u ∈ U ´es tegy¨ uk fel, hogy a (7.3)-(7.5) rendszernek (s, σ), s 6= 0, σ > 0 megold´asa. Ha i ∈ I(u), akkor o(ε) gi (u + εs) = g(u) +ε hgi0 (u), si +o(ε) < ε(−σ + ) < 0, |{z} | {z } ε |{z} =0
<−σ<0
>0
ha ε el´eg kicsi. Ha j ∈ J1 (u), akkor haj , u + εsi − bj = haj , ui − bj +ε haj , si ≤ 0. | {z } | {z } =0
≤0
Ha j ∈ J2 , akkor haj , u + εsi − bj = haj , ui − bj +ε haj , si = 0. | {z } | {z } =0
=0
Ha i 6∈ I(u), akkor gi (u) < 0, ha j 6∈ J(u), akkor haj , ui − bj < 0 ´es gi ill. haj , ui folytonoss´aga miatt el´eg kis ε > 0 eset´en gi (u + εs) > 0 ill. haj , u + εsi − bj < 0 is teljes¨ ul. Vagyis s megengedett ir´any.
26
7.1.3. Defin´ıci´ o. A 0 6= s ∈ Rn vektor az f : Rn → R f¨ uggv´eny cs¨ okken´ esi ir´ anya az u ∈ Rn pontb´ ol, ha ∃ε0 > 0, hogy f (u + εs) < f (u)
∀ε ∈ (0, ε0 ].
7.1.2. T´ etel. Ha 0 6= s ∈ Rn cs¨ okken´esi ir´ anya az f : Rn → R f¨ uggv´enynek akkor ∃σ ≥ 0, hogy (s, σ) kiel´eg´ıti a hf 0 (u), si + σ ≤ 0
(7.6)
egyenl˝ otlens´eget. Ha a (7.6) egyenl˝ otlens´egnek (s, σ) olyan megold´ asa, hogy s 6= 0 ´es σ > 0, akkor s cs¨ okken´esi ir´ anya f -nek. Bizony´ıt´ as. Sz¨ uks´egess´eg. Ha 0 6= s ∈ Rn cs¨ okken´esi ir´anya az f : Rn → R f¨ uggv´enynek, akkor f (u + εs) = f (u) + εhf 0 (u), si + o(ε) < f (u) miatt hf 0 (u), si + Minthogy
o(ε) < 0. ε
o(ε) ε → 0, ha ε → 0, ´ıgy
hf 0 (u), si ≤ 0, amib˝ol k¨ovetkezik a t´etelbeli σ ≥ 0 l´etez´ese. El´egs´egess´eg. Ha a (7.5) egyenl˝ otlens´eg (s, σ) megold´as´ara σ > 0, akkor f (u + εs)
= f (u) + εhf 0 (u), si + o(ε) o(ε) = f (u) + ε(hf 0 (u), si + ) ε o(ε) ≤ f (u) + ε(−σ + ) < f (u), ε
ha ε el´eg kicsi.
7.1.3. T´ etel. Annak, hogy az u ∈ U pont lok´ alis minimumpontja legyen a (7.1)-(7.2) feladatnak, sz¨ uks´eges felt´etele, hogy a (7.3)-(7.6) egyenl˝ otlens´egrendszer minden (s, σ) megold´ as´ ara σ ≤ 0 legyen. Bizony´ıt´ as. Ha a σ ≥ 0 felt´etel teljes¨ ulne a (7.3)-(7.6) egyenl˝otlens´egrendszer valamely (s, σ) megold´as´ara, akkor a 7.1.1. ´es 7.1.2. T´etelek szerint s megengedett ir´anya lenne U -nak az u ∈ U pontb´ol, ugyanakkor ebb˝ ol a pontb´ ol cs¨ okken´esi ir´anya lenne az f f¨ uggv´enynek, vagyis l´etezne olyan ε0 > 0, hogy u + εs ∈ U ´es f (u + εs) < f (u) ∀ε ≤ ε0 , vagyis u nem lenne lok´alis minimumpont.
27
7.1.4. T´ etel. (Fritz-John felt´ etel) Legyen az u ∈ U pont lok´ alis minimumpontja a (7.1)-(7.2) feladatnak Akkor l´eteznek olyan λ0 ≥ 0, λi ≥ 0, i ∈ I, µj ≥ 0, j ∈ J1 ´es ϑ ∈ R, j ∈ J2 nem mind z´erus konstansok, hogy X X X λ0 f 0 (u) + λi gi0 (u) + µj aj + ϑj aj = 0, (7.7) i∈I
j∈J1
j∈J2
. λi gi (u) = 0, i ∈ I, µj (haj , ui − bj ) = 0, j ∈ J1
(7.8)
. Bizony´ıt´ as. A 7.1.3. T´etelb˝ ol a Farkas lemm´ aval kapjuk, hogy l´eteznek olyan λ0 ≥ 0, λi ≥ 0, i ∈ I(u), µj ≥ 0, j ∈ J1 (u) ´es ϑj ∈ R, j ∈ J2 skal´ arok, hogy X X X λ0 f 0 (u) + λi gi0 (u) + µj aj + ϑj aj = 0, (7.9) i∈I(u)
j∈J2
j∈J1 (u)
´es λ0 +
X
λi = 1.
i∈I(u)
Az ut´obbi felt´etel garant´ alja, hogy m´ ar a fenti egyenletben szerepl˝o param´eterek nem mindegyike z´erus. A λi = 0 (i ∈ I \ I(u) ´es µj = 0 (j ∈ J1 \ J1 (u) v´alaszt´assal a t´etel bizony´ıt´asa teljess´e tehet˝o.
7.1.5. T´ etel. (Kuhn-Tucker-f´ ele szu eges felt´ etel) Legyen az u ∈ U pont lok´ alis minimum¨ ks´ pontja a (7.1)-(7.2) feladatnak ´es tegy¨ uk fel, hogy a gi0 (u), i ∈ I(u), aj , j ∈ J1 (u)∪J2 vektorrendszer line´ arisan f¨ uggetlen. Akkor l´eteznek olyan λi ≥ 0, i ∈ I, µj ≥ 0, j ∈ J1 ´es ϑ ∈ R, j ∈ J2 skal´ arok, hogy X X X f 0 (u) + λi gi0 (u) + µj aj + ϑj aj = 0, (7.10) i∈I
j∈J1
j∈J2
´es X i∈I
λi gi (u) +
X
µj (haj , ui − bj ) = 0.
(7.11)
j∈J1
Bizony´ıt´ as. A t´etel felt´etelei mellett teljes¨ ulnek a 7.1.4. T´etel felt´etelei. De most λ0 > 0 lehets´eges csak, mert λ0 = 0 eset´en ellentmond´ asra jutn´ ank a t´etelbeli line´aris f¨ uggetlens´egi felt´etellel. Az ´altal´anoss´ag megszor´ıt´asa n´elk¨ ul feltehetj¨ uk, hogy λ0 = 1. Bevezetve a λi = 0, ha i ∈ / I(u) ´es µj = 0, ha j∈ / J1 (u) param´etereket, a (7.10) ´es (7.9) egyenl˝os´egek ekvivalensek. Ugyanakkor fenn´allnak a λi gi (u) = 0 (i ∈ I) ´es µj (haj , ui − bj ) = 0 (j ∈ J1 ) felt´etelek, amib˝ol (7.11) azonnal ad´ odik.
28
7.2. Feladatok 7.2.1. Feladat. Mi a megengedett ir´ anya 1.) U = {u = (x, y) ∈ R2 : −x3 + y ≤ 0, x, y ≥ 0} halmaznak az u = (0, 0) pontban? 2.) U = {u = (x, y) ∈ R2 : 2x + y ≤ 4, x + y ≤ 1} halmaznak az (1, 3) pontban? 3.) U = {u = (x, y) ∈ R2 : x − y + 3 ≥ 0, −x2 + y − 1 ≥ 0, x, y ≥ 0} halmaznak a (2, 5) ill. a (1, 2) pontokban? 7.2.2. Feladat. A megengedett ir´ anyok m´ odszer´evel ellen˝ orizze hogy, az al´ abbi feladatokra a megadott pont optim´ alis-e? 1.) x2 + y x2 + y 2 x+y
→ min ≤ 9 ≤ 1.
u∗ = (x∗ , y∗ ) = (0, −3). 2.) y x + 3y 2x + 3y x, y 2
→ ≤ ≤ ≥
max 3 4 0
u∗ = (x∗ , y∗ ) = (0, 1). 3.) x + y → min x2 − y ≤ 0 2y + x ≤ 4 u∗ = (x∗ , y∗ ) = (0, 0). 7.2.3. Feladat. Teljes¨ ul-e a 7.2.2. Feladat probl´em´ aira az adott pontokban 1.) a Fritz-John optimalit´ asi krit´erium? 2.) a Kuhn-Tucker-f´ele sz¨ uks´eges optimalit´ asi krit´erium? 7.2.4. Feladat. ´ Irja fel a Kuhn-Tucker optimalit´ asi felt´eteleket az al´ abbi feladatokra, ´es oldja meg ˝ket: o 1.)
3u1 − u2 + u23 →
min
,
(u1 ,u2 )∈U
U = {(u1 , u2 ) ∈ R2 : u1 + u2 + u3 ≤ 0, −u1 + 2u2 + u23 ≤ 0}.
29
2.)
u21 + 4u1 u2 + u22 →
min
,
(u1 ,u2 )∈U
U = {(u1 , u2 ) ∈ R2 : (u1 − 1)2 + u22 ≤ 1}. 3.)
(u1 − 3)2 + (u2 − 2)2 → min ∈ U (u1 ,u2 )
U = {(u1 , u2 ) ∈ R2 : u21 + u22 ≤ 5, u1 + 2u22 ≤ 4, u1 , u2 ≥ 0}.
30
7.3. Konvex MP feladatok optimalit´ asi krit´ eriumai Tegy¨ uk fel, hogy a (7.1)-(7.2) feladatban az f ´es gi , i ∈ I f¨ uggv´enyek konvexek. Ekkor a 4.3.3. T´etel ´ertelm´eben az U halmaz is konvex. Ezt a feladatot konvex programoz´ asi feladatnak nevezz¨ uk.
7.3.1. Defin´ıci´ o. Az (7.2)-val defini´ alt U halmaz regul´ aris, ha minden (i ∈ I) eset´en l´etezik olyan ui ∈ U , melyre gi (ui ) < 0.
7.3.2. Defin´ıci´ o. Az (7.2)-val defini´ alt U halmaz kiel´eg´ıti a Slater felt´ etelt, ha l´etezik olyan u ∈ U , melyre gi (u) < 0, ∀i ∈ I. Az u pontot Slater pontnak nevezz¨ uk.
7.3.1. T´ etel. A Slater felt´etel teljes¨ ul´es´eb˝ ol k¨ ovetkezik a regularit´ asi felt´etel teljes¨ ul´ese. Konvex programoz´ asi feladat eset´en a k´et felt´etel ekvivalens. Bizony´ıt´ as. Ha l´etezik u Slater pont, akkor az ui = u (i ∈ I) v´aP laszt´assal teljes¨ ul a regularit´asi felt´etel. Ha az U halmaz konvex ´es regul´ aris, akkor az u = αk uk Slater pont. Val´oban, mivel gi (ui ) < 0 k∈I
´es a gi f¨ uggv´enyek konvexek, ´ıgy X X X gi (u) = gi ( αk uk ) ≤ αk gi (uk ) = αi gi (ui ) + αk g(uk ) < 0 | {z } | {z } k∈I
k∈I
<0
k6=i
≤0
7.3.2. T´ etel. (Kuhn-Tucker optimalit´ asi t´ etel) Legyen a (7.1)-(7.2) konvex programoz´ asi feladat, ´es az U halmaz legyen Slater regul´ aris. u ∈ U akkor ´es csak akkor optimumpontja a (7.1)(7.2) feladatnak, ha l´eteznek olyan λi ≥ 0 (i ∈ I), µj ≥ 0 j ∈ J1 ´es ϑj ∈ R j ∈ J2 konstansok, hogy X X X f 0 (u) + λi gi0 (u) + µj aj + ϑj aj = 0. (7.1) i∈I
j∈J1
j∈J2
´es teljes¨ ulnek a λi gi (u) = 0, i ∈ I, µj (haj , ui − bj ) = 0, j ∈ J1
(7.2)
. komplementarit´ asi felt´etelek. Bizony´ıt´ as. Sz¨ uks´egess´eg. Hasonl´ oan mint a 7.1.5. T´etel bizony´ıt´as´an´al l´eteznek olyan λ0 ≥ 0, λi ≥ 0, i ∈ I(u), µj ≥ 0, j ∈ J1 (u) ´es ϑj ∈ R, j ∈ J2 skal´ arok, hogy X X X λ0 f 0 (u) + λi gi0 (u) + µj aj + ϑj aj = 0, (7.3) i∈I(u)
j∈J1 (u)
j∈J2
´es λ0 +
X
λi = 1.
(7.4)
i∈I(u)
31
Azt kell bel´ atnunk, hogy λ0 > 0. Tegy¨ uk fel az ellenkez˝oj´et, vagyis legyen λ0 = 0. A(7.4)-b˝ol k¨ovetkezik, hogy van legal´ abb egy olyan k ∈ I(u) index, hogy λk > 0 ´es gk (u) = 0. Ha z ∈ U a Slater pont, akkor s = z − u megengedett ir´any. Val´oban, minthogy gi (z) < 0 (i ∈ I), haj , zi − bj ≤ 0 (j ∈ J1 ) ´es haj , zi − bj = 0 (j ∈ J2 ), ´ıgy ∀0 < ε ≤ 1 = ε0 eset´en gi (u + εs) = gi (εz + (1 − ε)u) ≤ ε gi (z) +(1 − ε) gi (u) < 0, | {z } | {z }
(i ∈ I),
≤0
<0
haj , u + εsi − bj = ε(haj , zi − bj ) + (1 − ε)(haj , ui − bj ) ≤ 0, | {z } | {z }
(j ∈ J1 )
haj , u + εsi − bj = ε(haj , zi − bj ) + (1 − ε)(haj , ui − bj ) = 0, | {z } | {z }
(j ∈ J2 ).
≤0
≤0
´es
=0
=0
(7.3)-t skal´arisan s-sel szorozva X X X λi hgi0 (u), si + µj haj , si + ϑj haj , si = 0. i∈I(u)
(7.5)
j∈J2
j∈J1 (u)
Mivel s megengedett ir´ any, a 7.1.1. T´etel szerint (7.5) baloldal´an minden tag nempozit´ıv, ´es figyelembe v´eve gk konvexit´ as´ at (ld. 4.1.2. T´etel) 0 > gk (z) = gk (z) − gk (u) ≥ hgk0 (u), z − ui = hgk0 (u), si, vagyis (7.5) baloldala hat´ arozottan negat´ıv, ´ıgy ellentmond´aashoz jutottunk. A (7.2) komplementarit´ asi felt´etelek teljes¨ ul´ese most is a λi = 0 (i ∈ I \ I(u) ´es µj = 0 (j ∈ J1 \ J1 (u) v´ alaszt´ assal biztos´ıthat´ o. El´egs´egess´eg. Legyen y ∈ U tetsz˝ oleges. f konvexit´asa, valamint (7.1) miatt X X X f (y) − f (u) ≥ hf 0 (u), y − ui = −h λi gi0 (u) + µj aj + ϑj aj , y − ui (7.6) i∈I
j∈J1
j∈J2
U konvexit´ asa miatt s = y − u megengedett ir´anya U -nak az u pontb´ol (bizony´ıt´asa anal´og az el˝obbiekkel), ´ıgy a 7.1.1. T´etel szerint hgi0 (u), si ≤ 0 (i ∈ I), haj , si ≤ 0 (j ∈ J1 ) ´es haj , si = 0 (j ∈ J2 ). Ez´ert (7.6)-b˝ ol f (y) − f (u) ≥ 0, vagyis u val´ oban minimumpont.
32
7.4. Feladatok 7.4.1. Feladat. abbi feladat konvex programoz´ asi feladat, teljes´ıti a Slater √ Mutassa √ meg, hogy az al´ felt´etelt ´es a ( 2/2, − 2/2) pontban teljes¨ ulnek a a Kuhn-Tucker optimalit´ asi felt´etelek. Hat´ arozza meg a megfelel˝ o Lagrange szorz´ okat. y x + y2 −x + y 2 x+y 2
→ ≤ ≤ ≥
min 1 0 0
7.4.2. Feladat. Ellen˝ orizze az al´ abbi feladatokra a Slater felt´etelt ´es a Kuhn-Tucker felt´etelek teljes¨ ul´es´et az adott pontban 1.) y x2 + 3y 2x + 3y x, y
→ ≤ ≤ ≥
max 3 4 0
u∗ = (x∗ , y∗ ) = (0, 1). 2.) xy x + y2 x+y x, y 2
→ ≤ ≤ ≥
max 100 14 0
u∗ = (x∗ , y∗ ) = (7, 7). 3.) −x + y → min x + y 2 + 2x ≤ 1 |x| ≤ 1 |y| ≤ 1 2
u∗ = (x∗ , y∗ ) = (0, −1). 4.) y x2 + 3y 2x + 3y x, y
→ ≤ ≤ ≥
max 3 4 0
u∗ = (x∗ , y∗ ) = (0, 1).
33
7.5. Megengedett ir´ anyok m´ odszere A 7.1.3 t´etel alkalmas arra, hogy seg´ıts´eg´evel megold´asi m´odszert konstru´aljunk. Ehhez ugyanis csak a (7.3)-(7.6) rendszer (s, σ) megold´asait kell megkeresn¨ unk ´es σ el˝ojel´et vizsg´alnunk. Vegy¨ uk azonban ´eszre, hogy ha (s, σ) egy megold´asa (7.3)-(7.6)-nak, akkor (αs, ασ) is az ∀α ≥ 0 eset´en. Ez´ert elegend˝ o az a norm´ aban fel¨ ulr˝ ol korl´atozott megengedett/cs¨okken´esi ir´anyokat vizsg´alni. Minthogy a (7.3)-(7.6) rendszer (s, σ)-ban line´aris, c´elszer˝ u az Rn -beli maximum-norm´at alkalmazni, hogy a rendszer linearit´ as´ at ne rontsuk el, azaz legyen ||s|| = max |si |, ahol s = i=1,...,n
(s1 , . . . , sn ) ∈ Rn . Ezzel az (7.3)-(7.6) rendszer az max |si | ≤ 1
i=1,...,n
felt´etellel b˝ ov¨ ul, ami ekvivalens a − 1 ≤ si ≤ 1, i = 1, . . . , n
(7.1)
felt´etelrendszerrel. Algoritmus: 1.l´ ep´ es: (Inicializ´ al´as) Legyen k := 1, ´es v´alasztunk egy u1 ∈ U pontot. 2.l´ ep´ es: Meghat´ arozzuk az akt´ıv felt´etelek I(uk ) ∪ J1 (uk ) ∪ J2 indexhalamaz´at. 3.l´ ep´ es: Megoldjuk a σ → max hf (uk ), si + σ ≤ 0, hgi0 , si + σ ≤ 0, (i ∈ I(uk )), haj , si ≤ 0, (j ∈ J1 (uk )), haj , si = 0, (j ∈ J2 ), −1 ≤ si ≤ 1, (i = 1, . . . , n) 0
line´aris programoz´ asi feladatot. ´ • Ha σ = 0, akkor KESZ. u∗ = uk kiel´eg´ıti a Fritz-John sz¨ uks´eges felt´etelt. • Ha σ = 0 ´es m´eg a gi0 (uk ), i ∈ I(uk ), aj , j ∈ J1 (uk ) ∪ J2 vektorrendszer line´arisan f¨ uggetlen, akkor u∗ = uk kiel´eg´ıti a Kuhn Tucker sz¨ uks´eges felt´etelt. • Ha a megoldand´ o feladat konvex ´es teljes´ıti a Slater felt´etelt, akkor u∗ = uk optim´alis. • Ha σ ≥ 0, akkor s megengedett cs¨okken´esi ir´any, GOTO 4. l´ep´es. 4.l´ ep´ es: uk+1 := uk + εs az ε > 0 olyan v´alaszt´as´aval, hogy f (uk+1 ) ≤ f (uk ) legyen (pl. ε ∈ argmin f (uk + εs)). GOTO 2. l´ep´es. ε>0
34
7.6. Feladatok 7.6.1. Feladat. Hat´ arozza meg az al´ abbi halmazoknak az adott u0 pontokhoz legk¨ ozelebbi nemnegat´ıv koordin´ at´ aj´ u pontj´ at megengedett ir´ anyok m´ odszer´evel az optimumpontt´ ol k¨ ul¨ onb¨ oz˝ o kezd˝ opontb´ ol kiindulva: 1.)
U = {u = (x, y) ∈ R2 : 2x + y ≤ 4, x + y ≤ 1} u0 = (2, 0).
2.)
U = {u = (x, y) ∈ R2 : x − 2y ≤ 6, −2x + y ≤ 6} u0 = (1, 3).
3.)
U = {u = (x, y) ∈ R2 : x − 2y ≤ 4, x + y ≥ 5} u0 = (1, 0).
7.6.2. Feladat. Az al´ abbi feladatokra a megengedett ir´ anyok m´ odszer´evel az adott u0 = (x0 , y0 ) pontb´ ol kiindulva hajtson v´egre egy teljes iter´ aci´ os l´ep´est, majd ´ırja fel a m´ asodik megengedett ir´ anyt meghat´ aroz´ o feladatot! 1.) x2 + y 2 − 4x + 4 → min x−y+3 ≥ 0 −x2 + y − 1 ≥ 0 x, y ≥ 0 u0 = (2, 5). 2.) x2 + xy + 2y 2 − 6x − 2y − 12z → min x+y+z = 2 −x + 2y ≤ 3 x, y, z ≥ 0 u0 = (1, 0, 1). 3.) x2 + xy + 2y 2 − 6x − 2y − 12z → min 2x2 + y 2 ≤ 15 −x + 2y + z ≤ 3 x, y, z ≥ 0 u0 = (1, 1, 1). 4.) (x − 2)2 + (y − 1)2 x2 − y −x + 2y
→ min ≤ 0 = 1
u0 = (1, 1).
35
7.7. Nyeregpontfelt´ etelek Legyenek a tov´ abbiakban I = {1, . . . , m}, J1 = {m + 1, . . . , p} ´es J2 = {p + 1, . . . , s} a korl´atoz´o felt´etelek indexhalmazai, G1 = (g1 , . . . , gm ), G2 = (gm+1 , . . . , gp ) ´es G1 = (gp+1 , . . . , gs ) a korl´atoz´o felt´etelek vektorf¨ uggv´enyei, azaz legyen U = {u ∈ Rn : G1 (u) ≤ 0, G2 (u) = A1 u − b1 ≤ 0, G3 (u) = A2 u − b2 = 0},
(7.1)
ahol A1 ´es A2 (p − m) × n ill. (s − p) × n t´ıpus´ u m´atrixok, b1 ∈ Rp−m , b2 ∈ Rs−p . (0 minden¨ utt a megfelel˝ o m´eret˝ u nullvektort jel¨ oli.) Legyen Λ = {(λ, µ, ϑ) ∈ Rm × Rp−m × Rs−p : λ ≥ 0, µ ≥ 0}.
7.7.1. Defin´ıci´ o. Az f (u) → min
(7.2)
u∈U
feladathoz rendelt L : Rn × Λ → R Lagrange fu eny: ¨ ggv´ L(u, λ, µ, θ) = f (u) + hλ, G1 (u)i + hµ, G2 (u)i + hϑ, G3 (u)i.
(7.3)
7.7.2. Defin´ıci´ o. Az (u∗ , λ∗ , µ∗ , ϑ∗ ) ∈ Rn × Λ az L(u, λ, µ, ϑ) Lagrange f¨ uggv´eny nyeregpontja az Rn × Λ halmazon, ha minden u ∈ Rn ´es (λ, µ, ϑ) ∈ Λ eset´en L(u∗ , λ, µ, ϑ) ≤ L(u∗ , λ∗ , µ∗ , ϑ∗ ) ≤ L(u, λ∗ , µ∗ , ϑ∗ ).
(7.4)
7.7.1. T´ etel. Ahhoz, hogy az(u∗ , λ∗ , µ∗ , ϑ∗ ) ∈ Rn ×Λ nyeregponja legyen a (7.2)-(7.1) nemline´ aris programoz´ asi feladatnak, sz¨ uks´eges, hogy teljes¨ uljenek az al´ abbi felt´etelek: L0u (u∗ , λ∗ , µ∗ , ϑ∗ ) L0λ (u∗ , λ∗ , µ∗ , ϑ∗ ) L0µ (u∗ , λ∗ , µ∗ , ϑ∗ ) L0ϑ (u∗ , λ∗ , µ∗ , ϑ∗ ) hλ∗ , G1 (u∗ )i hµ∗ , G2 (u∗ )i
= = = = = =
0, G1 (u∗ ) ≤ 0, G2 (u∗ ) = A1 u∗ − b1 ≤ 0, G3 (u∗ ) = A2 u∗ − b2 = 0, 0, hµ∗ , A1 u∗ − b1 i = 0.
(7.5) (7.6) (7.7) (7.8) (7.9) (7.10)
Ha a (7.2)-(7.1) feladat konvex programoz´ asi feladat, akkor a (7.5)-7.10) felt´etelek el´egs´egesek is. Bizony´ıt´ as. Sz¨ uks´egess´eg. A (7.4) nyeregpontfelt´etel jobboldali egyenl˝otlens´eg´eb˝ol az u = (u1∗ , . . . , uk−1∗ , uk , uk+1∗ , . . . , un∗ ) v´alaszt´assal a L(u1∗ , . . . , uk−1∗ , uk∗ , uk+1∗ , . . . , un∗ , λ∗ , µ∗ , ϑ∗ ) ≤ L(u1∗ , . . . , uk−1∗ , uk , uk+1∗ , . . . , un∗ , λ∗ , µ∗ , ϑ∗ ) ∀uk ∈ R azaz L(u1∗ , . . . , uk−1∗ , uk , uk+1∗ , . . . , un∗ , λ∗ , µ∗ , ϑ∗ ) , mint uk f¨ uggv´enye az uk∗ pontban veszi fel a minimum´ at. (7.5) az optimalit´ as sz¨ uks´eges felt´etele.
36
A (7.4) felt´etel baloldal´ ab´ ol hλ − λ∗ , G1 (u∗ )i + hµ − µ∗ , G2 (u∗ )i + hϑ − ϑ∗ , G3 (u∗ )i ≤ 0 ∀(λ, µ, ϑ) ∈ Λ.
(7.11)
Legyen λ = λ∗ + ek , ahol ek az Rm t´er k. egys´egvektora ´es legyen tov´abb´a µ = µ∗ ´es ϑ = ϑ∗ . Akkor (7.11)-b´ ol a gk (u∗ ) ≤ 0 egyenl˝otlens´eget kapjuk, ´es ez igaz minden k = 1, . . . , m-re, azaz (7.6) teljes¨ ul. Hasonl´ o technik´ aval, ha µ = µ∗ + ek , ahol ek az Rp−m t´er k. egys´egvektora, tov´abb´a λ = λ∗ ´es ϑ = ϑ∗ , akkor ∀k = m + 1, . . . , p eset´en hak , u∗ i − bk ≤ 0, azaz fenn´all (7.7). V´eg¨ ul, ha ϑ = ϑ∗ ± ek , ahol ek az Rs−p t´er k. egys´egvektora, tov´abb´a λ = λ∗ ´es µ = µ∗ , akkor ∀k = p + 1, . . . , s-re hak , u∗ i − bk ≤ 0, −(hak , u∗ i − bk ) ≤ 0. Ezzel (7.8)-t is igazoltuk. Figyelembe v´eve λ ´es µ nemnegativit´as´at, valamint a m´ar bel´atott (7.6), (7.7) ´es (7.8) ´all´ıt´asokat, a hλ∗ , G1 (u∗ )i ≤ 0, hµ∗ , G2 (u∗ )i = hµ∗ , A1 u∗ − b1 i ≤ 0. egyenl˝otlens´egeket kapjuk. M´ asr´eszt a (7.11) felt´etelb˝ol λ = 0, µ = 0, ϑ = 0 v´alaszt´assal hλ∗ , G1 (u∗ )i + hµ∗ , G2 (u∗ )i + hϑ∗ , G3 (u∗ )i ≥ 0 ad´odik, ami az ¨ osszeadand´ ok b´ armelyik´enek negat´ıvit´asa mellett nem lehets´eges, vagyis teljes¨ ulnie kell a (7.9) ´es (7.10) felt´eteleknek. El´egs´egess´eg. Tegy¨ uk fel, hogy a (7.2)-(7.1) feladat konvex ´es (u∗ , λ∗ , µ∗ , ϑ∗ ) ∈ Rn × Λ teljes´ıti az (7.5)-(7.10) felt´eteleket. Mivel az f (u), gi (u)(i = 1, . . . , s) f¨ uggv´enyek konvexek, az L(u, λ∗ , µ∗ , ϑ∗ ) Lagrange f¨ uggv´eny is konvex u-ban, ´es a konvexit´ as els˝ orend˝ u felt´etel´et, valamint a (7.5) felt´etelt felhaszn´alva L(u, λ∗ , µ∗ , ϑ∗ ) ≥ L(u∗ , λ∗ , µ∗ , ϑ∗ ) + hL0u (u∗ , λ∗ , µ∗ , ϑ∗ ), u − u∗ i ≥ L(u∗ , λ∗ , µ∗ , ϑ∗ ), {z } | ≥0
azaz (7.4) felt´etel jobboldala teljes¨ ul. Az L(u∗ , λ, µ, ϑ) Lagrange f¨ uggv´eny line´aris (λ, µ, ϑ)-ban, ´ıgy felhaszn´alva a (7.6)-(7.10) felt´eteleket: L(u∗ , λ, µ, ϑ)
= L(u∗ , λ∗ , µ∗ , ϑ∗ ) + hL0λ (u∗ , λ∗ , µ∗ , ϑ∗ ), λ − λ∗ i + hL0µ (u∗ , λ∗ , µ∗ , ϑ∗ ), µ − µ∗ i + hL0ϑ (u∗ , λ∗ , µ∗ , ϑ∗ ), ϑ − ϑ∗ i = L(u∗ , λ∗ , µ∗ , ϑ∗ ) + hG1 (u∗ ), λ − λ∗ i + hG2 (u∗ ), µ − µ∗ i + hG3 (u∗ ), ϑ − ϑ∗ i = L(u∗ , λ∗ , µ∗ , ϑ∗ ) + λ i + hG2 (u∗ ), µ i + hG3 (u∗ ), ϑi − hG1 (u∗ ), |{z} | {z } |{z} | {z } | {z } ≥0
≤0
≤0
≥0
=0
(hG1 (u∗ ), λ∗ i + hG2 (u∗ ), µ∗ i + hG3 (u∗ ), ϑ∗ i) | {z } | {z } | {z } ∗
∗
=0 ∗
=0
≤ L(u∗ , λ , µ , ϑ ), 37
=0
azaz a (7.4) felt´etel baloldali egyenl˝ otlens´ege is igaz.
7.7.2. T´ etel. Ha az (u∗ , λ∗ , µ∗ , ϑ∗ ) ∈ Rn ×Λ nyeregpontja a (7.2)-(7.1) feladathoz rendelt Lagrange f¨ uggv´enynek az Rn × Λ halmazon, akkor u∗ ∈ U∗ = {u∗ ∈ U : f (u∗ ) = inf f (u)}. Ha (7.2)-(7.1) u∈U
konvex programoz´ asi feladat, ´es teljes´ıti a Slater regularit´ asi felt´etelt, akkor a felt´etel sz¨ uks´eges is. Bizony´ıt´ as. Sz¨ uks´egess´eg. Legyen (u∗ , λ∗ , µ∗ , ϑ∗ ) ∈ Rn × Λ nyeregpontja a (7.2)-(7.1) feladathoz rendelt Lagrange f¨ uggv´enynek az Rn ×Λ halmazon. Akkor sz¨ uks´eges a (7.6)-(7.8) felt´etelek teljes¨ ul´ese, vagyis u∗ ∈ U , tov´ abb´ a a nyeregpontfelt´etel jobboldala teljes¨ ul minden u ∈ U -ra, ´ıgy ∀u ∈ U eset´en L(u∗ , λ∗ , µ∗ , ϑ∗ ) = f (u∗ ) ≤ L(u, λ∗ , µ∗ , ϑ∗ ) = f (u) + hG1 (u∗ ), |{z} λ i + hG2 (u∗ ), µ i + hG3 (u∗ ), ϑi ≤ f (u) | {z } | {z } |{z} | {z } ≤0
≥0
≤0
≥0
=0
El´egs´egess´eg. Mint l´ attuk kor´ abban, a Slater felt´etelt teljes´ıt˝o konvex programoz´asi feladatra a 7.3.2. T´etel felt´etelei el´egs´egesek is ahhoz, hogy egy u∗ ∈ U pont optim´alis legyen. Ezek a felt´etelek ekvivalensek a (7.5)-(7.10) felt´etelekkel.
38
7.8. Feladatok 7.8.1. Feladat. Tekints¨ uk a −u → min u∈U
U = {u ∈ R : u ≥ 0, u2 ≤ 0}; feladatot. Mutassuk meg, hogy a feladathoz rendelt Lagrange f¨ uggv´enynek nincs nyeregpontja. 7.8.2. Feladat. Tekints¨ uk az u → min u∈U
U = {u ∈ R : u ≥ 0, u2 ≤ 0} feladatot. Mutassuk meg, hogy a feladathoz rendelt Lagrange f¨ uggv´enynek (0, 1, λ∗2 ) nyeregpontja ∗ ∀λ2 ≥ 0 eset´en . 7.8.3. Feladat. Tekints¨ uk az |u|2 → min u∈U
U = {u ∈ R : |u|2 − 1 ≤ 0} feladatot. Mutassuk meg, hogy u∗ = 0, λ∗ = 0 nyeregpont. 7.8.4. Feladat. Nyeregpont-e az y x + y2 −x + y 2 x+y 2
→ ≤ ≤ ≥
min 1 0 0
√ √ √ √ feladatra (u∗ , λ∗ ), ha u∗ = ( 22 , − 22 ), λ∗ = (1 + 22 , 2 + 1, 0)?
39
8. A line´ aris komplementarit´ asi feladat megold´ asa Legyen M tetsz˝ oleges p × p m´ atrix, ´es q ∈ Rp . Keress¨ uk olyan w, z ∈ Rp vektorokat, amelyek kiel´eg´ıtik a w − Mz = q
(8.1)
wj ≥ 0, zj ≥ 0 (j = 1, . . . , p)
(8.2)
wj zj = 0, (j = 1, . . . , m)
(8.3)
rendszert. A (wj , zj ) v´ altoz´ okat komplement´ aris v´ altoz´ oknak nevezz¨ uk.
8.1. Defin´ıci´ o. A (w, z) p´ ar t¨ ok´ eletes megengedett b´ azis megold´ asa a (8.1-8.3) feladatnak, ha kiel´eg´ıtik (8.1-8.2)-t ´es minden j-re a (wj , zj ) p´ arnak pontosan az egyik komponense b´ azisbeli. Ha qi ≥ 0 ∀i = 1, . . . , p, akkor (8.1-8.3)-nak nyilv´anval´oan megold´asa a w = q, z = 0 p´ar. Ha legal´ abb egy j ∈ {1, . . . , p}-re qj < 0), akkor az eredeti feladat megold´asa helyett keress¨ uk a (w, z, z0 ) megold´ as´ at a w − Mz − 1z0 = q
(8.4)
wj ≥ 0, zj ≥ 0 (j = 1, . . . , p)
(8.5)
wj zj = 0, (j = 1, . . . , m)
(8.6)
rendszernek, ahol 1 = {1, . . . , 1}. Nyilv´anval´ oan, z0 = − min qi , z = 0, w = q + z0 1
(8.7)
i=1,...,p
egy megengedett megold´ asa a (8.4)-(8.6) rendszernek. Megfelel˝o b´azistranszform´aci´okkal megkis´erel¨ unk olyan megengedett megold´ ast keresni, ahol z0 = 0 teljes¨ ul.
8.2. Defin´ıci´ o. A (w, z, z0 ) h´ armas majdnem to eletes megengedett b´ azis megold´ asa a ¨k´ (8.4-8.6) feladatnak, ha 1. kiel´eg´ıti (8.4-8.5)-t; 2. l´etezik olyan 1 ≤ s ≤ p, hogy sem zj , sem wj nem b´ azisbeli; 3. minden j 6= s-re a (wj , zj ) p´ arnak pontosan az egyik komponense b´ azisbeli. A defin´ıci´ ob´ ol k¨ ovetkezik, hogy majdnem t¨ok´eletes megengedett b´azis megold´as eset´en z0 b´azisbeli kell legyen. M´ asr´eszt az is l´ atszik, hogy (8.7) egy majdnem t¨ok´eletes megengedett b´azis megold´as. A (w, z, z0 ) majdnem t¨ ok´eletes megengedett b´azis megold´as szomsz´ edos majdnem t¨ ok´ eletes megengedett b´ azis megold´ as´ ahoz u ´gy juthatunk, hogy a b´azisban eddig nem szerepl˝o (ws , zs ) p´arb´ol valamelyiket bevonjuk a b´ azisba, felt´eve, hogy ezzel z0 nem ker¨ ul ki a b´azisb´ol. A Lemke algoritmus alapgondolata a k¨ovetkez˝o: (8.7) majdenem t¨ok´eletes megengedett b´azis megold´asb´ ol kiindulva b´ azistranszform´ aci´okkal szomsz´edos majdenem t¨ok´eletes megengedett b´azis megold´asokon haladva jav´ıtjuk a megold´ast. 40
Algoritmus: ´ 1.l´ ep´ es: Ha qi ≥ 0 ∀i = 1, . . . , p, akkor w = q, z = 0 megold´as. KESZ! Ha ∃i ∈ {1, . . . , p}, melyre qi < 0, akkor az indul´o majdenem t¨ok´eletes megengedett b´azis megold´ as el˝ o´ all´ıt´asa: Legyen qs = − min qi . A z0 oszlop´ab´ol az s-edik elemet v´alasztva i=1,...,p
pivot elemk´ent, a ws -t kivonjuk a b´azisb´ol, s hely´ere z0 ker¨ ul. k.l´ ep´ es: ((k > 1)) Jel¨ olje vs a (k − 1)-dik l´ep´esben a b´azisb´ol kivont v´altoz´ot ´es ys annak a p´arj´at. Most ys -t (ami szint´en nincs a b´azisban) kell bevonnunk a b´azisba, ha ez lehets´eges. Jel¨olje a (k − 1)-dik l´ep´esben kapott szimplex t´abl´aban az ys -nek megfelel˝o oszlopvektort ds , a transzform´ alt jobboldali vektort pedig q. A k¨ovetkez˝ o esetek lehets´egesek: • Ha ∃i ∈ {1, . . . , p}, melyre dis > 0, akkor legyen qr = min i=1,...,p drs
qi : dis > 0 dis
– Ha az r-edik sor a b´ azisban valamelyik w- vagy z-komponensnek felel meg, akkor a b´ azistranszform´ aci´ ot a drs pivot elemmel v´egrehajtva, ez lesz ebben a l´ep´esben a b´azisb´ol kivont vs v´ altoz´ o. k := k + 1-gyel megism´etelj¨ uk a k-dik l´ep´est. – Ha az r-edik sor a b´ azisban a z0 v´altoz´onak felel meg, akkor a z0 v´altoz´ot kivonva a b´ azisb´ ol egy t¨ ok´eletes megengedett b´azist kapunk ´es meg´allunk. • Ha dis ≤ 0 ∀i ∈ {1, . . . , p}, akkor egy R = {(w, z, z0 ) + λ(ew , ez , ez0 ), λ ≥ 0} v´egtelen sug´ arhoz jutunk. Itt az e = (ew , ez , ez0 ) v´egtelen ir´anyvektor koordin´at´ait a k¨ovetkez˝ok´eppen kapjuk meg: az ys -nek megfelel˝o sorban 1, −dis , az i-edik b´ azisv´altoz´o sor´aban . ej = 0, egy´ebk´ent A k¨ovetkez˝ o k´et p´elda az algoritmus menet´et illusztr´alja a k´et k¨ ul¨onb¨oz˝o le´all´as eset´en. 1. p´ elda
0 0 −1 −1 0 0 1 −2 , M = 1 −1 2 −2 1 2 −2 4
2 2 q= −2 −6
0.l´ ep´ es: Indul´ o szimplex t´ abla
w1 w2 w3 w4
w1 w2 d1 d2 1 0 0 1 0 0 0 0
w3 w4 d3 d4 0 0 0 0 1 0 0 1
z1 z2 z3 z 4 d5 d6 d7 d8 0 0 1 1 0 0 −1 2 −1 1 −2 2 −1 −2 2 −4 41
z0 q d9 −1 2 −1 2 −1 −2 -1 −6
Indul´ o b´ azis: B = {w1 , w2 , w3 , w4 } be
(z0 −→ B)
^
( min qi = q4 )
ki
B −→ w4
=⇒
1≤i≤4
Pivot elem: d49 ´ szimplex t´ 1.l´ ep´ es: Uj abla
w1 w2 w3 z0
w1 w2 d1 d2 1 0 0 1 0 0 0 0
w3 d3 0 0 1 0
w4 z1 z2 d4 d5 d6 −1 1 2 −1 1 2 −1 0 3 −1 1 2
z3 d7 −1 −3 −4 −2
z4 z 0 d8 d9 5 0 6 0 6 0 4 1
q 8 8 4 6
Aktu´ alis b´ azis: B = {w1 , w2 , w3 , z0 } be
(z4 −→ B)
^
( min
1≤i≤4 di8 >0
qi q3 = ) di8 d38
ki
B −→ w3
=⇒
Pivot elem: d38 ´ szimplex t´ 2.l´ ep´ es: Uj abla
w1 d1
w2 d2
w3 d3
w4 d4
w1
1
0
− 56
− 16
w2
0
1
−1
0
1 6 2 −3
− 16 − 13
z4
0
0
z0
0
0
z1 d5
z2 d6
z3 d7
1 − 12
z4 d8
z0 d9
q
0
0
14 3
0
0
4
1
0
0
1
2 3 10 3
7 3
1
−1
1
0
1 2
1
0
− 23 2 3
Aktu´ alis b´ azis: B = {w1 , w2 , z4 , z0 } be
(z3 −→ B)
^
( min
{1≤i≤4 di7 >0
qi q1 = ) di7 d17
ki
B −→ w1
=⇒
Pivot elem: d17 ´ szimplex t´ 3.l´ ep´ es: Uj abla w1 d1
z4
3 7 − 37 2 7
z0
− 27
z3 w2
w2 w3 d2 d3 5 0 − 14
w4 d4 1 − 14
9 1 − 14
0
1 − 14
1 14 3 − 14
0
− 37
− 72
z1 d5
z2 d6
3 7 4 7 2 7
3 − 14
5 7
z 3 z4 z0 q d7 d8 d9 1 0 0 2
− 11 14
0
0
0 2
5 14
0
1
0
2
1 7
0
0
1
2
42
Aktu´ alis b´ azis: B = {w1 , w2 , z4 , z0 } be
(z1 −→ B)
^
( min
1≤i≤4 di5 >0
qi q4 = ) di5 d45
ki
B −→ z0
=⇒
Pivot elem: d45 4.l´ ep´ es: V´egs˝ o szimplex t´ abla w1 d1 z3 w2 z4 z1
3 5 − 15 2 5 − 25
w2 w3 d2 d3 1 0 − 10 3 1 − 10
0 0
1 10 − 35
w4 d4
z1 z2 d5 d6 3 0 − 10
1 10 3 10 1 − 10 − 25
z 3 z4 z0 d7 d8 d9 1 0 − 35
9 0 − 10
0
0 − 45
3 10 1 5
0
1
− 25
0
0
7 5
0 1
q 4 5 2 5 6 5 14 5
Megold´ as: (w, z) = (w1 , (0,
w2 , 2 5,
w3 , 0,
w4 , 0,
z1 , 14 5 ,
z2 , z3 , z4 ) 0, 45 , 65 )
=
2. p´ elda
0 0 1 −1 0 0 −1 2 , M = −1 1 2 −2 1 −2 −2 2
1 4 q= −2 −4
0.l´ ep´ es: Indul´ o szimplex t´ abla
w1 w2 w3 w4
w1 w2 d1 d2 1 0 0 1 0 0 0 0
w3 w4 d3 d4 0 0 0 0 1 0 0 1
z1 z2 z3 z4 d5 d6 d7 d8 0 0 −1 1 0 0 1 −2 1 −1 −2 2 −1 2 2 −2
z0 q d9 −1 1 −1 4 −1 −2 -1 −4
Indul´ o b´ azis: B = {w1 , w2 , w3 , w4 } be
(z0 −→ B)
^
( min qi = q4 ) 1≤i≤4
=⇒
Pivot elem: d49
43
ki
B −→ w4
´ szimplex t´ 1.l´ ep´ es: Uj abla w1 w2 d1 d2 1 0 0 1 0 0 0 0
w1 w2 w3 z0
w3 d3 0 0 1 0
w4 z1 d4 d5 −1 1 −1 1 −1 2 −1 1
z2 d6 −2 −2 −3 −2
z3 d7 −3 −1 −4 −2
z4 z0 d8 d9 3 0 0 0 4 0 2 1
q 5 8 2 4
Aktu´ alis b´ azis: B = {w1 , w2 , w3 , z0 } be
(z4 −→ B)
^
( min
1≤i≤4 di8 >0
qi q3 = ) di8 d38
ki
B −→ w3
=⇒
Pivot elem: d38 ´ szimplex t´ 2.l´ ep´ es: Uj abla
w1 w2
w1 w2 d1 d2 1 0 0
w3 d3 − 34
w4 d4 − 14
1
0
−1
1
−2 −1
1 4 1 −2
− 14 − 12
1 2
− 34 − 12
z4
0
0
z0
0
0
z1 d5 − 12
0
z2 d6
z3 z4 z0 d7 d8 d9 0 0 0
1 4
0
q 7 2
0
8
−1
1
0
1 2
0
0
1
3
be
z3 −→ B de {i : di7 > 0} = ∅ V´egtelen sug´ ar: R= { ( λ(
w1 , ew1 ,
w2 , ew2 ,
w3 , w4 , z1 , z2 , z3 , ew3 , ew4 , ez1 , ez2 , ez3 ,
z4 , ez4 ,
z0 ) + ez0 ) =
( w1 , w2 , λ( −d17 , −d27 ,
0, 0,
0, 0,
0, 0,
0, 0,
0, z4 , z0 ) 1, −d37 , −d47 )
7 2,
0, 0,
0, 0,
0, 0,
0, 0,
0, 1,
( λ(
0,
8, 1,
1 2,
1,
+ =
3) + 0) : λ ≥ 0}
A Lemke algoritmus v´egess´eg´et mondja ki a k¨ovetkez˝o
8.1. T´ etel. Tegy¨ uk fel, hogy (8.4)-(8.6) minden majdnem t¨ ok´eletes megengedett b´ azisa nemdegener´ alt (azaz minden b´ azisbeli elem pozit´ıv). Akkor a Lemke algoritmus v´eges sz´ am´ u l´ep´esben befejez˝ odik, mik¨ ozben az iter´ aci´ ok sor´ an egyetlen gener´ alt majdnem t¨ ok´eletes megengedett b´ azismegold´ as sem ism´etl˝ odik. 44
Bizony´ıt´ as. Jel¨olje (w, z, z0 )k , k = 1, 2, . . . a k. iter´aci´oban gener´alt majdnem t¨ok´eletes megengedett b´azist. Mivel a feladatr´ ol felt´etelezt¨ uk a nemdegener´alts´agot, a lehets´eges majdnem t¨ok´eletes megengedett b´azisok sz´ ama v´eges, ´ıgy az algoritmus v´egess´eg´ehez elegend˝o bel´atnunk, hogy egyetlen majdnem t¨ok´eletes megengedett b´ azis sem ism´etl˝ odik meg. Tegy¨ uk fel az ellenkez˝ oj´et. Legyen (w, z, z0 )k az els˝o olyan majdnem t¨ok´eletes megengedett b´azis, amely m´ ar szerepelt egy kor´ abbi iter´aci´oban. Jel¨olje ennek az iter´aci´onak az index´et k − α, azaz legyen (w, z, z0 )k = (w, z, z0 )k−α . A nemdegener´alts´agi felt´etelb˝ol, valamint az algoritmus konstrucci´ oj´ ab´ ol k¨ ovetkezik, hogy α > 2. Vegy¨ uk ugyanis ´eszre, hogy az indul´o majdnem t¨ok´eletes megengedett b´ azisnak egy, minden t¨ obbinek k´et szomsz´edos majdnem t¨ok´eletes megengedett b´azisa van. Az els˝ o esetben a ws bevon´ as´ aval, a m´asodik esetben vagy a ws vagy a zs bevon´a´aval kaphatunk szomsz´edos majdnem t¨ ok´eletes megengedett b´azist. Mivel (w, z, z0 )k−1 szomsz´edos (w, z, z0 )k -val, ´ıgy szomsz´edos (w, z, z0 )k−α -val is. Ha k − α = 1, akkor annak csak egy szomsz´edja van, ´ıgy (w, z, z0 )k−1 = (w, z, z0 )k−α+1 , azaz lenne a k. iter´ aci´ o el˝ ott ism´etl˝ od´es, ami ellentmond´as. Legyen k − α > 1. Mivel (w, z, z0 )k−1 szomsz´edos (w, z, z0 )k−α -val, ´ıgy vagy (w, z, z0 )k−1 = (w, z, z0 )k−α−1 , vagy (w, z, z0 )k−1 = (w, z, z0 )k−α+1 , azaz ebben az esetben is lenne a k. iter´aci´o el˝ott ism´etl˝od´es, ami ellentmond´ as. Az al´abbi t´etelben vizsg´ aljuk a v´egtelen ir´any tulajdons´agait.
8.2. T´ etel. Tegy¨ uk fel, hogy (8.4)-(8.6) minden majdnem t¨ ok´eletes megengedett b´ azisa nemdegener´ alt ´es a Lemke algoritmus R = {(w, z, z0 ) + λ(ew , ez , ez0 ), λ ≥ 0} v´egtelen sug´ ar megtal´ al´ as´ aval fejez˝ odik be, ahol (w, z, z0 ) majdnem t¨ ok´eletes megengedett b´ azis ´es (ew , ez , ez0 ) a v´egtelen ir´ anyvektor. Akkor fenn´ allnak a k¨ ovetkez˝ o¨ osszef¨ ugg´esek: 1.) (ew , ez , ez0 ) 6= (0, 0, 0), ew , ez , ez0 ≥ 0; 2.) ew − Mez − 1ez0 = 0; 3.) hw, zi = hw, ez i = hew , zi = hew , ez i = 0; 4.) ez 6= 0; 5.) hez , Mez i = −h1, ez iez0 . Bizony´ıt´ as. 1.) ´es 2.) k¨ ozvetlen¨ ul ad´ odik a v´egtelen ir´any definici´oj´ab´ol. A v´egtelen sug´ ar minden pontja kiel´eg´ıti a komplementarit´asi felt´etelt, ez´ert hw + λew , z + λez i = 0 ∀λ ≥ 0. Elv´egezve a szorz´ ast, valamennyi ¨ osszeadand´o z´erus kell legyen, figyelembe v´eve a v´altoz´ok nemnegativit´as´ at. Ez 3.) teljes¨ ul´es´et jelenti. Tegy¨ uk fel, hogy ez = 0. Ekkor 2.) miatt csak ez0 > 0 lehet, mert ellenkez˝o esetben ew = 0 is teljes¨ ulne, ami ellentmondana a (ew , ez , ez0 ) 6= (0, 0, 0) felt´etelnek. Ugyancsak 2.)-b˝ol ew = 1ez0 . Ezt skal´arisan z-vel szorozva ´es felhaszn´ alva 3.)-t 0 = hew , zi = hz, 1iez0 . Inn´et hz, 1i = 0. Mivel z ≥ 0, ez csak z = 0 mellett lehes´eges. Figyelembe v´eve a feladat felt´etelezett nemdegener´ alts´ ag´ at, ez azt jelenti, hogy z egyetlen koordin´at´aja sem b´azisbeli. Minthogy z0 45
b´azisbeli, ´ıgy w-nek p − 1 b´ azisbeli koordin´at´aja van. w − Mz − 1z0 = q-b´ol ´es z = 0-b´ol k¨ovetkezik, hogy ez akkor teljes¨ ul, ha z0 = − min qi , vagyis ha a kezd˝o majdnem t¨ok´eletes megengedett i=1,...,p
b´azisunk van. Ez viszont ellentmond annak, hogy a majdnem t¨ok´eletes megengedett b´azisok nem ism´etl˝odnek. ´Igy ez = 0 nem lehet igaz. V´egezet¨ ul, az ew − Mez − 1ez0 = 0 egyenletet skal´arisan ez -vel szorozva ´es felhaszn´alva, hogy hez , ew i = 0, valamint ez , ez0 ≥ 0 kapjuk, hogy hez , Mez i = −hez , 1iez0 ≤ 0. A tov´abbiakban azt vizsg´ aljuk, hogy milyen felt´etelek mellett lehet eld¨onteni, hogy a kapott megold´as optim´ alis-e? Ehhez az M m´ atrixok egy speci´alis oszt´aly´ara van sz¨ uks´eg¨ unk.
8.3. Defin´ıci´ o. Legyen M (p × p) t´ıpus´ u m´ atrix. Azt mondjuk, hogy M kopzit´ıv, ha hz, Mzi ≥ 0 ∀z ≥ 0.
(8.8)
M kopozit´ıv-plusz, ha kopozit´ıv ´es z ≥ 0, hz, Mzi = 0 =⇒ (M + MT )z = 0.
(8.9)
Az al´abbi ´ all´ıt´asok a m´ atrixok kopozit´ıv ill. kopozit´ıv-plusz tulajdons´ag´ara ad meg krit´eriumot.
8.3. T´ etel. Legyen M nemnegat´ıv elem˝ u m´ atrix. Akkor M kopozit´ıv. Ha a nemnegat´ıv elem˝ u m´ atrix f˝ odiagon´ alis´ aban az elemek pozit´ıvak, akkor M kopozit´ıv-plusz. Bizony´ıt´ as. Mivel M nemnegat´ıv, minden z ≥ 0-ra Mz ≥ 0, ´ıgy ugyancsak teljes¨ ul a hz, Mzi ≥ 0 felt´etel. Ha M diagon´ alis elemei pozit´ıvak, akkor az Mz ´es MT z vektorok mindegyik´enek van legal´abb egy pozit´ıv komponense minden z ≥ 0 eset´en, ha z 6= 0. Nevezetesen, ha z i. koordin´at´aja pozit´ıv, akkor Mz i. koordin´ at´ aja is pozit´ıv. Ha teh´at hz, Mzi = 0 valamely z ≥ 0 eset´en, akkor z = 0 ´es az (M + MT )z = 0 trivi´ alisan teljes¨ ul.
8.4. T´ etel. Ha az M pozit´ıv szemidefinit m´ atrix, akkor kopozit´ıv. Ha M m´eg szimmetrikus is, akkor kopozit´ıv-plusz tulajdons´ ag´ u is. Bizony´ıt´ as. A pozit´ıv szemidefinits´eg automatikusan maga ut´an vonja a kopozitivit´ast, mivel a kiv´ant hz, Mzi ≥ 0 felt´etel teljes¨ ul minden z-re, ´ıgy z ≥ 0-ra is. Ha M szimmetrikus szemidefinit m´ atrix, akkor a kopozit´ıv-plusz tulajdons´ag bel´at´as´ahoz el´eg bel´atni, hogy hz, Mzi = 0 =⇒ Mz = 0. Jel¨olje d = Mz. A pozit´ıv szemidefinits´egb˝ol k¨ovetkezik, hogy hz − λd, M(z − λd)i ≥ 0 ∀λ > 0, azaz 0 ≤ hzMzi − λhd, Mzi − λhz, Mdi + λ2 hd, Mdi = −λ(2||d||2 + λhd, Mdi). λ > 0-val osztva ´es a λ ↓ 0 hat´ ar´ atmenettel 0 ≤ −||d||2 ≤ 0, amib˝ol k¨ovetkezik, hogy d = Mz = 0.
46
8.5. T´ etel. Legyenek M1 , M2 ´es A m × m, p × p ill. p × m t´ıpus´ u m´ atrixok ´es legyen M = M1 AT (m + p) × (m + p) t´ıpus´ u m´ atrix. Akkor −A M2 1.) ha M1 ´es M2 kopozit´ıvak, akkor M is az; 2.) ha M1 ´es M2 kopozit´ıv-plusz tulajdons´ ag´ u, akkor M is az. Bizony´ıt´ as.
x 1.) Legyen z = ≥ 0, ahol az x ≥ 0, y ≥ 0 az M1 ´es M2 m´atrixoknak megfelel˝o particion´al´asa y z-nek. Ekkor M1 ´es M2 kopozit´ıvit´ asa miatt hz, Mzi = hx, M1 xi + hx, AT yi − hy, Axi + hy, M2 yi = hx, M1 xi + hy, M2 yi ≥ 0. 2.) Ha hz, Mzi = hx, M1 xi + hy, M2 yi = 0 valamely z ≥ 0-ra, akkor M1 ´es M2 kopozit´ıvit´asa miatt hx, Mxi = 0 ´es hy, Myi = 0. Az M1 ´es M2 m´atrixok kopozit´ıv-plusz tulajdons´aga miatt M1 + MT1 0 x (M1 + MT1 )x 0 (M + MT )z = = = . y 0 0 M2 + MT2 (M2 + MT2 )y
8.6. T´ etel. Tegy¨ uk fel, hogy a (8.4)-(8.6) line´ aris komplementarit´ asi feladat nemdegener´ alt ´es az M m´ atrix kopozit´ıv-plusz tulajdons´ ag´ u. 1.) A Lemke algoritmus pontosan akkor hat´ aroz meg egy v´egtelen sugarat, ha a (8.1)-(8.2) rendszer inkonzisztens. 2.) A Lemke algoritmus az eredeti (8.1)-(8.3) t¨ ok´eletes b´ azismegold´ as´ aval pontosan akkor fejez˝ odik be, ha a (8.1)-(8.2) rendszer konzisztens. Bizony´ıt´ as. A t´etel felt´etelei mellett a Lemke algoritmusnak pontosan k´et meg´all´asi lehet˝os´ege van. 1) Nyilv´ anval´ o, ha a (8.1)-(8.2) rendszer inkonzisztens, akkor nem fejez˝odhet be az algoritmus az eredeti feladat t¨ ok´eletes megengedett b´azis´aval. Tegy¨ uk fel, hogy az algoritmus az R = (w, z, z0 ) + λ(ew , ez , ez0 ), λ ≥ 0 sug´arral fejez˝odik be, ahol (w, z, z0 ) majdnem t¨ ok´eletes megengedett b´azis, (ew , ez , ez0 ) pedig v´egtelen ir´any. A 8.2. T´etel szerint ez ≥ 0, ez 6= 0, hez , Mez i = −h1, ez iez0 ≤ 0, m´asr´eszt M kopozit´ıvit´ asa miatt hez , Mez i ≥ 0, ´ıgy 0 = hez , Mez i = −h1, ez iez0 . Inn´et k¨ovetkezik, hogy ez0 = 0, mivel ez 6= 0. Ez a 8.2. T´etel 2.) ´all´ıt´as´aval egy¨ utt a 0 ≤ ew = Mez ¨osszef¨ ugg´eshez vezet. Felhaszn´ alva mindezeket, valamint az M m´atrix kopozit´ıv-plusz tulajdons´ag´at ´es azt a t´enyt, hogy (w, z, z0 ) majdnem t¨ ok´eletes megengedett b´azis, a k¨ovetkez˝o ¨osszef¨ ugg´eseket kapjuk: 0
= = = >
hw, ez i = hq + Mz + 1z0 , ez i hq, ez i + hz, MT ez i + h1, ez iz0 hq, ez i − hz, Mez i + h1, ez iz0 hq, ez i − hz, ew i = hq, ez i
A fentiek azt jelentik, hogy az MT y = −My ≤ 0 −y ≤ 0 hq, yi < 0 47
rendszernek van megold´ asa, nevezetesen y = ez . Akkor a Farkas lemma szerint nincs megold´asa a w − Mz w z
= q ≥ 0 ≥ 0
rendszernek. 2.) Ha a (8.1)-(8.2) rendszer konzisztens, akkor az el˝obbiek szerint a Lemke algoritmus nem fejez˝odhet be v´egtelen sug´ arral, csak az (8.1)-(8.3) t¨ok´eletes b´azismegold´as´aval. M´asr´eszt (8.1)(8.3) t¨ok´eletes b´ azismegold´ as l´etez´ese (8.1)-(8.2) konzisztenci´aj´at is jelenti.
8.6.1. K¨ ovetkezm´ eny. Ha M nemnegat´ıv m´ atrix pozit´ıv diagon´ alis elemekkal, akkor a Lemke algoritmus v´eges sok l´ep´esben a (8.1)-(8.3) t¨ ok´eletes b´ azismegold´ as´ at szolg´ altatja. Bizony´ıt´ as. A t´etel felt´etelei mellett M kopozit´ıv-plusz tulajdons´ag´ u. Tov´abb´a (8.1)-(8.2) konzisztens, ugyanis megold´asa minden olyan w ≥ 0, z ≥ 0 ahol z koordin´at´ai el´eg nagyok ahhoz, hogy w = Mz +q ≥ 0 legyen.
48
8.1. Feladatok 8.1.1. Feladat. Keress¨ uk a line´ aris komplementarit´ asi feladat 1 1 3 4 −1 5 3 1 1 2 1.) M = 2 1 2 2 , q = 1 . 1 4 1 1 −3 1 −1 0 0 −1 2 2 0 0 , q = 3 . 2.) M = 0 −2 1 −1 −2 1 0 1 −2 −4 1 2 0 −.5 2 −2 , q = 0 8.1.2. Feladat. Legyen M = −2 1 −1 2 −2 mentarit´ asi feladatot a Lemke m´ odszerrel. Hogyan viselkedik a 2. ´es 3. oszlop´ at felcser´elj¨ uk.
megold´ as´ at, ha
. Oldjuk meg a line´ aris kompleLemke m´ odszere, ha az M m´ atrix
8.1.3. Feladat. Legyen M1 ´es M1 m × m ill. p × p t´ıpus´ u m´ atrixok ´es legyen M =
M1 0 0 M2
(m + p) × (m + p) t´ıpus´ u m´ atrix. Mutassa meg, hogy 1.) ha M1 ´es M2 kopozit´ıvak, akkor M is az; 2.) ha M1 ´es M2 kopozit´ıv-plusz tulajdons´ ag´ u, akkor M is az. 8.1.4. Feladat. Kopozit´ıvak ill. kopozit´ıv-plusz tulajdons´ ag´ uak a k¨ ovetkez˝ o m´ atrixok: 1 1 1 1.) M = 0 2 0 ; 2 1 1 1 1 1 2.) M = 2 0 0 ; 2 1 1 1 1 3.) M = ; 2 1 1 1 −1 4.) M = 2 1 −2 ; 1 2 3 1 1 0 0 0 2 1 0 0 0 5.) M = 0 0 1 1 1 . 0 0 0 2 0 0 0 2 1 1 8.1.5. Feladat. zis´ at, ha 1 5 M = 2 1
Hat´ arozza meg a line´ aris komplementarit´ asi feladat indul´ o majdnem t¨ ok´eletes b´ a1 3 1 4
3 1 2 1
4 1 , 2 1
−1 2 q= 1 . −5 49
8.1.6. Feladat. Egy line´ aris komplementarit´ asi feladat els˝ o iter´ aci´ oja ut´ an a k¨ ovetkez˝ o t´ abl´ azatot kapjuk: w1 w2 z4 z0
w1 1.00 0.00 0.00 0.00
w2 w3 w4 z1 z2 z3 0.00 −0.75 −0.25 −0.50 0.25 0.00 1.00 0.00 −1.00 1.00 −2.00 −1.00 0.00 0.25 −0.25 0.50 −0.75 −1.00 0.00 −0.50 −0.50 0.00 −0.50 0.00
z4 0.00 0.00 1.00 0.00
z0 0.00 0.00 0.00 1.00
q 3.50 8.00 0.50 3.00
Mit tud mondani az eredeti feladat megoldhat´ os´ ag´ ar´ ol? (Ha van megold´ as akkor azt, ha v´egtelen sug´ ar van, akkor azt ´ırja fel, megfelel˝ o indokl´ assal). 8.1.7. Feladat. Valaki egy line´ aris komplement´ arit´ asi feladatnak v´egtelen ir´ anyak´ent a (0, 5, −2, 0, −1, 0, 3, 1, 2) + λ(2, 0, 0, 1, 2, 1, 0, 0, 0),
λ∈R
vektort hat´ arozta meg. Adjon min´el t¨ obb indokot arra, hogy megold´ asa biztosan hib´ as!
50
9. Kvadratikus programoz´ as A kvadratikus programoz´ as feladat´ anak a kvadratikus c´elf¨ uggv´eny optimaliz´al´as´at tekintj¨ uk line´aris korl´ atoz´ o, valamint a v´ altoz´ ok nemnegat´ı vit´asi felt´eteei mellett, azaz a 1 hu, Hui + hc, ui → min u∈U 2
(9.1)
U = {u ∈ Rn : Au ≤ b, u ≥ 0}
(9.2)
nemline´aris programoz´ asi feladatot, ahol H – szimmetrikus n×n-m´atrix, c ∈ Rn , A – m×n-m´atrix, b ∈ Rm . Ha H pozit´ıv szemidefinit, akkor a fenti feladat konvex programoz´asi feladat. A feladathoz rendelt Lagrange f¨ uggv´eny: L(u, λ) = f (u) + hλ, Au − bi − hµ, ui. ∗ n ´ A Kuhn-Tucker t´etelt alkalmazva, ha u∗ minimumpont, akkor ∃λ∗ ∈ Rm + , µ ∈ R+ Ugy, hogy ∗ ∗ (u∗ , λ , µ ) kiel´eg´ıti a
Hu + c + AT λ − µ Au − b u, λ, µ hλ, Au − bi hµ, ui
= ≤ ≥ = =
0 0 0 0 0
(9.3) (9.4) (9.5) (9.6) (9.7)
rendszert. Bevezetve az y ∈ Rm altoz´ ot, (9.3)-(9.7) a k¨ovetkez˝o alakba ´ırhat´o ´at: + v´ Hu + c + AT λ − µ Au − b + y u, λ, µ, y hλ, yi hµ, ui
= = ≥ = =
0 0 0 0 0
(9.8) (9.9) (9.10) (9.11) (9.12)
vagy m´atrix alakban: µ u c H AT − = y λ b −A 0
(9.13)
u, λ, µ, y ≥ 0
(9.14)
hλ, yi = 0 hµ, ui = 0
(9.15)
A kvadratikus programoz´ as feladata teh´at ekvivalens a k¨ovetkez˝o line´ aris komplementarit´ asi feladattal: Keres¨ unk olyan w, z ∈ Rn+m vektorokat, amelyek kiel´eg´ıtik a + w − Mz = q hw, zi = 0 w, z ≥ 0 rendszert, ahol H AT M= , −A 0
(9.16) (9.17) (9.18)
q=
c b
,
w=
51
µ y
,
z=
u λ
.
(9.19)
(9.18) miatt (9.17) nyilv´ anval´oan wj zj = 0, (j = 1, . . . , m + n)
9.1. T´ etel. A kvadratikus programoz´ asb´ ol nyert M m´ atrix kopozit´ıv, ha H kopozit´ıv ´es kopozit´ıvplusz, ha H is az. Bizony´ıt´ as. Az ´all´ıt´as a 8.5. T´etel speci´ alis esete.
9.2. T´ etel. Ha H pozit´ıv szemidefinit szimmetrikus m´ atrix, akkor M kopozit´ıv-plusz. Bizony´ıt´ as. Az ´all´ıt´as a 9.1. ´es a 8.4. T´etelek k|¨ ovetkezm´enye.
9.3. T´ etel. Ha H nemnegat´ıv m´ atrix, akkor M kopozit´ıv. Ha a nemnegat´ıv H m´ atrix diagon´ alis elemei pozit´ıvak, akkor M kopozit´ıv-plusz. Bizony´ıt´ as. Az ´all´ıt´as a 9.1. ´es a 8.3. T´etelek k¨ ovetkezm´enye.
9.4. T´ etel. Tegy¨ uk fel, hogy a (9.1)-(9.2) kvadratikus programoz´ asi feladat megengedett tartom´ anya nem u ahoz rendelt (9.16)-(9.18) line´ aris komplementarit´ asi feladat nem dege¨res ´es a probl´em´ ner´ alt. Akkor a Lemke algoritmus a 1.) H pozit´ıv szemidefinit ´es c = 0; 2.) H pozit´ıv definit; 3.) H nemnegat´ıv m´ atrix pozit´ıv f˝ odiagon´ alisbeli elemekkel felt´etelek b´ armelyike mellett v´eges sok l´ep´esben meghat´ arozza a (9.1)-(9.2) probl´ema Kuhn-Tucker pontj´ at. Pozit´ıv szemidefinit H m´ atrix eset´en, ha a Lemke algoritmus v´egtelen sugarat hat´ aroz meg, akkor alis megold´ asa nem korl´ atos. a (9.1)-(9.2) probl´ema optim´ Bizony´ıt´ as. Mivel a H-ra adott felt´etelek b´ armelyike mellett M kopozit´ıv-plusz tulajdons´ag´ u, ´ıgy a 8.6. T´etel szerint, azt kell bel´ atnunk, hogy az 1.)-3.) felt´etelek mellett a Lemke algoritmus nem ´allhat meg sug´arn´al. Tegy¨ uk fel, hogy fel az ellenkez˝oj´et. Akkor a (9.13)-9.14) rendszer inkonzisztens, ez´ert a Farkas lemma szerint l´etezik a Hd − AT e Ad d e hc, di + hb, ei
≤ ≤ ≥ ≥ <
0 0 0 0 0
(9.20) (9.21) (9.22) (9.23) (9.24)
rendszernek megold´ asa.
52
A (9.20) egyenl˝ otlens´eget d-vel skal´ arisan szorozva 0 ≥ hd, Hdi − hd, AT ei = hd, Hdi − hAd, ei ≥ hd, Hdi ≥ 0, azaz hd, Hdi = 0. Inn´et H kopozit´ıv-plusz tulajdons´aga miatt Hd = 0. A t´etel felt´etele szerint l´etezik olyan u0 ≥ 0, y 0 ≥ 0, melyre Au0 + y 0 = b. (9.24)-b˝ol 0 > skprodc, d + hb, ei = hc, di + hAu0 + y 0 , ei ≥ hc, di + hAu0 , ei ≥ hc, di + hu0 , Hdi.
(9.25)
A 2.) ´es 3.) felt´etelek mellett hd, Hdi = 0 felt´etelb˝ol d = 0, az 1. felt´etellel Hd = 0 ´es c = 0, ´ıgy mindegyik ellentmond (9.25)-nak. Tegy¨ uk fel, hogy pozit´ıv szemidefinit H m´atrix mellett a Lemke algoritmus v´egtelen sugarat hat´aroz meg. Mivel Hd = 0, (9.25)-b´ ol hc, di < 0 ad´odik. (9.21) ´es (9.22) miatt d a megengedett tartom´any v´egtelen ir´ anya, azaz u0 + λd megengedett pont minden λ ≥ 0 eset´en. Jel¨olje a kvadratikus programoz´ as c´elf¨ uggv´eny´et f (u). Akkor, figyelembe v´eve, hogy Hd = 0, azt kapjuk, hogy 1 f (u0 + λd) = f (u0 ) + λhc + Hu0 , di + λ2 hd, Hdi = f (u0 ) + λhc, di. 2 Mivel hc, di < 0, ha λ → ∞, akkor f (u0 + λd) → −∞.
53
9.1. Feladatok 9.1.1. Feladat. ´ Irja ´ at line´ aris komplementarit´ asi feladatt´ a az al´ abbi feladatokat ´es adja meg az indul´ o majdnem t¨ ok´eletes b´ azist:
1.)
x2 + 3xy + y 2 − 2xz − 4yz + x − 3y → min x + y + z ≤ 10 . 2x − y ≥ 0 x, y, z ≥ 0
2.)
x2 + 6xy + y 2 − 3xz − 4yz − 5x − 3y → min x + y + 2z ≤ 10 . 2x − y ≥ 1 x, y, z ≥ 0
9.1.2. Feladat. Hat´ arozza meg az al´ abbi halmazoknak az adott ponthoz legk¨ ozelebbi nemnegat´ıv koordin´ at´ aj´ u pontj´ at a Lemke algoritmussal: 1.)
U = {u = (x, y) ∈ R2 : 2x + y ≥ 6, 3x − 2y ≤ 2} u = (4, 3);
2.)
U = {u = (x, y) ∈ R2 : −x + 2y ≤ 2, x − y ≥ 3} u = (7, 2);
3.)
U = {u = (x, y) ∈ R2 : −x + 3y ≤ 6, x − y ≥ 3} u = (5, 7)
4.)
U = {u = (x, y) ∈ R2 : 3x + 2y ≤ 24, x − y ≥ 3} u = (8, 7).
54
10. Hiperbolikus programoz´ as Tekints¨ uk a k¨ ovetkez˝ o optimaliz´ al´ asi feladatot: hp, ui + α → min hq, ui + β Au u
(10.1)
≤ b ≥ 0,
(10.2) (10.3)
ahol p, q, u ∈ Rn , b ∈ Rm , A – m × n m´atrix, α, β ∈ R. Feltessz¨ uk, hogy a C = {u ∈ Rn : Au ≤ u, u ≥ 0} halmaz kompakt ´es hq, ui + β a C halmazon azonos el˝ojel˝ u ´es nem veszi fel a nulla ´ert´eket (az ´altal´anoss´ag megszor´ıt´ asa n´elk¨ ul feltehetj¨ uk, hogy pozit´ıv, ellenkez˝o esetben a c´elf¨ uggv´eny sz´aml´al´oj´at ´es nevez˝ oj´et is megszorozzuk −1-gyel). Charnes-Cooper elj´ ar´ as Vezess¨ uk be a k¨ ovetkez˝ ou ´j v´ altoz´ okat: z=
1 , y = zu. hq, ui + β
A nevez˝o pozit´ıvit´ asi felt´etele miatt z > 0. Ezekkel a v´ altoz´ okkal: hp, ui + α hq, ui + β
u α i+ hq, ui + β hq, ui + β = hp, zui + αz = hp, yi + αz; = hp,
Ay = Auz ≤ bz ´es z(hq, ui + β) = hq, yi + zβ = 1. Azaz az eredeti feladat a k¨ ovetkez˝ o feladatba transzform´al´odik: hp, yi + αz → min Ay − bz hq, yi + βz y z
≤ = ≥ >
0 1 0 0.
Val´oj´aban a (10.4) felt´etel a z≥0 felt´etelre cser´elhet˝ o, ugyanis ez ut´ obbi esetben sem lehet az (y, 0) megengedett pont. Ha ugyanis z = 0 lenne, akkor (10.4) miatt y 6= 0, de Ay ≤ 0, y ≥ 0 lenne, vagyis y v´egtelen ir´anya lenne a C tartom´anynak, ami ellentmond annak, hogy C kompakt.
55
10.1. T´ etel. Ha (y ∗ , z ∗ ) optim´ alis megold´ asa a hp, yi + αz → min Ay − bz hq, yi + βz y z
≤ 0 = 1 ≥ 0 ≥ 0.
line´ aris programoz´ asi feladatnak, akkor u∗ = y ∗ /z ∗ optim´ alis megold´ asa az eredeti hiperbolikus programoz´ asi feladatnak. Megjegyz´ esek: • A kompakts´ ag ellen˝ orz´ese a n X i=1
xi → max C
LP feladat megold´ as´ aval lehets´eges, ha ez nem v´egtelen ir´annyal fejez˝odik be, akkor korl´atos a C halmaz. • A nevez˝ o azonos el˝ ojel˝ us´eg´ehez a hp, yi → min C
ill. hp, yi → max C
LP feladatokat kell megoldani. Ha a k´et optim´alis c´elf¨ uggv´eny el˝ ojele azonos, akkor a nevez˝o nem v´ alt el˝ ojelet.
56
10.1. Feladatok 10.1.1. Feladat. Oldja meg az al´ abbi hiperbolikus programmoz´ asi feladatokat: 1.) −2x − y + 2 x+y+1 x+y x−y x, y
→ min ≤ ≤ ≥
4 2 0.
2.) −2x + y + 2 x + 3y + 4 −x + y y 2x + y x, y
→ min ≤ ≤ ≤ ≥
4 6 14 0.
3.) y x+y+1 x−y x + 3y x, y
→ min ≤ ≤ ≥
2 4 0.
57
11. Egyv´ altoz´ os unimod´ alis fu enyek minimaliz´ al´ asa ¨ ggv´ Legyen f : R → R ´es [a, b] ⊆ R. Tekints¨ uk az f (u) → min u∈[a,b]
egyv´altoz´os optimaliz´ al´ asi feladatot.
11.1. Defin´ıci´ o. Az f (u) f¨ uggv´enyt unimod´ alisnak nevezz¨ uk az [a, b] intervallumon, ha folytonos [a, b]-n ´es l´etezik olyan α ´es β a ≤ α ≤ β ≤ b, hogy teljes¨ ulnek a k¨ ovetkez˝ o tulajdons´ agok: 1. f (u) szigor´ uan cs¨ okken [a, α]-n, felt´eve, hogy a < α; 2. f (u) szigor´ uan n˝ o [β, b]-n, felt´eve, hogy β < b; 3. f (u) = f∗ = inf f (u) ∀u ∈ [α, β], azaz a minimumpontok halmaza U∗ = [α, β]. u∈[a,b]
Ha α = β, akkor f (u) szigor´ uan unimod´alis.
11.1. Intervallumfelez´ esi elj´ ar´ as A m´odszer akkor alkalmazhat´ o, ha f (u) unimod´alis az [a, b] intervallumon. Legyen adott 0 < δ < b − a ´es ε > δ pontoss´agi krit´erium. Algoritmus: 1.l´ ep´ es: Legyen u1 =
a+b−δ , 2
u2 =
a+b+δ . 2
Ha f (u1 ) < f (u2 ), akkor legyen a1 = a ´es b1 = u2 , egy´ebk´ent legyen a1 = u1 ´es b1 = b. k.l´ ep´ es: Legyen [ak−1 , bk−1 ] a minimumhalmazt tartalmaz´o r´eszhalmaz. Ha |bk−1 − ak−1 | < ε, akkor STOP, egy´ebk´ent legyen u2k−1 =
ak−1 + bk−1 − δ , 2
u2k =
ak−1 + bk−1 + δ . 2
Ha f (u2k−1 ) < f (u2k ), akkor legyen ak = ak−1 ´es bk = u2k , egy´ebk´ent legyen ak = u2k−1 ´es bk = bk−1 . k:=k+1, GO TO k. l´ep´es.
11.1.1. T´ etel. Az intervallumfelez´esi elj´ ar´ assal a k. iter´ aci´ o ut´ an a minimumhalmaz k¨ ozel´ıt´es´ere bk − ak =
b−a−δ +δ >δ 2k
hossz´ us´ ag´ u intervallumot kapunk. Az ε > δ pontoss´ ag´ u intervallum el´er´es´ehez n = 2k ≥ 2 log2 (
b−a−δ ) ε−δ
l´ep´essz´ amra van sz¨ uks´eg.
58
Bizony´ıt´ as. Az algoritmus szerint bk − ak =
bk−1 − ak−1 − δ + δ, 2
ugyanis ha f (u2k−1 ) < f (u2k ), akkor bk − ak = u2k − ak−1 , egy´ebk´ent bk − ak = bk − u2k−1 , ´es u2k−1 , u2k algoritmusbeli definici´ oj´ at figyelembe v´eve kapjuk az intervallum hossz´at az el˝oz˝o iter´aci´ohoz viszony´ıtva. A t´etelbeli becsl´es inn´et teljes indukci´oval k¨onnyen megkaphat´o. A l´ep´essz´ am a bn − an ≤ ε formula megfelel˝o ´atrendez´es´eb˝ol ad´odik.
11.2. Aranymetsz´ es m´ odszere Az intervallumfelez´esi elj´ ar´ asn´ al minden l´ep´esben k´et u ´j f¨ uggv´eny´ert´ek kisz´am´ıt´as´area van sz¨ uks´eg. Ez a m´odszer minden l´ep´esben csak egy u ´j pontban sz´am´ıt f¨ uggv´eny´ert´eket, a m´asikat az el˝oz˝o iter´aci´ob´ol veszi.
11.2.1. Defin´ıci´ o. Egy pont az [a, b] intervallumot aranymetsz´esben osztja, ha a kisebbik r´esz hossza u ´gy ar´ anylik a nagyobbik´ehoz, mint a nagyobbik´e az eg´eszhez. Az aranymetsz´esre k¨ ozismert az al´ abbi k´et t´etel:
11.2.1. T´ etel. Minden [a, b] intervallumhoz k´et szimmetrikusan elhelyezked˝ o aranymetsz´esi pont tartozik: √ √ 3− 5 5−1 (b − a), u2 = a + (b − a). u1 = a + 2 2
11.2.2. T´ etel. Ha u1 ´es u2 aranymetsz´esben metszi az [a, b] intervallumot ´es u1 < u2 , akkor u1 a nagyobbik aranymetsz´ese az [a, u2 ] intervallumnak ´es u2 a kisebbik aranymetsz´ese az [u1 , b] intervallumnak. Algoritmus: 1.l´ ep´ es: Legyen a0 = a, b0 = b, ´es k = 1. Legyen u1 < u2 az [ak−1 , bk−1 ] intervallum aranymetsz´esi pontjai. k.l´ ep´ es: Ha f (u1 ) < f (u2 ), akkor legyen ak = ak−1 , bk = u2 , u2 = u1 , u1 = ak−1 + bk−1 − u2 , vk = u2 , ellenkez˝ o esetben legyen ak = u1 , bk = bk−1 u1 = u2 , u2 = ak−1 + bk−1 − u1 , vk = u1 . Ha bk − ak < ε, akkor u∗ = vk ´es STOP, ellenkez˝o esetben k := k + 1 ´es GOTO k.l´ep´es.
11.2.3. T´ etel. Az n-edik l´ep´esben t¨ ort´en˝ o meg´ all´ as eset´en az optim´ alis megold´ ast´ ol val´ o elt´er´esre √ 5 − 1 n+1 ρ(u∗ , U∗ ) ≤ ( ) (b − a). 2 59
Bizony´ıt´ as. Az algoritmus szerint, ha f (u1 ) < f (u2 ), akkor bk − ak = u2 − ak−1 egy´ebk´ent bk − ak = bk−1 − ak . Mindk´et esetben – u1 ´es u2 defin´ıci´ oj´ at figyelembe v´eve √ 5−1 bk − ak = )(bk−1 − ak−1 ). 2 Inn´et teljes indukci´ oval √ 5−1 k bk − ak = ) (b − a). 2 Ezt felhaszn´ alva √ √ 5 − 1 5 − 1 n+1 (b − a). ρ(u∗ , U∗ ) ≤ max(bn − vn , vn − an ) = 2 (bn − an ) = ( 2 )
60
11.3. Feladatok 11.3.1. Feladat. Unimod´ alisak-e az al´ abbi f¨ uggv´enyek az adott intervallumon? Indokolja! 1.)
f (x) = ||x − 3| − x|, U = [0, 4]
2.)
f (x) = ||x2 − 2| − x3 | U = [−1, 5]
11.3.2. Feladat. Alkalmas-e az intervallumfelez˝ o ´es az aranymetsz´es m´ odszere az al´ abbi f¨ uggv´enyek minimaliz´ al´ as´ra az adott intervallumon: 1.)
f (x) = |x − 1| + |3x − 1| U = [0, 2].
2.)
f (x) = ||x2 − 2| − x| • U = [−2, 3] • U = [−3, 1].
11.3.3. Feladat. Oldja meg a 11.3.2. Feladat probl´em´ ait a lehets´eges m´ odszerekkel! 11.3.4. Feladat. Mekkora pontoss´ agot tud el´erni a 11.3.2. Feladataiban a k¨ ul¨ onb¨ oz˝ o m´ odszerekkel 10 iter´ aci´ o ut´ an?
61
12. Egyv´ altoz´ os fu enyek minimaliz´ al´ asa: t¨ or¨ ottvonal ´ es ¨ ggv´ ´ erint˝ o m´ odszer
12.1. Defin´ıci´ o. A f (u) f¨ uggv´eny kiel´eg´ıti a Lipschitz felt´ etelt az [a, b] intervallumon, ha l´etezik olyan L > 0 konstans, hogy |f (u) − f (v)| ≤ L|u − v| ∀u, v ∈ [a, b]. (Jel¨ ol´esben f ∈ Lip([a, b], L).
12.1. T´ etel. Legyen [a, b] =
m−1 S
[ui , ui+1 ], ahol u0 = a ´es um = b. Tegy¨ uk fel, hogy az f (u)
i=0
f¨ uggv´eny minden [ui , ui+1 ] intervallumon kiel´eg´ıti a Lipschitz felt´etelt Li konstanssal. Akkor az f (u) f¨ uggv´eny kiel´eg´ıti a Lipschitz felt´etelt az [a, b] intervallumon is L = max Li . i=0,...,m−1
Bizony´ıt´ as. Legyen u, v ∈ [a, b] tetsz˝ oleges k´et pont, ´es az ˝oket tartalmaz´o r´eszintervallumok: u ∈ [up , up+1 ] ill. v ∈ [us , us+1 ]. Az ´ altal´anos´ıt´as megszor´ıt´asa n´elk¨ ul feltehetj¨ uk, hogy u < v, azaz p ≤ s. Ekkor X |f (u) − f (v)| = |f (u) − f (up ) + s − 1(f (ui ) − f (ui+1 )) + f (us ) − f (v)| i=p+1
≤
s−1 X
|f (u) − f (up+1 )| +
|f (ui ) − f (ui+1 | + |f (us ) − f (v)|
i=p+1
≤ Lp |u − up+1 | +
s−1 X
Li |ui − ui+1 | + Ls |us − v|
i=p+1
≤ (max Li )(|u − up+1 | + p≤s
s−1 X
|ui − ui+1 | + |us − v|
i=p+1
≤ L|u − v|.
12.2. T´ etel. Ha f (u) differenci´ alhat´ o a ny´ılt (a, b) intervallumon, akkor az [a, b] intevallumon 0 kiel´eg´ıti a Lipschitz felt´etelt az L = sup f (u) konstanssal. u∈(a,b)
Bizony´ıt´ as. A Lagrange k¨ oz´ep´ert´ekt´etel szerint ∀u, v ∈ [a, b] eset´en f (u) − f (v) = hf 0 (v + ϑ(u = v)), (u − v)i valamely ϑ ∈ (0, 1) mellett. Inn´et ´es f 0 (u) korl´atoss´ag´ab´ol k¨ovetkezik az ´all´ıt´as.
62
12.1. T¨ or¨ ottvonal m´ odszer Tegy¨ uk fel, hogy az f ∈ Lip([a, b], L). Megengedj¨ uk, hogy a f¨ uggv´enynek t¨ obb lok´alis minimuma is legyen. Az algoritmussal a glob´alis optimum megkeres´es´et k´ıv´ anjuk el´erni. Legyen v ∈ [a, b] tetsz˝ oleges r¨ ogz´ıtett pont. Defini´aljuk a v ponthoz tartoz´o t¨or¨ott vonalat a g(u, v) = f (v) − L|u − v| egyenlettel. Az u0 , u1 , . . . , un pontokhoz tartoz´ o t¨or¨ottvonal pn (u) = max g(u, ui ). 0≤i≤n
Nyilv´anval´ oan igazak a k¨ ovetkez˝ o´ all´ıt´ asok: 1. pn (u) szakaszonk´ent line´ aris L ill. −L ir´anytangenssel 2. pn ∈ Lip([a, b], L); 3. pn (u) = max{g(u, un ), pn−1 (u)} ≥ pn−1 (u); 4. g(u, ui ) ≤ f (u), g(ui , ui ) = f (ui ), k¨ovetkez´esk´eppen pn (u) ≤ f (u). Algoritmus: 0. l´ ep´ es: Meghat´ arozzuk a f¨ uggv´eny Lipschitz konstans´at az [a, b] intervallumon ´es v´alasztunk egy indul´ o u0 ∈ [a, b] pontot, ´es egy ε pontoss´agi korl´atot. Legyen k := 0; 1. l´ ep´ es: p0 (u) = g(u, u0 ) = f (u0 ) − L|u − u0 | ´es u1 = argmin p0 (u). u∈[a,b]
k. l´ ep´ es: Ha f (uk+1 ) − pk (uk+1 ) ≤ ε, akkor u∗ = uk+1 ´es STOP, egy´ebk´ent legyen k := k + 1, pk (u) = max{g(u, uk ), pk−1 (u)} ´es uk+1 ∈ argmin pk (u) ´es GOTO k.l´ep´es. u∈[a,b]
12.1.1. T´ etel. Ha f ∈ Lip([a, b], L), akkor a t¨ or¨ ottvonal m´ odszerrel kapott uk sorozatra igazak a k¨ ovetkez˝ o´ all´ıt´ asok: 1. lim f (uk ) = lim pk (uk+1 ) = f∗ = inf f (u); k→∞
k→∞
u∈[a,b]
2. 0 ≤ f (uk+1 ) − f∗ ≤ f (uk+1 ) − pk (uk+1 ), k = 0, 1, . . . ; 3. az uk sorozat tart a minimumpontok U∗ halmaz´ ahoz, azaz inf |uk − u| → 0, ha k → ∞. u∈[a,b]
Bizony´ıt´ as. Legyen u∗ ∈ U∗ . Az algoritmus ´es az azt meghat´aroz´o t¨or¨ottvonal fent eml´ıtett tulajdons´agai miatt pk−1 (uk )
=
min pk−1 (u) ≤ pk−1 (uk+1 ) ≤ pk (uk+1 )
u∈[a,b]
=
min pk (u) ≤ pk (u∗ ) ≤ f (u∗ ) = f∗ ≤ f (uk+1 ).
u∈[a,b]
Inn´et a 2. becsl´es azonnal ad´ odik. Tov´abb´a k¨ovetkezik ebb˝ol az is, hogy a {pk (uk+1 )} sorozat monoton n˝o ´es fel¨ ulr˝ ol korl´ atos, ez´ert l´etezik a lim pk (uk+1 ) = p∗ ≤ f∗ hat´ar´ert´ek. k→∞
63
Bel´atjuk, hogy p∗ = f∗ . Az {uk } pontsorozat korl´atos, ez´ert a Bolzano-Weierstrass t´etel szerint van legal´abb egy torl´ od´ asi pontja. Legyen v∗ egy torl´od´asi pont ´es ukn az uk sorozat egy v∗ -hoz konverg´al´o r´eszsorozata, ahol feltehetj¨ uk, hogy {kn } monoton n¨ov˝o indexsorozat. Mivel f (ui ) = g(ui , ui ) ≤ pk (ui ) ≤ f (ui ), azaz f (ui ) = pk (ui ) ∀i = 0, . . . , k, ez´ert b´armely k ´es i ∈ {0, . . . , k} eset´en 0 ≤ pk (ui ) − min pk (u)
= f (ui ) − pk (uk+1 )
u∈[a,b]
= pk (ui ) − pk (uk+1 ) ≤ L|ui − uk+1 |. Alkalmazva ezt az egyenl˝ otlens´eget az k = nk − 1 ´es i = kn−1 indexekkel kn ≥ 2 eset´en, azt kapjuk, hogy 0 ≤ f (ukn−1 ) − pkn −1 (ukn ) ≤ L|ukn−1 − ukn |. Inn´et n → ∞ hat´ ar´ atmenettel kapjuk, hogy f∗ ≤ f (v∗ ) = lim f (ukn−1 ) = lim pkn −1 (ukn ) = p∗ ≤ f∗ , n→∞
k→∞
azaz lim f (ukn ) = lim pkn −1 (ukn ) = p∗ = f∗ .
k→∞
k→∞
Mivel v∗ tetsz˝ oleges torl´ od´ asi pont volt, a t´etel 1. ´all´ıt´as´at bebizony´ıtottuk. Mivel f ∈ Lip([a, b], L) folytonos, a defini´alt uk sorozat minimaliz´al´o sorozat, Weierstrass t´etel´eb˝ol k¨ ovetkezik a 3. ´ all´ıt´ as.
´ 12.2. Erint˝ o m´ odszer Tegy¨ uk fel, hogy az f : R → R f¨ uggv´eny konvex ´es differenci´alhat´o az [a, b] intervallumon. Ekkor 0 0 l´eteznek az f (a + 0) ´es f (b − 0) jobb ill. baloldali deriv´altak. 0
0
12.2.1. T´ etel. Ha az f f¨ uggv´eny konvex az [a, b] intervallumon ´es az f (a + 0) ´es f (b − 0) jobb 0 0 ill. baloldali deriv´ altak v´egesek, akkor f ∈ Lip([a, b], L), ahol L = max(|f (a + 0)|, |f (b − 0)|). A fenti t´etel azt jelenti, hogy ebben az esetben alkalmazhat´o a t¨or¨ottvonal m´odszer. Azonban a m´odszer jav´ıthat´ ou ´gy, hogy a v pontbeli g(u, v) t¨or¨ott vonalat ´atdefini´aljuk a v pontbeli ´erint˝ore: 0
g(u, v) = f (v) + f (v)(u − v). A konvexit´ as miatt fenn´ all a g(u, v) ≤ f (v) egyenl˝otlens´eg ∀u ∈ [a, b] eset´en. Ezzel a m´odos´ıt´assal a t¨or¨ottvonal m´ odszer l´ep´eseit˝ ol csak kis m´ert´ekben k¨ ul¨onb¨oz˝o algoritmus defini´alhat´o ´es arra fenn´allnak ugyanazok a konvergencia ´ all´ıt´asok, mint a t¨or¨ottvonal m´odszerre. 1. Algoritmus: 0. l´ ep´ es: V´ alasztunk egy indul´ o u0 ∈ [a, b] pontot. Legyen k := 0; 0
1. l´ ep´ es: p0 (u) = g(u, u0 ) = f (u0 ) + f (u0 )(u − u0 ) ´es u1 = argmin p0 (u). u∈[a,b] 0
k. l´ ep´ es: Ha uk+1 ∈ (a, b) ´es f (uk+1 ) = 0, akkor u∗ = uk+1 ´es STOP. 0 Ha uk+1 = a ´es f (a + 0) ≥ 0, akkor u∗ = a ´es STOP. 0 Ha uk+1 = b ´es f (b − 0) ≤ 0, akkor u∗ = b ´es STOP. Egy´ebk´ent pk+1 (u) = max{g(u, uk+1 ), pk (u)}, k := k + 1 ´es uk+1 ∈ argmin pk (u). GOTO u∈[a,b]
k.l´ep´es. 64
A konvexit´as miatt az U∗ halmaz maga is egy intervallum, a konvergencia U∗ -hoz teh´at azt jelenti, hogy az uk sorozatnak legfeljebb k´et torl´od´asi pontja van, az U∗ = [a∗ , b∗ ] k´et v´egponja. Ugyancsak a konvexit´ as miatt, amennyiben tal´alunk olyan ak ≤ bk pontokat az [a, b] interval0 0 lumban, hogy f (ak + 0) ≥ 0, akkor U∗ ⊆ [a, ak ], ha f (bk − 0) ≤ 0, akkor U ∗ ⊆ [bk , b], egy´ebk´ent U∗ ⊆ [ak , bk ]. Ennek megfelel˝ oen az ´erint˝o m´odszer algoritmusa a k¨ovetkez˝o l´ep´esekkel is fel´ırhat´o: 2. Algoritmus: 0
0
0
0
0. l´ ep´ es: Legyen a0 = a, b0 = b, f (a0 ) = f (a + 0), f (b0 ) = f (b − 0). k := 0. 0
k. l´ ep´ es: Ha f (ak ) ≥ 0, akkor ak ∈ U∗ , STOP. 0 Ha f (bk ) ≤ 0, akkor bk ∈ U∗ , STOP. Kisz´ am´ıtjuk a g(u, ak ) ´es g(u, bk ) ´erint˝ok 0
uk+1 =
0
f (ak ) − f (bk ) + bk f (bk ) − ak f (ak ) 0
0
f (bk ) − f (ak ) 0
metsz´espontj´ at. Ha f (uk+1 ) = 0, akkor uk+1 ∈ U∗ , STOP. Ellenkez˝o esetben legyen ak+1 =
ak uk+1
0
ha f (uk+1 ) ≥ 0 0 ha f (uk+1 ) ≤ 0
bk+1 =
Legyen k := k + 1, GOTO k. l´ep´es.
65
bk uk+1
0
ha f (uk+1 ) ≤ 0 0 ha f (uk+1 ) ≥ 0
12.3. Feladatok 12.3.1. Feladat. Megoldhat´ ok-e a 11.3.2. feladat probl´em´ ai t¨ or¨ ottvonal m´ odszerrel, vagy ´erint˝ o m´ odszerrel. Oldja meg ˝ oket a lehets´eges m´ odszerrel! 12.3.2. Feladat. Melyik m´ odszerrel oldan´ a meg a tanultak k¨ oz¨ ul az al´ abbi probl´em´ akat: 1.)
f (x) = |x − 1| + |3x − 1| U = [−1, 3];
2.)
f (x) = (x − 3)4 − 2(y − 2x) U = [0, 2].
66
