OPTIMALIZÁLÁSI ELJÁRÁSOK Matematika MSc hallgatók számára
4. Előadás Előadó: Hajnal Péter Jegyzetelő: Magyari Nikolett
2011. március 2.
1. A legkisebb négyzetek probléma A legkisebb négyzetek problémája a következő optimalizálási alapfeladat: Minimalizáljuk
c(x) = |Ax − b|-et
ahol A ∈ RN ×n egy teljes oszloprangú mátrix. Azaz, ha A = (a1 , a2 , . . . , an ) — ahol ai az A mátrix i-edik oszlopa —, akkor az ai ∈ RN vektorok lineárisan függetlenek. Speciálisan N ≥ n. Igazából az N ≫ n a helyes szemlélet. Megjegyzés. Egy k × ℓ méretű mátrix teljes rangú, ha rangja min{k, ℓ}. Ez a tulajdonság két lehetőséget takar. Ha a rang k, akkor k ≤ ℓ. Erre az esetre szokásos úgy hivatkozni, hogy kövér teljes rangú mátrix. A másik eset (amikor a rang ℓ és ekko ℓ ≤ k) a sovány teljes rangú mátrix esete. A teljes rangú négyzetes mátrixok mindkét esetbe beleérthetők. Esetünkben feltesszük, hogy a legkisebb négyzetek problémájában szereplő mátrix sovány teljes rangú. A feltétel kikerülhető, de technikai problémákhoz vezet. Az áttekinthetóség kedvéért élünk a megszorítással. Bizonyítás nélkül közlünk egy számunkra fontos lineáris algebrai állítást. 1. Lemma. Egy A sovány teljes rangú A mátrixra AT A invertálható. Az optimalizálási feladatnak nagyon szemléletes geometriai tartalma van (lásd ábra). range A = {Ax : x ∈ Rn } ⊆ RN , egy lineáris altér, amit ha1 , . . . , an i vektorok
1. ábra. generálnak. Feltételünk alapján generáló elemek lineárisan függetlenek (az altér egy
4-1
bázisát alkotják), azaz az altér dimenziója n. Feladatunk b és range A távolságának meghatározása. Látható, hogy a célfüggvény egyszerű, nincs feltétel speciálisan D = L = Rn . A feladatunk ekvivalens a távolság négyzetének minimalizálásával, azaz az Minimalizáljuk
c(x) = |Ax − b|2 -et
alakkal. Ez hasznosabb számunkra, mert a célfüggvény differenciálható.
1.1. Első nekifutás A probléma egy konvex, differenciálható függvény minimalizálása. A klasszikus analízis technikái adják a megoldást: c(x) = (Ax−b)T (Ax−b) = xT AT Ax−xT AT b−bT Ax+bT b = xT AT Ax−2bT Ax+bT b. Ekkor ∇c(x) = 2AT Ax − 2AT b. ∇c(x) akkor lesz 0, ha x = [(AT A)−1 AT ]b. Mivel c konvex ez a feltétel elegendő is ahhoz, hogy minimumhelye legyen c(x)-nek: x∗ = [(AT A)−1 AT ]b, ahol x∗ az optimalizálási feladat optimális helye. A megoldó képletben” szereplő mátrix sok helyen felmerül. Érdemes közelebbről ” is megvizsgálni. Megjegyzés. • Ha N = n, akkor A invertálható. Ebben az esetben (AT A)−1 AT = −1 T −1 T A (A ) A = A−1 • Általában [(AT A)−1 AT ]A = (AT A)−1 (AT A) = I, azaz az x∗ -ra felírt kifejezésben szereplő mátrix A EGY bal oldali inverze. Definíció (Moore—Penrose-inverz/pszeudoinverz). Ha A oszlopai lineárisan függetlenek, akkor A† = (AT A)−1 AT az A mátrix pszeudoinverze. Igen ritka, hogy egy általános optimalizálási feladatnak ennyire explicit megoldása legyen. Egyszerűsége ellenére a legkisebb négyzetek problémája az egyik leggyakrabban alkalmazott optimalizálási feladat
1.2. Második nekifutás Emlékeztető (Gram—Schmidt-ortogonalizálási-eljárás). A Gram—Schmidt-ortogonalizálási-eljárást az A mátrix a1 , . . . , an oszlopaira alkalmazva egy q1 , . . . , qn vektorrendszert kapunk, amelyre teljesül, hogy (i) elemei ortogonális egységvektorok, (ii) az általuk kifeszített altér, megegyezik az a1 , . . . , an oszlopok által kifeszített altérrel, range A-val, 4-2
(iii) a1 meghatározza q1 -et, a1 , a2 meghatározza q2 -t, a1 , a2 , a3 meghatározza q3 -t és így tovább, plusz az összes kapcsolat lineáris. A fentieket a lineáris algebra nyelvén leírva A = (q1 , . . . , qn )Rn×n := QN ×n · R. (i) megfogalmazása: QT Q = I. (iii) megfogalmazása A felsőtrianguláris, a főátlóban lévő elemek nem-nullák. A ilyen felírását A QR-felbontásának nevezzük Megjegyzés. Az eljárás akkor is működik, amikor az ai vektorok nem lineárisan függetlenek. Legyen rank A = n0 < n. Ekkor AN ×n = QN ×n0 · Rn0 ×n . Ekkor R-ről azt tudjuk, ha soraira az első nem 0 elem indexének sorozat nézzük, akkor ez szigorúan monoton lesz. Fejezzük ki A pszeudoinverzét a QR-felbontása alapján: A† = ((QR)T QR)−1 (QR)T = (RT QT QR)−1 RT QT = R−1 (RT )−1 RT QT = R−1 QT Általában ezen alakon alapulnak a konkrét pszeudoinverzet számoló algoritmusok.
1.3. Harmadik nekifutás Előbb az analitikus megoldásból vettük x∗ -ot leíró képlet mátrixát. Most függetlenül dolgozunk. A QR-felbontásnak van egy kiterjesztett alakja, a teljes-QR-felbontás. Először idézzük fel ezt: Emlékeztető. Az q1 , . . . , qn ortonormált rendszer megkapása után a kapott vektrokat egészítsük ki további vektorokkal, hogy RN egy ortonormált bázisát kapjuk. (Ezt megtehetjük például a Gram—Schmidt-eljárást alkalmazzuk az (A|I)N ×(n+N ) teljes sorrangú mátrixra.) R , A = (Q1 |Q2 )N ×N 0 N ×n ahol Q1 a korábbi Q. Az optimalizálási feladatunk célfüggvénye 2 R 2 x − b . c(x) = |Ax − b| = (Q1 |Q2 ) 0
A célfüggvény egy vektor hossznégyzete. Ez nem változik, ha ortogonális transzformációt alkalmazunk rá. Mi a (Q1 |Q2 ) mátrix-szal való szorzást alkalmazzuk: T 2 Rx − QT1 b 2 Q1 R T = x− b = c(x) = c((Q1 Q2 ) x) = Q2 T 0 −Q2 T b 2 2 2 2 T T = Rx − Q1 b + Q2 b = Q1 Rx − Q1 QT1 b + Q2 QT2 b . 4-3
(Az utolsó egyenlőségnél ismét kétszer alkalamztunk egy hosszt megőrző ortogonális transzformációt.) Némi elnevezéstan”: Q1 QT1 a projekció mátrix. (Emlékezzünk a másik irányú ” szorzatra is: QT1 Q1 = I.) (Q1 |Q2 ) oszlopai egy ortonormált bázisát adják RN nek. Ebben a bázisban felírható minden vektor, speciálisan b is. A b vektor a Q1 oszlopaihoz tartozó koordinátáit éppen a Q1 b vektor adja meg. Ezt Q1 -gyel szorozva — a Q1 (QT1 b) vektor — adja a Q1 oszlopaihoz tartozó komponensek összegét, a Q1 sorai által kifeszített altérre vonatkozó vetített képet. Azaz legyen πrange A a range A altérre való vetítés. Ennek lineáris algebrai alakja πrange A (b) = Q1 QT1 b, ahol Q1 QT1 mérete N × N. Q2 oszlopai éppen a Q1 oszlopai által kifeszített range A altér ortogonális kiegészítőjét feszítik ki. Q2 QT2 b a b vektor erre vonatkozó vetülete. Azaz c(x) fenti felírása tulajdonképpen csak egy Pitagorasz-tétel:
2. ábra. Az új alakból nyilvánvaló, hogy az optimális érték azon x-re vevődik fel, amelyre Q1 Rx = Q1 QT1 b, azaz x∗ = R−1 QT1 b. Egyszerű lineáris algebra adta az optimálizálás megoldását és annak geometriai tartalmát.
1.4. Dualizálás Optimalizálási feladatunk: Minimalizáljuk
|Ax − b|2 -et
Nincs feltételünk, a dualizálásnak nincs értelme: L(x, λ, µ) = c(x). A duális feladat célfüggvénye b c(λ, µ) = inf x c(x). Ennek meghatározása ugyanaz mint az eredeti probléma. A probléma átfogalmazására nagyon érzékeny a dualizálás. Triviális átírások lényegesen eltérő duális feladathoz vezetnek. Lássuk a legkisebb négyzetek problémájának egy átírását: 4-4
Minimalizáljuk Feltéve, hogy
|x|2 -et Ax = Ab,
ahol A ∈ RN ×n , ahogy előbb. Maximalizáljuk
− 21 µT AAT µ − AT bT µ-et
A Slater-feltétel nyilván teljesül. Erős dualitás van, azaz ha p∗ < ∞, akkor p = d∗ , ahol d∗ a duális optimális érték. ∗
1.5. Egy alkalmazás Adottak a(ti , fi) számpárok (i = 1, . . . , 10.000), ahol ti : különböző helyek, fi : mért függvényértékek (ti , fi ∈ R). Kerssünk d fokú polinomot, amely jól egyezik” a mért ” adatokkal. p(x) = x0 + x1 t + x2 t2 + · · · + xd−1 td−1 , ahol (x0 , x1 , . . . xd−1 ) ∈ Rd . Tegyük fel, hogy d ≪ 10.000. Speciálisan nem egy interpolációs feladatról van szó. A jó egyezést persze tisztázni kell. Egy lehetséges megoldás, hogy a jó egyezés” ” (p(ti )) és (fi ) közelsége. Ekkor a legkisebb négyzetek problémájával állunk szemben. A paraméterek: 1 t1 tk1 . . . td−1 t f1 1 1 d−1 k t2 f2 1 t t . . . t 2 2 2 x = .. . b= A = .. , .. .. , .. .. . . . . ... . . d−1 k t10.000 f10.000 1 t10.000 t10.000 . . . t10.000
2. Lineáris programozás A lineáris programozás egy rendkívül fontos esete az optimalizálási problémáknak. Láttuk már néhány alkalmazását. Most további kettőt említünk. Példa (Politópok Csebisev-középpontja). A P = {x ∈ Rn : aTi x ≤ b, i = 1, . . . , k} alakú ponthalmazokat poliédereknek nevezzük. Ha a P poliéder korlátos (amikor is kompakt: korlátos és zárt), akkor politópnak nevezzük. Fontos probléma, hogy mérjük P egy pontja milyen mélyen van P belsejében. Illetve fontos kérdés: Melyek P legbelső pontjai? Igazából az is központi probléma, hogy P-ről döntsük el, hogy üres-e. Sokféle megoldás/válasz van. Mi egy, Csebisev nevéhez fűzött, megoldásról beszélünk. Definíció. B(c, r) = {x ∈ Rn : |x − c|2 ≤ r 2 } a c középpontú r sugarú gömb. A p ∈ P pont Csebisev mélysége M(p) = max{r : B(p, r) ≤ P}. c a P politóp egy Csebisev középpontja, ha M(c) = sup M(p). p∈P
4-5
Az alapprobléma: Adott P esetén keressünk egy Csebisev középpontot. A feladat első ránézesre nem lineáris. Némi ötlettel azonban LP feladatként fogalmazhatjuk meg. Némi geometriai ismeretre lesz szükségünk. Definíció. Egy hipersík Rn -ben: H = {x : aT x = b} alakú ponthalmaz. r pont pontosan akkor esik H-ra, ha aT r − b = 0. Egy p pont előjeles távolsága H-tól b aT p− . |a| |a| Az előjeles távolság abszolútértéke a távolság, előjele a hipersík azon oldalát írja le, ahová pontunk esik. Kétféle előjeles távolság létezik. A fenti az, amelyik az {x : aT x > b} féltérben pozitív, a komplementer (nyilt) féltérben negatív. A Csebisev-középpont problémája ekvivalens a következővel: Maximalizáljuk Feltéve, hogy
r-et aTi x + |ai |r ≤ bi , r≥0
Első típusú feltételünk ekvivalens azzal, hogy r≤
aT i x |ai |
i = 1, . . . , k
+r ≤
b , |ai |
azaz
b aT − i x. |ai | |ai |
A jobb oldalon egy előjeles távolság szerepel, amit úgy választottunk, hogy az ai x < b félterekben legyen pozitív. Az átfogalmazott optimalizálási feladat egy LP feladat. Példa (Gráfok súlyozott párosítási problémája). G egyszerű gráf esetén határozzuk meg ν(G) = max{|M| : M párosítás G-ben}. Általánosabban: Ha adott G és w : E(G) → R≥0 élsúlyozás, akkor határozzuk meg νw (G) = max{w(M) : M párosítás G-ben} P értékét, ahol egy X élhalmazra w(X) = e:e∈X w(e). M ⊆ E élhalmaz leírható/kódolható χM ∈ Rm ≡ RE(G) karakterisztikus vektorával. Nyilván 1T χM = |M|, w T χM = w(M). Könnyű látni, ν(G) = max{1T χM : M párosítás G-ben} és νw (G) = max{1T χM : M párosítás G-ben}. Definíció. Legyen MP(G) = conv{χM : M párosítás}. A fenti politóp csúcsai a χM vektorok. A politópon lineáris függvény szélsőértékét csúcson veszi fel. Így a párosítási, illetve súlyozott párosítási probléma Maximalizáljuk Feltéve, hogy
Maximalizáljuk Feltéve, hogy
1T x-et x ∈ MP(G).
w T x-et x ∈ MP(G).
Az LP problémákban is egy poliéderhez tartozás szerepel feltételrendszerként, de ott a poliéder egy másik leírását kell látnunk. Az LP-ben leírt ponthalmazok mint félterek metszete adott. MP(G) ilyen leírását Edmonds adta meg. 4-6
2. Tétel (Edmonds-féle poliéder-tétel). MP(G) = {x ∈ RE(G) : P xe ≥ 0 x ≤1 Pe:vIe e e=xy:x,y∈S xe ≤
|S|−1 2
minden e ∈ E esetén minden v ∈ V esetén minden S ⊆ V páratlan elemszámú halmazra}.
A fenti módon a súlyozott párosítási probléma egy LP feladatként írható le. Megjegyzés. Vigyázni kell arra, hogy a probléma mérete nagyon megváltozott. Eredetileg egy gráf és élsúlyozása volt az input. LP feladatként az egyenlőtlenségrendszer, ami leírta a politópot exponenciálisan hosszú lehet. Azaz a fenti átfogalmazás és a szimplex módszer ismerete nem jelenti a probléma kezelhetőségét. A szimplex módszernek szüksége van az egyenletrendszer mátrixára, ami óriási a gráf és ehhez mérhető súlyokhoz. Példa. Specializáljuk az előző példát G = C5 esetére.
3. ábra. Öt változónk lesz, mindegyik előjel feltétellel: xe , xf , xg , xh , xi ≥ 0. A csúcsokra felírt feltételek: xe + xf ≤ 1 xf + xg ≤ 1 xg + xh ≤ 1 x + xi ≤ 1 h xi + xe ≤ 1
Ha itt megállunk, akkor nem MP(G)-t kapjuk: 1 1 1 1 1 1 1 1 1 1 , , , , kielégíti eddigi feltételeinket, de , , , , ∈ / MP(C5 ). Valóban 2 2 2 2 2 2 2 2 2 2 MP(G) minden pontja olyan, hogy kooordinátái összege legfeljebb 2. (Ez a χM , ahol M párosítás, alakú pontokra nyilván igaz és ez öröklódik a konvex burokra is.) Az Edmonds-tétel egy lényeges további feltételt ad: xe + xf + xg + xh + xi ≤ 2. Ezzel megcsonkítva az előző egyenletrendszer megoldáshalmazát MP(G)-t kapjuk. A továbbiakben két példát mutatunk, ami a lapszám (definiáló egyenlőtlenségek száma) és a csúcsok száma közötti nagyságrendi különbség lehetőségét mutatják. Példa. Az n dimenziós kocka (hiperkocka) Hn = {x ∈ Rn : 0 ≤ xi ≤ 1, i = 1, . . . , n} 2n darab egyenlőtlenség írja le a halmaz. Ezek mindegyike lényeges, azaz 2n darab lapja van az n-dimenziós kockának. 4-7
A csúcsok konvex burkaként való leírában: Hn = conv {v : v ∈ {0, 1}n } 2n darab csúcsra van szükségünk. Példa. Az előző példa dualizálható. Az n-dimenziós kocka duálisa az n-dimenziós oktaéder: X On = {x ∈ Rn : ǫi xi ≤ 1}, ǫi ∈{±}
2n darab lap határozza meg. Ezzel egy időben látható, hogy On = conv {±ei : i = 1, . . . , n} ekvivalens leíráshoz csak 2n csúcs kell.
4-8
