OPT Flashcards

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

Takova ctvercova matice, ktera zachovava kladny skalarni soucin, tedy xTAx >(=) 0. 1. Matice je pozitivne (semi)definitni 2. Vlastni cisla matice A jsou >(=) 0 3. Vsechny vedouci subdeterminanty jsou >(=) 0 4. 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

Answer 7

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

Answer 8

Uvazujme kvadratickou formu f(x) = xTAx 1. Je-li f pozitivne definitni, pak ma f v bode 0 ostre minimum 2. Je-li f pozitivne semidefinitni, pak ma f v bode 0 minimum 3. Je-li f indefinitni, pak f nema minimum ani maximum Analogicky pro negativne definitni...

Answer 9

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)

Answer 10

Je polynom f: R^2 -> R druheho stupen f(x) = xTAx + bTx + c, kde A je symetricka

Answer 11

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

Answer 12

LSM - minimalizuju ctverce SVISLYCH vzdalenosti od prokaldane primky PCA - minimalizuju ctverce KOLMYCH vzdalenosti od prokladane primky

Answer 13

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

Answer 14

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.

Answer 15

Soucet prvku na diagonale. 1. tr(A+B) = tr(A) + tr(B) 2. tr(xA) = x*tr(A) 3. tr(AT) = tr(A) 4. tr(AB) = tr(BA) 5. tr(A) = Suma vlastnich cisel 6. tr(P) = tr(UU^T) = tr(U^TU) = tr(I) = k, kde k je dimezne prostoru U

Answer 16

= tr(A^TB) = tr(AB^T) = tr(B^TA) = tr(BA^T) tedy vsechny mozne kombinace plati

Answer 17

Frobeniova norma matice: ||A|| = odmocnina() = odmocnina(tr(AA^T))

Answer 18

1. Prolozeni bodou podprostorem nizsi dimenze, to same jako hledani matice nizsi hodnosti. 2. Komprese namerenych hodnot 3. Redukce dimenze 4. Vizualizace dat 5. Rozpoznavani trendu

Answer 19

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

Answer 20

1. A je pozitivne semidefinitniv = rovnaji se 2. Negativne semidefinitni = V ziskame vynasobenim matice V spektralniho rozkladu -1.

Answer 21

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} 1. Prevod na PCA ulohu a stopu - 1. metoda nebo druha metoda: 2. 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.

Answer 22

Klasicky postup PCA: 1. 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 2. Pomoci SVD - serazeno sestupne -> beru prvnich k SINGULARNICH VEKTORU matice U z A=USV^T

Answer 23

Minimum - pokud f(x) <= f(x`) pro Vsechna x` z mnoziny X Lokalni minimum - je to minimum na nejakem okoli epsilon

Answer 24

Volny - pokud x je vnitrnim bodem mnoziny X (zadano nerovnosti) Vazany - pokd x je hranicnim bodem mnoziny X (zadano rovnosti)

Answer 25

1. 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 2. 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

Answer 26

1. Globalni vs. lokalni Globalni extrem plati pro cely definicni obor. Lokalni extrem plati pouze v okoli daneho bodu. 2. Ostry vs. neostry Ostry extrem znamena striktni nerovnost, napr. mensi nebo vetsi. Neostry extrem dovoluje rovnost, napr. mensi nebo rovno. 3. 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.

Answer 27

1. Iteracni 2. Metoda nejvetsiho spadu (gradientni) 3. Newtnova metoda

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

iterace: x(k+1) = x(k) - g'(xk)^T*g(xk) / g'(xk)^T*g'(xk) tedy je to podil skalarniho soucinu derivace*nederivace / derivace*derivace Kde puvodni funkce je f a plati: f'(x) = 2g(x)^Tg'(x)

Answer 32

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)^T*g(xk) / g'(xk)^T*g'(xk) + mi*I, kde I jednot. matice

Answer 33

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

Answer 34

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))

Answer 35

Optimalizace produkcni vyroby - minimalizace nakladu dualne s maximalizaci zisku - optimalni prirazeni, toky v siti - aproximace, regrese

Answer 36

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

Answer 37

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.

Answer 38

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.

Answer 39

1. 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 2. 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

Answer 40

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

Answer 41

1. Norma jednotkova: ||x|| = |x1| + ... |xn| soucet slozek vektoru x 2. Eukleidova: odmocnina(suma ctvercu slozek vektoru x) - standardni 3. Nekonecna: max{|x1|, ..., |xn|} maximum ze slozek vektoru x

Answer 42

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} 2. Eukleidovska - metoda nejmensich ctvercu 3. Nekonecna norma: lze formulovat pomoci LP jako: min y z.p. -y <= a^Tx - b <= y, y je real

Answer 43

Konvexni mnoziny

Answer 44

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

Answer 45

Ve vrcholu konvexniho polyedru ktery je zadan omezujicimi rovnostmi Simplexova metoda prochazi tyto vrcholy

Answer 46

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.

Answer 47

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

Answer 48

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

Answer 49

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...

Answer 50

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

Answer 51

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

Answer 52

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...

Answer 53

1. Konvexni polyedr vymezeny omezujicimi nerovnostmi neobsahuje primku (tedy je hranatej, omezenej) 2. Funkce c^Tx ma na X minimum 3. Umime efektivne prochazet vrcholy - Simplexova metoda

Answer 54

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

Answer 55

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 1. 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 2. 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. 3. Inicializace tabulky -1 -2 -4 0 0 0 |0 //c^Tx, radek cen ------------------- 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) 4. 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. 5. 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 6. Pokud budu vybirat vzdy prvni moznost - zamezim cykleni 7. V pripade maximalizace jen obratim logicky postup - vybiram nejvetsi ceny a optimum pak musim vynasobit -1.

