Optimálási módszerek Galántai Aurél

Optimálási módszerek Galántai Aurél 2004-2-8

Optimálási módszerek, 2003/2004, II. félév (óravázlat)

1 Bevezetés Optimalizálási feladat számos helyen elýofordul. Példák: 1. Dido probléma. 2. Legrövidebb út probléma. 3. A lineáris programozás feladata. 4. Motorok optimális vezérlése.

Alkalmazott Matematika Tanszék

2


3

A lineáris programozás alapfeladata: 1. Egy üzem m alapanyagból n féle terméket gyárt. 2. A j -edik termék egy egységének elýoállításához aij nyersanyag mennyiség kell az i-edik anyagból. A = [aij ]m,n i,j=1 ∈ Rm×n az üzem technológiai mátrixa. 3. Az i-edik nyersanyagból bi mennyiség (kapacitás) áll rendelkezésre. A b = [b1, . . . , bm]T ∈ Rm vektort kapacitásvektornak nevezzük. 4. Jelölje xi ≥ 0 az i-edik termékbýol gyártott termék mennyiségét. Az x = [x1, . . . , xn]T ∈ Rn vektort termelési programnak nevezzük.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Egy x termelési program anyagszükséglete:  Pn  j=1 a1j xj . Ax =  ..P n j=1 amj xj

Az x termelési programot lehetséges, ha n X xi ≥ 0, aij xj ≤ bi (i = 1, . . . , n). j=1

Legyen a j -edik termék ára cj és c = [c1, . . . , cn]T ∈ Rn. Ekkor az x termelési programhoz tartozó árbevétel:

cT x = c1x1 + . . . + cnxn.


4


5

Ha a cél az árbevétel maximálása, akkor az n X j=1

cT x → max, aij xj ≤ bi (i = 1, . . . , n), xi ≥ 0,

(i = 1, . . . , n)

lineáris programozási feladathoz jutunk.


(1) (2) (3)


6

2 Jelölések és alapfogalmak DeÞníció. Az

S (x∗, δ) = {x ∈ Rn| kx − x∗k < δ} ⊂ Rn

(4)

halmazt az x∗ ∈ Rn pont körüli δ sugarú nyílt gömbi környezetnek nevezzük. A deÞnícióban szereplýo norma tetszýoleges. Az n-edrendýu egységmátrixot I ∈ Rn×n, vagy In jelöli.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) DeÞníció. Az A ∈ Rn×n mátrix pozitív (negatív) deÞnit, ha ¡ T ¢ T x Ax > 0 x Ax < 0 ∀x ∈ Rn, x 6= 0. Az A mátrix pozitív (negatív) szemideÞnit, ha ¡ T ¢ T x Ax ≥ 0 x Ax ≤ 0 ∀x ∈ Rn.

7

(5) (6)

Az A mátrix indeÞnit, ha nem tartozik a fenti kategóriák egyikébe sem.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Az A = [aij ]ni,j=1 mátrix k-adik fýominor mátrixa:   a11 . . . a1k ..  , Ak =  .. ak1 . . . akk

ahol k = 1, . . . , n.


8

(7)


9

Tétel. Egy szimmetrikus A ∈ Rn×n mátrix akkor és csak akkor pozitív (negatív) deÞnit, ha

det (A1) > 0, . . . , det (An) > 0

³ ´ sign (det (Ai)) = (−1)i , i = 1, . . . , n .


(8) (9)


10

Tétel. Egy szimmetrikus A ∈ Rn×n mátrix akkor és csak akkor pozitív (negatív) deÞnit, ha minden sajátértéke pozitív (negatív) valós szám. Tétel. Egy szimmetrikus A ∈ Rn×n mátrix akkor és csak akkor pozitív deÞnit, ha az A = LU felbontásban, ahol L egység alsó, U felsýo háromszögmátrix, az U mátrix diagonális elemei mind pozitívak.



11

DeÞníció. Az f : Rn → R függvény gradiensén az

∇f (x) =

·

∂f ∂f ,..., ∂x1 ∂xn

¸T

∈ Rn

oszlopvektort értjük. DeÞníció. Az f : Rn → R függvény Hesse-mátrixa: ¸n · 2 ∂ f (x) H(x) = = ∇2f (x) = ∇2xxf (x) . ∂xi∂xj i,j=1

(10)

(11)

Kétszer folytonosan differenciálható függvények Hessemátrixa szimmetrikus!



12

DeÞníció. Az

F : Rn → Rm (F (x) = [F1 (x) , . . . , Fm (x)]T )

vektor-vektor függvény gradiensén az

∇F (x) = [∇F1 (x) , . . . , ∇Fm (x)]

elýoírással megadott n × m tipusú mátrixot értjük.


(12)


13

Az f : Rn → R vektor-skalár függvény Taylor-sora: 1 f (x + p) = f (x) + ∇f (x)T p + pT H(x)p + . . . 2 1 r 1 r−1 D f (x) + D f (x + θp) , (13) + (r − 1)! r!

ahol x, p ∈ Rn, 0 < θ < 1 és n X n n ½ X X pi1 pi2 · · · pis Dsf (x) = ... i1 =1 i2=1

is =1

∂ sf (x) ∂xi1 ∂xi2 . . . ∂xis


¾

.

(14)

Optimálási módszerek, 2003/2004, II. félév (óravázlat) A Taylor-sor speciális esetei: 1. Az f : Rn → R függvény lineáris közelítése:

f (x + p) ≈ f (x) + ∇f (x)T p

A közelítés hibája O(kpk2), ha f ∈ C 2. Az

(x, p ∈ Rn) .

y = f (x) + ∇f (x)T p

függvény az f függvény x pontbeli érintýosíkját adja meg.


14

(15)


15

2. Az f : Rn → R függvény kvadratikus közelítése (érintýo paraboloidja):

1 T f (x + p) ≈ f (x) + ∇f (x) p + p H(x)p, x, p ∈ Rn. (16) 2 A kvadratikus közelítés hibája O(kpk3), ha f ∈ C 3. T



16

Emlékeztetünk arra, hogy egy f (x) mennyiség O (g (x)) nagyságrendýu, ha egy K > 0 konstanssal fennáll, hogy kf (x)k ≤ K |g (x)|. Példa. Tekintsük az

f (x1, x2) = (1 + ex2 ) cos (x1) − x2ex2

függvény lineáris és kvadratikus közelítéseit az [x1, x2]T = [0, 0] helyen!



és

17

Egyszerû számolással kapjuk, hogy ¸ · x2 − (1 + e ) sin (x1) ∇f (x1, x2) = x2 e (cos (x1) − x2 − 1)

H (x1, x2) =

·

x2

x2

¸

−e sin (x1) − (1 + e ) cos (x1) . −ex2 sin (x1) ex2 (cos (x1) − x2 − 2)


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Minthogy f (0, 0) = 2, ∇f (0, 0) = [0, 0]T és · ¸ −2 0 H (0, 0) = , 0 −1

azért a lineáris közelítés alakja

f (p1, p2) ≈ 2,

míg a kvadratikus közelítés alakja

f (p1, p2) ≈ 2 − p21 − (1/2) p22.

Az f függvény és kvadratikus közelítésének képét mutatják a következõ ábrák:


18



19


Vizsgáljuk meg az ábrázolt felületek metszetét a p1 = 0, illetve a p2 = 0 síkokkal! Mit tapasztalunk?


20


21

3 Függvények szélsýoértékei DeÞníció. Legyen f : Rn → R tipusú függvény (n ≥ 1). Az x∗ ∈ D (f ) pont az f függvény globális minimumhelye, ha

f (x∗) ≤ f (x)

(x ∈ D (f ))

(17)

f (x∗) ≥ f (x)

(x ∈ D (f )) .

(18)

és globális maximumhelye, ha



22

DeÞníció. Legyen f : Rn → R tipusú függvény (n ≥ 1). Az x∗ ∈ D (f ) pont az f függvény lokális minimumhelye, ha létezik δ > 0 szám, hogy

f (x∗) ≤ f (x)

(x ∈ D (f ) ∩ S (x∗, δ))

(19)

f (x∗) ≥ f (x)

(x ∈ D (f ) ∩ S (x∗, δ)) .

(20)

és lokális maximumhelye, ha

A minimum-, vagy maximumhelyre egyaránt az extremális pont elnevezéssel utalunk.



23

Példa. Az f (x) = (x2 − x1)4 + 8x1x2 − x1 + x2 + 3 függvénynek egy lokális és egy globális minimumhelye van a −2 ≤ x1, x2 ≤ 2 tartományban:



24

DeÞníció. Egy x∗ ∈ D (f ) minimumhelyet szigorúnak nevezzük, ha egy δ > 0 számra fennáll, hogy

f (x∗) < f (x) ,

∀x ∈ D (f ) ∩ S (x∗, δ) , x 6= x∗.

(21)

∀x ∈ D (f ) ∩ S (x∗, δ) , x 6= x∗.

(22)

Egy x∗ ∈ D (f ) maximumhelyet szigorúnak nevezzük, ha egy δ > 0 számra fennáll, hogy

f (x∗) > f (x) ,

Ha egy minimumhely nem szigorú (erýos), akkor gyenge minimumhelynek is hívjuk. Az elýozýo ábra két minimumhelye szigorú.



¢ ¡ 2 2 Példa: Az f (x) = 0.1 x1 + x1x2 + x2 (x1 − 2x2)2 függvénynek az x1 = 2x2 egyenes bármely pontja gyenge minimumhelye, amint azt a következýo ábra is mutatja:


25


26

Ismertek a következýo eredmények: Tétel. Legyen f : R → R tipusú függvény. Ha f ∈ C 1 és x∗ extremális pont, akkor f 0(x∗) = 0. Tétel. Legyen f : R → R tipusú függvény. Ha f ∈ C 2 és x∗ minimumhely (maximumhely), akkor f 0(x∗) = 0, f 00(x∗) ≥ 0 (f 00(x∗) ≤ 0). Tétel. Legyen f : R → R tipusú függvény. Ha f ∈ C 2, f 0(x∗) = 0 és teljesül, hogy f 00(x∗) > 0 (f 00(x∗) < 0), akkor x∗ az f függvény minimumhelye (maximumhelye).



27

Tétel. Legyen f : Rn → R tipusú vektor-skalár függvény. Ha f ∈ C 1 és x∗ extremális pont, akkor

∇f (x∗) = 0.

(23)

A ∇f (x∗) = 0 feltételt stacionárius egyenletnek (egyenletrendszernek) nevezzük. Tétel. Legyen f : Rn → R tipusú vektor-skalár függvény. Ha f ∈ C 2 és x∗ minimumhely (maximumhely), akkor és a

∇f (x∗) = 0 ·

2

∗

(24)

¸n

∂ f (x ) ∂xi∂xj i,j=1 Hesse-mátrix pozitív (negatív) szemideÞnit. H (x∗) =


(25)


28

Tétel. Legyen f : Rn → R tipusú vektor-skalár függvény. Ha f ∈ C 2, ∇f (x∗) = 0 és a H (x∗) Hesse-mátrix pozitív (negatív) deÞnit, akkor az x∗ pont minimumhely (maximumhely). Bizonyítás (vázlat). Tekintsük az f : Rn → R függvény 1 f (x∗ + p) ≈ f (x∗) + ∇f (x∗)T p + pT H(x∗)p (x∗, p ∈ Rn) 2 (26) kvadratikus közelítést. Ha ∇f (x∗) = 0, akkor 1 f (x∗ + p) ≈ f (x∗) + pT H(x∗)p. (27) 2


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Ha H (x∗) pozitív deÞnit, akkor az 1 T ∗ ∗ f (x + p) ≈ f (x ) + p H (x∗) p> f (x∗) 2 | {z } >0

29

(p 6= 0) (28)

miatt az x∗ pont minimumhely. Ha H (x∗) negatív deÞnit, akkor az 1 f (x∗ + p) ≈ f (x∗) + pT H (x∗) p< f (x∗) 2 | {z }

miatt az x pont maximumhely. ¤

<0

∗



30

A ∇f (x) = 0 (f : Rn → R) egyenlet megoldásait stacionárius pontoknak, ill. az f függvény kritikus pontjainak is szokás hívni. Az x kritikus pont degenerált, ha det (H (x)) = 0. Megmutatható, hogy csak olyan nemdegenerált kritikus (stacionárius) pontok léteznek, amelyekben a H (x) Hessemátrixnak l pozitív és n − l negatív sajátértéke van (0 ≤ l ≤ n).


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Ha l = 0, akkor H (x) negatív deÞnit (maximumhely). Ha l = n, akkor H (x) pozitív deÞnit (minimumhely). A 0 < l < n esetben Morse-féle l-nyeregrýol, vagy nyeregpontról beszélünk. Nyeregpontban nincs szélsýoérték. Degenerált kritikus pontokban elvileg lehet szélsýoérték (pl. f (x, y) = x4 + y 4), ennek vizsgálata általában nem egyszerýu. Függvények degenerált kritikus pontjait az un. katasztrófaelméletben vizsgálják.


31


32

Példa. Határozzuk meg az f (x1, x2) = 2x41 + x42 − x21 − 2x22 függvény szélsõértékeit és kritikus pontjait (nyeregpontjait)! Az ¸ · 3 8x1 − 2x1 =0 ∇f (x1, x2) = 4x32 − 4x2

stacionárius egyenletbõl könnyen kapjuk, hogy az x1 = 0, ± 12 és x2 = 0, ±1 értékekkel képezett 9 darab (x1, x2) pontpár adja a függvény kritikus pontjait.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Minthogy

H (x1, x2) =

·

24x21 0

−2

0 12x22 − 4

¸

33

behelyettesítéssel könnyen megkaphatjuk, hogy mely pontokban van szélsõérték hely, vagy inßexiós (nyereg) pont. Az alábbi ábráról látható, hogy a (0, 0) pontban lokális maximum van.



34

Feladat. Adjuk meg a fenti példa összes szélsõérték helyét és nyeregpontját! Igazoljuk, hogy a minimum helyek egyúttal globális minimum helyek is!



35

Példa. f (x, y) = x2 − y 2 →extr Ekkor fx0 = 2x, fy0 = −2y, (x∗, y ∗) = (0, 0). Az f (x, 0) = x2 függvénynek az x = 0 pontban lokális minimuma, az f (0, y) = −y 2 függvénynek pedig lokális maximuma van. A · ¸ 2 0 H= 0 −2 Hesse mátrix nem pozitív deÞnit, mert D1 = 2, D2 = −4 (determináns tétel), illetve mert λ1 = 2 és λ2 = −2 (sajátérték tétel). A H mátrix indeÞnit, a (0, 0) pont un. nyeregpont (l = 1).


Optimálási módszerek, 2003/2004, II. félév (óravázlat) A vizsgált függvény ábrája:

A z = x2 − y 2 nyeregfelület


36


37

3.1 Kvadratikus függvények és szélsýoértékeik Az f : Rn → R függvényt kvadratikusnak nevezzük, ha alakja n X n n X X 1 T 1 f (x) = x Ax + bT x + c = aij xixj + bixi + c, 2 2 i=1 j=1 i=1 (29) ahol A ∈ Rn×n szimmetrikus mátrix, b ∈ Rn és c ∈ R. Könnyen megmutatható, hogy minden n X n n X X f (x) = αij xixj + β ixi + γ i=1 j=1

i=1

alakú függvény (”kvadratikus alak”) is a fenti alakra hozható.



38

Az f : Rn → R függvény R

1 f (x + p) ≈ f (x) + ∇f (x)T p + pT H(x)p (x, p ∈ Rn) 2 kvadratikus közelítése maga is kvadratikus függény, amelynek a tulajdonságai lényegében meghatározzák a szélsýoérték létezését és jellegét. Igazak a következõ tulajdonságok: ∇f (x) = Ax + b,

H (x) = A.

Ha létezik A−1, akkor a

∇f (x) = Ax + b = 0

stacionárius egyenlet megoldása x = −A−1b.


(30)


39

Ha A pozitív deÞnit, akkor xmin = −A−1b minimumhely és f (xmin) = − 12 bT A−1b + c. Ha A negatív deÞnit, akkor xmax = −A−1b maximumhely és f (xmax) = − 12 bT A−1b + c. Ha A indeÞnit, akkor megmutatható, hogy x = −A−1b nyeregpont.



40

Megjegyzés. És az elfajult, szemideÞnit esetek? Példa. Az f (x) = x21 − x1x2 + x22 függvénynek egy szigorú (erýos) minimumhelye van (∇2f (x) pozitív deÞnit):


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Az f (x) = 12 x21 − 2x1x2 + 2x22 függvénynek gyenge minimumhelye van (∇2f (x) pozitív szemideÞnit):


41

Optimálási módszerek, 2003/2004, II. félév (óravázlat) 42 ¢ ¡ 2 1 2 Az f (x) = x1 − 2x1x2 − 2 x2 − 1 függvénynek nyeregpontja van (∇2f (x) indeÞnit):



43

4 Feltételes szélsýoértékfeladatok A vizsgált optimalizálási feladatok legáltalánosabb alakja:

f (x) → min (max) hi (x) = 0 (i = 1, . . . , m) , gj (x) ≤ 0 (j = 1, . . . , r) ,

ahol x ∈ Rn, f : Rn → R és

hi, gj : Rn → R (i = 1, . . . , m, j = 1, . . . , r).


(31)

(32)


44

egyenlýoségi feltételek:

hi (x) = 0 (i = 1, . . . , m)

(33)

egyenlýotlenségi feltételek:

gj (x) ≤ 0 (j = 1, . . . , r)

(34)

Ha nincs semmilyen korlátozó feltétel, akkor feltétel nélküli optimalizálásról beszélünk.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Legyen

és

45



h1 (x) h(x) =  ..  hm (x)

(h : Rn → Rm)

(35)



g1 (x) g(x) =  ..  gr (x)

(g : Rn → Rr )

(36)







46

DeÞníció. Legyen x, y ∈ Rn. Az x ≤ y egyenlýotlenség akkor és csak akkor teljesül, ha xi ≤ yi (i = 1, . . . , n). Példa:     · ¸ · ¸ 3 3.1 2 −1  −2  ≤  −2  , · . −3 2 1 8



47

A feladat tömör alakja:

f (x) → min (max) h(x) = 0 g(x) ≤ 0


(37)


48

DeÞníció. A (31) feladat megengedett megoldásainak halmaza:

S = {x | x ∈ Rn, h (x) = 0, g (x) ≤ 0} .

Az x vektor megengedett megoldás, ha x ∈ S . Megjegyzés: Valójában

S = {x | x ∈ D (f ) , h (x) = 0, g (x) ≤ 0}

volna a helyes deÞníció. Tkp. hallgatólag feltesszük, hogy

h (x) = 0 ∧ g (x) ≤ 0 ⇒ x ∈ D (f ) .


(38)


49

Csak egyenlýoségi korlátokat tartalmazó szélsýoértékfeladatok általános alakja:

f (x) → min h (x) = 0

(max)

,

(39)

ahol

S = {x | x ∈ Rn, h (x) = 0} .


(40)


50

Csak egyenlýotlenségi korlátokat tartalmazó szélsýoértékfeladatok általános alakja:

ahol

f (x) → min g (x) ≤ 0

(max)

,

S = {x | x ∈ Rn, g (x) ≤ 0} .


(41)

(42)


51

Feltétel nélküli optimalizálás esetén

S = D (f ) .

Feltételes optimalizálásról akkor beszélhetünk, ha

S ⊂ D (f ) ∧ S 6= D (f ) . Az optimalizálási feladat felírható a következýo formában is:

f (x) → min (max)

(x ∈ S) .


(43)


52

DeÞníció. Az x∗ ∈ S vektor optimális megoldás, ha fennáll, hogy

f (x∗) ≤ f (x) ,

(f (x∗) ≥ f (x) ,

∀x ∈ S) . (44) Tömören jelölve: x∗ ∈ S optimális megoldás, ha µ ¶ f (x∗) = min f (x) f (x∗) = max f (x) . (45) x∈S

∀x ∈ S

x∈S



53

DeÞníció. Az x∗ ∈ S vektor lokálisan optimális megoldás, ha ∃δ > 0, hogy µ ¶ f (x∗) = min f (x) f (x∗) = max f (x) . (46) x∈S∩S(x∗ ,δ)

