Optimalizálási eljárások MSc hallgatók számára
10. Előadás Előadó: Hajnal Péter Jegyzetelő: T. Szabó Tamás
2011. április 20.
1. Feltétel nélküli optimalizálás: Az eljárás alapjai A feltétel nélküli optimalizálásnál a feladatunkat a következőképp lehet megfogalmazni: egy c(x) célfüggvényt kell minimalizálni az egész dom(c) értelmezési tartományon. Korábbi jelöléseinkkel tehát D = L = dom(c). A módszerünk a következő lesz: iterációval szeretnénk közelíteni x∗ -ot: a(0) → a(1) → a(2) → . . . , ahol mindegyik a(i) ∈ L. Az iterációt valamilyen leállási feltételig folytatjuk. Az a pontokat aktuális pontoknak nevezzük. Azt szeretnénk, ha ez a sorozat x∗ -hoz konvergálna (feltéve, hogy c(x) felveszi p∗ -ot, ez speciálisan azt is jelenti, hogy p∗ véges). A megállási feltételt úgy szeretnénk választani, hogy jelezze”, hogy x∗ közelében vagyunk. Ez lehet valamilyen ” metrikában való közelség, vagy lehet az, hogy c(a(i) ) > p∗ − ǫ (egy ǫ-szuboptimális pontban vagyunk). A továbbiakban c(x)-re a következő feltételeket tesszük: • c(x) konvex (az egész L-en), • c(x) kétszer folytonosan differenciálható (az egész L-en), • c(x) szigorúan konvex egy az alábbiakban leírt S ⊂ L halmazon, amely x∗ -ot tartalmazza: azaz alkalmas m > 0 teljesíti, hogy ∇2 c(x) mI
minden x ∈ S esetén,
ahol ∇2 c(x) a c(x) Hesse-mátrixa, és azt jelenti, hogy a bal és jobb oldal különbsége pozitív szemidefinit. Most az iteráció szabályait vizsgáljuk: ezeket úgy nevezetett update szabályoknak nevezzük, amelyek segítségével a(k) -ból megkaphatjuk a(k+1) -et. Mi csak olyan, úgy nevezetett uniform szabályokkal foglalkozunk, ahol ez a lépés nem függ k értékétől. Tehát egy a értékből szeretnénk meghatározni a következő iteráció a+ értékét. Ez az eljárás két lépésből fog állni: • irányválasztás: ∆(a) ∈ Rn • lépésválasztás: t(a) ∈ R≥0
10-1
Ezután a következő iteráció értéke a+ = a + t(a)∆(a) Vizsgáljuk most külön ezt a két lépést. I. Az irányválasztásnak mindig olyannak kell lennie, hogy (∇c(a))⊤ ∆(a) < 0, vagyis a függvény a ∆(a) irányba csökken” (legalábbis a egy kis környezetében). ” II. A lépésválasztás az irányválasztás után következik. Itt is olyan választással élünk, hogy a c célfüggvény értéke csökken. Speciálisan az értelmezési tartománynak az algoritmusaink során fellépő értékei mind az S := {x ∈ dom c : c(x) ≤ c(a(0) )} halmazból kerülnek ki. c konvex, speciálisan folytonos, így S zárt. A lépésválasztásnál is több lehetőség közül csak kettőt ismertetünk. Ezek leírásához vezessük be a e c(t) := e ca (t) = c(a + t∆(a)), t ≥ 0 jelölést. 1. lehetőség. Mohó lépésválasztás: t = t(a) legyen a e c(t) minimumhelye. 2. lehetőség. Visszakozó” lépésválasztás: A konvexitás miatt tudjuk, hogy ” e c(x) ≥ c(a) + (∇c(a))⊤ ∆(a) · x.
A jobb oldal egy határt szab arra, hogy a választott irányba haladva milyen gyorsan eshet a célfüggvény értéke. Egy kicsit relaxáljuk a függvény érték csökkenését. Válasszunk most α ∈ 0, 12 és β ∈ (0, 1) paramétereket alkalmas módon (ez a probléma jellegétől, az alkalmazási területtől függően más és más lehet). Ekkor az c(a) + α · (∇c(a))⊤ ∆(a) · x > e c(x).
egyenlőtlenség valamely ǫ > 0 esetén teljesül [0, ǫ) intervallumban. Olyan x = t értékét szeretnénk választani, hogy a relaxált egyenlőtlenség teljesüljön. Először kipróbáljuk a t = 1 értéket; ha ez nem jó, akkor t-t a β-szorosára csökkentjük, és ezt addig folytatjuk, amígy nem teljesül a kívánt egyenlőtlenség (a fentiek miatt ez garantáltan teljesül). ⋆ A továbbiakban már csak az irányválasztás témakörével foglalkozunk. Ebben az esetben is a sokféle lehetőség közül csupán kettővel foglalkozunk érdemben. Mindegyik esetben a teljes optimalizálási algoritmus úgy alakul ki, hogy az irányválasztási eljárás mellé választjuk az egyik lépésválasztó sémát és leírjuk a leállási szabályt.
2. A gradiensmódszer A lépés irányát ∆(a) := −∇c(a) 10-2
írja le. Ezt az irányválasztást nevezhetjük mohó irányválasztásnak mert lokálisan a lenagyobb növekedést igéri a célfüggvény követésénél. Ezután t = t(a)-t a korábban ismertetett két módszer egyikével határozhatjuk meg. Ennél a módszernél a leállási feltétel, hogy k∇c(a)k ≤ δ teljesüljön az aktuális helyen egy előre adott δ > 0 konstansra. 1. Lemma. Legyen f egy kétszer differenciálható függvény, amely S-en szigorúan konvex valamely m > 0 paraméterrel. Ekkor minden x, y ∈ S esetén (i) f (y) ≥ f (x) + ∇f (x)⊤ (y − x) + (ii) inf f (s) = p∗ ≥ f (x) −
s∈S
(iii) kx − x∗ k2 ≤
m ky − xk22 , 2
1 k∇f (x)k22 , 2m
2 k∇f (x)k2 . m
Bizonyítás. Az (i) pont bizonyítása: legyen x, y ∈ S tetszőleges. Ekkor az elsőrendű Taylor-sorfejtés szerint van olyan z ∈ [x, y] úgy, hogy 1 f (y) = f (x) + ∇f (x)⊤ (y − x) + (y − x)⊤ ∇2 f (z)(y − x) 2 1 ≥ f (x) + ∇f (x)⊤ (y − x) + (y − x)⊤ mI(y − x) 2 1 ≥ f (x) + ∇f (x)⊤ (y − x) + mky − xk22 , 2 ahol I az n-dimenziós egységmátrix, és az első egyenlőtlenségben használtuk, hogy f szigorúan konvex. A (ii) pont bizonyítása: Legyen y ∈ S tetszőleges. Az (i) pont bizonyítása szerint m ky − xk22 2 m ≥ f (x) + ∇f (x)⊤ (y0 − x) + ky0 − xk22 , 2
f (y) ≥ f (x) + ∇f (x)⊤ (y − x) +
(1)
ahol y0 az az y érték, amelyre az f (x) + ∇f (x)⊤ (y − x) +
m ky − xk22 2
kifejezés felveszi a minimumát. Keressük meg egy adott x ponthoz ezt az y0 -t! A harmadik tag csak ky − xk2 -tól függ. Ha pedig y − x = α adott, akkor a második tag csak (y − x)-nek a ∇f (x)-hez viszonyított irányától függ. Ez a skalárszorzat pedig akkor lesz minimális, ha y − x = −α∇f (x). Ekkor a kifejezésünk α függvényében f (x) −
αk∇f (x)k22
mα2 k∇f (x)k22 . + 2
10-3
Ezt a másodfokú függvényt α-ban minimalizálva az optimális α érték vagyis a kifejezés minimumát (1)-be beírva f (y) ≥ f (x) −
1 -nek m
adódik,
1 1 1 k∇f (x)k22 + k∇f (x)k22 = f (x) − k∇f (x)k22 . m 2m 2m
Mivel pedig ez minden y ∈ S-re igaz, azért az f függvény S-en felvett infimuma is teljesíti az egyenlőtlenséget. A (iii) pont bizonyítása: az (i) pontba y helyére x∗ -ot írva a következőt kapjuk: m ∗ kx − xk22 ≥ 2 m ≥ f (x) − k∇f (x)k2 kx∗ − xk2 + kx∗ − xk22 ≥ 2 m ∗ ∗ ∗ ≥ p − k∇f (x)k2 kx − xk2 + kx − xk22 . 2
p∗ ≥ f (x) + ∇f (x)⊤ (x∗ − x) +
Ezt átrendezve pedig k∇f (x)k2 kx∗ − xk2 ≥
m ∗ kx − xk22 , 2
ami éppen a bizonyítandó.
Mielőtt továbbhaladunk megemlítjük a szigorúan konvexitás feltételének egy következményét. A Lemma (i) pontjából könnyen kiolvasható, hogy f függvény szubszinthalmazai (Sτ = {x ∈ dom c : f (x) ≤ τ } halmazok) korlátosak. Így speciálisan S is korlátos, mellesleg zárt. Azaz S kompakt. Ebből következik, hogy ∇2 c maximális sajátértéke felveszi maximumát S-en. Azaz alkalmas M konstanssal minden x ∈ S esetén ∇2 c(x) MI. Ahogy az előző Lemma (i) pontját bizonyítottuk most kapjuk, hogy x, y ∈ S esetén f (y) ≤ f (x) + ∇f (x)⊤ (y − x) +
M ky − xk22 . 2
Ezek után nézzük a gradiens módszer (mohó lépés választással) analízisét szigorúan konvex célfüggvény esetén (használva a fogalom mögött rejlő gyakran nehezen becsülhető m és M konstansokat). 2. Tétel. Legyen a c(x) függvény szigorúan konvex S-en, speciálisan létezzenek olyan 0 < m ≤ M < ∞ konstansok, hogy bármely x ∈ S esetén mI ∇2 c(x) MI teljesüljön. Ekkor a mohó lépésválasztással futtatott gradiensmódszer k-adik lépése teljesíti a m k 0 ≤ c a(k) − p∗ ≤ 1 − (c(a0 ) − p∗ ) M egyenlőtlenséget. Bizonyítás. Az előző lemma (i) pontját alkalmazzuk. A választott lépéshosszat tm mel (index a mohó szóból) jelölve, az a aktuális pont után szeretnénk meghatározni az iteráció következő, a+ -szal jelölt helyét: c(a+ ) = c(a + tm ∆) = c(a − tm ∇c(a)) ≤ c(a) − tm k∇c(a)k22 + 10-4
Mt2m k∇c(a)k22 . 2
Mivel tm -et a mohó lépésválasztás szerint választottuk, ezért ha tm helyébe például 1 - et írunk, a c függvény értéke nem csökkenhet: M 1 1 + c(a ) ≤ c a + ∆ ≤ c(a) − k∇c(a)k22 , M 2M azaz
1 k∇c(a)k22 . 2M A lemma (ii) pontját 2m-mel átszorozva (x = a esetben), rendezve kapjuk hogy c(a+ ) − p∗ ≤ c(a) − p∗ −
k∇c(a)k22 ≥ 2m(c(a) − p∗ ), azaz
2m c(a+ ) − p∗ ≤ c(a) − p∗ − (c(a) − p∗ ), 2M m (c(a) − p∗ ). c(a+ ) − p∗ ≤ 1 − M amiből teljes indukcióval adódik a bizonyítandó.
Példa. Tekintsük a c(x) = (x21 + Mx22 )/2 célfüggvényt. Ez középiskolai háttérrel is nyilvánvaló optimalizálási probléma. c(x) nemnegatív és egyetlen helyen veszi fel a 0 értéket. Azaz p∗ = 0 és x∗ = (0, 0). Nézzük meg mi lesz, ha a gradiens módszert futtatjuk a mohó lépésválasztással: A célfüggvény az egész R2 -en szigorúan konvex. m = 1, míg az M paraméter a m fent használt M szám. Ha most M ≫ 1, akkor M = M1 ≈ 0. A fenti tétel alapján csak lassú konvergenciat látunk. Ez nem elméleti hátterünk gyengeségéből adódik, ez valójában így lesz. (i) (i) Vegyük az a(0) = (M, 1) kezdőértékkel az a(i) = (a1 , a2 ) aktuális értékek a következő formulával írhatók le: i i M −1 M −1 (i) (i) a1 = M , a2 = − , M +1 M +1 továbbá a célfüggvény értéke 2i 2i 2i M −1 2 M(M + 1) M − 1 (0) (i) = c(a ) = 1 − c(a(0) ). c(a ) = 2 M +1 M +1 M +1 A képletek ellenőrzését az érdeklődő hallgatóra bízzuk.
3. A Newton-módszer A Newton-módszerben először felírjuk a céfüggvény másodrendű Taylor-közelítését a körül: 1 c(a + v) ≈ c(a) + ∇c(a)⊤ v + v ⊤ ∇2 c(a)v. 2 Úgy szeretnénk megválasztani a v értékét, hogy az a+ = a + v-ben a jobb oldali közelítő kifejezés a minimumát vegye fel. Ehhez a jobb oldal gradiensét (v szerint) kell 0-val egyenlővé tenni: ∇v J.O. = ∇c(a) + ∇2 c(a)v. 10-5
A jobb oldalt 0-val egyenlővé téve kapjuk, hogy ∆(a) = vopt = ∇2 f (a)
−1
∇f (a).
A lépésválasztásra a korábbi két lehetőség fennáll, de megemlítünk egy harmadikat is: Egyszerűen legyen t = 1.
4. Belső pontos módszerek Az ismertetett módszerek feltétel nélküliek” voltak, azaz a célfüggvény teljes értel” mezési tartományán optimalizáltunk. A módszerek alkalmazása feltételek melletti optimalizálásra nem nyilvánvaló. Egy ötlet: definiáljunk egy (paraméteres) segédfüggvényt, amely a feltételnek megfelelő tartomány határozott belsejében közel egyenlő a célfüggvénnyel, a tartomány határához közel nagyon nagy értékeket vesz fel, és továbbra is konvex, többszörösen differenciálható (a tartomány belsején kívül nem is lesz értelmezett). A paraméter értékét növelve az a tartomány, ahol a közelítő segédfüggvény jól approximálja a célfüggvényt egyre jobban a feltételek által leírt tartományhoz simul”. ” Azaz dom cp approximálja dom c ∩ F -et. cp optimalizálása feltétel nélküli, de egy feltételes minimalizálást modellál. A segédfüggvényre alkalmazva a most leírt módszereket egy a aktuális értéket kapunk. A paraméter növelésével kapott jobb segédfüggvényt véve a-ból megkapjuk az update-lt a+ pontot. Ezen módszereket nevezik belső pontos módszernek A részletek kidolgozását a jövő alkalommal végezzük el.
10-6
