OPT Flashcards
Ucelova funkce
Takova, pro kterou hledame min/max na mnozine pripustnych reseni. Argmin/max.
Optimalni reseni patri do min(f)
Typy mnozin pripustnych reseni
Spojita - x je nespocetna mnozina vektoru jako mnozina reseni rovnic a nerovnic
Diskretni - konecna spocetna
Variacni pocet - realne funkce
Obecny tvar ulohy promspojitou optimalizaci
min f(x1, … xn)
Za podminek
g(x1,…xn) <= 0
h(x1, … xn) = 0
Kde x jsou realna
Minimalizuju funkci f vice promenncych za podminek omezujicich
min{f(x) | g(x) <= 0, h(x) = 0, x je real}
Linearnimobal mati e A je…
Jeji image, rng
Afinni kombinace vektoru x a skalaru alfa
Je to takova lin kombinace, kde suma vsech koeficientu =1
Afinni obal
Mnozina vsech afinnich kombinaci
Afinni podprostor
Je uzavreny na afinni kombinace, je to posunuty lin podprostor do nejakej bodu mimo tem lin podprostor
Kazdy aff podprostor je zaroven…
Lin podprostroem, kterz je posunuty do bud x mimo tem podprostor
Dimenze aff podprostoru je
Dimenze lin podprostoru ze ktereho vznikl aff podprosotr
Afinni podprostor je resenim…
Nejakej soustavy lin rovnic s matici Ax=b
Afinni zobrazeni
Zobrazeni platimsuperpozice a navic summa koeficientu je rovna 1
Je to pusunute zobrazeni, tedy je to lin zobrazeni, ke kteremu prictemu pevny vejtor b nejaky
f(x) = Ax + b, kde Ax je lin zobrazeni a b je posunuti.
Treba matice rotace plus b je affinni zobrazeni = zrotuju vektor a pak k nemu neci prictu
Ortogonalni matice
Je CTVERCOVA matice s ortonormalni i sloupci a plati pro ni
- UTU = I // skalarni soucin sam se sebou ale ortogonalni prvky takze bud daji 1 nebo 0
- Z toho plyne ze Ut = inverze(U)
- UUT = I // PLATI POUZE PRO CTVERCOVE, pro nectvercove matice ale s ortonomrmalnimi sloupci to neplati!!!
- UT je taky ortogonalni matice
Izometrie je co
Matice/zobrazeni, ktere zachovava velikosti vektoru a neovlivnuje skalarni soucin.
Treba rotace - nemeni delku rotovaneho vektoru
Ortogonalni matice je izometrie?
Ano, proto se s nimi dobre pocita, protoze zachovavaji pripadne chyby na vstupu a nemodifikujou je
QR rozklad
KAZDOU matici mxn jde rozlozit na ortogonalni matici Q mxm a regularni matici R mxn splnujici
A=QR
Redukovana verze - vynecham posledni nulove radky v R a tolik sloupcu v Q, pak Q je mxn ortogonalni, R je ctvercova trojhuelnikova
Pouze pro UZKOU MATICI s LN sloupci - existuje JEDNOZNACNY QR rozklad
Pouziti QR rozkladu 2
- Ortogonalizace - sloupce redukovaneho Q tvori ortonormalni bazi pro zadanou matici A
- Reseni lin rovnice
Ax=b
QRx=b
QTQRx=QTb
Rx = QTb
Ortogonalni doplnek podprosotru X
Mnozina takovych vektoru, ktere jsou kolme na X
Je tomzarovdn i lin. Podprostor ktery prochazi pocatkem a je to jediny spolecny bod pruniku s X
rng(A) ort. doplnek = ?
null(A) ort. doplnek = ?
rng(A) ort. doplnek = null(AT)
null(A) ort. doplnek = rng(AT)
Ortogonalni protjektor na obecny a ortonormalni podprostor U
Obecne
P = suma(uutx / ||u||)
V pripade otronormalni bazenje ale velikost u = 1, tedy projektor na ortonormalni podprostor je
P=UUT
- P je ctvercova
- P = P^2
- P = PT
Ortogonalni rejekce
Je to projekce na ortogonalni doplnek podprostoru
x = proj(x) + rej(x)
rej(x) = x - proj(x)
rej(x) = x - UUTx
rej(x) = x(I - UUT)
Obecny rejektor je
R = I - UUT
Vzdalenost dvou afinnich podprostoru
Je to bud velikost rejekce pricky jednim ze dvou podprostoru
Nebo velikost projekce pricky na kolmy podprostor tedy kolmy na oba zadane
Ortogonalni projektor na obecnou bazi
P = U(UTU)^-1UT
Odvozeno ze sumacniho vzorce pro projekci na obecny podprostor
Metoda nejmensich ctvercu
Pro preurcenou soustavu, kdy mame nejaka mereni a tvori vic rovnic nez je neznamych, trbe zavislost vahy na vysce
Nase data zaneseme do 2D grafu a chceme najit nejakou primku, na ktere by lezely vsechny nase body
Tzn soustava Ax=b musi mit reseni, kde A jsou koeficienty nasbirane prvni veliciny a b jsou nasbirane hodnoty druhe veliciny.
Preurcena soustava nema treba reseni, proto hledam priblizne ve smyslu, ze se snazim najit takove, ktere minimalizuje ctverec odchylky, tedy
min || Ax - b || ^2, tedy se snazim co nejvic priblizit nasbirane hodnoty b nejakym parametrum neznamych koeficientu x
Prevedu na tvar x=A(ATA)^-1ATb postupnym odvozovanim.
ATA je regularni pro A s LN sloupci, tedy to muzu invertovat.
Dostanu reseni SOUSTAVY NORMALNICH ROVNIC, ne puvodni soustavy, a,e toto reseni nejlepe odhaduje vysledek
Varianty reseni Ax=b
- Nema reseni - hledame priblizne, treba LSM
- Ma prave jedno reseni - pro A regularni, x=A-1b
- Ma nekon. reseni - A ma zavisla sloupce
Jak vypada zapis ulohy nejmensich ctvercu pro prékladani peimkou hodnot
f(y) = θ1 + θ2x // rovnice primky, kde hledam takove koeficienty theta 1 a 2, abych trefil primku, prochazejici namerenymi hodnotami
min||y-Aθ||^2, kde theta je realne,
A = matice koeficientu theta, tedy ZNAMYCH, y je vektor namerenych hodnot, theta je vektor neznamych
A[1 x1, 1 x2, 1 x3…], prvni sloupce je 1 protoze v rovnici primky ma u sebe 1.
Prokladat muzu jakoukoliv krivkou, jmenuje se ri regresni model, vyajdruje zavislost promennych x a y nejakou funkci
Reseni nedourcene soustavy lin rovnic s nejmensi normou
Pro treba sirokou matici mam reseni nekonecne mnoho, z nich chci vybrat takove x, ktery bude ze vsech nejmensi, tedy resim ulohu
minimalizuj kvadrat velikost x za podminky Ax=b
Pseudoinverze
Matice, ktera se chova jako inverzni pro singularni matici, mjze byt zleva nebo zprava, regularni matice ma oboje stejne tedy jednu urcitou inverzi
Treba v LSM je pouzita pseudoinverze
x=(ATA)^-1ATb, prepisu jako
x = A^+b, tedy matice A^+ je pseudoinverze
Spektralni rozklad
Je obycejny postup diagonalizace, tedy vlastni visla, vlastni podprostoru…
A = VLV^-1, kde L je matice lambd = vlastnich cisel
Diagonalizovat jde jen takovou matici, ktera je ctvercova a jeji geometricka nasobnost je stejna jako algebraicka
SPektralni rozklad SYMETRICKE MATICE
Tedy pro matici plati A = A^T
Plati - kazde vlastni cislo je realne, a matice vlastnich vektoru V je OTROGONALNI
Pro ortogonalni matici V plati, ze VV^T = I, protoze kdyz udelam transpozici, tak je to vlastne skalarni soucin radku sam se sebou a jelikoz jsou ortonormalni, tak jsou bud kolem = 0, nebo jednotkove = 1, tedy se mi vynuluje vsechno krome diagonaly. Tzn, ze V^T = V^-1, tak to muzu videt
Tedy:
A = VLV^-1 = VLV^T // kvuli ortogonallite V
Je to jakasi uprava nad vektorem, pak apliakce skalovani a navrat zpet
Pozitivne (semi)definitni matice
Takova ctvercova matice, ktera zachovava kladny skalarni soucin, tedy
xTAx >(=) 0.
- Matice je pozitivne (semi)definitni
- Vlastni cisla matice A jsou >(=) 0
- Vsechny vedouci subdeterminanty jsou >(=) 0
- Matice je symetricka (pouze symetricke matice zadavaji skalarni soucin)
Pozitivni definitnost znamena ze je to jako “druha” mocnina je kladna -> smer nahoru -> minimum zde ale, je to jako udoli
Obracene (ne)rovnosti pro negativne (semi)definitni
Negativni definitnost znamena ze jsme na kopecku -> pujdeme dolu -> zde je ale maximum, je to jako druha mocnina je zaporna -> smer dolu
Indefinitni - alespon jedna podminka porusena
sedlovy bod, jednim smere klesame, druhym stoupame, neni extrem zde
Kvadraticka forma
Homogenni polynom stupne dva tavu:
f(x) = xTAx = SumaSuma(aijxixj), kde A je ctvercova matice, ktera zadava skalarni soucin
Pro kazdou kvadratickou formu umime najit matici A
Definitnost kvadraticke formy se odviji podle definitnosti A
Extremy kvadraticke formy
Uvazujme kvadratickou formu f(x) = xTAx
- Je-li f pozitivne definitni, pak ma f v bode 0 ostre minimum
- Je-li f pozitivne semidefinitni, pak ma f v bode 0 minimum
- Je-li f indefinitni, pak f nema minimum ani maximum
Analogicky pro negativne definitni…
Diagonalizace kvadratice formy
Mejme kvadratickou formu
f(x) = xTAx, kde A je symetricka matice
Tu muzeme rozlozit na spektralni rozklad jako A = VLV^T
Kde V predstavuje prechod do jineho souradnicoveho systemu
Kdybychom pocitali v nem, tak mame prijemnejsi tvar a pocitame s diagonalni matici L.
Tedy prejdem do souradnicoveho systemu V jako:
x = Vy, tedy vektor x si vyjadrime jako lin. kombinace novych souradnic nejakeho vektory y.
dosadime:
f(x) = xTAx = (Vy)TA(Vy) = yTVT(VLV^T)Vy = yTLy,
tedy presel jsem do jineho systemu, kde kvadratickou formu pocitam s DIAGONALNI matici, tedy mi vypadnou vsechny smisene linearni cleny jako x1x2 a mam pouze kvadraticke y1^2, y2^2… (protoze u lin. clenu je 0 v matici)
Kvadraticka funkce
Je polynom f: R^2 -> R druheho stupen
f(x) = xTAx + bTx + c, kde A je symetricka
Kvadrika
Je to vrstevnice vysky 0 kvadraticke funkce, tj mnozina
{x | xTAx + bTx + c = 0}
Vrstevnice vysky 1 je elipsa natocena ve smeru vlastnich vektoru a delka poloos je 1/lambda^1/2
Rozdil v ulohach LSM a PCA
LSM - minimalizuju ctverce SVISLYCH vzdalenosti od prokaldane primky
PCA - minimalizuju ctverce KOLMYCH vzdalenosti od prokladane primky
PCA - minimalizuju pro
Prolozeni bodu linearnim podprostorem dimenze k<m
Tedy mame v rovine nejake rozmistene body (a1, …, an). Chci jimi prolozit takovy lin podprostor mensi dimenze (abych to treba mohl zakreslit, ze treba mam 4D vektory, ale chci si je zobrazit ve 3D, tedy hledam podprostor mensi dimenze), v tomto pripade primku, ktera by minimalizovala ctverce KOLMYCH vzdalenosti od hledane primky.
Hledam tedy takovy podprostor Y, na ktery budu delat projekce bodu a1,…an. Vzdalenost bodu ai od Y je rejekce(ai) na Y. Coz je stejny jako projekce na kolmy podprostor. Pokud bych zavedl podprostor X ktery je ortogonalnim doplnekm (kolmy na) Y, tak vzdalenost bodu ai od Y (rejekce bodu ai od Y) je rovna veliksot projekce ai na X (rejekce = projekce na kolmy doplnek).
Tedy obecnou ulohu:
“Najdi lin. podprostor Y, ktery by minimalizoval ctverce vzdalenosti bodu ai od Y, tedy rejekce ai Y”
Prevedu na:
“Najdi lin. podprostor X, ktery je kolmy na Y tak, ze minimalizuje ctverce projekci bodu ai od X”
Projektor na OBECNY podprostor je zadan jako:
P = A(ATA)^-1AT, pokud je ale A ortogonalni (tedy ma ortonormalni sloupce), tak ATA = I, tedy projektor na podprostor s ORTOGONALNI bazi je:
P = AAT
Tedy tady:
P = XXT, projekce bodu ai je tedy:
P(ai) = XXTai.
Velikost projekce je: ||XXTai||, ale jelikoz X je ortogonalni -> tak je izometrie -> takze nemeni velikost = ||XTai||
Tedy uloha zni jako:
- min Suma||XTai|| ^ 2, za podminky, X(mx(m-k) je ortog. doplnek Y(mxk)
SPECIALNI PRIPAD:
V pripade, ze prokladame podprostrem Y, ktery je o 1 dimenzi mensi nez je dimenze celeho prostoru (k = m-1), tak je uloha jednoducha, protoze matice X je tim padem rozmeru mX1, kde m je pocet radku. a uloha zni:
min Suma |xTai| ^2 = xTAATx (roznasobim) za podminky |x| = 1
Reseni:
1. Spektralni rozklad AAT = VLVT
2. Resenim ulohy je nejmensi vlastni cislo lambda1 matice AAT
3. Ortonormalni bazi hledaneho podprostoru X tvori ZBYTEK vlastnich vektoru v2,…vm (protoze hledam podprostor dimenze o 1 mensi, a zbytek vektoru uz je ortonormalni -> baze hledaneho podprostoru)
OBECNY PRIPAD PRO k<m:
min Suma||XTai|| ^ 2 prepisu na = min |X^TA|^2 = pomoci uprav o velikosti matic podle stopy ulohu prevedu na ekvivaletni tvar…:
min{tr(X^TAA^TX), kde X^TX = I, X je velikosti (mx(m-k))}
RESENI:
1. Spektralni rozklad AA^T = VLV^T
2. Seradim vlastni cisla vzestupne
3. Matice V se sklada z (v1, …, v(m-k), v(m-k+1), … vm)
4. Rozdelim ji na X a Y jako: X = [v, …, v(m-k)], Y=[v(m-k+1), … vm]
5. Optimalni reseni ulohy je k nejmensich vl. cisel = l1, …, lk a je to chyba prolozeni, kterou minimalizujeme
6. Ortonormalni bazi hledaneho podprostoru dimenze k tvori poslednich k vlastnich vektoru - neboli matice Y
Tedy vstupni matice ma rozmery treba A(4x150), tj 150 mereni o 4 neznamych, chci zvolit dimenzi k=2, abych to zobrazil do roviny. Vyberu proto podprostor s matici Y, ktera je tvorena (4-k) poslednimi vlastnimi vektory matice V ze spektralniho rozkladu AA^T.
EKVIVALENTNI ULOHA
Hledani nejblizsi matice nizsi hodnosti (tedy skoro stejne jako PCA, protoze v PCA jsem hledal matici, ktera mela nizsi dimenzi/hodnost a definovala mensi podprostoru kterym to prokladam, v tomto pripade delam to same - hledam matici nizsi hodnosti, ale tak, aby byla nejbliz vuci zadane matici)
Mam zadanou matici A=[a1, …, an], rank(A) = k. Hledam matici B takovou, ze:
min{|A-B|^2 | B ma n sloupcu, ale rank(B) <=k}. Upravami lze ukazat, ze ucelova funkce je totozna, jako uloha PCA. Tedy stejny postup:
1. Spektralni rozklad AA^T = VLV^T
2. Seradim vlastni cisla vzestupne
3. Matice V se sklada z (v1, …, v(m-k), v(m-k+1), … vm)
4. Rozdelim ji na X a Y jako: X = [v, …, v(m-k)], Y=[v(m-k+1), … vm]
5. Optimalni reseni ulohy je B=YY^TA, tedy je to jakasi projekce matice A na degenerovanejsi matici B
Courant-Fisherova veta o reseni ulohy:
min{xTBx | ||x|| = 1}
Tedy chci najit minimum kvadraticke formy s matici B na jednotkove sfere v prostoru R^m.
Resenim je nejmensi vlastni cislo lambda1 ze spektralniho rozkladu matice B.
Spektralni rozklad obecne radim vzestupne. Minima se nabyva tedy pro vlasatni vektor v1 a vlastni cislo lambda1.
Stopa matice
Soucet prvku na diagonale.
- tr(A+B) = tr(A) + tr(B)
- tr(xA) = x*tr(A)
- tr(AT) = tr(A)
- tr(AB) = tr(BA)
- tr(A) = Suma vlastnich cisel
- tr(P) = tr(UU^T) = tr(U^TU) = tr(I) = k, kde k je dimezne prostoru U
Skalarni soucin matic
<A:B> = tr(A^TB) = tr(AB^T) = tr(B^TA) = tr(BA^T)
tedy vsechny mozne kombinace plati
</A:B>
Norma matice (velikost)
Frobeniova norma matice:
||A|| = odmocnina(<A|A>) = odmocnina(tr(AA^T))
Vzdalenost dvou matic
|A-B|
Apliakce PCA
- Prolozeni bodou podprostorem nizsi dimenze, to same jako hledani matice nizsi hodnosti.
- Komprese namerenych hodnot
- Redukce dimenze
- Vizualizace dat
- Rozpoznavani trendu
SVD Rozklad matice A
Je jakysi zpusob diagonalizace LIBOVOLNE i nectvercove matice.
A(mxn) = USV^T, kde S je diagonalni se singluarnimi cisly
U(mxm), V(nxn) jsou ortogonalni s levymi/pravymi singularnimi vektory.
Singularni cislo - odmocnina z vlastniho cisla, radime SESTUPNE
Predstavuje to neco jako linearni transofmrace, aplikace skalovani, zase transformace - treba pootoceni souradnicovych os.
Plne SVD - uvedeno vyse, ale muze byt hodne singularnich cisel = 0, pokud je vynechame, tak urizneme tolik sloupcu v matici S:
A = U(mxr) S(rxr) V^T(nxr), kde r = rank(A) = pocet nenulovych singularnich cisel
Pokud je matice symetricka, pak jeji spektalni a SVD rozklad se…
- A je pozitivne semidefinitniv = rovnaji se
- Negativne semidefinitni = V ziskame vynasobenim matice V spektralniho rozkladu -1.
Ortogonalni matice ma vsechna vlastni/singualrni cisla rovna…
1
Nejblizsi matice nizsi hodnosti pomoci SVD rozkladu
Mejme obecnou matici A(mxn)=USV^T. Hledam takovou matici B, ktera ma nizsi rank nez A ale je k ni nejbliz podle Frobenivy normy. Tedy:
min{|A-B|^2 | B ma stejny rozmer, ale mensi hodnost nez rank(A) = k}
- Prevod na PCA ulohu a stopu
- Pomoci SVD rozkladu - spocitam B jako:
B = USrV^T, kde
Sr - redukovana matice S, kde jsem vynoval poslednich (n-k)-singularnich cisel - tedy odebral jsem “dimenze” navic
Priklad:
rank(A) = 10, hledam B tak, ze rank(B) = 8.
Udelam SVD rozklad:
A = USV^T,
B = USrV^T, kde v matici Sr jsem vynoval (10-8) = 2 poslednich nejmensich singularnich cisel, tedy odebral jsem “posledni nejmene dulezite singularni cisla” - nejmensi chyba, nizsi hodnost => hotovo
Cim vic odeberu sing. cisel (tedy cim mensi chci rank(B)) tim vic mi degeneruje B - treba nizsi kvalita komprese, tedy B mi dela jakousi kompresi dat z puvodni matici A, a cim je B degenerovanejsi (nizsi rank) tim je vetsi komprese.
Uloha PCA pomoci SVD rozkladu
Klasicky postup PCA:
- Spektralni rozklad AA^T…
Ale to muze byt vypocetne narocny, pouziju tedy SVD pouze z A:
A = USV^T.
Vlastni vektory matice AA^T jsou v matici U=[u1, …, un] a jsou serazeny podle singularnich cisel TEDY OPACNE NEZ PODLE VLASTNICH CISEL
Staci tedy vzit PRVNICH K SINGULARNICH VEKTORU matice U a je to baze hledaneho podprosotoru dimenze K.
Dva postupy:
1. klasicky PCA - serazeno vzestupne -> beru poslednich (m-k) VLASTNICH VEKTORU matice V z AA^T=VLV^T
- Pomoci SVD - serazeno sestupne -> beru prvnich k SINGULARNICH VEKTORU matice U z A=USV^T
Funkce f v bode x na mnozina X nabyva minima/lokalniho minima definice
Minimum - pokud f(x) <= f(x) pro Vsechna x z mnoziny X
Lokalni minimum - je to minimum na nejakem okoli epsilon
Volny/vazany extrem v bode x
Volny - pokud x je vnitrnim bodem mnoziny X (zadano nerovnosti)
Vazany - pokd x je hranicnim bodem mnoziny X (zadano rovnosti)
Podminky 1. a 2. radu pro lokalni extremy funkce f na mnozine X a vnitrni bod x
- Rad - pokud ma funkce f v bode x lok. extrem, pak 1. derivace v tomto bode = 0.
- Stacionarni bod - takovy, ve kterem je 1. derivace 0, ALE NEMUSI TO BYT EXTREM, je to bod podezrely z extremu - Rad - pokud je Hessova matice pozitivne (semi)definitni v bode x, pak x je (ne)ostre lokalni minimum.
- opacne pro maximum
- pokud je indefinitni - neni lok. extrem
Prehled extremu funkci
- Globalni vs. lokalni
Globalni extrem plati pro cely definicni obor.
Lokalni extrem plati pouze v okoli daneho bodu. - Ostry vs. neostry
Ostry extrem znamena striktni nerovnost, napr. mensi nebo vetsi.
Neostry extrem dovoluje rovnost, napr. mensi nebo rovno. - Volny vs. vazany
Volny extrem neni omezen zadnymi podminkami.
Vazany extrem je hledan na mnozine urcene rovnostmi nebo nerovnostmi.
3.1. Volny extrem
Hledam stacionarni body, kde je gradient nulovy.
Typ extrému urcuje Hessian, coz je matice druhych derivaci.
Pokud je Hessian pozitivne definitni, jde o lokalni minimum.
Pokud je Hessian negativne definitni, jde o lokalni maximum.
Pokud je Hessian indefinitni, jde o sedlovy bod.
Pokud je Hessian semidefinitni, je nutna dalsi analyza.
Nalezeny extrem je pouze lokalni, globalni extrem je zarucen pouze tehdy, pokud je funkce konvexni nebo pokud porovnam hodnoty na hranici definicniho oboru.
3.2. Vazany extrem
Pokud jsou podminky rovnosti, resim pomoci Lagrangeovych multiplikatoru.
Definuji Lagrangeovu funkci jako cilovou funkci doplnenou o nasobky podminek.
Resim podminku, kde je gradient cilove funkce roven nasobku gradientu podminek.
Pokud jsou podminky nerovnosti, pouziju Karush Kuhn Tucker podminky.
Lagrangeova metoda najde pouze lokalni extremy, globalitu musim overit stejne jako u volneho extremu, bud konvexitou funkce nebo porovnanim hodnot na hranici definicniho oboru.
Iteracni metody hledani volnych lokalnich extremu funkce f
- Iteracni
- Metoda nejvetsiho spadu (gradientni)
- Newtnova metoda
Iteracni metoda hledani volneych lok extremu
Hledame lokalni minimum funkice pomoci konstrukce posloupnosti bodu x0, x1, .. kde kazdy bod je krucek v sestupnym smeru, tedy ja furt klesam klkesa a klesam do nejakeho udoli, kde zustanu nebo ho prestrelim
Volim pocatecni bod x0, smer hledani v a delku kroku alfa >0
Tedy krok iterace vypada jako:
x(k+1) = x(k) + alfa*v
Sestupna metoda = f(x(k+1)) < f(x(k)), tedy kazdy dalsi bod je niz
Sestupny smer v = derivace ve smeru v je zaporna -> smernice dolu
Optimalni delku kroku odhadujeme
Metoda nejvetsiho spadu - gradientni metoda
Je to iteracni metoda, ktera jako smer iterace vyuziva gradient - tj smer nejvetsiho rustu, ale jde v opacnem smeru, tedy ve smeru nejvetsiho spadu.
x(k+1) = x(k) - alfa*grad(f(x(k)))
Sestupny smer v = -grad(f(x)), tedy v kazdem bode pocitam opacny gradient
Je to robustni metoda, ale muze konvergovat extremne pomalu, nebo dokonce i divergovat
Koeficient alfa je bud fixni, treba alfa = 0.1, nebo klesajici pro upresnovani kolem uz konecne hodnoty, abych to neprestrelil - alfa = 1/k, nebo adaptivni alfa
Algoritmus se zastavi kdyz je rezidual uz hodne maly
Newtnova metoda
Newtnuv smer je:
v = -f’‘(xk)^-1 * f’(xk)^T, tedy jinak
v = - prvni_der_v_xk / druha_der_v_xk, tedy zaporny pomer derivaci
Je to sestupny smer, pokud xk neni stacionarni (pak je v=0) a matice druhe derivace je pozitivne definitni (tedy pomer je zaporny a klesame)
Cista Newtnova metoda: alfa = 1
Je to nevyhodne metoda pro velka n (dimenze, muze byt drahe pocitat ivnerzi hessianu)
Je to ale rychla konvergence, ale nutno zacit od zacatku s dobrou aproximaci x0
Je zalozena na aproximaci Taylorovym polynomem prvniho stupne v kazdem bode - tedy v bode x0 udelam tecnu a kouknu, kde je = 0, pak v tomto bode na krivce zase udelam tecnu a tim se postupne budu priblizvovat k minimu
Gauss-Newtnova metoda
iterace:
x(k+1) = x(k) - g’(xk)^Tg(xk) / g’(xk)^Tg’(xk)
tedy je to podil skalarniho soucinu derivacenederivace / derivacederivace
Kde puvodni funkce je f a plati:
f’(x) = 2g(x)^Tg’(x)
Levenberg-Marquardtova metoda
Je to GN metoda, kam pridame regularizacni parametr mi >0 pro plynulou kombinaci mez GN metodou (male mi) a gradientni metodou (velke mi)
iterace:
x(k+1) = x(k) - g’(xk)^Tg(xk) / g’(xk)^Tg’(xk) + mi*I, kde I jednot. matice
Pokud je vektor tecny k mnozine X, pak je derivace v tomto smeru v tomto bode …
0, protoze je to smer kolmy na gradient, tedy grad(f)*v = 0
Naopak to plati taky:
Pokud je grad(f)*v = 0, pak v je tecny vektor (je to smerovy vektor tecne roviny ke grafu funkce f)
Protoze pokud se pohybuju ve smeru kolmem na grad - zustavam na 0, nemenim funkcni hodnoty - vrstevnice
Pokud jdu ve smeru gradientu - nejvetsi narust - normala grafu funkce f
Tecny prostor ke grafu funkce f
Tecny prostor definuju jako mnozinu vektoru takovych, ze derivace v jejich smerech je nulova, tedy kolme na gradient
grad(f)*vi = 0, pro vsechny vektory vi z tecneho prostoru
Zaroven je to vlatne mnozina takovych vektoru, ktere jsou resenim homogenni rovnice grad(f) = 0,
tedy tecny prostor je ker(grad(f)) - jadro
Ortogonalni prostor - normalovy prostor, kolmy prostor v bode x grafu funkce f je ortogonalni doplnek tecneho prostoru, je dan span(grad(f))
Vyuziti LP
Optimalizace produkcni vyroby - minimalizace nakladu dualne s maximalizaci zisku
- optimalni prirazeni, toky v siti
- aproximace, regrese
Obecna uloha LP
Linearni programovani - historicky nazev, jde o minimalizaci/maximalizaci linearni funkce za linearnich podminek-omezeni pripustnych reseni, ktere tvori jako pruniky primek konvexni polyedry jejich vrcholy nebo cele hrany tvori hledana optima zadanych uloh.
Obecny tvar je:
min c^Tx
z.p. Ax >= b,
x >= 0, real
Neboli:
min {c^Tx | Ax >= b, x je real >=0} Pripousti to i opacne nerovnosti
Rovnicovy-normalni-standardni tvar ulohy LP
Omezeni je zadano rovnostmi misto nerovnosti (nerovnosti zadavaji nadrovinu, rovnosti pouze primky).
Tedy uloha je ve tvaru:
min c^Tx (pouze min!!!)
z.p. Ax = b, x>=0 real.
Kazdou obecne zadanou ulohu LP lze prevest na …
Normalni-rovnicovy tvar.
Postup:
0. Prevedu na minimalizaci jako -(ucelova funkce)
1. Do nerovnosti pridam slackovou promennou z, kterou prictu/odectu a tim ziskam rovnost.
2. Neomezene x puvodni rozdelim na x+ a x-, obe jsou nezaporna a x je jejich souctem. Slackova promenna je >= 0.
Dva typicke tvary LP
- Maximalizace zisku z vyrabenych produktu x
- c je cena za kus (za prodej)
- A udava spotrebu materialu i pri vyrobe produktu j (naklady materialni)
- b je disponovane mnozstvi materialu
- Tedy chci maximalizovat cenu pri disponovanem mnozstvi materialu
max c^Tx z.p. Ax <= b, x>=0
// max prodejni cenu tak, abych se vesel do limitu materialu b - Minimalizace nakladu pri mixovani surovin y
- b je cena za kus (za nakup)
- A udava mnozstvi latky j v surovine i
- c udava pozadovane mnozstvi jednotlivych latek v mixu
- Tedy chci minimalizovat naklady pri sestaveni potrebneho mixu
- treba jidelni uloha
min b^Ty z.p. A^Ty >= c, y>=0
// min kupni cenu tak, abych pokryl pozadovane mnozstvi latek c
Jsou ekvivalentni - dualni, mohu je prepisovat mezi sebou:
max c^Tx min b^Ty
z.p. Ax <= b z.p. A^Ty >= c // A musim transponovat
x >= 0 y >= 0
Minimax uloha
Uloha lienarniho programovani, kde ucelova funkce neni zadana jako linearni kombinace, ale jako jina optimalizacni uloha z linearnich funkci treba, treba max(neco)
min max(c^Tx + d)
z.p. Ax >= b,
x >= 0
Tedy minimalizuj maximum z linearnich funkci za omezujicich podminek
Vnitrni ulohu mohu schovat do pomocne promenne z, ktera mi nahradi maximum:
min z
z.p. z >= c^Tx + d
Ax >= b,
x >= 0
z je real
3 druhy norem
- Norma jednotkova: ||x|| = |x1| + … |xn| soucet slozek vektoru x
- Eukleidova: odmocnina(suma ctvercu slozek vektoru x) - standardni
- Nekonecna: max{|x1|, …, |xn|} maximum ze slozek vektoru x
Priblizne reseni preurcene soustavy v ruznych normach
Hledame reseni ulohy preurcene soustavy ve smyslu nejmensi normy
min ||Ax-b||
Muzu si zvolit ruzne druhy norem:
1. Jednotkova: lze formulovat pomoci LP jako:
min Suma(yi) pro i=1…m
z.p. -y <= a^Tx - b <= y,
y je real
neboli:
min{1^Ty | -y<=a^Tx-b<=y, y je real}
- Eukleidovska - metoda nejmensich ctvercu
- Nekonecna norma: lze formulovat pomoci LP jako:
min y
z.p. -y <= a^Tx - b <= y,
y je real
Mnozinu priopustnych reseni uloh LP tvori…
Konvexni mnoziny
Konvexni mnozina
Mnozina vsech konvexnich kombinaci vektoru x,y, treba.
Tedy je to takova mnozina, kde pro kazde dva body palti, ze i usecka mezi nimi lezi v teto mnozine (nesmi nic koukat ven, zadne vchlipeniny, pouze vyrustky)
Mnozina M je konvexni, pokud pro libovolne dva body x,y plati, ze jejich konvexni kombinace lezi v mnozine M.
Tedy jejich lin. kombinace, ale suma koeficientu u a1+…+an = 1 A ZAROVEN ai >= 0
Minimum ulohy LP pokud existuje, tak se nachazi v …
Ve vrcholu konvexniho polyedru ktery je zadan omezujicimi rovnostmi
Simplexova metoda prochazi tyto vrcholy
Mnozina {x | a^Tx >= b} je geometricky…
Uzavreny poloprostor, tedy je to reseni nejake linearni nerovnice, tedy je to afinni podprostor (v pripade rovnosti) a vsechna x nad tim, tedy to tvori nadrovinu v prostoru.
Konvexni polyedr je prunik konecne mnoha …
poloprostoru.
Tedy pokud dam vicero poloprostoru jako omezujici podminky, tak mi vyhradi nejaky prunik vsech a to je pripustny prostor reseni.
{x | Ax >= b}, kde prava cast mi koduje soustavu lienarnich nerovnic, kde kazda ma jako svoje reseni svoji vlastni nadrovinu, ktere spojim dohromady
Dimenze konv. polyedru je dimenze afinniho obalu, neboli je to dimenze utvaru, ktery je vymezen jeho hranami
Extremalni bod konvexni mnozny
Je spicka/hrot teto mnoziny, tedy bod je extramlni, kdyz nelezi na usecce nejakych dvou bodu.
Definice: kdyz bod x je extremalni, pokud pro libovolne body x1, x2 plati, ze x = 1/2(x1 + x2) => pak x1=x2,
tedy rika to, ze bod x je extremalni, pokud kdyz lezi v pulce usecky dvou bodu, tak ty body jsou totozne a jde o ten samy extremalni bod x
Ne vsechny konvexni mnoziny maji extremalni body - otevreny interval
Nektere konv. mnoziny jsou definovany extr. body - trojuhelnik
Jak ze zadaneo mnoziny konvexniho polyedru sestavit matici?
{(x,y) z R^2 | x>=0, y>=0, x+y>=1}
Muzu si zakreslit omezujici podminky a tim uvidim konvexni polyedr.
Abych ziskal matici A omezujicich nerovnic, poskladam jejich koeficienty do sloupcu.
Vidim, ze mam 2 promenne - 2 sloupce a 3 nerovnice - 3 radky.
Do matice A poskladam KOEFICIENTY u neznamych, tedy:
A: b: prave strany nerovnic
[1 0] [0]
[0 1] [0]
[1 1], [1]
Extremalni body jsou pruseciky zadanych rovnic, tedy mohu zkouset hledat takove podmnoziny radku matice A a b, abych nasel reseni, ktera patri do zadane mnoziny.
Tedy podle jiste vety existuje nejaka vybrana podmnozina radku matice A a prislusne radky b tak, ze je to sosutava rovnic, jejichz resenim jsou pruseciky, ktere patri do zadane mnoziny => jsou to EXTREMALNI body.
Ale tento postup je pomaly, protoze pocet extremalnich bodu je exponencilani k prostoru - musel bych prochazet extremne moc ruznych kombinaci pruseciku…
Operna nadrovina
Je to nadrovina H = {x| a^Tx = b} takova, ze ma neprazdny prunik s konvexni mnozinou X, ale pouze tak, ze X je cele POUZE V JEDNE polorovine ohledne nadroviny.
Tedy moje konvexni mnozina X se jednim bodem (nebo celou hranou) se dotyka primky H, ale pouze jako tecna, nesmi ji prochazet jako secna, tedy X je pouze z jedne strany vuci H a ne z obou
V operne nadrovine se nabyva minima funkce f(x) na konvexni mnozine X
Stena polyedru X
Je mnozina pruniku X s jeho opernou nadrovinou - tedy misto, kde se dotyka polyedr se svoji opernou nadrovinou H.
Podle dimenzce pruniku rozlisujeme:
1. Vrchol (dimenze 0) - spicka, extremalni bod
2. Hrana (dimenze 1) - X cely “sedi” na operne nadrovine
3. Faseta (dimenze X -1) - “stena” standardni, tedy hrana ale vyssi dimenze, tedy X na ni lezi cely, ale ve vyssi dimenzi hrana
Polyedr X ma alespon jeden extremalni bod p.t.k…
Neobsahuje primku. Tedy je nejak omezenej ve vsech smerech - tedy kdybych zvolil nejaky smer tak bych se v nem mohl pohybovat do nekonecna a furt lezel v X - neomezenost - nenarazim na nejakou jinou stenu atd - neni vrchol - neni extremalni bod…
Kdy umime vyresit ulohu LP?
- Konvexni polyedr vymezeny omezujicimi nerovnostmi neobsahuje primku (tedy je hranatej, omezenej)
- Funkce c^Tx ma na X minimum
- Umime efektivne prochazet vrcholy - Simplexova metoda
Konvexni plyedr Ax=b, x>=0 ma extremalni bod?
Ano, protoze neobsahuje primku diky podmince nezapornosti x, tedy jsem vymezil pouze polovinu prostoru, tim padem tam neexistuje primka, ktera by nenarazila na nejake linearni omezeni
Simplexovy algoritmus
Umi efektivne prochazet po hranach vrcholy konv. polyedru vymezeneho omezujicimi podminmkami tak, aby ucelova funkce behem toho nerostla.
Pracuje ale s rovnicovym tvarem LP a s matici A, ktera ma podmonozinu sloupcu jako LN bazi a prave starny omezeni b musi byt >= 0. Iterace je prechod mezi sousednimi bazovymi resenimi.
Priklad:
max x1+2x2+4x4
z.p.
x1 <= 2
x1 + x2 + 2x3 <= 4
3x2 +4x3 <= 6
- Prevod na rovnicovy tvar:
min -x1 - 2x2 -4x4
zp
x1 + u1 = 2
x1 + x2 + 2x3 + u2 = 4
3x2 +4x3 + u3 = 6
xi, ui >= 0 pro i=1,2,3 - Sestavim tabulku kde prvni radek je ucelova funkce, koncici d, kde v tomto pripade d=0. Pod tim je matice A soustavy spolu s pravou stranou b. Pod to zapisu bazove reseni, kde k bazovym vektorum zapisu koeficienty b a u zbytku je 0.
- Inicializace tabulky
1 0 0 1 0 0 | 2
1 1 2 0 1 0 | 4 // matice A
0 3 4 0 0 1 | 6
——————-
0 0 0 2 4 6 | // x - vektor baz. reseni (koeficienty b)
- Kroky algoritmu:
- vyber PRVNI NEJMENSI cenu - sloupec
- v tomto sloupci vyber PRVNI radek pivotu tak, aby pivot byl KLADNY a podil bi/ai byl mensi nez vsechny ostatni podobne podily v tomto sloupci
- nastav tento pivot na 1 (vydel cely radek jeho cislem)
- vynuluj vsecno nad/pod pivotem (proved ekvivaletni upravy tak, aby pivot byl jediny jednotkovy cislo ve sloupci, vcetne cen)
- updatni radek x podle novych sloupcu baze - je nastav na nove koeficienty b, zbytek vynuluj. - Algoritmus konci kdyz uz vsechny ceny jsou nezaporne - jsme v optimu a hodnotu vyctu v pravem hornim rohu a vektor reseni je x.
- NEBO uloha je neomezena a to poznam tak, ze nemohu zvolit pivota, protoze cely “pivotni sloupec” je zaporny - neomezena uloha - Pokud budu vybirat vzdy prvni moznost - zamezim cykleni
- V pripade maximalizace jen obratim logicky postup - vybiram nejvetsi ceny a optimum pak musim vynasobit -1.
Dualni uloha LP
Mejme zadanou ulohu LP
min c^Tx
z.p. Ax >= b,
x >= 0
K teto uloze (primalu) mohu vytvorit ekvivalentni dualni ulohy, ktera mi bude rikat totez a budu tvaru:
max b^Ty
z.p. y >= 0,
A^Ty <= c
Dual dualu je puvodni primal, tedy jsou anvzajem dualni a postup prevodu je identicky pro oba pripady ALE ROVNOSTI SE DELAJI RUZNE
min -> max ==> zachovam horni nerovnosti, obratim spodni
max -> min ==> obratim horni nerovnosti, zachovam horni…
Prevod primalu na dual priklad:
min 2x1 - 3x3 + x4
z.p.
2x1 - x2 + x3 + 2x4 = 6
-x1 + 2x2 - 3x3 <= 5
x1 - x2 - x3 - 3x4 >= 0
x1 >= 0
x2 je real
x3 >= 0
x4 <=0
Obecna kucharka:
min -> max
c^Tx -> b^Ty
Suma (ax) = b -> y je real (pripad rovnosti)
Suma (ax) >= b -> y >= 0 (nerovnost se zachova)
Suma (ax) <= b -> y <= 0 (nerovnost se zachova)
x je real -> Suma (ya) = c (pripad realne promenne)
x >= 0 -> Suma (ya) <= c (nerovnost se OBRATI)
x <= 0 -> Suma (ya) >= c (nerovnost se OBRATI)
Tedy koeficienty ucelove funkce primaru se stanou pravymi strany omezeni dualu a naopak. Matici primaru transponuju a mam matici dualu ktere se maji rovnat koeficientum ucelove funkce primaru. Ucelova funkce dualu ma koeficienty pravy strany primaru.
Tedy konkretne:
1. Ucelovou funkci dualu sestav z koeficientu pravych stran primaru a nove promenne y=(y1, …, yn)
2. Pro kazdou lienarni podminku zaved novou promennou yi, zachovej nerovnost (vuci 0 ale) a v pripade rovnosti je y real.
3. Vem matici A primaru a transponuj ji - toto je matice omezeni dualu.
4. Novy vektor pravych stran dualu je roven koeficientum c v primaru (navzajem se tedy prohodi koeficienty ucelovych funkci a omezujciich podminek)
5. Pro kazde omezeni JEDNOTLIVYCH promennych xi zaved novou linearni podminku pres matici A^T a OBRAT NEROVNOSTI (vuci novym pravym stranam) a v pripade x je real udelej = 0.
Tedy dual k zadanemu prikladu je:
puvodni matice A =
[2 -1 1 2]
[-1 2 -3 0]
[1 -1 -1 -3]
Matice dualu je tedy A^T:
[2 -1 1]
[-1 2 -1]
[1 -3 -1]
[2 0 -3]
max 6y1 + 5y2
z.p.
y1 je real (pripad rovnosti)
y2 <= 0 (zachovam nerovnost ale vuci 0)
y3 >= 0 (zachovam nerovnost ale vuci 0)
2y1 - y2 + y3 <= 2 (prava strana je c1 v primaru, obracena nerovnosti, A^T)
-y1 + 2y2 - y3 = 0 (prava strana je c2 v primaru, obracena nerovnosti, A^T)
y1 - y2 - y3 <= -3 (prava strana je c3 v primaru, obracena nerovnosti, A^T)
2y1 + 0y2 - 3y3 >= 1 (prava strana je c4 v primaru, obracena nerovnosti)
Veta o slabe dualite
Pro kazde pripustne reseni x primaru a kazde pripustne reseni y dualu plati:
- c^Tx >= b^Ty // tedy primar shora omezuje dual a naopak
- Pokud c^Tx* = b^Ty, potom jsou x a y* optimalni reseni.
Reseni najdu tak, ze spoctu treba x a skalarne ho dosadim do zadane ucelove funkce. To same udelam pro y a pokud se vysledky rovnaji, tak je to hodnota ucelove funkce a x* a y* jsou optimalni reseni svych uloh
Veta o silne dualite
Stejna jako slaba dualita, akorat druha podminka je ekvivalence, tedy:
c^Tx = b^Ty p.t.k. x a y jsou optimalni reseni svych uloh
Neboli veta:
Primarni uloha ma optimalni reseni x p.t.k. dualni uloha ma optimalni reseni y. Pak c^Tx = b^Ty
Dualni uloha tedy nejen zdola omezuje primarni, ale dokonce ma i stejnout hodnoty spolecneho optima
Veta o komplementarite
Nech x je pripusten resnei primaru a y je pripustne reseni dualu. ROvnost c^Tx = b^Tx plati p.t.k. plati tyto podminky:
- Suma (ax) = b NEBO y = 0
- x = 0 NEBO Suma (ya) = c
Tedy alespon jeden “radek” je aktivni, tedy po spocitani reseni x a y je dosadim do “hornich” podminek a musi nastat alespon jedna ostra rovnost v kazdem radku. Nemuze platit, ze obe jsou neostre