x∈S∩S(x∗,δ)



54

DeÞníció. Egy x∗ ∈ S minimumhely szigorú, ha egy δ > 0 számra fennáll, hogy

f (x∗) < f (x) ,

∀x ∈ S ∩ S (x∗, δ) , x 6= x∗.

(47)

∀x ∈ S ∩ S (x∗, δ) , x 6= x∗.

(48)

Egy x∗ ∈ S maximumhely szigorú, ha egy δ > 0 számra fennáll, hogy

f (x∗) > f (x) ,



55

Megjegyzések: 1. Számos esetben csak egy lokális optimumot tudunk (akárcsak közelítýoleg is) meghatározni. 2. Az optimum létezése következik Weierstrass-tételébýol, ha S ⊆ Rn korlátos és zárt halmaz és az f (x) célfügggvény az S halmazon folytonos. A gyakorlatban ez a tény csak ritkán használható. 3. Elég csak az f (x) → min (x ∈ S) minimum feladatot vizsgálni, mert fennáll a min f (x) = − max (−f (x)) egyenlýoség.



56

5 Egyenlýoségi feltételek Legyen f : Rn → R, h : Rn → Rm (m < n) és vizsgáljuk az

f (x) → extr h(x) = 0

feltételes szélsýoértékfeladatot!


(49)


57

DeÞníció. Legyen x∗ ∈ S = {x ∈ Rn | h (x∗) = 0} és h ∈ C 1 (S (x∗, ε)) valamilyen ε > 0 értékre. Az x∗ pont reguláris, ha a ∇h1 (x∗) , . . . , ∇hm (x∗) (50) gradiens vektorok lineárisan függetlenek.



58

DeÞníció. Az (49) optimalizálási feladat Lagrange-függvénye m X L(x, λ) = f (x) + λT h(x) = f (x) + λihi (x) , (51) i=1

ahol λ = [λ1, . . . , λm]T ∈ Rm. A λ1, . . . , λm együtthatókat Lagrange-szorzóknak (multiplikátoroknak) is nevezik. A L(x, λ) függvény x vektor szerinti gradiense: ∇xL(x, λ), az x vektor szerinti Hesse-mátrixa: ∇2xxL(x, λ).



59

Tétel. Legyen x∗ lokális minimum (maximum) pont és tegyük fel, hogy az x∗ pont reguláris. Ekkor ∃!λ∗ ∈ Rm úgy, hogy

∇xL(x∗, λ∗) = 0.

Ha f, h ∈ C 2 (S (x∗, ε)) és x∗ minimumhely, akkor fennáll

(52)

z T ∇2xxL(x∗, λ∗)z ≥ 0,

∀z ∈ Rn és ∇h (x∗)T z = 0.

(53)

z T ∇2xxL(x∗, λ∗)z ≤ 0,

∀z ∈ Rn és ∇h (x∗)T z = 0.

(54)

Ha f, h ∈ C 2 (S (x∗, ε)) és x∗ maximumhely, akkor fennáll



60

Megjegyzés: 1. Az (x∗, λ∗) pont tulajdonképpen az L(x, λ) Lagrangefüggvény nyeregpontja. 2. Minimum esetén a ∇2xxL(x∗, λ∗) Hesse-mátrix feltételesen pozitív szemideÞnit, a maximum esetén pedig feltételesen negatív szemideÞnit.



61

DeÞníció. Legyen A ∈ Rn×n szimmetrikus mátrix, B pedig egy n × m tipusú valós mátrix, amelynek rangja maximális, azaz rank(B) = m. Az A mátrix feltételesen pozitív deÞnit (B szerint), ha xT Ax > 0, ∀x ∈ Rn, x 6= 0, B T x = 0; (55) feltételesen pozitív szemideÞnit, ha

xT Ax ≥ 0,

∀x ∈ Rn, B T x = 0;

(56)

∀x ∈ Rn, x 6= 0, B T x = 0;

(57)

feltételesen negatív deÞnit, ha

xT Ax < 0,

feltételesen negatív szemideÞnit, ha

xT Ax ≤ 0,

∀x ∈ Rn, B T x = 0.


(58)


62

A fenti szükséges optimalitási tételben A szerepét ∇2xxL (x∗, λ∗) a B szerepét pedig ∇h (x) játssza. A B T x = 0 homogén lineáris egyenletrendszer általános megoldása megadható x = Zy alakban, ahol Z ∈ Rn×(n−m), rank(Z) = n − m és y ∈ Rn−m. Ezért xT Ax = y T Z T AZy és a feltételes deÞnitség a redukált kvadratikus alak ´ ³ ¢ ¡ T T T (n−m)×(n−m) n−m φ (y) = y Z AZ y Z AZ ∈ R ,y∈R (59) feltétel nélküli deÞnitségét jelenti.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) A

Dx = 0 (D ∈ Rm×n, rank (D) = m). homogén egyenletrendszer általános megoldása: rank(D) = m ⇒ ∃ P ∈ Rn×n permutáció mátrix, hogy DP = [D1, D2] és D1 ∈ Rm×m invertálható. Legyen · ¸ x1 T (x1 ∈ Rm, x2 ∈ Rn−m). P x= x2


63


64

Ekkor

Dx = DP P T x·= [D¸1, D2] P T x x = [D1, D2] 1 = D1x1 + D2x2 = 0, x2

ahonnan x1 = −D1−1D2x2 és az ¸ · −1 −D1 D2x2 x=P x2 megoldás adódik.


(60)


65

Minthogy dim (N (D)) = n − m, keresnünk kell n − m lineárisan független megoldást, amelyek a N (D) altér egy bázisát alkotják. Ha x2 = ei ∈ Rn−m és i = 1, . . . , n − m, akkor bázist kapunk, ui. a ¸ · −1 −D1 D2ei , i = 1, . . . , n − m P ei megoldások lineárisan függetlenek.



66

Minthogy tetszýoleges megoldás ezen megoldások lineáris kombinációja, felírhatjuk, hogy a Dx = 0 homogén egyenletrendszer általános megoldása ¸ · −1 −D1 D2 t, t ∈ Rn−m. x=P (61) In−m


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Tétel. Tegyük fel, hogy x∗ ∈ S reguláris pont, f, h ∈ C 2 (S (x∗, ε)) (ε > 0) és ∃λ∗ ∈ Rm úgy, hogy

∇xL(x∗, λ∗) = 0.

67

(62)

Ha ∇2xxL (x∗, λ∗) feltételesen pozitív deÞnit, azaz

∀z ∈ Rn, z 6= 0, ∇h (x∗)T z = 0, (63) akkor x∗ szigorú lokális minimumhely. Ha a ∇2xxL(x∗, λ∗) Hesse-mátrix feltételesen negatív deÞnit, azaz z T ∇2xxL(x∗, λ∗)z > 0,

∀z ∈ Rn, z 6= 0, ∇h (x∗)T z = 0, (64) akkor x∗ szigorú lokális maximumhely. z T ∇2xxL(x∗, λ∗)z < 0,



68

A feltételes pozitív deÞnitség ellenýorzése meglehetýosen nehéz feladat. A két legismertebb eredményt mondjuk ki. Tétel. Legyen A ∈ Rn×n szimmetrikus. Az A mátrix akkor és csak akkor feltételesen pozitív deÞnit (negatív deÞnit), ha a ¸¶ µ· A − γI B =0 p (γ) = det (65) 0 BT polinomegyenlet gyökei mind pozitívak (negatívak).



69

Tétel (Chabrillac, Crouzeix). Legyen A ∈ Rn×n szimmetrikus. Az A mátrix feltételesen pozitív deÞnit, akkor és csak akkor, ha az · ¸ A B (n+m)×(n+m) ∈ R (66) T B 0

szegélyezett mátrixnak m negatív, 0 zérus és n pozitív valós sajátértéke van. Az A mátrix akkor és csak akkor feltételesen negatív deÞnit, ha a fenti szegélyezett mátrixnak n negatív, 0 zérus és m pozitív valós sajátértéke van.



70

Tehát a ∇2xxL(x∗, λ∗) Hesse-mátrix feltételes deÞnitségét vagy a ¸¶ µ· 2 ∗ ∗ ∗ ∇xxL(x , λ ) − γI ∇h (x ) =0 p(γ) = det (67) ∗ T ∇h (x ) 0 polinomegyenlet gyökeinek, vagy a ¸ · 2 ∗ ∗ ∗ ∇xxL(x , λ ) ∇h (x ) (n+m)×(n+m) ∈ R T ∇h (x∗) 0

(68)

szegélyezett mátrix sajátértékeinek elýojelvizsgálatával dönthetjük el (negatív, zérus és pozitív sajátértékek száma).



71

Megjegyezés: A szegélyezett mátrix az L (x, λ) Lagrangefüggvény (x, λ) változó szerinti Hesse-mátrixa az (x∗, λ∗) helyen, azaz ¸ · 2 ∗ ∗ ∗ ∇xxL(x , λ ) ∇h (x ) = ∇2(x,λ),(x,λ)L (x∗, λ∗) . (69) ∗ T ∇h (x ) 0



72

A (49) feltételes optimalizálási feladat megoldása a következýoképpen történhet: 1. Megoldjuk a

∇xL(x, λ) = 0,

h (x) = 0

(70)

egyenletrendszert. Jelölje a megoldást (x∗, λ∗)! 2. Ellenýorizzük a ∇2xxL(x∗, λ∗) Hesse-mátrix feltételes deÞnitségét a fenti két tétel valamelyikével.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa. Határozzuk meg az (x1 − 4)2 + (x2 − 3)2 = 1 kör origóhoz legközelebbi és legtávolabbi pontját!


73


74

Az

x21 + x22 → extr h1 (x1, x2) = (x1 − 4)2 + (x2 − 3)2 − 1 = 0 feladatot kell megoldanunk. A célfüggvényt és a h (x1, x2) = 0 feltételt szemléltetõ hengerpalástot a következõ ábrán láthatjuk:



75

Látható, hogy a hengerpalást és a z = x21 + x22 felület metszéspontja adja a célfüggvény értékeit a megengedett megoldások halmazán. Ennek egy legkisebb és egy legnagyobb pontja van.



76

A feladat Lagrange-függvénye:

³ ´ L (x1, x2, λ) = x21 + x22 + λ (x1 − 4)2 + (x2 − 3)2 − 1 .

Ennek gradiensére fenn kell, hogy álljon

∇xL (x1, x2, λ) = [2x1 (1 + λ) − 8λ, 2x2 (1 + λ) − 6λ]T = 0 ∈ R2 Az egyenletrendszer megoldása

x1 = x1 (λ) = 4λ/ (1 + λ) ,

x2 = x2 (λ) = 3λ/ (1 + λ) ,

amelyet a feltételi egyenletbe helyettesítve



25 h (x1 (λ) , x2 (λ)) = 2 −1=0 (1 + λ) adódik. Innen a lehetséges megoldások: 16 12 λ = 4, x1 = , x2 = 5 5 és 24 18 λ = −6, x1 = , x2 = . 5 5 Mindkét pont reguláris.


77


78

A pontok jellegét elýoször a determináns tétel alapján ellenýorizzük. Ekkor   2 (1 + λ) − γ 0 2x1 − 8 0 2 (1 + λ) − γ 2x2 − 6  = 0, p (γ) = det  2x1 − 8 2x2 − 6 0 amelyet kifejtve kapjuk, hogy



´ ³ 2 2 p (γ) = 4 (x1 − 4) + (x2 − 3) (γ − 2 (1 + λ)) = 0.

79

Innen az egyetlen gyök γ = 2 (1 + λ). Ha λ = 4, akkor γ = 10, ami a determináns tétel szerint azt jelenti, hogy a (16/5, 12/5) pont szigorú lokális minimumhely. A λ = −6 pont esetén γ = −10, amibýol az következik, hogy a (24/5, 18/5) pont szigorú lokális maximumhely.



80

A Chabrillac-Crouzeix tétel alapján eljárva kapjuk, hogy a szegélyezett mátrix   2 (1 + λ) 0 2x1 − 8  0 2 (1 + λ) 2x2 − 6  . 2x1 − 8 2x2 − 6 0 12 Ennek sajátértékei a λ = 4, x1 = 16 , x = 2 5 5 esetben: 10, -0.3851, 10.3851. A negatív sajátértékek száma 1, a zérus sajátértékek száma 0, a pozitívaké pedig 2. Eszerint itt a feladatnak szigorú lokális minimuma van.



81

A szegélyezett mátrix sajátértékei a λ = −6, x1 = 24 5 , x2 = 18 5 esetben: -10, -10.3851, 0.3851. Tehát 2 negatív, 0 zérus és 1 pozitív sajátérték van, aminek következtében az adott pont szigorú lokális maximumhely. A kapott pontok nemcsak lokális szélsýoérték helyek, hanem globálisak is. Ez a Weierstrass tételbýol következik.



82

DeÞníció: Legyen A ∈ Rn×n szimmetrikus mátrix. Az in (A) = (n+, n0, n−) vektort az A mátrix inerciájának nevezzük, ha n+ az A pozitív, n0 az A zérus, n− pedig az A negatív sajátértékeinek a számát jelenti. Értelemszerýuen n = n+ + n0 + n−. A Chabrillac-Crouzeix tétel tkp. a szegélyezett mátrix inerciáját használja fel. Az inercia meghatározása véges lépésben pl. Egerváry rangszámcsökkentõ algoritmusával lehetséges.



83

6 Egyenlýotlenségi feltételek Lényegesen bonyolultabb. Vizsgáljuk a következýo általános esetet f (x) → min h (x) = 0, (71) g (x) ≤ 0, ahol f : Rn → R, h : Rn → Rm, g : Rn → Rr adott függvények és m + r < n.



84

DeÞníció. Ha gj (x) = 0 (x ∈ S ), akkor j -edik egyenlýotlenségi feltétel az x pontban aktív. Az x ∈ S pontban aktív egyenlýotlenségi feltételek halmazát

A (x) = {j | gj (x) = 0}

(72)

jelöli. Egy gj (x) ≤ 0 egyenlýotlenségi feltétel az x ∈ S pontban inaktív, ha gj (x) < 0.



85

DeÞníció. Legyen x∗ ∈ S és h, g ∈ C 1 (S (x∗, ε)) valamilyen ε > 0 értékre. Az x∗ pont reguláris, ha a

∇h1 (x∗) , . . . , ∇hm (x∗) , ∇gj (x∗)

gradiens vektorok lineárisan függetlenek.

(j ∈ A (x∗))


(73)


86

Vezessük be a z = [z1, . . . , zr ]T ∈ Rr változót az alábbiak szerint: g1 (x) + z12 = 0, . . . , gr (x) + zr2 = 0. (74) Legyen továbbá

F (x, z) = f (x) , Hi (x, z) = hi (x) (i = 1, . . . , m) , Gj (x, z) = gj (x) + zj2 (j = 1, . . . , r) , valamint H = [H1, . . . , Hm]T és G = [G1, . . . , Gr ]T .


(75)


87

Könnyýu belátni, hogy ha x∗ az eredeti feladat lokális minimumhelye, akkor az   ∗ p x  −g1 (x∗)   ∈ Rn+r  (76) .   . p −gr (x∗) pont az ekvivalens

F (x, z) → min H (x, z) = 0, G (x, z) = 0, optimumfeladat lokális minimumhelye. Tehát alkalmazható a Lagrange-féle elmélet.


(77)


88

Tétel (Carathéodory, John). Legyenek f , hi (i = 1, . . . , m) és gj (j = 1, . . . , r) folytonosan differenciálhatók egy G ⊆ Rn halmazon. Tegyük fel, hogy x∗ ∈ G belsýo pont és egyúttal az (71) feladat lokális minimuma. Ekkor létezik λ0 ∈ R, λ ∈ Rm és µ ∈ Rr úgy, hogy m r X X λ0∇f (x∗) + λi∇hi (x∗) + µj ∇gj (x∗) = 0, (78) i=1

µ ≥ 0, és

j=1

r X

µj gj (x∗) = 0

(79)

j=1

·

λ µ

¸

6= 0.


(80)


89

A tétel

µ ≥ 0,

r X

µj gj (x∗) = 0

j=1

szükséges feltételét szokás az alábbi ekvivalens formában is megadni:

µ ≥ 0,

µj gj (x∗) = 0,

j = 1, . . . , r.


(81)


90

Az ekvivalenciát elég csak egyik irányban igazolni. Ha gj (x∗) ≤ 0, akkor két lehetýoség áll fenn: 1. Ha gj (x∗) = 0, azaz j ∈ A (x∗), akkor µj gj (x∗) = 0 is fennáll. 2. Ha ∃j ∈ / A (x∗), hogy gj (x∗) < 0 és µj > 0, akkor µj gj (x∗) < 0 miatt r X j=1

∗

µj gj (x ) =

X

µj gj (x∗) < 0