Answer 56

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...

Answer 57

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)

Answer 58

Pro kazde pripustne reseni x primaru a kazde pripustne reseni y dualu plati: 1. c^Tx >= b^Ty // tedy primar shora omezuje dual a naopak 2. 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

Answer 59

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

Answer 60

Nech x je pripusten resnei primaru a y je pripustne reseni dualu. ROvnost c^Tx = b^Tx plati p.t.k. plati tyto podminky: 1. Suma (ax) = b NEBO y = 0 2. 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

Answer 61

Je stejne zadana jako spojita LP, akroat promenne nejsou real ale Z. Tedy nakreslim si vymezenou plochu podle podminek ale ted pripustna reseni jsou POUZE konkretni celociselne body v rovine, tedy 0,1,2,3... a ne spojite real hodnoty. Takze Je mohu proste rovnou dosadit a porovnat. Relaxace - vypusteni podminky celociselnosti, tedy misto konkretnich bodu mam pripustnych reseni nekonecne mnoho - prevod z celociselneho LP na spojity pripad klasicky. Optima obou uloh jsou podobne - treba real = 11.4 a celociselne = 11. Tedy jsou si blizko a mohu pres jedno se dostad do druhehoale zaokrouhleni obecene nemusi fungovat, protoze bud to bude mimo optimum, nebo reseni je nepripusten - tedy lezi vne omezeni Relaxovana uloha je z prinicpu vetsi nez celociselna (protoze pripousti vic reseni), tak pokud puvodni uloha je pripustna, pak i relaxovana je taky pripustna. Optimalni hodnota relaxace je dolnim odhadem puvodni hodnoty Mezera celociselnost - rozdil opt. hondoty celociselneh a relaxovane ulohy Priklady - spise obsahem magisterskeho predmetu kombinatoricka optimalizace - obchodni cestujici, toky v sitich, batoh, rovzrhovani ... obycejne LP ale za podminky x je Z, prirazovaci ulohy - jak ucitelum priradit predmety aby bylo nejvetsi skore, nejmensi vrcholove pokryti - kolik nejmin potrebujem umistit hlidacu do vrcholu grauf, aby kazda hrana byla monitorava Je to NP tezky problem

Answer 62

Funkce je konvexni, kdyz pro libovolne dva body x,y plati, ze bod mezi nimi z = alfa*x + (1-alfa)*y //tedy jejich konvexni kombinace ma mensi nebo rovnou funkcni hodnotu, nez jeho usecka spojujici x a y. Tedy udelam usecku mezi x a y a porovnam, zda tato usecka lezi nad grafem funkce, tedy jestli jeji realna hodnota je vetsi nez funkcni hodnota. Tedy overuju pomoci vzroce. Treba exponeniala, kvadraticka forma, max(slozek vektoru), jakakoliv norma...

Answer 63

Epigraf funkce f je mnozina bodu, ktera je nad grafem funkce. Konvexita epigrafu je stejna jako konvexita jeho funkce. Tedy je to: {(x,y) | f(x) <= y}

Answer 64

Je definovana jako kontura (vrstevnice) akorat s nerovnosti misto rovnosti: Tedy vezmu vrstevnici vysky y a pridam k tomu vsechny body ktere jsou niz. Tedy: {x | f(x) <= y} Tedy je to mnozina bodu mensich nebo rovnych nejake konstantni hodnote y.

Answer 65

konvexni mnozina

Answer 66

konvexni mnozina

Answer 67

Pokud h je slozeno z g*f, kde f je konvexni a g je konvexni NEKLESAJICI pak je i h konvexni Pokud h=g(Ax+b) kde g je konvexni a vnitrni funkce je afinni, pak i h je konvexni

Answer 68

Konvexitu max(aff funkce) max(normy) max(LP)

Answer 69

Je uloha ve tvaru MINIMALIZUJ f(x) za podminky x je v X, kde f je konvexni funkce a X je konvexni mnozina. Dulezite je minimum, maximum ne vzdy je jednoduse najit

Answer 70

Podle jiste vety konvexni funkce na konvexni mnozine ma kazde lokalni minum na X zaroven i globalnim. Tedy staci hledat lok. minimum a prohlasim ho za globalni

Answer 71

Maticove: min{f(x) | g(x) <= 0, h(x) = 0}, kde g jsou konvexni, h jsou afinni tedy je konvexni funkce na konvexni mnozine omezene jako prunik konvenich subkontur a afinniho podprostoru neboli min f(x1, ..., xn) z.p. gi(x1, ..., xn) <= 0, hi(x1, ..., xn) = 0, x1, ..., xn jsou real

Answer 72

1. Linearni programovani - specialni pripad konvexni optimalizace, kde f,g,h jsou vsechny linearni (afinni) 2. Kvadraticke programovani - ucelova funkce je konvexni kvadraticka, omezeni jsou afinni 3. Kvadraticke programovani s kvadratickymi omezenimi - ucelova funkce i g jsou kvadraticke konvexni, h je afinni 5. Programovani na kuzelu druheho radu

Answer 73

Funkce f je konvexni, pokud je diferencovatelna a splnuje podminku: v kazdem bode definicniho oboru je tecna rovina grafu funkce f pod grafem. Tedy pokud ke grafu funcke delam tecny, tak jsou pod grafem (tecna vyjadrena pomoci derivace v tomto bode). y = f(a) + f'(x)(x-a) Podminka 2./ radu: Funkce f je konvexni p.t.k jeji Hessova matice pozitivne semidefinitni.