∗) j ∈A(x /

lenne, ami ellentmondás. Tehát a gj (x∗) < 0 esetekben szükségképpen µj = 0. Ezzel igazoltuk, hogy fenn kell állnia a µj gj (x∗) = 0 (j = 1, . . . , r) feltételnek.



91

A Carathéodory-John tétel híres következménye a következýo Tétel (Karush, Kuhn, Tucker). Ha az x∗ pont reguláris, akkor a Carathéodory-John tétel a λ0 = 1 választással igaz.



92

A tétel alapján bevezethetjük a

L (x, λ, µ) = f (x) + λT h (x) + µT g (x)

(λ ∈ Rm, µ ∈ Rr ) (82) Lagrange-féle függvényt és az alábbi fogalmat.



93

DeÞníció. Az x∗ ∈ S pontot az (71) szélsýoérték feladat KKTLpontjának (Karush-Kuhn-Tucker-Lagrange pontjának) nevezzük, ha léteznek λ∗ ∈ Rm és µ∗ ∈ Rr Lagrange-szorzók úgy, hogy · ∗¸ λ 6= 0, µ∗ ≥ 0, (83) µ∗ és

∇xL (x∗, λ∗, µ∗) = 0

(84)

(µ∗)T g (x∗) = 0.

(85)



94

Tétel. Legyen x∗ ∈ S az (71) szélsýoérték feladat reguláris KKTLpontja és tegyük fel, hogy µ∗j > 0 minden j ∈ A (x∗) esetén. Tegyük fel továbbá, hogy f, h, g ∈ C 2 (S (x∗, ε)) valamilyen ε > 0 értékre. Ha fennáll

y T ∇2xxL (x∗, λ∗, µ∗) y > 0

∇gj (x∗)T y = 0 (∀j ∈ A (x∗)) (87) esetén, akkor x∗ szigorú lokális minimum pont. ∀y 6= 0,

∇h (x∗)T y = 0,

(86)



95

A feltételes pozitiv deÞnitség ellenýorzésére vezessük be a Z mátrixot, amelynek oszlopait a

∇hi (x∗) , i = 1, . . . , m, és ∇gj (x∗) , j ∈ A (x∗)

vektorok alkotják. Legyen s a Z oszlopainak száma. Ha a ¸ · 2 ∗ ∗ ∗ ∇xxL (x , λ , µ ) Z ZT 0

(88)

(89)

szegélyezett mátrixnak s negatív, 0 zérus és n pozitív sajátértéke van, akkor x∗ szigorú lokális minimumhely. A tétel alkalmazásához szükséges, hogy µ∗j > 0 teljesüljön minden j ∈ A (x∗) esetén.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa. Oldjuk meg a

feladatot!

f (x1, x2, x3) = −x1x2x3 → min g (x1, x2, x3) = x1 + 3x2 + 9x3 − 9 ≤ 0


96


97

A Lagrange-függvény

L (x1, x2, x3, µ) = −x1x2x3 + µ (x1 + 3x2 + 9x3 − 9) ,

amelynek gradiense

∇xL (x, µ) = [µ − x2x3, 3µ − x1x3, 9µ − x1x2]T = 0 ∈ R3.

Innen és az x1 + 3x2 + 9x3 − 9 = 0 feltételbýol a 1 1 µ = , x1 = 3, x2 = 1, x3 = 3 3 megoldás (KKTL pont) adódik.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Az egyenlýotlenségi feltétel aktív, A = {1} (így kaptuk a KKTL pontot) és µ > 0. A KKTL pont reguláris, mert ∇g = [1, 3, 9]T 6= 0. Esetünkben Z = ∇g = [1, 3, 9]T és a szegélyezett mátrix   1 0 − 3 −1 1  − 1 0 −3 3    3  −1 −3 0 9  . 1 3 9 0

98

Ennek sajátértékei 9, 0.1609, 1.7137, -10.8747, amibýol megállapíthatjuk, hogy 1 negatív, 0 zérus és 3 pozitív sajátérték van. Az elégséges tétel alapján a KKTL pontban szigorú lokális minimum van.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa. Oldjuk meg az

feladatot!

f (x, y, z) = x2 + y 2 − z 2 → min h (x, y, z) = z − p = 0 g (x, y, z) = 1 − x − y − z ≤ 0


99


100

A feladat Lagrange-függvénye:

L (x, y, z, λ, µ) = x2 + y 2 − z 2 + λ (z − p) + µ (1 − x − y − z) , amelynek gradiense

∇xL (x, y, z, λ, µ) = [2x − µ, 2y − µ, −2z + λ − µ]T = 0 ∈ R3. Felhasználva a h (x, y, z) = 0 és g (x, y, z) = 0 feltételeket (az egyenlýotlenségi feltételt aktívnak tekintjük, A = {1}), kapjuk, hogy a megoldás (KKTL pont) 1−p 1−p , y= , z = p. λ = 1 + p, µ = 1 − p, x = 2 2



101

Ha p < 1, akkor µ > 0. Esetünkben ∇h = [0, 0, 1]T és ∇g = [−1, −1, −1]T lineárisan függetlenek, tehát a KKTL pont reguláris. Így   0 −1 Z = [∇h, ∇g] =  0 −1  1 −1 és a megfelelýo szegélyezett mátrix





2  0   0   0 −1

0 2 0 0 −1

0 0 −2 1 −1

0 0 1 0 0

102



−1 −1   −1  . 0  0

A sajátértékek: -0.5082, -2.7823, 0.5082, 2, 2.7823, amibýol megállapítható, hogy 2 negatív,¡ 0 zérus és¢3 pozitív sajátérték 1−p van. Ha tehát p < 1, akkor az 1−p , 2 2 , p pont szigorú lokális minimumhely. A célfüggvény értéke pedig µ ¶ 1−p 1−p 1 − 2p − p2 , ,p = . fmin 2 2 2



103

Egyszerû fogásokkal meghatározhatjuk a fenti feladat globális minimumát is. Minthogy z = p, azért a feladat felírható az f1 (x, y) = x2 + y 2 − p2 → min g1 (x, y) = 1 − p − x − y ≤ 0 kétváltozós ekvivalens alakban is. Legyen most

g1 (x, y) = 1 − p − x − y = a ≤ 0,

ahol a ≤ 0 egy újabb paraméter. Innen x = 1 − p − a − y és

f1 (x, y) = 2y 2 + 2y (a + p − 1) + a2 + 2a (p − 1) − 2p + 1.



104

Ez y -ban akkor minimális, ha y = (1 − p − a) /2. Ekkor x = (1 − p − a) /2 és µ ¶ 1−p−a 1−p−a , min f1 = f1 1−p−x−y=a 2 2 a2 + 2a (p − 1) + 1 − 2p − p2 = . 2 Tetszõleges, de rögzített p esetén a jobboldali kifejezés akkor minimális, ha a = 1 − p.



105

Az a ≤ 0 feltétel miatt ez csak a p ≥ 1 esetben ad megoldást. Ekkor azonban x = y = 0 (z = p), fmin = −p2 és az egyenlõtlenségi feltétel p > 1 esetén inaktív. Ha p < 1, akkor p − 1 < 0 és a2 + 2a (p − 1) ≥ 0 (a ≤ 0). Tehát a p < 1 esetben a fenti jobboldali kifejezés minimumát ¡ az a = 20¢helyen éri el. Ekkor x = y = (1 − p) /2, fmin = 1 − 2p − p /2 és az egyenlõtlenségi feltétel aktív



106

Következésképpen a korábban kapott ”lokális” minimum valójában globális. Azt, hogy egy globális minimumhely van, a z = x2 + y 2 − p2 forgás paraboloid és a z = 1 − p − x − y síkok egyidejû ábrázolásával is láthatjuk. A következõ két ábra a p = 1/2 és p = 2 eseteknek felel meg:



A p = 1/2 eset.


107


A p = 2 eset.


108


109

DeÞníció: Elsýorendýu optimalitási feltételek: ∇xL (x, λ) = 0, ill. ∇xL (x, λ, µ) = 0. Másodrendýu optimalitási feltételek:a ∇2xxL (x, λ), ill. ∇2xxL (x, λ, µ) Hesse-mátrixok feltételes (pozitív) (szemi) deÞnitsége. Megjegyzés: Fontos speciális esetekben a másodrendýu feltételek vizsgálata elhagyható.



110

7 A konvex programozási feladat Egy programozási feladat konvex, ha a célfüggvény és a feltételi függvények konvexek és csak egyenlýotlenség típusú korlátozó feltételek vannak. DeÞníció. Az X ⊆ Rn halmaz konvex, ha bármely két pontját összekötýo szakaszt is tartalmazza. Képletben: X konvex ⇔

∀x, y ∈ X ⇒ λx + (1 − λ) y ∈ X

(∀λ ∈ [0, 1])


(90)


111

A konvex egyváltozós függvény olyan, amely mindig a húrja alatt van. DeÞníció. Az f : Rn → R függvény konvex a D ⊂ D (f ) konvex halmazon, ha

f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y)

teljesül ∀x, y ∈ D és ∀λ ∈ [0, 1] esetén.


(91)


112

DeÞníció. Az f : Rn → R függvény konkáv a D ⊂ D (f ) konvex halmazon, ha −f konvex. Eszerint a konkávitás feltétele: x, y ∈ D, λ ∈ [0, 1] ⇒

f (λx + (1 − λ) y) ≥ λf (x) + (1 − λ) f (y) .


(92)


113

1.Példa. Legyen B ∈ Rn×n szimmetrikus valós mátrix, p ∈ Rn és c ∈ R. Az f (x) = xT Bx + pT x + c (93) kvadratikus függvény akkor és csak akkor konvex, ha a B mátrix pozitív szemideÞnit.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 2. Példa. Legyen a ∈ Rn és b ∈ R. Az

f (x) = aT x − b

114

(94)

lineáris függvény konvex és egyúttal konkáv is. Ez triviális, mert λ ∈ [0, 1] és x, y ∈ Rn esetén ¡ T ¢ ¡ T ¢ T a (λx + (1 − λ) y) − b = λ a x − b + (1 − λ) a y − b .



115

Tétel. Legyen φ : Rn → R konvex függvény a konvex D ⊂ Rn halmazon. A következýo állítások igazak: 1. Tetszýoleges c ∈ R esetén az Lc = {x ∈ D|φ (x) ≤ c} szint-, vagy nívóhalmaz konvex. 2. A ξ (x) = max {φ (x) , 0} függvény konvex az D halmazon.



116

3. Ha φ (x) ≥ 0 (x ∈ D), akkor a φ2 (x) függvény is konvex az D halmazon. 4. Ha x∗ ∈ D a φ (x) lokális minimumhelye, akkor x∗ egyúttal a φ (x) globális minimumhelye is az D halmazon. A 2. és 3. tulajdonságot a büntetýofüggvény módszereknél használjuk ki.



117

Tétel. Tegyük fel, hogy φ : Rn → R differenciálható az D ⊆ Rn konvex halmazon. A φ (x) akkor és csak akkor konvex az D halmazon, ha fennáll

φ (y) − φ (x) ≥ ∇φ (x)T (y − x) ,

∀x, y ∈ D.


(95)


118

DeÞníció. A konvex optimalizálás alapfeladatának nevezzük az

f (x) → min g (x) ≤ 0

(f : Rn → R, g : Rn → Rr )

(96)

optimalizálási feladatot, ahol f (x), g1 (x) , . . . , gr (x) konvex függvények. Példa: A

cT x → min Ax ≤ b, x ≥ 0

¢ ¡ m×n A∈R

lineáris programozási feladat konvex.



119

Minthogy konvex halmazok metszete konvex és

S = {x ∈ Rn|gi (x) ≤ 0, i = 1, . . . , r} = ∩ri=1 {x ∈ Rn|gi (x) ≤ 0}

(97) (98)

az 1. tulajdonságból következik, hogy S konvex. A 4. tulajdonság miatt a konvex optimalizálási alapfeladatnál a lokális minimumhely egyúttal globális is.



120

DeÞníció. A megengedett megoldások S halmaza kielégíti a Slater-féle regularitási feltételt, ha létezik olyan x ∈ S pont, hogy g (x) < 0, azaz

gi (x) < 0,

i = 1, . . . , r.


(99)


121

Tétel (Kuhn, Tucker). Legyenek f, g1, . . . , gr konvex és folytonosan differenciálhatók az Rn téren és tegyük fel, hogy a megengedett megoldások halmaza Slater-reguláris. Az x∗ ∈ S ⊆ Rn pont akkor és csak akkor optimális megoldása a konvex programozási feladatnak, ha létezik µ∗ ∈ Rr úgy, hogy

µ∗j ≥ 0,

∇xL (x∗, µ∗) = 0, µ∗j gj (x∗) = 0 (j = 1, . . . , r) .


(100)


122

A tétel tkp. azt mondja ki, hogy a konvex programozási feladatoknál a Karush-Kuhn-Tucker-féle szükséges feltétel egyúttal elégséges is. Ezért itt a másodrendýu optimalitási feltételeket nem kell vizsgálni.



123

Példa. Határozzuk meg az (x − 1)2 + (y − 2)2 → min feladat megoldását a g (x, y) = x2 + 4x − y + 6 ≤ 0 mellékfeltétel mellett! A feladat tkp. az y = x2 + 4x + 6 parabolának az (1, 2) ponthoz legközelebbi pontjának meghatározását jelenti. A célfüggvény és a feltételi függvény konvexek. A megengedett megoldások halmaza Slater-reguláris, ui. pl.

g (−2, 3) = −1 < 0.



124

A feladat Lagrange-függvénye

¡ 2 ¢ L (x, y, µ) = (x − 1) + (y − 2) + µ x + 4x − y + 6 , 2

2

amelynek x és y szerinti parciális deriváltjaira fenn kell, hogy álljon ∂ L (x, y, µ) = 2x (1 + µ) + 4µ − 2 = 0, ∂x ∂ L (x, y, µ) = 2y − µ − 4 = 0. ∂y



125

A megoldás:

1 − 2µ , x = x (µ) = 1+µ ahonnan

g(x(µ)), y(µ)) =

4+µ y = y (µ) = , 2

¢ ¡ 2 (2 − µ) µ + 4µ + 9 2

2 (µ + 1)

.

A g(x∗, y ∗) ≤ 0, µ∗ ≥ 0, µ∗g(x∗, y ∗) = 0 feltételeket csak a µ∗ = 2 választás elégíti ki, amikor is x∗ = −1 és y ∗ = 3.



126

DeÞníció. Legyen az F (x, µ) függvény F : Rn × Rm → R tipusú. Az (x∗, µ∗) pont (x∗ ∈ Rn, µ∗ ∈ Rm, µ∗ ≥ 0) a F (x, µ) függvény nyeregpontja, ha minden x ∈ Rn és µ ∈ Rm, µ ≥ 0 esetén teljesül a

F (x∗, µ) ≤ F (x∗, µ∗) ≤ F (x, µ∗)

(101)

egyenlýotlenség. Az F (x, µ∗) függvénynek az x∗ pontban lokális minimuma, az F (x∗, µ) függvénynek pedig a µ∗ pontban lokális maximuma van.



127

Tétel. Tegyük fel, hogy a konvex programozási alapfeladat olyan, hogy S Slater-reguláris. Ha létezik x∗ ∈ S és µ∗ ∈ Rr úgy, hogy az L (x, µ) = f (x) + µT g (x) (x ∈ S , µ ∈ Rr ) Lagrange-függvényre fennáll az

L (x∗, µ) ≤ L (x∗, µ∗) ≤ L (x, µ∗) ,

x ∈ Rn, µ ≥ 0, (102)

akkor a konvex optimalizálási feladatnak az x∗ pontban minimuma van. Fordítva, ha x∗ a konvex optimalizálási feladat minimumhelye, akkor létezik µ∗ ∈ Rr , µ∗ ≥ 0 úgy, hogy fennáll a (102) nyeregpont egyenlýotlenség.



128

Példa. Tekintsük az f (x) = (x − 1)2 + 2 → min, x2 − 1 ≤ 0 feladatot! A megfelelýo Lagrange függvény ¡ 2 ¢ 2 L (x, w) = (x − 1) + 2 + w x − 1 , amelyet az alábbi ábra mutat be.



Lagrange-függvény


129


130

Példa. A

−x1 + x2 → min x21 + x2 ≤ 0, x2 ≥ 0

konvex optimalizálási feladatnak csak egyetlen megengedett megoldása van: (0, 0)T . Ez egyúttal az optimális megoldás is. o n T Az S = [0, 0] halmaz nem Slater-reguláris. A feladat Lagrange-függvénye: ¡ 2 ¢ L (x, µ) = −x1 + x2 + µ1 x1 + x2 + µ2 (−x2) .



131

Minthogy L (x, µ) differenciálható, a feltételezett nyeregpontban teljesülnie kell a ¸ · 2µ1x1 − 1 ≥0 ∇xL (x, µ) = µ1 − µ2 + 1

és

·

x21

¸

+ x2 ≤0 ∇µL (x, µ) = −x2 feltételeknek. Ennek az egyenlýotlenség rendszernek pedig nincs megoldása. Tehát a Lagrange-függvénynek nincs nyeregpontja.



132

8 Duális programozási feladatok Az

f (x) → min g (x) ≤ 0 primál konvex optimalizálási feladat duálisa a L (x, µ) → max x ∈ Rn, µ ∈ Rr , µ ≥ 0, ∇xL (x, µ) = 0

(103)

(104)

programozási feladat. A két feladat viszonya speciális és ez sok esetben igen hasznos.



133

A duális feladat megengedett megoldásainak halmazát jelölje ½· ¸ ¾ x Sd = | x ∈ Rn, µ ∈ Rr , µ ≥ 0, ∇xL (x, µ) = 0 . µ



134

Tétel (gyenge dualitási tétel). Ha f (x) , g1 (x) , . . . , gr (x) differenciálható konvex függvények Rn-en, akkor ¾ ½ · ¸ x inf {f (x) |x ∈ S} ≥ sup L (x, µ) | ∈ S d . (105) µ

A tétel jelentése: a primál feladat minimuma, ha létezik nem lehet kisebb mint a duál feladat maximuma (ha létezik). Az un. erýos dualitási tételek a két optimum egyenlýoségét mondják ki létezés esetén.



135

Vizsgáljuk a

cT x → min (LP) Ax ≤ b, x ≥ 0, lineáris programozási feladatot, ahol A ∈ Rm×n, c ∈ Rn és b ∈ Rm.



136

Hozzuk a feltételi egyenlýotlenségeket a

gi (x) = aTi x − bi ≤ 0 (i = 1, . . . , m), −x ≤ 0

alakra, ahol aTi az A mátrix i-edik sorvektora. Az (LP) feladat Lagrange függvénye

L (x, µ, ν) = cT x + µT (Ax − b) − ν T x.


(106)


137

A Kuhn-Tucker tétel alapján teljesülnie kell a

∇xL (x, µ, ν) = c + AT µ − ν = 0, µ ≥ 0, µT (Ax − b) = 0 ν ≥ 0, ν T x = 0

(107)

feltételnek. Elimináljuk ν -t a Lagrange-függvénybýol és a feltételekbýol.



138

Minthogy ν = c + AT µ kapjuk, hogy

¡ ¢T T L (x, µ, ν) = c x + µ (Ax − b) − c + A µ x = −bT µ = L (µ) . T

T

Figyelembevéve, hogy ν ≥ 0 ⇔ AT µ ≥ −c, a primál (LP) feladat duálisa: −bT µ → max (DLP) AT µ ≥ −c, µ ≥ 0.



139

Tétel (A lineáris programozás dualitási tétele). (a) (Gyenge dualitás): Fennáll, hogy © T ª © T ª T inf c x|Ax ≤ b, x ≥ 0 ≥ sup −b µ|A µ ≥ −c, µ ≥ 0 . (108) (b) (Erýos dualitás): Ha a primál, vagy a duál feladatok valamelyikének van optimális megoldása, akkor a másiknak is van és a két optimum (célfüggvényérték) megegyezik.



140

9 Minimumkeresýo eljárások Fýo lehetýoségek: 1. Gyökkeresýo eljárás alkalmazása a ∇f (x) = 0 stacionárius egyenletre. 2. Direkt keresýo eljárások. 3. A kétféle közelítés kombinációja. 9.1 Egyváltozós függvények direkt keresýo eljárásai 1. Csak az f függvény értékeit használják fel; 2. Az x∗ minimumhelyet tartalmazó un. befoglaló intervallumból indulnak ki és ezt szýukitik az eljárások során.



141

DeÞníció. Az f ∈ C [a, b] függvény unimodális, ha tetszýoleges x1, x2 ∈ [a, b], x1 < x2 esetén

x2 ≤ x∗ ⇒ f (x1) > f (x2) , x1 ≥ x∗ ⇒ f (x1) < f (x2) .

Az unimodális f az x∗ minimumhelytýol balra szigorúan monoton csökkenýo, týole jobbra szigorúan monoton növýo. A szigorúan konvex függvények unimodálisak. A keresýo eljárások a következýo észrevételen alapulnak.


(a) (b)


Unimodális függvény minimumhelye


142


143

Tétel. Legyen f ∈ C [a, b] unimodális és a < c < d < b. (i) Ha f (c) < f (d), akkor x∗ ∈ [a, d]. (ii) Ha f (c) > f (d), akkor x∗ ∈ [c, b]. (iii) Ha f (c) = f (d), akkor x∗ ∈ [c, d]. Bizonyítás. (i) Tegyük fel, hogy x∗ > d. Akkor (a) miatt f (c) > f (d), ami ellentmondás. A többi rész igazolása hasonló. ¤ Megjegyezés: Csak egy belsýo pontból származó információ alapján nem lehet a minimumhelyet tartalmazó intervallumot szýukiteni.



144

Általános keresõ algoritmus 1. Input [a1, b1], k := 1. 2. Legyen ck , dk ∈ (ak , bk ) és ck < dk . 3. Ha f (ck ) < f (dk ), akkor ak+1 := ak , bk+1 := dk . 4. Ha f (ck ) ≥ f (dk ), akkor ak+1 := ck , bk+1 := bk . 5. k := k + 1 és menjünk a 2. pontra. MegÞgyelések: 1. x∗ ∈ . . . ⊂ [ak , bk ] ⊂ . . . ⊂ [a1, b1]. 2. Ha bk − ak → 0, akkor az x∗ minimumhely adott ε > 0 pontosságú közelitését véges iterációs lépésben megkaphatjuk. 3. A ck vagy dk pont ismételt felhasználásával az f függvény behelyettesitéseinek száma csökkenthetõ.



145

¡√ ¢ Aranymetszõ keresés (τ := 5 − 1 /2 ≈ 0.618) Input [a1, b1], ε > 0, k := 1. c1 := a1 + (1 − τ ) (b1 − a1) , Fc := f (c1) d1 := b1 − (1 − τ ) (b1 − a1) , Fd := f (d1) while bk − ak ≥ ε if Fc < Fd ak+1 := ak , bk+1 := dk , dk+1 := ck , Fd := Fc ck+1 := ak+1 + (1 − τ ) (bk+1 − ak+1) , Fc := f (ck+1) else ak+1 := ck , bk+1 := bk , ck+1 := dk , Fc := Fd dk+1 := bk+1 − (1 − τ ) (bk+1 − ak+1) , Fd := f (dk+1) end k := k + 1 end



146

Ha az eljárás befejezýodik, akkor x∗ ∈ [ak , bk ] és bk − ak < ε. Javasolt közelítés: a k + bk ∗ , x ≈x e := 2 mert |e x − x∗| < ε/2. Az aranymetszýo keresést alkalmazzuk nem unimodális függvényekre is. Ekkor nincs garancia az eljárás konvergenciájára. Az aranymetszýo keresés sebessége lineáris. Vannak gyorsabb, de több információt felhasználó keresýo eljárások is. A kvadratikus interpolációs eljárás alapgondolata a következõ.



147

Tegyük fel, hogy 1. f (x) unimodális az [a, b] intervallumon. 2. x∗ ∈ [ak , bk ], ak < ck < bk és f (ak ) > f (ck ), f (ck ) < f (bk ). Közelítsük az f (x) függvényt az (ak , f (ak )), (bk , f (bk )), (ck , f (ck )) pontokon átmenõ Lagrange-féle interpolációs polinommal: h(x) = px2 + qx + r (x−ak )(x−bk ) k )(x−bk ) + f (c ) = f (ak ) (a(x−c k (ck −ak )(ck −bk ) + k −ck )(ak −bk ) k )(x−ck ) +f (bk ) (b(x−a k −ak )(bk −ck )



148

A h(x) parabola x e minimumhelye lesz az x∗ újabb közelítése. ∃hmin ⇔

p =

Ekkor

f (ak ) (ak −ck )(ak −bk )

+ (ck −afk(c)(ck )k −bk ) +

+ (bk −afk(b)(bk )k −ck ) > 0.

¡ 2 ¡ 2 ¡ 2 ¢ ¢ ¢ 2 2 2 ck − bk f (ak ) + bk − ak f (ck ) + ak − ck f (bk ) . x e= 2 [(ck − bk ) f (ak ) + (bk − ak ) f (ck ) + (ak − ck ) f (bk )]



Kvadratikus interpoláció unimodális függvényen


149

Optimálási módszerek, 2003/2004, II. félév (óravázlat) Lehetséges esetek: 1. x e < ck , f (e x) < f (ck ). Ekkor x∗ ∈ [ak , ck ], ak+1 bk+1 := ck , ck+1 := x e. 2. x e < ck , f (e x) ≥ f (ck ). Ekkor x∗ ∈ [e x, bk ], ak+1 bk+1 := bk , ck+1 := ck . 3. x e > ck , f (e x) < f (ck ). Ekkor x∗ ∈ [ck , bk ], ak+1 bk+1 := bk , ck+1 := x e. 4. x e > ck , f (e x) ≥ f (ck ). Ekkor x∗ ∈ [ak , x e], ak+1 bk+1 := x e, ck+1 := ck .


150

:= ak , := x e,

:= ck , := ak ,


151

Alkalmazható kilépési feltételek: vagy

bk+1 − ak+1 < ε,

|h (e x) − f (e x)| < ε, |f (e x)| amely az f (x) függvény közelítésének relatív hibája a közelítõ parabola minimumhelyén.



152

Parabola keresõ eljárás 1. Input [a1, b1], c1 ∈ (a1, b1), ε1 > 0, ε2 > 0, k := 1. 2. Számítsuk ki az ¡ 2 ¡ 2 ¡ 2 ¢ ¢ ¢ 2 2 2 ck − bk f (ak ) + bk − ak f (ck ) + ak − ck f (bk ) x e := 2 [(ck − bk ) f (ak ) + (bk − ak ) f (ck ) + (ak − ck ) f (bk )]

és f (e x) értékeket! 3. Ha x e < ck ∧ f (e x) < f (ck ), akkor

ak+1 := ak , bk+1 := ck , ck+1 := x e.

4. Ha x e < ck ∧ f (e x) ≥ f (ck ), akkor

ak+1 := x e, bk+1 := bk , ck+1 := ck .



153

5. Ha x e > ck ∧ f (e x) < f (ck ), akkor

ak+1 := ck , bk+1 := bk , ck+1 := x e.

6. Ha x e > ck ∧ f (e x) ≥ f (ck ), akkor

ak+1 := ak , bk+1 := x e, ck+1 := ck .

7. Ha bk+1 − ak+1 < ε, vagy

|h(e x)−f (e x)| |f (e x)|

< ε, akkor vége. 8. Legyen k := k + 1 és menjünk a 2. pontra! Az eljárás gyorsabb mint az aranymetszõ keresés. Gyakran alkalmazzák nem unimodális függvényekre, amikor is a konvergencia nem feltétlenül teljesül.



154

9.2 Többváltozós függvények keresýo eljárásai 9.2.1 A Newton-módszer Az

F (x) = 0 (F : Rn → Rn) egyenletrendszer alakja: −1

ahol

xk+1 = xk − [F 0 (xk )]

F (xk )

·

¸n

F 0 (x) =

∂Fi (x) ∂xj

(k = 0, 1, . . .) ,

i,j=1

∈ Rn×n.


(109) (110)


155

Az F 0 (x) Jacobi-mátrix invertálásának elkerülése miatt az eljárást a for k = 0, 1, . . . F 0 (xk ) sk = −F (xk ) (111) xk+1 = xk + sk end alakban használjuk.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Ha F (x) = ∇f (x) = 0, akkor a Jacobi mátrix alakja ¸n · 2 ∂ f (x) 0 2 F (x) = ∇xxf (x) = , ∂xi∂xj i,j=1

156

(112)

ami azonos f (x) függvény Hesse-mátrixával. Ekkor a Newtonmódszer alakja for k = 0, 1, . . . ∇2xxf (xk ) sk = −∇f (xk ) xk+1 = xk + sk end


(113)


157

∇2xxf (xk ) szimmetrikus. Ha xk ≈ xmin és ∇2xxf (xmin) pozitív deÞnit, akkor ∇2xxf (xk ) is pozitív deÞnit. Ekkor a Cholesky-módszert célszerýu alkalmazni. A Newton-módszer lépésenkénti számítási költsége: 1 szimmetrikus lineáris egyenletrendszer megoldása, a ∇f (x) a gradiens vektor és a ∇2xxf (x) Hesse-mátrix kiértékelése. A Newton-módszer fenti alakját megkaphatjuk egy más okfejtéssel is!



158

Közelítsük az f (x) függvényt az xk pontban az

1 T 2 f (xk + s) ≈ qk (s) = f (xk ) + ∇f (xk ) s + s ∇xxf (xk ) s 2 (114) kvadratikus kifejezéssel. Ennek minimumhelyét a T

∇2xxf (xk ) s = −∇f (xk )

egyenletrendszer megoldása adja, ahonnan az f (x) minimumhelyének következýo közelitése: £ 2 ¤−1 xk+1 = xk − ∇xxf (xk ) ∇f (xk ) .



159

¢ ¡ 2 2 + (1 − x)2, amelynek Példa. Legyen f (x, y) = y − x egyetlen minimumhelye az (1, 1)T pont. A (0, 0)T pontban vett ”érintýoparaboloid” q (x, y) = 1 − 2x + x2 + y 2, amelynek minimumhelye az (1, 0)T pont. A két függvényt a következýo ábra szemlélteti.



Függvény és érintõ paraboloidja


160


161

9.2.2 Módosított Newton-módszer Ha H(x) = ∇2xxf (x) rosszul kondicionált, akkor Newton helyett for k£= 0, 1, . . . ¤ 2 ∇xxf (xk ) + Ek sk = −∇f (xk ) xk+1 = xk + sk end

(115)

Ek nemnegatív elemû diagonális mátrix, ∇2f (xk ) + Ek jól kondícionált pozitív deÞnit.



162

Ek megválasztására sok algoritmus ismert. A legismertebb Gill és Murray eljárása. Legyen A szimmetrikus, ε ≥ 0 és β > 0 paraméter. Az eljárás R felsýo háromszögmátrixot és E = diag(εi) ≥ 0 diagonális mátrixot állít elýo, amelyekre A + E = RT R fennáll.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Gill-Murray algoritmus: for i = 1 : n Pi−1 γ ij = aij − k=1 rkj rki, i ≤ j ≤ n ¯ ¯ µi = max{¯γ ij ¯ : i < j ≤ n}

rii = max{ε, |γ ii|1/2 , µβi } γ ij rii , i < j rii2 − γ ii

rij =

εi = end

≤n


163


164

Javasolt β érték:

1 β = max{ max{|aij | : i 6= j}, max{|aii| : 1 ≤ i ≤ n}}. n (116) 2



165

9.2.3 Trust region módszerek Legyen

Ωk = {x : kx − xk k ≤ ∆k } az un. trust region (megbízhatósági tartomány). Az

(117)

xk+1 = xk + sk közelítést Ωk -ban keressük:

xk+1 = xk + sk ,

sk = arg min {qk (s) | ksk2 ≤ ∆k }

ahol ∆k > 0 az un. trust-region paraméter.


(118)

Optimálási módszerek, 2003/2004, II. félév (óravázlat) Jelölés: arg min f (x) = xmin, amelyre min f (x) = f (xmin). Megjegyzések: 1. Ha ∆k elég nagy, akkor feltétel nélküli eset. 2. Ha ∆k elég kicsi, akkor ez megszorítás. 3. ∆k értékét f (x) értékének becsült és tényleges csökkenését Þgyelembevéve változtatjuk


166


167

A trust region módszer algoritmusa x0 ∈ Rn, ∆0 > 0, 0 < µ < η < 1, 0 < γ 1 < 1 < γ 2 for i = 0, 1, . . . Határozzuk meg a min {qk (s) | ksk2 ≤ ∆k } feladat sk közelítõ megoldását! k )−f (xk +sk ) ρk := f (x f (xk )−qk (sk ) Ha ρk > µ, akkor xk+1 := xk + sk , egyébként xk+1 := xk . Határozzuk ∆k+1 értékét! end



168

A ρk > µ esetben az iterációs lépés sikeres. A ρk ≤ µ esetben az iterációs lépés sikertelen. A ρk hányados jelentése: a függvény tényleges csökkenése . a függvény jelzett csökkenése A ∆k paramétert megválasztó algoritmus a következõ.



169

A ∆k update algoritmus: Legyen 0 < µ < η < 1 és 0 < γ 1 < 1 < γ 2. a) Ha ρk ≤ µ, akkor ∆k+1 ∈ (0, γ 1∆k ]. b) Ha ρk ∈ (µ, η), akkor ∆k+1 ∈ [γ 1∆k , ∆k ]. c) Ha ρk ≥ η , akkor ∆k+1 ∈ [∆k , γ 2∆k ]. Az algoritmus a paraméterek megválasztására nem túl érzékeny. Néhány javasolt érték: µ = 0.25, η = 0, 75, γ 1 = 0, 25, γ 2 = 2.



170

A feltételes kvadratikus optimalizálási probléma megoldására vonatkozik a következõ Lemma (Gay, 1981): Az s = s (λ) vektor a

min {qk (s) | ksk2 ≤ ∆k }

(119)

feladat megoldása akkor és csak akkor, ha létezik λ ≥ 0 úgy, hogy ´ ³ ¡ 2 ¢ 2 2 ∇ f (xk ) + λI s = −∇f (xk ) , λ ksk2 − ∆k = 0. (120)



171

Eset szétválasztással adódik, hogy λ = 0 és ksk2 < ∆k , vagy λ > 0 és ksk2 = ∆k . Az utóbbi esetben kapjuk, hogy ¢ ¡ 2 ∇ f (xk ) + λI s (λ) = −∇f (xk ) , (121) ks (λ)k22 = ∆2k , amely λ-ban nemlineáris. Elég nagy k esetén ∆k már nem csökken, az ksk k = ∆k feltétel inaktívvá válik, λk = 0 és sk a Newton-lépéssel lesz azonos.



172

Minthogy

sk = sk (λk ) = −(∇2f (xk ) + λk I)−1∇f (xk ),

tkp. az egyváltozós

° 2 ° −1 ° ∆k = (∇ f (xk ) + λk I) ∇f (xk )°

egyenletet kell megoldanunk λk -ra.


(122)


173

A Hesse-mátrix szimmetrikus, tehát van olyan Q ortogonális mátrix, hogy ∇2f (xk ) = QΓQT , ahol Γ = diag(α1, . . . , αn). Ezért n 2 X ° ° d 2 j ksk k2 = °Q(Γ + λk I)−1QT ∇f (xk )° = 2, (αj + λk ) j=1

ahol dj a QT ∇f (xk ) vektor j -edik komponense. Mármost ebbõl következik, hogy Pn 2 Pn 2 j=1 dj j=1 dj 2 2 ≤ ksk k ≤ 2, (αn + λk ) (α1 + λk ) ahol α1 a ∇2f (xk ) legkisebb, αn a legnagyobb sajátértéke.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Tehát λk az

·

kdk kdk − αn , − α1 ∆k ∆k

¸

174

intervallumban van. Az α1 helyen ksk k-nak szingularitása van. Ezért a Newton-módszer nem a legjobban viselkedik. Hebden az ksk k = ∆k megoldása helyett javasolja az 1 1 =0 − (123) ∆k ksk k egyenlet megoldását, amelynek már nincs szingularitása.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Az eljárás variánsai: 1. A min {qk (s) | ksk2 ≤ ∆k } feladat helyett a

min {qk (s) | kDk sk2 ≤ ∆k }

175

(124)

alak, ahol Dk valamilyen skálázó mátrix. Ekkor az optimális megoldás sk meghatározható a módosított ´ ³ ¡ 2 ¢ 2 T 2 ∇ f (xk ) + λDk Dk s = −∇f (xk ) , λ kDk sk2 − ∆k = 0 (125) feltételbõl, ahol λ ≥ 0. Ezt az alakot használja pl. a LANCELOT programcsomag is.



176

2. Powell-féle dogleg lépés: Az xk pontból kiszámítunk egy

sN = −(∇2f (xk ))−1∇f (xk ) (126) ° N° Newton lépést. Ha °s ° ≤ ∆k , akkor sk := sN . Ha nem, akkor a leggyorsabb lecsökkenés irányába teszünk egy Cauchy-lépést, ahol

sC = −θ∇f (xk )

k∇f (xk )k2 θ= ∇f (xk )T ∇2f (xk )∇f (xk )

minimalizálja a qk (−θ∇f (xk )) függvényt.


(127)

Optimálási módszerek, 2003/2004, II. félév (óravázlat) 177 ° C° Ha °s ° ≥ ∆k , akkor az irányt elfogadjuk, de csökkentjük, azaz ∆k ∇f (xk ) sk := − (128) k∇f (xk )k ° N° ° C° lesz. Ha °s ° > ∆k és °s ° < ∆k , akkor

sk := αsN + (1 − α)sC

lesz, ahol 0 < α < 1 és ksk k = ∆k .


(129)


178

9.3 Kvázi-Newton módszerek

¡ 2¢ Iterációs lépésenkénti költségük O n ßop. Ezért a számítási összköltségük is kisebb mint a Newton-módszeré. Alapgondolatuk: F (x) = 0 (F : Rn → Rn)

nemlineáris egyenletrendszer. Legyen

x0 ≈ x∗,

B0 ≈ F 0 (x∗) .

A Newton-módszerben Bk ≈ F 0 (xk ) helyettesítést végzünk:


Optimálási módszerek, 2003/2004, II. félév (óravázlat) for k = 0, 1, . . . Bk sk = −F (xk ) . xk+1 = xk + sk end


179

(130)


180

A Bk mátrixot a Bk−1 mátrixból nyerjük egy, vagy több diadikus mátrix hozzáadásával. Egyrangú módositás (update) alakja:

Bk = Bk−1 + uk vkT

(uk , vk ∈ Rn) ,

(131)

Kétrangú módositás alakja:

Bk = Bk−1 + uk vkT + wk zkT

(uk , vk , wk , zk ∈ Rn) .


(132)


181

Tétel (Sherman-Morrison-Woodbury). Ha A nemszinguláris és fennáll, hogy 1 + v T A−1u 6= 0, akkor ¡ ¢ A−1uv T A−1 T −1 −1 A + uv . =A − (133) T −1 1+v A u ¡ 2¢ Ha Bk−1 inverze ismert, akkor Bk inverze O n ßop −1 mýuvelettel¡kiszámolható. Az s = −B F (xk ) mátrix-vektor k k ¡ 2¢ ¢ 2 szorzás O n ßop. Tehát az új xk+1 közelités költsége: O n ßop.



182

A Newton-módszer Gauss-eliminációt (Cholesky-módszert) használ az ∇2xxf (xk ) sk = −∇f (xk ) egyenletrendszer megoldására, amelynek mýuveletigénye O(n3) ßop. Ezért kvázi-Newton módszerek olcsóbbak. Hasonló eredményt lehet elérni a Bk mátrixok QRfelbontásával is.



183

Legyen

Bk ≈ F 0 (xk ) (134) Az xk+1 közelítést az Lk (x) = 0 megoldása adja. A kváziNewton módszerek esetén kikötjük, hogy F (x) ≈ Lk (x) = F (xk ) + Bk (x − xk ) ,

Lk+1 (xk ) = F (xk ) ,

Lk+1 (xk+1) = F (xk+1) .

(135)

Legyen yk = F (xk+1) − F (xk ). Ekkor a fenti két feltételbýol kapjuk az un. Bk+1sk = yk (136) szelýo egyenletet.



184

Az egyrangú kvázi-Newton update formulák általános alakja

Bk+1

(yk − Bk sk ) zkT = Bk + , T zk sk

(137)

ahol zk ∈ Rn alkalmas módon megválasztott paraméter. Az optimális Broyden-módszer esetén zk = sk .



185

Broyden módszer: x0 ≈ x∗, B0 ≈ F 0 (x∗),.

for k = 0, 1, . . . Bk sk = −F (xk ) xk+1 = xk + sk yk = F (xk+1) − F (xk ) (yk −Bk sk )sTk Bk+1 = Bk + sTk sk end


(138)


186

A Newton-módszer konvergencia rendje 2. A kvázi-Newton módszerek konvergencia rendje csak szuperlináris. A lépések lényegesen kisebb számitási költsége miatt a kvázi-Newton módszerek használata nagyméretýu feladatok esetén sok esetben elõnyösebb mint a Newton-módszeré. Minimalizálási feladatoknál olyan kvázi-Newton módszereket kell alkalmazni, amelyekben Bk szimmetrikus. Ezt biztosítják a kétrangú diáddal dolgozó kvázi-Newton módszerek.



187

A ma legjobbnak tartott eljárás a BFGS (Broyden-Fletcher-Goldfarb-Shanno) eljárás: for k = 0, 1, . . . Hk sk = −∇f (xk ) xk+1 = xk + sk yk = ∇f (xk+1) − ∇f (xk ) . yk ykT Hk sk sTk Hk Hk+1 = Hk + yT sk − sT Hk sk k k end Itt a Bk mátrixot a Hesse-mátrixra való utalásként Hk jelöli.


(139)


188

9.4 A vonalmenti minimalizálás algoritmusa 1. Input x1, k = 1. 2. Válasszuk meg az sk ∈ Rn keresési irányt! 3. Határozzuk meg az αk ∈ R+ értéket, amely minimumhelye a g (α) = f (xk + αsk ) (g : R → R) függvénynek, azaz f (xk + αk sk ) = min f (xk + αsk ) . (140) α≥0

4. xk+1 = xk + αk sk . 5. Legyen k = k + 1 és menjünk a 2. pontra!



Vonalmenti minimalizálás kvadratikus függvényen


189


190

Általános követelmények: Csökkenési feltétel:

f (x1) ≥ f (x2) ≥ . . . ≥ f (xk ) ≥ f (xk+1) ≥ . . . .

(141)

Állítás: A csökkenési feltétel teljesül, ha az sk irány olyan, hogy fennáll g 0 (0) = ∇f (xk )T sk < 0. (142)

Bizonyítás: g 0 (0) < 0 miatt a g (α) függvény csökkenýo az α = 0 helyen. ⇒

∃αk > 0 : f (xk+1) = f (xk + αk sk ) ≤ f (xk ) .



191

Armijo-Goldstein (AG) feltételek:

f (xk+1) ≤ f (xk ) + αk ρ∇f (xk )T sk

(143)

f (xk ) + αk σ∇f (xk )T sk ≤ f (xk+1) , (144) ¡ 1¢ ahol ρ ∈ 0, 2 , σ ∈ (ρ, 1) Þx paraméterek. 1 A gyakorlatban ρ = 10 (σ = 1 − ρ), vagy kisebb. AG feltételek: a függvényértékek se túl lassan, se túl gyorsan nem csökkenhetnek: αk > 0 és ∇f (xk )T sk < 0 miatt f (xk+1) ≤ f (xk ), de ¯ ¯ ¯ ¯ T |f (xk+1) − f (xk )| ≤ αk ¯∇f (xk ) sk ¯ . (145)



192

Egy αk lépéshossz akkor és csak akkor elégíti ki a két Armijo-Goldstein feltételt, ha

g (0) + αk σg 0 (0) ≤ g (αk ) ≤ g (0) + αk ρg 0 (0) .

(146)

Példa. Az f (x) = 2x41 + x42 − x21 − 2x22 függvény esetén legyen xk = [0.1, 0.4]T és sk = [−1, 1]T . A következõ ábrán a g (t) = f (xk + tsk ), y = g (0) + tρg 0 (0) és y = g (0) + tσg0 (0) függvényeket láthatjuk (ρ = 1/10, σ = 9/10).



Armijo-Goldstein feltételek


193


194

Szögfeltétel:

π θk = (sk , −∇f (xk ))∠ ≤ − µ, 2 T −∇f (xk ) sk ahol µ > 0 és cos (θk ) = k∇f (xk )k ksk k . 2

2


(147)


195

Az (144) feltétel helyett Wolfe-féle feltétel:

− ∇f (xk+1)T sk ≤ −σ∇f (xk )T sk ,

(148)

Egy αk lépéshossz akkor és csak akkor elégíti ki az (143) és (148) feltételeket, ha

g (αk ) ≤ g (0) + αk ρg 0 (0) ,

−g 0 (αk ) ≤ −σg 0 (0) . (149)



196

Példa. Az f (x) = 2x41 + x42 − x21 − 2x22 függvény esetén legyen xk = [0.1, 0.4]T és sk = [−1, 1]T . A következõ ábrán a g (t) = f (xk + tsk ), y = g (0) + tρg 0 (0) (Armijo felsõ) y = −g 0 (t) és y = −σg 0 (0) (Wolfe felsõ) függvényeket láthatjuk (ρ = 1/10, σ = 9/10).



Armijo-Wolfe feltételek


197


198

A két ábra összehasonlítása mutatja, hogy a vonatkozó feltételek nem ekvivalensek. Megjegyzés: A most vizsgált feltételek esetén a vonalmenti minimalizálások nem a g (t) = f (xk + tsk ) függvény t ≥ 0 feltétel melletti globális minimumát adják meg, hanem csak egy olyan αk > 0 pontot, amelyre fennáll f (xk ) ≥ f (xk + αk sk ). Bizonyos esetekben ez az αk minimumhely egy [0, T ] intervallumon.



199

Tétel. Tegyük fel, hogy minden k ≥ 1 esetén fennállnak az alábbi feltételek: (i) ∇f (xk )T sk < 0, (ii) αk > 0, (iii) f (xk+1) ≤ f (xk ) + αk ρ∇f (xk )T sk , (iv) −∇f (xk+1)T sk ≤ −σ∇f (xk )T sk . Ha f (x) kétszer folytonosan differenciálható és az Ω = {x : f (x) ≤ f (x1)} nívóhalmaz korlátos és zárt, akkor

∇f (xk )T sk = 0. lim k→+∞ ksk k


(150)


200

Bizonyítás. ∇f (xk )T sk < 0 ⇒ f (xk+1) ≤ f (xk ) és xk+1 ∈ Ω. f (x) az Ω halmazon alulról korlátos ⇒ {f (xk )} alulról korlátos (és monoton) ⇒ {f (xk )} konvergens. Tegyük fel, hogy (150) nem teljesül. Ekkor ∃ ² > 0, K végtelen indexhalmaz, hogy

∇f (xk )T sk ≥ ², − ksk k

(143) feltétel ⇒

k ∈ K.

Ã

T

∇f (xk ) sk f (xk ) − f (xk+1)≥ ραk ksk k − {z } | ksk k →0

!

⇒ {αk ksk k}k∈K zérushoz konvergál.


≥ ραk ksk k ²,

k


201

(148) feltétel ⇒ ´ ³ T (1 − σ) −∇f (xk ) sk ≤ (∇f (xk + αk sk ) − ∇f (xk ))T sk , ¯ T ¯ Ebbýol, az elýozýo és az ¯x y ¯ ≤ kxk kyk egyenlýotlenségekbýol

1 ∇f (xk )T sk ≤ k∇f (xk + αk sk ) − ∇f (xk )k , ²≤− ksk k 1−σ

k

k∈

Minthogy {αk ksk k}k∈K zérushoz tart és f (x) egyenletesen folytonos az Ω halmazon, a jobboldal zérushoz kell, hogy tartson. Ellentmondásra jutottunk. Tehát a (150) reláció teljesül. ¤



202

Ezt a fajta konvergencia tételt gyakran globálisnak nevezik, mert nincs benne feltevés az x1 kiindulási pont és a stacionárius pont közelségérýol. Következmény: Ha a (147) szögfeltételt is kikötjük, akkor

lim ∇f (xk ) = 0.

k→∞


(151)


203

Bizonyítás. DeÞníció szerint

∇f (xk )T sk = − k∇f (xk )k ksk k cos (θk ) ,

ahol sin (µ) ≤ cos (θ k ) ≤ 1. Ennek következtében

∇f (xk )T sk = − lim k∇f (xk )k cos (θk ) = 0 lim k→+∞ k→+∞ ksk k

csak akkor állhat fenn, ha k∇f (xk )k → 0, azaz, ha ∇f (xk ) → 0. ¤ Megjegyezzük, hogy a ∇f (xk ) → 0 konvergenciából még nem következik xk → x∗, csak annyi, hogy létezik konvergens {xki } részsorozat, amelynek határértéke kielégíti a ∇f (x) = 0 stacionárius egyenletrendszert.



204

Számos lehetýoség van az {sk } kutatási irányok megválasztására: 1. A leggyorsabb lecsökkenés módszere: sk = −∇f (xk ); 2. Newton-szerû módszerek: sk = −Bk−1∇f (xk ), ahol Bk szimmetrikus pozitív deÞnit mátrix.



205

Mindkét esetben a csökkenýo tulajdonság teljesül. A leggyorsabb lecsökkenés módszerénél

∇f (xk )T sk = − k∇f (xk )k2 < 0

(∇f (xk ) 6= 0) .

(152)

A Bk−1 pozitív deÞnitsége miatt a Newton-szerýu módszereknél

∇f (xk )T sk = −∇f (xk )T Bk−1∇f (xk ) < 0

(∇f (xk ) 6= 0) .


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Newton-módszer vonalmenti minimalizálással: for k = 0, 1, . . . ∇2xxf (xk ) sk = −∇f (xk ) αk > 0 : f (xk + αk sk ) = minα≥0 f (xk + αsk ) xk+1 = xk + αk sk end


206


207

Módositott Newton-módszer vonalmenti minimalizálással: for k£= 0, 1, . . . ¤ 2 ∇xxf (xk ) + Ek sk = −∇f (xk ) αk > 0 : f (xk + αk sk ) = minα≥0 f (xk + αsk ) xk+1 = xk + αk sk end



208

DFP (Davidon-Fletcher-Powell) eljárás: for k = 0, 1, . . . sk = −Hk−1∇f (xk ) αk > 0 : f (xk + αk sk ) = minα≥0 f (xk + αsk ) xk+1 = xk + αk sk . yk = ∇f (xk+1) − ∇f (xk ) −1 Hk+1

end

=

Hk−1

+

sk sTk αk sT yk k

−

Hk−1 yk ykT Hk−1 ykT Hk−1 yk

Vegyük észre, hogy ezt az eljárást már inverz formában adtuk meg.



209

Egy egyszerýu, lassú, de sok esetben használható eljárás a Hooke-Jeeves módszer: Az sk irányok ciklikusan rendre az e1, e2, . . . , en n-dimenziós egységkoordináta irányok. Képletben kifejezve

sin+j = ej ,

j = 1, . . . , n; i = 0, 1, . . . .

(153)

A Hooke-Jeeves módszer bizonyos esetekben nem konvergál. Ennek oka az sk irányok rögzítése. Szokás az sin+j = ±ej választással élni, aszerint, hogy az f (xin+j + ej ) ≤ f (xin+j ), vagy f (xin+j − ej ) ≤ f (xin+j ) feltételek közül melyik teljesül.



210

Más hatékonyabb módszerek pl. Rosenbrock-módszer az irányokat nem rögzítik, hanem valamilyen elv alapján változtatják. További eljárások: Nelder-Mead szimplex eljárás, direct search eljárások (?).



211

9.5 Numerikus deriváltak Számos esetben probléma: analitikus deriváltak meghatározása, ill. programozása. Egyszerû, a gyakorlatban - bizonyos korlátok között- bevált közelítõ formulákat adunk meg:



212

Legyen f : Rn → R tipusú függvény. A ∇f (x) gradiens egy ∇hf (x) közelítését adja meg az alábbi képlet:  f (x+hkxkej )−f (x)  , x 6= 0  hkxk (j = 1, . . . , n) . ∇hf (x)T ej =   f (hej )−f (x) , x=0 h (154)



213

Legyen F : Rn → Rn típusú függvény. Az F 0 (x) Jacobi mátrix egy Fh0 (x) közelítését adja meg az alábbi képlet:  F (x+hkxkej )−F (x)  , x 6= 0  hkxk Fh0 (x) ej = (j = 1, . . . , n) .   F (hej )−F (x) , x=0 h (155)



214

Az f : Rn → R tipusú függvények ∇2xxf (x) Hesse mátrixát az alábbi képletek segítségével közelíthetjük: ¡ ¢ 2 2 T ∇xxf (x) ≈ ∇hf (x) = Ah + Ah /2, (156) ahol

Ahej = Dh2 f (x : ej ) és

Dh2 f (x : w) =

   0,

(j = 1, . . . , n)

(157)

w=0

  ∇f (x+hw/kwk)−∇f (x) , h/kwk

(158)

w 6= 0


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Az ismertetett formulák pontossága függ: 1. a függvénytõl, 2. az x helytõl. √ Az ajánlott h = ε, ahol ε > 0 az un. gépi epszilon. Nagyobb pontossághoz magasabb pontosságú formulák és/vagy nagyobb pontosságú gépi aritmetika kell.


215


216

9.6 Számítógépes programok, példák Tekintsük az alábbi számítógépes programokat: DFP program: ”DFP1” golden section programok: ”goldsec0”, ”goldsec1” numerikus gradiens program: ”numgrad” numerikus Hesse mátrix program: ”numhes” Példa: Határozzuk meg az f (x) = e−x + x2 (x ∈ [0, 1]) függvény minimumhelyét!


Optimálási módszerek, 2003/2004, II. félév (óravázlat) A függvény gráfja:


217

Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa: Határozzuk meg a következýo függvény minimumát! ¢ ¡ 2 2 f (x1, x2) = 10 x2 − x1 + (1 − x1)2 → min .

218

Világos, hogy f (x1, x2) ≥ 0 és f (x1, x2) = 0 ⇔ x1 = x2 = 1.



219

10 A büntetýofüggvény vagy SUMT módszerek SUMT=Sequential Unconstrained Minimization Techniques

f (x) → min h (x) = 0, ahol f : Rn → R és h : Rn → Rm. Alapgondolat: R. Courant (1943).


(159)


220

Vezessük be a m

σX 2 σ Φ (x, σ) = f (x) + hi (x) = f (x) + h (x)T h (x) (160) 2 i=1 2 σ = f (x) + kh (x)k22 (161) 2 un. büntetýofüggvényt és az eredeti feladat helyett vizsgáljuk a Φ (x, σ) → min

(162)

feltétel nélküli szélsýoérték feladatot a σ > 0 büntetýo paraméter különbözýo értékeire!



221

Ha x ∈ S = {x | h (x) = 0}, akkor Φ (x, σ) = f (x). Ha x ∈ / S , akkor van legalább egy i0 index, hogy hi0 (x) 6= 0. Ezért m σX 2 σ 2 Φ (x, σ) = f (x) + hi (x) ≥ f (x) + hi0 (x) > f (x) . 2 2 i=1

Tehát Φ (x, σ) > f (x) attól függýoen, hogy milyen mértékben tér el h(x) a 0 vektortól és mekkora a σ paraméter. Ha σ nagyobb, a büntetés is nagyobb.



222

Példa. Az f (x, y) = −x − y → min, h (x, y) = x2 + y 2 − 1 = 0 feladat célfüggvényét, megengedett megoldásainak halmazát és a σ = 10 értékhez tartozó büntetýofüggvényt ábrázolja az alábbi ábra.

A Courant-féle büntetõfüggvény. Látható, hogy büntetýofüggvény a célfüggvényt a megengedett megoldások halmazán (az egységkörön) kívül mintegy felhajlítja.



223

Példa. Legyen

f (x) = x → min,

h(x) = x − 1 = 0.

(163)

Ekkor Φ (x, σ) = x + σ2 (x − 1)2, amelynek minimumhelye x (σ) = 1 − σ1 . Ez σ → +∞ esetén tart 1-hez, az eredeti feladat minimumhelyéhez. Ha tehát σ elég nagy, akkor x(σ) elég pontosan megközeliti az eredeti feladat megoldását (lásd a következýo ábrát).



Courant-féle büntetõfüggvény különbözõ σ értékekre


224

Optimálási módszerek, 2003/2004, II. félév (óravázlat) A SUMT algoritmus általános sémája: 1. Válasszunk egy σ k → +∞ sorozatot! 2. Az xk−1 közelitésbýol kiindulva határozzuk meg a

Φ (x, σ k ) → min

feltétel nélküli szélsýoérték feladat egy xk = x (σ k ) lokális megoldását! 3. Fejezzük be az eljárást, ha h (x (σ k )) elég kicsi! Általában a σ k = 10k−1 sorozatot használjuk.


225


226

Tétel. Tegyük fel, hogy f (x) és h (x) folytonos, f (x) alulról korlátos a megengedett megoldások nemüres S = {x|h (x) = 0} halmazán és f ∗ = inf f (x) . (164) x∈S

Ha σ k → +∞ monoton növekedýo, akkor (i) A {Φ (xk , σ k )} sorozat monoton növekedýo. (ii) A {kh (xk )k} sorozat monoton csökkenýo. (iii) Az {f (xk )} sorozat monoton növekedýo. Továbbá h (xk ) → 0 és az {xk } sorozat bármely torlódási pontja megoldása a feltételes szélsýoérték feladatnak.



227

Bizonyítás. Legyen k < l és σ k < σ l . Az xk deÞníciójából és (160)-býol

Φ (xk , σ k ) ≤ Φ (xl , σ k ) ≤ Φ (xl , σ l ) ≤ Φ (xk , σ l )

(165)

következik. Az elsýo két egyenlýotlenség bizonyítja az (i) állítást. Az egyenlýotlenség láncból adódó

2 (Φ (xk , σ l ) − Φ (xl , σ³l ) + Φ (xl , σ k ) − Φ (xk ,´σ k )) = = (σ l − σ k ) kh (xk )k22 − kh (xl )k22 ≥ 0

egyenlýotlenség igazolja az (ii) állítást.



228

A Φ (xk , σ k ) ≤ Φ (xl , σ k ) egyenlýotlenségbýol kapjuk, hogy ´ σk ³ 2 2 kh (xk )k2 − kh (xl )k2 ≤ f (xl ) , f (xk ) + 2 | {z } ≥0

amibýol az {f (xk )} sorozat monoton növekedése következik. Az xk deÞníciója és (164) alapján =f (x)

z }| { f (xk ) ≤ Φ (xk , σ k ) = minn Φ (x, σ k ) ≤ inf Φ (x, σ k )= f ∗. x∈R x∈S (166)



229

Ha σ k → +∞, akkor

h (xk )T h (xk ) ≤ 2 (f ∗ − f (xk )) /σ k ≤ 2 (f ∗ − f (x1)) /σ k → 0

miatt, h (xk ) → 0. Ha xkj → x∗, akkor a folytonosság miatt h (x∗) = 0. Ezért f (x∗) ≥ f ∗. De (166) miatt f (xk ) ≤ f ∗, amibýol f (x∗) ≤ f ∗ következik. A két egyenlýotlenség együtt az f (x∗) = f ∗ egyenlýoséget adja, amivel állitásunkat maradéktalanul igazoltuk. ¤ Megjegyzés: A tételben nem tettünk fel differenciálhatóságot és a szokásos Kuhn-Tucker feltevéseket sem.



230

Egyenlýotlenségek esete:

f (x) → min h (x) = 0, g(x) ≤ 0,

(167)

ahol f : Rn → R, h : Rn → Rm, g : Rn → Rr . Ekkor a megfelelýo büntetýofüggvény m r X X Φ (x, σ) = f (x) + σ h2i (x) + σ (max {gj (x) , 0})2 . i=1

j=1


(168)


231

Ha valamely egyenlýotlenségre, mondjuk a j -edikre fennáll, hogy gj (x) > 0, akkor max {gj (x) , 0} = gj (x). Így az ebbýol származó büntetés mértéke σ (gj (x))2. A fenti büntetýofüggvénnyel a SUMT eljárás változatlan. Változik azonban az eljárás konvergenciája.



232

Nagy σ esetén Φ (x, σ) Hesse-mátrixa sok esetben rosszul kondicionált lesz. Megoldások: 1. Broyden és Attia speciális lineáris egyenletrendszer megoldó módszere. 2. Powell-féle büntetýofüggvény: m 1X Φ (x, θ, σ) = f (x) + σ i (hi (x) − θi)2 , (169) 2 i=1

ahol θ = [θ 1, . . . , θm]T és σ = [σ 1, . . . , σ m]T . A θi paraméterek az origótól való eltolást, a σ i ≥ 0 paraméterek pedig a büntetés mértékét szabályozzák. A Powell-féle büntetýofüggvény jellegében egy nemlineáris legkisebb négyzetes feladat célfüggvénye.



233

A (163) példa esetén Φ (x, θ, σ) = x + σ2 (x − θ)2, amelynek minimumhelye x (σ) = θ − σ1 (lásd a következýo ábrát).

A Powell-féle büntetõfüggvény



234

A Powell büntetýofüggvény jobban számitható alakja: Bevezetjük a λi = θiσ i változókat és elhanyagoljuk az x-týol P 2 független 12 m θ i=1 i σ i tagot. Ekkor a m X 1 Φ (x, λ, σ) = f (x) − λT h (x) + σ ih2i (x) (170) 2 i=1 1 = f (x) − λT h (x) + h (x)T Sh (x) (171) 2 büntetýofüggvényt kapjuk, ahol λ = [λ1, . . . , λm]T és S = diag (σ 1, . . . , σ m). Állítás: Létezik olyan λ∗ vektor, amelyre x∗ a Φ (x, λ∗, σ) minimuma lesz minden σ > σ 0 esetén. (x, y ∈ Rn, x < y ⇔ xi < yi (i = 1, . . . , n).)



235

Powell-féle SUMT eljárás: 1. Határozzuk meg a λ(k) → λ∗ sorozatot! ´ ³ (k) 2. Határozzuk meg a Φ x, λ , σ (k) függvény egy ´ ³ xk = x λ(k), σ (k) lokális minimumhelyét! ´´ ³ ³ 3. Fejezzük be az eljárást, ha h x λ(k), σ (k) elég kicsi!



236

λ(k) és σ (k) meghatározására a következýo algoritmust javasolják. Legyen   (k) σ1 . . . 0   S (k) =  .. . . . ..  . (172) (k) 0 . . . σm



237

Powell módszere: ° (0)° (1) (1) 1. Legyen λ = λ , σ = σ , k = 0, °h °∞ = ∞. 2. Határozzuk meg a Φ (x, λ, σ) függvény x (λ, σ) minimumhelyét és legyen h = h (x (λ, σ)). ° ° 1 ° (k−1)° 3. Ha khk∞ > 4 h , akkor legyen σ i = ∞ 10σ olyan i indexre, amelyre fennáll, hogy |hi| > i minden ° ° 1 ° (k−1)° . Menjünk a 2. pontra! 4 h ∞ 4. Legyen k = k + 1, λ(k) = λ, σ (k) = σ , h(k) = h. 5. Legyen λ = λ(k) − S (k)h(k). 6. Menjünk a 2. pontra!



238

11 NCP módszerek Vizsgáljuk az

f (x) → min hj (x) = 0, j ∈ J = {1, 2, . . . , p} , gi (x) ≤ 0, i ∈ I = {1, 2, . . . , m} ,

(173)

szélsõérték feladatot, ahol f, gi, hj : Rn → R (i ∈ I , j ∈ J ) eléggé síma (azaz elég sokszor folytonosan differenciálható) függvények.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Legyen

L (x, µ, λ) = f (x) +

X

µj hj (x) +

j∈J

és

X

λigi (x)

239

(174)

i∈I





x z =  µ . λ


(175)


240

£ ∗T ∗T ∗T ¤T pont Karush-Kuhn-Tucker (KKTL) A z = x ,µ ,λ pont, ha kielégítí a következõ feltételeket: ∗

∇xL (x, µ, λ) = 0, hj (x) = 0 (j ∈ J) , gi (x) ≤ 0 (i ∈ I) , λigi (x) = 0 (i ∈ I) , λi ≥ 0 (i ∈ I) .

(176)

Korábban láttuk, hogy regularitás feltevése esetén a (176) feltételek szükségesek ahhoz, hogy x∗ a (173) feladat optimális megoldása legyen.



241

DeÞníció: A φ : R2 → R leképezést NCP-függvénynek (NCP=Nonlinear Complementarity Problem) nevezzük, ha az

φ (a, b) = 0 ⇔ a ≥ 0, ab = 0, b ≤ 0

(177)

feltételt kielégíti. Tetszõleges NCP-függvényt használva a (176) Kuhn-Tucker feltételeket az ekvivalens ¡ ¢ n+p+m n+p+m Fφ (z) = 0 Fφ : R →R (178) nemlineáris egyenletrendszer formájában is felírhatjuk, ahol





242



∇xL (x, µ, λ)   h1 (x)  .  .    = 0.  Fφ (z) =  hp (x)   φ (λ1, g1 (x))   .  . φ (λm, gm (x))


(179)


243

Tehát a Karush-Kuhn-Tucker-Lagrange pontok keresését a fenti nemlineáris egyenletrendszer megoldásával is végezhetjük. Az eljárás ötlete Mangasariantól származik. Tegyük fel a következõ feltételeket: £ ∗T ∗T ∗T ¤T ∗ (A.0) z = x , µ , λ a (173) feladat KKT pontja. (A.1) Az f , gi és hj (i ∈ I , j ∈ J ) függvények kétszer folytonosan differenciálhatóak és a második deriváltak Lipschitz folytonosak az x∗ egy környezetében. (A.2) A ∇gi (x∗) (i ∈ I ∗∗) és ∇hj (x∗) (j ∈ J ) gradiensek lineárisan függetlenek, ahol I ∗∗ = {i ∈ I | λ∗i > 0}.



244

(A.3) y T ∇2xxL (x∗, µ∗, λ∗) y > 0 teljesül minden olyan y ∈ Rn vektorra, amelyre y 6= 0, y T ∇gi (x∗) = 0 (i ∈ I ∗∗) és y T ∇hj (x∗) = 0 (j ∈ J ). (A.4) I ∗ = I ∗∗, ahol I ∗ = {i ∈ I | gi (x∗) = 0}. (A.5) Az NCP függvény kielégíti az alábbi feltételeket ∂φ ∂a

(λ∗i , gi (x∗)) = 0

(i ∈ I ∗∗) ,

∂φ ∂b

(λ∗i , gi (x∗)) 6= 0

(i ∈ I ∗∗) ,

∂φ ∂a

(λ∗i , gi (x∗)) 6= 0

(i ∈ / I ∗∗) ,

∂φ ∂b

(λ∗i , gi (x∗)) = 0

(i ∈ / I ∗∗) .


(180)


245

Megjegyzés: Ha az NCP függvény folytonosan differenciálható, akkor (180) elsõ és az utolsó feltétele automatikusan teljesül. £ ∗T ∗T ∗T ¤T ∗ Tétel (Kanzow-Kleinmichel). Legyen z = x , µ , λ a (173) feladat KKT pontja. Tegyük fel, hogy az (A.1)-(A.5) feltételek teljesülnek az z ∗ pontban. Legyen φ : R2 → R folytonosan differenciálható NCP függvény. Ekkor az Fφ0 (z ∗) Jacobi mátrix nemszinguláris. Következmény: A Newton módszert alkalmazhatjuk az Fφ (z) = 0 nemlineáris egyenletrendszer megoldására. Könnyen igazolható, hogy a Fφ0 (z) Jacobi mátrix alakja





∇2xxL (x, µ, λ) ∇h1 (x)T .. T ∇h (x) p ³ ´

        ∂φ ∇g (x)T  ∂b 1 1   ³ ´ ..  T ∂φ ∇g (x) m ∂b

246

∇h1 (x) . . . ∇hp (x) ∇g1 (x) . . . ∇gm (x 0

0

0 ³ ´

∂φ ∂a 1

m


...

³ ´

∂φ ∂a m

(181)

Optimálási módszerek, 2003/2004, II. félév (óravázlat) ahol

³ ´

∂φ ∂a i

³ ´

∂φ ∂b i

= =

∂φ ∂a ∂φ ∂b

(λi, gi (x)) (λi, gi (x))

(i ∈ I) , (i ∈ I) .


247

(182)


248

Mindenhol differenciálható NCP függvények a következõk: 1 φ (a, b) = ab + (max {0, b − a})2 , (183) 2

φ (a, b) = ab + (max {0, a})2 + (min {0, b})2 , φ (a, b) = (a + b)2 + b |b| − a |a| .

A Kanzow-Kleinmichel tétel igaz marad a √ φ (a, b) = a2 + b2 + b − a

(184) (185) (186)

függvényre is, amely minden (a, b) 6= (0, 0) esetén differenciálható.



249

12 Többcélú optimalizálás Alapprobléma: több (egymásnak ellentmondó) célfüggvény feltételes szélsýoértékét szeretnénk egyidejýuleg biztosítani. Formálisan a többcélú optimalizálás alapfeladata:

fj (x) → min (j = 1, . . . , k) x ∈ S.


(187)


250

Legyen F (x) = [f1(x), . . . , fk (x)]T ∈ Rk . Ekkor a feladat tömörebb alakja:

F (x) → min (F : Rn → Rk ) x ∈ S.

(188)

Megjegyzés: Szokás vektor értékýu optimalizálásról is beszélni. A probléma a több kritériumú döntések elméletéhez tartozik.



251

DeÞníció. Az x∗ ∈ S az (187) feladat abszolut optimuma, ha

fj (x∗) ≤ fj (x) (x ∈ S, j = 1, . . . , k).

(189)

Abszolut optimum általában ritkán van. Helyette sok megoldási koncepció. Legszerencsésebb: a Pareto-féle efÞciens megoldás, amely az abszolut optimum kérdését bizonyos értelemben megfordítja.



252

A Pareto-féle efÞciens megoldás olyan x∗ ∈ S pont , amelyhez tartozó célfüggvényértékeket nem lehet egyidejýuleg minden célfüggvényben csökkenteni. Az efÞciens ponttól különbözýo y pontban valamelyik célfüggvény biztosan nagyobb lesz mint az x∗ pontban.



253

DeÞníció. Az x∗ ∈ S az (187) feladat gyengén Pareto-efÞciens megoldása, ha nem létezik olyan x ∈ S , amelyre fennáll, hogy F (x) < F (x∗), azaz

fj (x) < fj (x∗) (j = 1, . . . , k).

(190)

DeÞníció. Az x∗ ∈ S az (187) feladat erýosen Pareto-efÞciens megoldása, ha nem létezik olyan x ∈ S , amelyre fennáll, hogy F (x) ≤ F (x∗) és F (x) 6= F (x∗), azaz

fj (x) ≤ fj (x∗) (j = 1, . . . , k) és ∃t ∈ {1, . . . , k} : ft (x) < ft (x (191)



254

Állítás: Az erýosen efÞciens megoldások gyengén efÞciensek is. Bizonyítás: Tegyük fel, hogy x∗ erýosen Pareto-efÞciens, de nem gyenge Pareto-efÞciens. Ekkor létezik x ∈ S megoldás, hogy F (x) < F (x∗). Ámde ekkor fennáll, hogy F (x) ≤ F (x∗) és F (x) 6= F (x∗). Tehát x∗ nem erýosen Pareto-efÞciens pont, ami ellentmondás.



255

Példa.

f1 (x) = − (x1 + x2) = min, f2 (x) = −x1 = min, 4x1 + 3x2 ≤ 12, x1 ≥ 0, x2 ≥ 0.

A megengedett megoldások S halmaza az O (0, 0), A (3, 0), B (0, 4) pontok által közrezárt háromszög.




256


257

Könnyýu belátni, hogy x ≤ y (x, y ∈ S ) esetén f1 (x) ≥ f1 (y) és f2 (x) ≥ f2 (y). Ezért az S halmaz belsýo pontjai, valamint az OA és OB szakasz pontjai nem lehetnek efÞciens pontok. Az AB szakasz pontjai viszont mind erýosen efÞciensek. Ha az (x1, x2) pont rajta van az AB szakaszon, akkor f1 (x) = (x1 − 12) /3. Ha x1 nýo, akkor f1 (x) nýo, míg f2 (x) csökken. Tehát AB összes pontja erýosen efÞciens pont.



258

A Pareto-efÞciens megoldások száma nagy lehet. A kiválasztásukra sok módszer. Egy fontos általános technika: a redukciós módszer. Legyen H : Rk → R és h(x) = H(f1(x), . . . , fk (x)). Az (187) feladat helyett a

h(x) → min x∈S

egycélú optimalizálási feladatot vizsgáljuk.


(192)


259

Tétel. (a) Ha a H(y1, . . . , yk ) függvény minden változójában monoton növekedýo és legalább egy változóban szigorúan monoton, akkor a (192) redukált feladat minden optimális megoldása egyúttal az (187) többcélú optimalizálási feladat gyengén ParetoefÞciens megoldása is. (b) Ha a H(y1, . . . , yk ) függvény minden változójában szigorúan monoton növekedýo, akkor a (192) redukált feladat minden optimális megoldása egyúttal az (187) többcélú optimalizálási feladat erýosen Pareto-efÞciens megoldása is.



260

Bizonyítás. (a) Legyen x∗ a (192) feladat optimális megoldása és tegyük fel, hogy ez nem gyengén efÞciens megoldása (187)-nek. Ekkor létezik x ∈ S pont, amelyre fennáll F (x) < F (x∗). A H függvény monotonitása miatt

h(x) = H(f1(x), . . . , fk (x)) < h(x∗) = H(f1(x∗), . . . , fk (x∗)), (193) ami ellentmond a h(x∗) = min feltételnek.



261

(b) Ismét tegyük fel, hogy x∗ nem erýosen efÞciens megoldása (187)-nek. Ekkor van olyan x ∈ S pont, amelyre F (x) ≤ F (x∗) és F (x) 6= F (x∗). A H függvény szigorú monotonitása miatt

h(x) = H(f1(x), . . . , fk (x)) < h(x∗) = H(f1(x∗), . . . , fk (x∗)), (194) ami ellentmond a h(x∗) = min feltételnek. ¤



262

1. A súlyok módszere. Legyen µj ≥ 0 (j = 1, . . . , k ) és Pk j=1 µj = 1. Ekkor H(y1 , . . . , yk ) = j=1 µj yj , azaz

Pk

h(x) =

k X

µj fj (x).

(195)

j=1

A µj súlyok a célfüggvények egymás közti relatív fontosságát fejezik ki. A súlyok megállapitása szakértýoi feladat és szubjektív elemeket hordoz magában.



263

2. A korlátok módszere. Tegyük fel, hogy a t-ik célfüggvény fontosabb mint a többi (1 ≤ t ≤ k) és rendelkezésünkre állnak olyan dj ∈ R korlátok (j = 1, . . . , k; j 6= t), amelyeket a j -ik célfüggvényben el kell érni. Ekkor H(y1, . . . , yk ) = yt és a következýo feladatot vizsgáljuk:

ft(x) → min fj (x) ≤ dj (j = 1, . . . , k; j 6= t) x ∈ S.


(196)


264

3. A cél-programozás módszere. Tegyük fel, hogy vannak olyan uj (j = 1, . . . , k ) célok ((u1, . . . , uk )T ∈ Rk cél-vektor), amelyeket az (187) P feladat megoldásával kivánunk elérni. Ekkor H(y1, . . . , yk ) = ( kj=1 γ j | yj − uj |p)1/p, ahol γ j ≥ 0 (j = 1, . . . , k). A megfelelýo redukált feladat pedig Pk h(x) = ( j=1 γ j | fj (x) − uj |p)1/p → min (197) x ∈ S.



265

13 A lineáris programozás A lineáris programozás normálfeladata:

cT x → max, Ax ≤ b, x ≥ 0 (A ∈ Rm×n)

Kantorovics (1939)


(198)


266

Példa. GraÞkusan oldjuk meg az alábbi feladatot:

2x1 + 4x2 → max 3x1 + 4x2 ≤ 1700 2x1 + 5x2 ≤ 1600 x1 ≥ 0, x2 ≥ 0

A megengedett megoldások halmazát a következýo ábra mutatja:




267


268

A célfüggvény a gradiens irányában növekedik (csökken, változik) a leggyorsabban. A cT x = p összefüggésnek eleget tévýo x vektorokat (egyeneseket) a p = 0, 700, 1400, 1600 értékekre ábrázoljuk. Az ábráról látható, hogy a célfüggvény a legnagyobb értékét akkor veszi fel, amikor a cT x = p egyenes átmegy a B ponton, amelynek koordinátái (300, 200). Ez a pont lesz a példa optimális megoldása.



269

A lineáris programozási feladatok általános alakja: ¡ T ¢ T c x → max c x → min A1x ≤ b1 (A1 ∈ Rm1×n) A2x = b2 (A2 ∈ Rm2×n) A3x ≥ b3 (A3 ∈ Rm3×n)

(199)



270

Az A1x ≤ b1 egyenlýotlenség rendszer a v ∈ Rm1 , v ≥ 0 hiányváltozó bevezetésével az

A 1 x + v = b1 egyenlýoséggé alakítható át.


(200)


271

Az A3x ≥ b3 feltétel esetén a w ∈ Rm3 , w ≥ 0 feleslegváltozót levonjuk a baloldalból és az ekvivalens egyenletet tekintjük.

A3x − w = b3


(201)


272

Általában kikötjük, hogy minden j esetén xj ≥ 0. Ha van olyan xj változó, amelyre ilyen kikötés nincs, akkor ezt a kötetlen elýojelýu változót az ¡ + ¢ + − − xj ≥ 0, xj ≥ 0 xj = xj − xj (202) helyettesítéssel kiküszöbölhetjük.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Bevezetve az £ T T T ¤T x˜ = x , v , w ∈ Rn+m1+m3 , és



273

c˜ = [c1, . . . , cn, 0, . . . , 0]T ∈ Rn (203) 





A1 Im1 0 b1 0  , b =  b2  A˜ =  A2 0 A3 0 −Im3 b3 jelöléseket az ekvivalens ˜x = b, x˜ ≥ 0 c˜T x˜ → max, A˜ feladatot kapjuk.


(204)

(205)


274

Feltehetýo, hogy b ≥ 0. Ha ugyanis valamelyik bi < 0, akkor az i-edik feltételi egyenlet (−1)-el való szorzásával ez elérhetýo.



275

Példa. Az x1 és x2 változók kötetlen elýojelýuek a

2x1 − x2 + 5x3 → max x1 − 2x2 + x3 ≤ 8 −3x1 + 2x2 ≥ 18 x3 ≥ 0

lineáris programozási feladatban. Bevezetve a v1 hiány- és − w1 feleslegváltozókat, valamint az xj = x+ j − xj (j = 1, 2) helyettesítéseket, az ekvivalens



276

− + − 2x+ 1 − 2x1 − x2 + x2 + 5x3 → max − − + x+ − x − 2x + 2x 1 2 + x3 + v1 = 8 1 2 − − + −3x+ + 3x + 2x − 2x 1 2 − w1 = 18 1 2 − − + x+ 1 ≥ 0, x1 ≥ 0, x2 ≥ 0, x2 ≥ 0, x3 ≥ 0, v1 ≥ 0, w1 ≥ 0

feladatot kapjuk.



277

A következýokben a

cT x → max,

Ax = b,

x≥0

(LP)

alapfeladatot vizsgáljuk, ahol A ∈ Rm×n, b ∈ Rm, c, x ∈ Rn. Feltételezzük, hogy rank(A) = m és m < n. Az x ∈ Rn vektort megengedett megoldásnak nevezzük, ha Ax = b és x ≥ 0.



278

Ha az A mátrixot az A = [a1, . . . , an] alakban particionáljuk és a0 = b, akkor Ax = b felírható az

x1a1 + x2a2 + . . . + xnan = a0

(206)

alakban. Az {ai}ni=1 vektorok olyan nemnegatív lineáris kombinációját keressük, amelyre cT x maximális. Az (LP) feladat megoldhatóságának szükséges feltétele, hogy a0 benne legyen az {ai}ni=1 vektorok lineáris terében. Ezt tetszõleges a0 = b ∈ Rm esetén éppen a rank(A) = m feltétel biztosítja.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 279 © ªm Válasszuk ki az B = aij j=1 oszlopvektorokat úgy, hogy Rm egy bázisát alkossák. A vektorok sorrendje nem kötött. Legyen I = {i1, i2, . . . , im}. ¡n¢ Megjegyzés: Legfeljebb m különbözýo bázis választható ki.



280

Adott bázisban minden oszlopvektort egyértelmýuen felírhatunk az m X as = djsaij , s = 0, 1, . . . , n (207) j=1

formában, a djs együtthatók az as vektor koordinátái a © ªahol m B = aij j=1 bázisban. A djs együttható az as vektor aij bázisvektorra (koordináta tengelyre) vonatkozó koordinátája.



281

DeÞníció. Az x megoldást bázismegoldásnak nevezzük, ha van olyan B bázis, hogy xi = 0, ha i ∈ / I . Az xij (j = 1, . . . , m) komponenseket báziskomponenseknek nevezzük. A B bázis és a hozzátartozó x bázismegoldás megengedett, ha x ≥ 0.



282

Igazolható, hogy az (LP) feladat célfüggvénye a maximumát megengedett bázismegoldáson veszi fel. A Dantzigtól (1947, 1951) származó szimplex módszer alapgondolata az, hogy egy megengedett bázisból és a hozzátartozó bázismegoldásból kiindulva bázisvektor cseréket hajtunk végre úgy, hogy az új bázis mindig megengedett legyen és a célfüggvény értéke növekedjen. A szimplex eljárás véges lépésben befejezýodik.



283

Legyen B = {ai|i ∈ I} megengedett bázis és

d0s =

m X j=1

cij djs − cs,

s = 0, 1, . . . , n; c0 = 0.

A B bázishoz tartozó szimplex tábla:


(208)


a i1 a i2 .. aim

a0 d10 d20 .. dm0 d00

a1 a2 an d11 d12 . . . d1n d1 d21 d22 . . . d2n d2 .. .. dm1 dm2 . . . dmn dm d01 d02 . . . d0n d0


284

(209)


285

A baloldali oszlop a bázisvektorokat sorolja fel. A jobboldali oszlop a tábla sorvektorait jelöli:

dj = [dj0, . . . , djn] .

(210)

A szimplex tábla tulajdonságai a következõk: 1. Ha as ∈ B , akkor az s-edik oszlopban egységvektor van. 2. Az a0-hoz tartozó oszlop a bázismegoldás báziskomponenseit tartalmazza. Eszerint xij = dj0, ha ij ∈ I és xt = 0, ha t∈ / I. 3. Ha a B bázis megengedett, akkor az a0 oszlophoz tartozó elemekre fennáll, hogy dj0 ≥ 0 minden j = 1, . . . , m indexre. 4. Vegyük észre, hogy s ∈ I esetén d0s = 0. 5. A d00 a célfüggvény értéke a bázismegoldáson.



286

Tétel. Tegyük fel, hogy a t-edik, azaz az ait ∈ B bázisvektort kicseréljük a bázison kívüli ak vektorral és ak olyan, hogy a B 0 = B\ {ait } ∪ {ak } vektorrendszer is bázis. Ekkor it = k lesz az új I 0 = I \ {it} ∪ {k} indexhalmazban. Az új B 0 bázishoz tartozó szimplex táblát a következýo transzformáció adja meg: djk d0j = dj − dt, j ∈ {0, 1, . . . , m} \ {t} (211) dtk 1 d0t = dt . (212) dtk



287

Bizonyítás. Tekintsük az Pm Pm Pm as = j=1 djs aij − βak + βak = j=1 djs aij − β j=1 djk aij +

=

Pm

j=1 (djs

− βdjk ) aij + βak

egyenlýoséget s = 0, 1, . . . , n esetén. Ha a β 6= 0 számot a dts − βdtk = 0 feltétel szerint választjuk meg, akkor az ait t-edik bázisvektor együtthatója 0 lesz és β = dts/dtk . Egyúttal megkapjuk az as vektor új B 0 bázisbeli elýoállítását: µ ¶ m X dts dts djs − djk aij + ak . as = dtk dtk j=1, j6=t



288

A szimplex tábla soraiban kifejezve a transzformációs képlet j = 1, . . . , m, j 6= t esetén dts djk d0js = djs − djk = djs − dts, s = 0, 1, . . . , n, dtk dtk az i = it = k esetben pedig dts 1 0 dts = = dts, s = 0, 1, . . . , n. dtk dtk A kapott összefüggések vektor alakja éppen a bizonyítandó transzformációs képlet j = 1, . . . , n esetén.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) A j = 0 eset igazolásához vegyük észre, hogy m X ¡ T ¢ T cˆ = [0, c1, . . . , cn] . d0 = cij dj − cˆ

289

j=1

Felhasználva a már igazolt eseteket és a dt − ddtktk dt = 0 összefüggést kapjuk, hogy



d00 = = =

290

³ ´ djk 1 ˆT j=1, j6=t cij dj − dtk dt + ck dtk dt − c

Pm

³ ´ djk 1 T d + c c − d d − c ˆ i j t k t j j=1 dtk dtk

Pm

³P m

j=1 cij dj

= d0 − dd0ktk dt,

´

− cˆT − d1tk

³P m

j=1 cij djk


´

− ck dt


291

Az új szimplex tábla baloldali elsýo oszlopában az ait helyett ak lesz. A bázisvektorok cseréje a Gauss-Jordan eliminációs módszer egy lépésének felel meg: ui. az ak vektornak megfelelýo k -adik oszlopban a t-edik elem alatti és feletti elemeket kinullázzuk a t-edik sor számszorosának az aktuális sorhoz történõ hozzáadásával. Magát a dt sorvektort lenormáljuk úgy, hogy osztjuk a dtk elemmel.



292

Tehát a báziscsere úgy végezhetýo el, hogy: 1. A t-edik sor elemeit elosztjuk a dtk 6= 0 együtthatóval. 2. A kapott vektor az új tábla d0t sorvektora lesz (és d0tk = 1). 3. A j -edik sorból kivonjuk az új d0k vektor djk -szorosát (j 6= it = k ). A dtk számot generáló-, vagy pivotelemnek nevezzük.



293

Példa. (A példában a kapott bázis nem megengedett!) Legyen a0 = [100, 100, 50]T , c = [2, 1, 3, −1, 2]T és   1 2 1 0 1 A =  0 1 1 1 1 . 1 0 1 1 0 Az {a1, . . . , a5} vektorrendszernek {a1, a4, a5} bázisa. A megfelelýo szimplex tábla



a1 a4 a5

a0 25 25 75 175

a1 1 0 0 0

a2 0.5 -0.5 1.5 3.5

a3 0.5 0.5 0.5 −1.5

a4 0 1 0 0

a5 0 0 1 0

294

d1 d2 . d3 d0

Ha az a4 vektort az a2 vektorral cseréljük ki, akkor a generáló, vagy pivotelem −0.5. Az új {a1, a2, a5} bázishoz tartozó szimplex táblát két lépésben kapjuk.



295

1. lépés: A −0.5 pivotelemmel végigosztjuk a pivotelem sorát:

a1 a4 a5

a0 25 −50 75 175

a1 1 0 0 0

a2 0.5 1 1.5 3.5

a3 0.5 −1 0.5 −1.5

a4 0 −2 0 0

a5 0 0 1 0

d1 d2 d3 d0


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 2. lépés: A pivotelem sorának számszorosait az egyes sorokhoz hozzáadva kinullázuk a pivotelem alatti és feletti elemeket a pivotelem oszlopában:

a1 a2 a5

a0 50 −50 150 300

a1 1 0 0 0

a2 0 1 0 0

a3 1 −1 2 2

a4 0 −2 3 7

a5 0 0 1 0

d1 d2 d3 d0


296


297

Vizsgáljuk a

a i1 a i2 .. aim

a0 d10 d20 .. dm0 d00

a1 a2 an d11 d12 . . . d1n d1 d21 d22 . . . d2n d2 .. .. dm1 dm2 . . . dmn dm d01 d02 . . . d0n d0

szimplex táblát és tegyük fel, hogy a B bázis megengedett.


(213)


298

Ekkor fennáll, hogy dj0 ≥ 0 minden j = 1, . . . , m indexre. A szimplex tábla az alábbi három típus valamelyikébe tartozik: I. d01 ≥ 0, d02 ≥ 0, . . ., d0n ≥ 0. II. Van olyan 1 ≤ k ≤ n index, hogy d0k < 0 és djk ≤ 0 (1 ≤ j ≤ m). III. Van olyan 1 ≤ k ≤ n index, hogy d0k < 0 és legalább egy 1 ≤ j ≤ m indexre teljesül, hogy djk > 0.



299

Tétel. Az I. esetben a B bázishoz tartozó bázismegoldás az (LP) feladat optimális megoldása. A II. esetben az (LP) feladatnak nincs véges optimuma.



300

Bizonyítás. Legyen y ≥ P 0 tetszýoleges megengedett m megoldás. Az y ≥ 0 és d = i 0s j=1 cij djs − cs ≥ 0 feltételek Pm miatt j=1 cij djs ≥ cs és   Ã n ! n n m m X X X X X   csys ≤ cij djs ys = cij djsys . s=1

s=1

j=1

j=1

s=1

Megmutatjuk, hogy az egyenlýotlenség jobboldalán cij együtthatója az xij = dj0 (j = 1, . . . , m) báziskomponenssel azonos:



301

  Ã n ! n n m m m X X X X X X  a0 = ysas = djsaij  ys = djsys aij = s=1

s=1

j=1

j=1

s=1

Adott bázisbeli elõállítás egyértelmûsége miatt szükségképpen fennáll az n X xij = dj0 = djsys (j = 1, . . . , m) . s=1


j=


302

Tekintve, hogy x bázismegoldás, a fenti egyenlýotlenség jobboldala cT x. Minthogy az I. feltétel mellett cT y ≤ cT x fennáll minden y megengedett megoldásra, az x bázismegoldás optimális megoldás és az optimális célfüggvényérték cT x.



303

A II. esetben írjuk fel az m m X X ¡ ¢ xij − βdjk aij + βak a0 = xij aij − βak + βak = j=1

j=1

egyenlýoséget. Az xij = dj0 ≥ 0, djk ≤ 0 (j = 1, . . . , m) miatt tetszõleges β > 0 esetén fennáll, hogy xij − βdjk ≥ 0 minden j = 1, . . . , m esetén. Legyen   xij − βdjk , l = ij ∈ I zl = β, l = k  0, egyébként



304

A z = [z1, . . . , zn]T vektor megengedett megoldás, amelyen a célfüggvény értéke m m X X ¡ ¢ cT z = cij xij − βdjk +βck = cij xij −βd0k = cT x−βd0k . j=1

j=1

Ha β > 0 elég nagy, akkor cT z értéke is tetszýolegesen nagy lesz. Tehát a II. esetben nincs véges optimum. ¤



305

A III. esetben olyan új bázisra kell áttéri, amely szintén megengedett és a hozzátartozó bázismegoldáson a célfüggvény értéke nagyobb. Válasszuk ki a k -adik oszlopot, amelyre d0k < 0 és legalább egy djk > 0 (1 ≤ j ≤ m). Válasszuk a dtk pivot elemet a ½ ¾ dt0 dj0 β= = min | djk > 0, 1 ≤ j ≤ m (214) dtk djk un. legszýukebb keresztmetszet szabály alapján!



306

A dj0 ≥ 0 (j = 1, . . . , m) feltétel miatt β ≥ 0. Az új B 0 bázisban a bázismegoldás komponensei: és

xij − βdjk , ha j = 1, . . . , m, j 6= t β , ha j = k (it = k).



307

Állítás: Az új bázis is megengedett lesz. Bizonyítás: Ha djk ≤ 0, akkor xij − βdjk ≥ xij ≥ 0. Ha xi d djk > 0, akkor djkj = djkj0 ≥ β miatt xij − βdjk = dj0 − βdjk ≥ 0. A d0k < 0 feltétel miatt fennáll, hogy m m X X ¡ ¢ cT z = cij xij − βdjk + βck = cij xij − βd0k ≥ cT x. j=1

j=1

Ha β > 0, akkor cT z > cT x, tehát a célfüggvény szigorúan nýo.



308

A szimplex módszer: 1. Legyen l = 0, B (0) egy megengedett bázis és írjuk fel a hozzátartozó szimplex táblát. 2. Ha a B (l) bázishoz tartozó szimplex tábla I. tipusú, akkor a hozzátartozó bázismegoldás az (LP) feladat optimális megoldása. 3. Ha a B (l) bázishoz tartozó szimplex tábla II. tipusú, akkor nincs véges optimum. 4. Ha a B (l) bázishoz tartozó szimplex tábla III. tipusú, akkor válasszunk ki egy pivotelemet a (214) szabály alapján és térjünk át az új B (l+1) = B (l)\ {ait } ∪ {ak } bázisra. 5. Legyen l = l + 1 és menjünk a 2. pontra.



309

Ha a pivotelemek kiválasztása olyan, hogy minden megengedett bázist csak egyszer érintünk, akkor véges lépésben megoldhatjuk az (LP) feladatot. Ui. vagy megkapjuk az optimális megoldást, vagy megállapíthatjuk, hogy nincs véges optimum.



310

Elvileg elýofordulhat, hogy az eljárás a (214) szabály alkalmazásánál beciklizál. Ilyen Beale alábbi példája −3 1 x + 20x − 1 2 4 2 x3 + 6x4 1 4 x1 − 8x2 − x3 + 9x4 + x5 1 1 x − 12x − 1 2 2 2 x3 + 3x4 + x6 x3 + x7

→ = = = x ≥

min 0 0 1 0

Ilyen esetekben más pivotelem választási szabályt pl. a lexikograÞkus szimplex módszert kell alkalmazni..



311

Az szimplex eljárás alkalmazásának fontos elýofeltétele az induló bázis és szimplex tábla elýoállítása. Ennek egyik legismertebb eljárása az un. kétfázisú szimplex módszer. Vizsgáljuk a Pm − i=1 vi → max Ax + v = a0 (215) x ≥ 0, v ≥ 0 (LP) feladatot, amelynek optimális megoldása a v = 0 vektor.



312

Ismerjük az (215) feladat egy megengedett bázisát {ei }m i=1-et, ahol ei ∈ Rm az i-edik egységvektor. Ha erre a mesterséges feladatra alkalmazzuk a szimplex módszert, akkor két eset lehetséges: (a) Az optimális megoldáshoz tartozó bázis nem tartalmaz valamelyik vi-hez tartozó oszlopvektort. (b) Az optimális megoldáshoz tartozó bázis tartalmaz valamelyik vi-hez tartozó oszlopvektort.



313

Ha az (a) eset fordul elýo, akkor a szimplex módszert ismét alkalmazzuk, immár az eredeti cT x → max, Ax = b, x ≥ 0 feladatra. Ekkor azonban a szimplex tábla alsó sorát az új célfüggvény miatt újra ki kell számolni. Az elmondottakat összefoglalva a módszer a következýo.



314

A kétfázisú szimplex eljárás: 1. Alkalmazzuk a szimplex módszert a (215) feladatra. 2. Ha fennáll az (a) eset, akkor új alsó sor (d0) készítése után alkalmazzuk a szimplex módszert az eredeti (LP) feladatra. Az 1. fázis indulótáblájának alakja:



e1 e2 .. em −

a0 a10 a20 .. Pam0

m j=1 aj0

e1 1 0 .. 0 0

e2 0 1 .. 0 0

. . . em a1 a2 ... 0 a11 a12 ... 0 a21 a22 .. .. .. ... 1 m1 m2 Pam Pam . . . 0 − j=1 aj1 − j=1 aj2


315

... ... ...

... P ... −


316

Nem szükséges a kétfázisú szimplex módszert használni a

cT x → max, Ax ≤ b, x ≥ 0 (A ∈ Rm×n)

(216)

normálfeladat esetén, ui. a v hiányváltozók hozzávételével az {ej }m j=1 oszlopvektorok megengedett bázist alkotnak. A hozzájuk tartozó szimplex tábla:



e1 e2 .. em

a0 a10 a20 .. am0 0

e1 1 0 .. 0 0

e2 0 1 .. 0 0

. . . em ... 0 ... 0 .. ... 1 ... 0

a1 a11 a21 .. am1 −c1

a2 a12 a22 .. am2 −c2

. . . an . . . a1n . . . a2n .. . . . amn . . . −cn


317


318

14 Bimátrix játékok Legyen két játékos A és B akik egymástól függetlenül választják meg stratégiájukat. Az A játékosnak m, a B játékosnak pedig n különbözýo stratégiája van. A játékosok nyereményei a két játékos együttes stratégiájától függenek. Jelölje φ1 (i, j) az A játékos nyereményét, φ2 (i, j) pedig a B játékos nyereményét, ha A az i-edik stratégiáját, B pedig a j -edik stratégiáját játssza. A φ1 és φ2 függvényeket kiÞzetýo függvényeknek nevezzük.



319

Legyen

φ1 (i, j) = aij ,

φ2 (i, j) = bij

(i = 1, . . . , m; j = 1, . . . , n) .

Ekkor az m,n A = [aij ]m,n , B = [b ] ij i,j=1 i,j=1 mátrixokat az A, ill. B játékos kiÞzetýo mátrixának nevezzük. A most deÞniált un. bimátrix játékot általában a kiÞzetýo mátrixokból álló [A, B] mátrixpár formában adjuk meg.



320

DeÞníció. Az (i0, j0) stratégiapárt az [A, B] bimátrix játék Nash-féle egyensúlypontjának nevezzük, ha minden 1 ≤ i ≤ m és 1 ≤ j ≤ n esetén fennáll, hogy

φ1 (i0, j0) ≥ φ1 (i, j0) ,

φ2 (i0, j0) ≥ φ2 (i0, j) .

Az egyensúlyi pont olyan stratégia pár, amelyre igaz, hogy ha a játékosok bármelyike eltér az egyensúlyi stratégiától, mialatt a másik tartja az egyensúlynak megfelelýo stratégiát, akkor az egyensúlyi stratégiától eltérýo játékos nem tudja megnövelni nyereményét.



321

Az (i0, j0) stratégia pár egyensúlyi stratégia, ha fennáll, hogy

ai0j0 ≥ aij0 (1 ≤ i ≤ m) bi0j0 ≥ bi0j (1 ≤ j ≤ n) .

Jelentése: Az A mátrixban ai0j0 a j0-adik oszlop legnagyobb eleme, míg bi0j0 a B mátrixban az i0-adik sor legnagyobb eleme.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa: Az

·

¸

·

¸

1 2 2 3 , B= 2 0 3 5 játék esetén egyetlen egyensúlyi pár van és ez (1, 2). A=


322


323

15 Mátrixjátékok DeÞníció: Ha B = −A, akkor az [A, B] bimátrix játékot zérusösszegýunek, vagy mátrixjátéknak nevezzük. Ekkor az (i, j) stratégia pár esetén az A játékos nyeresége aij , míg a B játékos nyeresége −aij (vesztesége aij ). Tehát az egyik játékos nyereményét a másik játékos Þzeti. A játék szokásos megadási formája:



AÂB 1 2 1 a11 a12 2 a21 a22 .. .. .. m am1 am2

... n . . . a1n . . . a2n .. . . . amn


324


325

Zérusösszegýu játék esetén az (i0, j0) stratégiapár akkor és csak akkor egyensúlypont, ha az A mátrixban ai0j0 a j0-adik oszlop legnagyobb és az i0-adik sor legkisebb eleme. Ebben az esetben az (i0, j0) elemet az A kiÞzetýomátrix nyeregpontjának is nevezzük. Neumann János (1920-tól). A Nash-féle egyensúlyi pont koncepció 1950-býol.



326

15.1 Példák 1. Példa: A és B játékos egymástól függetlenül egy-egy pénzt helyez az asztalra, fej, vagy írás oldallal, amelynek megválasztása týolük függ. Ha mindkét pénznek ugyanaz az oldala van felül, akkor A viszi el mindkét pénzt, egyébként pedig B . Elemezzük a játékot!



327

Egyik játékosnak sincs információja a másikról. Mindkét játékosnak két választása van: F (fej), vagy I (írás). A játék egy 2 × 2-es zérusösszegýu játék a következýo mátrixszal:

AÂB F I F 1 -1 I -1 1



328

A játéknak nincs Nash-egyensúlypontja, vagy nyeregpontja. Nincs nyerýo stratégia sem egyszeri lejátszás esetén. Más a helyzet információk szerzése esetén. Ha tudjuk, hogy A az F -et választja, akkor B választása nyilván I . Ha A az I -t választja, akkor B jó választása: F . Tehát kell a kevert stratégia sokszori lejátszás esetére.



329

2. Példa: Két játékos egymástól függetlenül egy-egy számot ír le az {1, 2, 3} számok közül. Ha a számok összege páros, akkor B kiÞzeti A-nak az összeget dollárban. Ha a számok összege páratlan, akkor A Þzeti ki az összeget B -nek. Elemezzük a játékot! Egyik játékosnak sincs információja a másikról. Mindkét játékosnak három választása van: 1, 2, vagy 3. A játék egy 3 × 3-es zérusösszegýu játék a következýo mátrixszal:



AÂB 1 2 3

1 2 -3 4

2 -3 4 -5

330

3 4 -5 6

A játéknak nincs Nash-egyensúlypontja. Van-e jó stratégia? Választhat-e B olyan stratégiát, ami mindig jó számára? Ha pl. A buta és mindig az 1-et választja, akkor B mindig 2-ýot ír, stb. Konklúzió: kell egy véletlen stratégia.



331

3. Példa: A és B ország háborúban áll egymással. Anak háromféle légvédelmi ütege (rakétája) van, B -nek pedig háromféle repülýogépe. Ha A az 1-ik üteget használja, akkor B repülýogépeit rendre 0.9, 0.4 és 0.2 valószínýuséggel találja el. Ha A a 2-ik üteget használja, akkor ugyanezen találati valószínýuségek: 0.3, 0.6, 0.8. A 3-ik üteg esetén a megfelelýo találati valószínýuségek rendre 0.5, 0.7 és 0.2. Elemezzük a játékot!



332

A 3 × 3-as játékban A nyeresége 1 lelýott repülýogép, vagy zérus. B nyeresége ennek ellentettje. Az (i, j) stratégia pár esetén A nyereségének várható értéke: pij · 1 + (1 − pij ) · 0 = pij . A játék mátrixa tehát a következýo:

AÂB 1 2 3

1 0.9 0.3 0.5

2 0.4 0.6 0.7

3 0.2 0.8 0.2

Ennek a játéknak sincs Nash-egyensúlypontja.



333

4. Példa (kétujjas Morra v. malom játék): Mindkét játékos felmutatja egy, vagy két újját és egyidejýuleg becslést ad a másik játékos által felmutatandó ujjak számára. Ha mindkét játékos jól, vagy rossul becsül, akkor a nyeremény 0. Ha csak az egyik becsül jól, akkor nyereménye a két játékos által mutatott ujjak összege, amit a másik játékos Þzet. Elemezzük a játékot!



334

Minden stratégia két komponensbýol áll: ha, bi, ahol a az ujjak száma, b a másik játékos által mutatott ujjak számának becslése. Mindkét játékosnak 4 lehetséges stratégiája van: h1, 1i, h1, 2i, h2, 1i, h2, 2i. A 4 × 4-es mátrixjáték kiÞzetýo mátrixa:



h1, 1i h1, 2i h2, 1i h2, 2i

h1, 1i h1, 2i h2, 1i h2, 2i 0 2 -3 0 -2 0 0 3 3 0 0 -4 0 -3 4 0

A játéknak szintén nincs egyensúlypontja.


335


336

5. példa (Hirdetés): Két konkurrens cég versenyez egy n független piacból álló területen, ahol

a1 > a2 > . . . > an az egyes piacon lévýo vásárlók száma. Az 1. cég elhatározza, hogy az egyik piacon hirdetési kampányt indít, hogy býovítse vevýokörét. Ezt a 2. cég ellenpropagandával akarja kivédeni. A cégek anyagi lehetýoségének korlátozottsága miatt az 1. cég hirdetési kampányát, a 2. cég ellenpropagandáját csak 1-1 piacon tudja Þnanszírozni. Ha az 1. cég hirdetési kampányát az i-edik piacon folytatja és nem ütközik ellenállásba, akkor minden vásárlót megnyer. Ha a 2. cég itt végez aknamunkát, akkor csak piai vásárlót tud megnyerni (0 ≤ pi < 1).



337

Ez is kétszemélyes véges játék, ahol a stratégiák mindkét játékosnál {1, . . . , n}. Az 1. játékos kiÞzetýofüggvénye ½ ai, ha i 6= j, φ1 (i, j) = piai, ha i = j.

Ha 2. cég célja az 1. játékos nyereségének csökkentése, akkor ugyanazon a piacon lép fel, és zérusösszegýu játékkal van dolgunk, ahol φ2 (i, j) = −φ1 (i, j) . A játék kiÞzetýomátrixa pedig a következýo:







p1a1 a1 . . . a1  a2 p2a2 . . . a2  A= .. ..   .. . an an . . . pnan


338


339

Akkor van egyensúlypontja a játéknak, ha a mátrixelem sorának legkisebb, oszlopának legnagyobb eleme. Minden sor legkisebb eleme a diagonális piai elem. Ez akkor lehet oszlopában maximális, ha

piai ≥ aj

Mivel i ≥ 2 esetén fennáll, hogy

(i 6= j) .

a1 > . . . > ai > piai, ez csak akkor lehetséges, ha i = 1. Ekkor az egyensúly feltétele

p1a1 ≥ a2 > ai

(i > 2) .

Tehát az egyensúlyi stratégia az (1,1) stratégia pár, feltéve, hogy p1a1 ≥ a2. Más esetben nincs egyensúlyi stratégia.



340

15.2 A játék alsó és felsýo értéke, a ”minimax” elv A következýokben biztonsági stratégiákat próbálunk meghatározni a játékosok számára. Ha A az i-edik stratégiát választja, akkor feltehetjük, hogy B olyan stratégiát választ, amelyre A nyereménye (B vesztesége) minimális. Ez az a j stratégia lesz, amelyre A i-edik sora minimális. Jelölje ezt a legkisebb értéket

αi = min aij . 1≤j≤n



341

Ha most A olyan stratégiát keres, amelynél kevesebbet nem nyerhet, akármit is játszik B , akkor az αi értékek maximumát kell keresni. Legyen ez az érték

α = max αi = max min aij . 1≤i≤m

1≤i≤m 1≤j≤n

Legyen i0 olyan stratégia, amelyre α = αi0 . Ha az A játékos az i0 stratégiát játssza, akkor nyereménye B bármilyen stratégiája esetén garantáltan legalább α. Az i0 stratégiát A ”maximin” stratégiájának, az α értéket A maximin nyereségének, és/vagy a játék alsó értékének nevezzük.



342

Hasonló okfejtés érvényes a B játékosra is. B abban érdekelt, hogy A nyereségét minimalizálja. Legyen B stratégiája j . Tekintsük az aij értékek maximumát a j -edik oszlopban:

β j = max aij . 1≤i≤m

Vegyük ezek minimumát:

β = min β j = min max aij . 1≤j≤n

1≤j≤n 1≤i≤m

A β mennyiséget a játék felsýo értékének, vagy ”minimax” értékének nevezzük. Legyen j0 olyan stratégia, amelyre β = β j0 . A j0 stratégia B ”minimax” stratégiája. Ha B a j0 stratégiát játssza, akkor nem veszíthet β -nál nagyobb összeget.



343

Az αi sor minimumokkal és β j oszlop maximumokkal az alábbi módon ki lehet egészíteni a játék mátrixát:



AÂB 1 1 a11 2 a21 .. .. m am1 β1

2 a12 a22 .. am2 β2

... n . . . a1n α1 . . . a2n α2 .. .. . . . amn αm . . . βm


344


345

A maximin és minimax stratégiákat szokás közös néven minimax stratégiáknak is nevezni. Tekintsük ismét a korábbi példákat!



346

1. Példa:

AÂB F I F 1 -1 -1 I -1 1 -1 1 1 Ekkor α = −1 < β = 1. Az A játékos vesztesége legfeljebb 1. Ugyanez áll B -re is. Az eredmény triviális.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 2. Példa:

AÂB 1 2 3

1 2 -3 4 4

2 -3 4 -5 4

3 4 -3 -5 -5 6 -5 6


347


348

Ekkor α = −3 < β = 4. Az A játékos maximin stratégiája: 1. Ha ezt szisztematikusan játssza, akkor legfeljebb 3 dollárt veszíthet játékonként. Az ellenfél minimax stratégiája 1 vagy 2. Ez garantálja, hogy vesztesége nem nagyobb mint 4. Ha A eltér a maximin strattégiától, akkor B játszhatja a 3-ik stratégiáját és −5-re redukálja A nyereségét. Ha B tér el a maximin stratégiától, akkor A a 3-ik stratégia választásával 6-ra növelheti nyereségét.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 3. Példa:

AÂB 1 2 3

1 0.9 0.3 0.5 0.9

2 0.4 0.6 0.7 0.7

3 0.2 0.2 0.8 0.3 0.2 0.2 0.8


349


350

Ekkor α = 0.3 < β = 0.7. Az A játékos maximin stratégiája: 2. Ekkor legalább 0.3 valószínýuséggel találja el az ellenség repülýogépét. A B játékos minimax stratégiája: 2. Ekkor B legfeljebb 0.7 valószínýuséggel veszít repülýogépet. A példa arra is jó, hogy a minimax stratégiák instabilitását bemutassa. Tegyük fel, hogy A a 2-ik maximin stratégiát játssza és B is a 2-ik minimax stratégiát játssza. Ekkor az átlagos nyereség 0.6 és α < 0.6 < β . Tegyük fel, hogy B megtudja, hogy A a 2-ik üteggel lýo. Rögtön az 1-es stratégiát választja és csökkenti B nyereségét 0.3-re. Erre A az 1-ik stratégiát választja, amely növeli 0.9-re a nyereségét, stb. Tehát a stratégiát megzavarhatja a bejövýo információ. Ezért is kell a Neumann által bevezetett kevert býovítés.


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 4. Példa (kétujjas Morra/malom játék):

h1, 1i h1, 2i h2, 1i h2, 2i

h1, 1i h1, 2i h2, 1i h2, 2i 0 2 -3 0 -2 0 0 3 3 0 0 -4 0 -3 4 0 3 2 4 3

-3 -2 -4 -3

Ekkor α = −2 < β = 2.


351


352

Az eddigi példákban α < β . Igaz a következýo eredmény. Tétel: α ≤ β . Bizonyítás: DeÞníció szerint

β = min max aij = min ai∗(j),j = ai∗(j ∗),j ∗ ≥ ai,j ∗ ≥ min aij = 1≤j≤n 1≤i≤m

1≤j≤n

j

Tehát fennáll, hogy

β = min β j ≥ max αi = α, j

i

ami bizonyítandó volt. A tétel sokkal általánosabb esetben is igaz.



353

Ha

α = max min aij = min max aij = β, 1≤i≤m 1≤j≤n

1≤j≤n 1≤i≤m

akkor a minimax stratégia stabil. Ekkor a játéknak nyeregpontja, azaz Nash-egyensúlypontja van. 4. Tétel (Goldmann, 1957): Legyen az A m × n mátrix minden elem azonos, tetszýoleges folytonos eloszlású valószínýuségi változó. Ekkor annak a valószínýusége, hogy A-nak van nyeregpontja m!n! . P (m, n) = (m + n − 1)!



354

16 Mátrixjátékok kevert býovítése A továbbiakban is zérusösszegýu játékokat vizsgálunk. Feltesszük, hogy a játékot sokszor játsszuk, mindkét játékos véletlenszerýuen választja stratégiáját egy-egy diszkrét valószínýuségeloszlás alapján és nyereségének várható értékét kívánja maximalizálni (minimalizálni).


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Legyen az A játékos új stratégia halmaza (

X=

[x1, . . . , xm]T | x1 ≥ 0, . . . , xm ≥ 0,

a B játékosé pedig (

Y =

[y1, . . . , yn]T | y1 ≥ 0, . . . , yn ≥ 0,

m X i=1

n X i=1


355

)

xi = 1 , )

yi = 1 .


356

Egy tetszýoleges x ∈ X stratégia azt jelenti, hogy az A játékos i-edik stratégiáját az x vektor i-edik komponensének megfelelýo valószínýuséggel választja. Hasonló az y ∈ Y stratégia jelentése a B játékos esetén. Ha végigjátsszuk az x ∈ X és az y ∈ Y stratégiának megfelelýo összes játékot, akkor az A játékos nyereményének várható értéke φ1 (x, y) = xT Ay, míg a B játékosé φ2 (x, y) = −xT Ay. A φ1 és φ2 függvényeket a kevert býovítésýu játék kiÞzetýofüggvényeinek nevezzük.



357

Levezetésük a következýo: az (i, j) stratégia pár megválasztásának valószínýusége a függetlenség miatt xiyj . Ilymódon a diszkrét

(aij , xiyj ) ,

(−aij , xiyj )

valószínýuségeloszlásokat nyerjük, amelyek várható értékei éppen φ1 és φ2.



358

Az új, un. kevert býovítésýu mátrixjátékot az {X, Y ; φ1, φ2} szimbólummal jelöljük. Egy x0 ∈ X , y0 ∈ Y stratégia pár egyensúlyi stratégia (egyensúlypont), ha fennáll, hogy

φ1 (x0, y0) ≥ φ1 (x, y0) (x ∈ X) φ2 (x0, y0) ≥ φ2 (x0, y) (y ∈ Y ) .

Figyelembevéve, hogy φ2 = −φ1, az utolsó egyenlýotlenség a

φ1 (x0, y0) ≤ φ1 (x0, y)

(y ∈ Y )

alakban írható fel. Összevonva az egyenlýotlenségeket kapjuk, hogy



359

(x0, y0) akkor és csak akkor egyensúlypontja a játék kevert býovítésének, ha kielégíti a φ1 (x, y0) ≤ φ1 (x0, y0) ≤ φ1 (x0, y)

(x ∈ X, y ∈ Y )

un. nyeregpont feltételt. Mátrix formában felírva ez a következýo

xT Ay0 ≤ xT0 Ay0 ≤ xT0 Ay

(x ∈ X, y ∈ Y ) .



360

1. Tétel (Neumann János, 1928). Tekintsük az A ∈ Rm×n mátrixjáték {X, Y ; φ1, −φ1} kevert býovítését! Ekkor léteznek a

v = max min φ1 (x, y)

(217)

v = min max φ1 (x, y)

(218)

x∈X y∈Y

és y∈Y x∈X

mennyiségek és ezek egyenlõk.



361

A tételbõl következik az alábbi megfogalmazás is. 2. Tétel (Neumann János): Az {X, Y ; φ1, −φ1} kevert býovítésýu mátrixjátéknak mindig van (x0, y0) Nash-egyensúlypontja. A ν = xT0 Ay0 érték minden egyensúlyi stratégia párra ugyanaz.



362

A tétel azt mondja ki, hogy a kevert bõvítésû mátrixjátéknak mindig van nyeregpontja, azaz Nash-féle egyensúlypontja. A közös v= v = v értéket a játék értékének nevezzük. A ν érték jelentése: az (x0, y0) stratégia szerint lejátszott mérkýozés sorozatban az A játékos nyereményének várható értéke biztosan ν , míg a B játékos vesztesége biztosan −ν . Ettýol eltérýo nem egyensúlyi stratégia esetén A nyereségének várható értéke csökken, a B játékos veszteségének várható értéke pedig nýo (a veszteség mértéke csökken!).


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa: Tekintsük az

AÂB F I F 1 -1 I -1 1 mátrixjátékot! A játék kevert bõvítését az


363


n o T X = [x, 1 − x] ∈ R2 | 0 ≤ x ≤ 1 , o n T Y = [y, 1 − y] ∈ R2 | 0 ≤ y ≤ 1

statégia halmazok és a


364


·

1 −1 −1 1 = 4yx − 2y − 2x + 1 = (2y − 1) (2x − 1)

φ1 (x, y) = [x, 1 − x]

¸·

y 1−y

kiÞzetõfüggvény adja meg. Ekkor


¸

365


v = min max φ1 (x, y) = min max (2y − 1) (2x − 1) y∈Y x∈X

0≤y≤1 0≤x≤1

és

v = max min φ1 (x, y) = max min (2y − 1) (2x − 1) . x∈X y∈Y

0≤x≤1 0≤y≤1


366

Optimálási módszerek, 2003/2004, II. félév (óravázlat) A következõ esetek lehetségesek:   2y − 1, y > 1/2 max (2y − 1) (2x − 1) = 0, y = 1/2 0≤x≤1  1 − 2y, y < 1/2

367

Ennek minimuma a 0 ≤ y ≤ 1 intervallumon 0. Tehát v = 0. Hasonlóan láthatjuk be, hogy



368

  1 − 2x, x > 1/2 , min (2y − 1) (2x − 1) = 0, x = 1/2 0≤y≤1  2x − 1, x < 1/2

amelynek maximuma a 0 ≤ x ≤ 1 intervallumon 0. Tehát v= 0 és v= v = 0. A

φ1 (x, y) = (2y − 1) (2x − 1) = 0 = v ¡1 ¢ ¡ 1¢ egyenletnek végtelen sok megoldása van: 2 , y , x, 2 (x, y ∈ [0, 1]). Vizsgáljuk most azt, hogy mely megoldások nyeregpontjai a φ1 kiÞzetõfüggvénynek. φ1 (x, y0) ≤ φ1 (x0, y0) ≤ φ1 (x0, y)

(x ∈ S1, y ∈ S2)



369

Egyszerû behelyettesítéssel kapjuk, hogy µ µ ¶ ¶ 1 1 0 = φ1 , y ≤ φ1 , y + δ = 0 (y + δ ∈ [0, 1]) 2 2 mindig teljesül, de µ µ ¶ ¶ ¶ µ 1 1 1 + γ, y = 2γ (2y − 1) ≤ φ1 , y = 0 + γ ∈ [0, 1] φ1 2 2 2 csak akkor teljesül, ha y = 1/2.



370

Hasonlóképpen eljárva kapjuk, hogy µ µ ¶ ¶ µ ¶ 1 1 1 ≤ φ1 x, =0 + γ ∈ [0, 1] 0 = φ1 x + γ, 2 2 2 mindíg teljesül, de µ µ ¶ ¶ ¶ µ 1 1 1 ≤ φ1 x, + δ = (2x − 1) 2δ + δ ∈ [0, 1] 0 = φ1 x, 2 2 2 csak akkor, ha x = 1/2. Tehát csak egy egyensúlypontja van a £ 1 1 ¤T £ 1 1 ¤T játék kevert bõvítésének: x0 = 2 , 2 és y0 = 2 , 2 . Ez azt jelenti, hogy mindkét játékos a pénzfeldobás módszerével választja stratégiáját és ennél jobb stratégia nincs. megjegyezzük még, hogy α = −1 és β = 1!


Optimálási módszerek, 2003/2004, II. félév (óravázlat) Példa: Tekintsük az

AÂB 1 2 1 1 3 2 4 2 mátrixjátékot! A játék kevert bõvítését az


371


n o T X = [x, 1 − x] ∈ R2 | 0 ≤ x ≤ 1 , o n T Y = [y, 1 − y] ∈ R2 | 0 ≤ y ≤ 1

statégia halmazok és a

·

¸·

1 3 y φ1 (x, y) = [x, 1 − x] 4 2 1−y = −4yx + 2y + x + 2

¸

adják meg. Keressük a φ1 (x, y) függvény nyeregpontját! Tekintsük a függvény


372


∇φ1 = gradiensét és

· ·

1 − 4y 2 − 4x

373

¸ ¸

0 −4 −4 0 Hesse-mátrixát! A gradiens az x = 1/2 és y = 1/4 pontban tûnik el. A Hesse mátrix sajátértékei: ±4. ∇2φ1 =


Optimálási módszerek, 2003/2004, II. félév (óravázlat) 374 ¡1 1¢ Tehát az 2 , 4 pont nyeregpont, a megfelelõ ¸ ¸ · · 1 1 1 3 x0 = , , y0 = , 2 2 4 4 kevert stratégiák (vsz. eloszlások) pedig a kevert játék Nashegyensúlypontját adják. A kevert bõvítésû játék értéke: v = ¡1 1¢ φ1 2 , 4 = 5/2. Az alapul szolgáló mátrixjáték alsó és felsõ értéke: α = 2, β = 3. A most látott példák megoldásai ad hoc jellegûek voltak, amelyek bonyolultabb esetekben nem feltétlenül vezetnek eredményre.



375

Tekintsük a

β → min eT x = 1 AT x ≥ −βe x≥0

α → min eT y = 1 Ay ≤ αe y≥0

programozási feladatokat, ahol e olyan vektort jelöl, amelynek minden komponense 1.



376

Jelölje x∗ az elsýo, y ∗ pedig a második programozási feladat optimális megoldását. Legyen továbbá β ∗ az x∗-hoz tartozó célfüggvényérték. Igaz a következýo 14. Tétel: Az (x∗, y ∗) pont a kevert játék egyensúlyi stratégia párja, β ∗ pedig a játék értéke. Minden egyensúlyi párt megkaphatunk az optimalizálási feladatok megoldásával.



377

Példa: Két cég három termékkel harcol egy piacon a másik kiszorítására. A játékuk kiÞzetýo mátrixa   2 1 0 A =  2 0 3 . −1 3 3

Ennek a játéknak nincs egyensúlypontja, tehát kevert býovítést kell alkalmazni. A megfelelýo programozási feladatok rendre a következýok



β → min x1 + x2 + x3 = 1 2x1 + 2x2 − x3 + β ≥ 0 x1 + 3x3 + β ≥ 0 3x2 + 3x3 + β ≥ 0 x≥0


378

Optimálási módszerek, 2003/2004, II. félév (óravázlat) és

α → min y1 + y2 + y3 = 1 2y1 + y2 − α ≤ 0 2y1 + 3y3 − α ≤ 0 −y1 + 3y2 + 3y3 − α ≤ 0 y≥0


379

Optimálási módszerek, 2003/2004, II. félév (óravázlat) Ezek optimális megoldása a következýo £ 4 4 5 ¤T ∗ x = 7 , 21 , 21 , β ∗ = − 97 ∗

y =

£3

3 1 , 7 7, 7

¤

.


380

Optimálási módszerek Galántai Aurél

Recommend Documents