Matematické Fórum

ježek · 13. 01. 2019 22:30 — Editoval ježek (13. 01. 2019 22:31)

Můžu poprosit o kontrolu příkladu 15 b)? Prý v bodě $[3,2]$ není splněna KKT podmínka stacionarity. Jsem zmatený. Díky za vysvětlení.
//forum.matweb.cz/upload3/img/2019-01/14828_IMG_20181227_194005.jpg

jardofpr · 15. 01. 2019 19:25

ahoj ↑ ježek:

mne sa tiež zdá že je splnená, takže ak zistíš prečo by nemala byť rád sa poučím

ježek · 15. 01. 2019 19:30 — Editoval ježek (15. 01. 2019 19:32)

Ty parciální derivace podle lambd nejsou nutná podmínka stacionarity. Zatím z důvodu mně ne zcela známého, neb to nechápu. :) Ale nutnou podmínkou stacionarity jsou v tomhle případě jenom parciální derivace podle x a y. Takže stacionarita v tomhle případě platí, ale já jsem do KKT podmínek v dané úloze zahrnul ty parciální derivace podle lambd, ale ty tam nepatří. Proto žel pro mne nula bodů. :)

jardofpr · 15. 01. 2019 20:40

↑ ježek:

okej, tak to je niečo iné ako nesplnená podmienka stacionarity

ono štandardne sa uvádza Karush-Kuhn-Tucker stacionarita ako
gradient Lagrangiánu podľa premenných pôvodnej funkcie položený rovný nulovému vektoru
t.j. ako píšeš v tvojom prípade je to x,y

derivácia Lagrangiánu podľa multiplikátorov položená rovná nule ti neprinesie nič iné ako pôvodné väzby

napr. ak by si mal rovnosti miesto nerovností v tvojom príklade t.j.
$h_1(x,y)=x-3=0$ , $h_2(x,y)=y-2=0$ tak derivácie podľa $\lambda$ rovné nule sú vlastne oddelené
a schované pod primárnu prípustnosť

to isté sa teoreticky deje aj v prípade nerovností, aj keď sa tam píše $3-x\leq 0$ a $2-y\leq 0$ ,
lebo ak tá nerovnosť bude ostrá pre optimum tak príslušný multiplikátor bude rovný nule
(lebo takéto obmedzenie potom neovplyvní výsledok)

takže reálne keď sa hľadá stacionárny bod nemá zmysel derivovať podľa multiplikátorov

ježek · 16. 01. 2019 15:49

Díky. Ta lambda u dané vazby je tedy nenulová právě tehdy, když vazebná podmínka není aktivní? To znamená když mi v optimu příslušný zdroj přebývá? A já jsem vlastně tím požadavkem na konstantní lambdy stanovil jakousi podmínku konstantního přebytku daného zdroje?

jardofpr · 16. 01. 2019 16:22

↑ ježek:

ježek napsal(a):
Ta lambda u dané vazby je tedy nenulová právě tehdy, když vazebná podmínka není aktivní?

Presne tak, ale pozor, výrok platí len pre väzby v tvare nerovností, a nielen nenulové, ale kladné.

ježek napsal(a):
To znamená když mi v optimu příslušný zdroj přebývá? A já jsem vlastně tím požadavkem na konstantní lambdy stanovil jakousi podmínku konstantního přebytku daného zdroje?

Nie som si istý čo myslíš zdrojom, neviem akú používate terminológiu a presný kontext pre ten príklad.
Znamená to asi toľko, že pokiaľ je nerovnosť-väzba neaktívna, t.j. ostrá nerovnosť tak hľadať optimum
bez tejto podmienky je to isté ako hľadať optimum s touto podmienkou, t.j. nemá vplyv.
Keď máš extrém pôvodnej funkcie vnútri útvaru ktorý nerovnosť ohraničuje, tak je jedno že má niekde hranicu, lebo ten extrém tam zostane a to ohraničenie ho nezmení. Ale keď je to na kraji, tam už to zaváži.

To ti hovorí aj podmienka komplementarity. Ak je napr. $-x+3=0$ tak je väzba aktívna.
Ak nie je aktívna, je $\lambda=0$ .

ježek · 19. 01. 2019 13:53

Tak jestli to chápu dobře: multiplikátor musí být nezáporný, pokud je vazba ve formě nerovnosti. Pokud je vazba ve formě rovnosti, tak multiplikátor může nabývat libovolné hodnoty.

Zdrojem mám na mysli třeba suroviny ve výrobním závodě.

jardofpr · 20. 01. 2019 11:30

↑ ježek:

ježek napsal(a):
Tak jestli to chápu dobře: multiplikátor musí být nezáporný, pokud je vazba ve formě nerovnosti. Pokud je vazba ve formě rovnosti, tak multiplikátor může nabývat libovolné hodnoty.

Áno, nasledujem ale pritom konvenciu že Lagrangián má tvar
$L(\bar{x},\bar{\lambda},\bar{\mu}) = f(\bar{x}) + \sum_{i=1}^m \lambda_i h_i(\bar{x}) + \sum_{i=1}^{n}\mu_ig_i(\bar{x})$ pre problém $\min_{\bar{x}}{f(\bar{x})}\,;\,h_i(\bar{x})=0\,,\,i=1,\dots,m\,;\,g_i(\bar{x})\leq 0\,,\,i=1,\dots,n$

a tvar

$L(\bar{x},\bar{\lambda},\bar{\mu}) = f(\bar{x}) + \sum_{i=1}^m \lambda_i h_i(\bar{x}) - \sum_{i=1}^{n}\mu_ig_i(\bar{x})$ pre problém $\max_{\bar{x}}{f(\bar{x})}\,;\,h_i(\bar{x})=0\,,\,i=1,\dots,m\,;\,g_i(\bar{x})\leq 0\,,\,i=1,\dots,n$

derivácia Lagrangiánu podľa $\bar{x}$ je stacionárna podmienka (a iba toto sa ráta ako stacionárna podmienka)
lebo udáva kde má Lagrangián stacionárne body vzhľadom na priestorovú premennú $\bar{x}$ keď dovolíme manipuláciu s parametrami $\bar{\lambda}$ a $\bar{\mu}$
toto je dôležité si uvedomiť že Lagrangián aj pôvodná funkcia majú tú istú priestorovú premennú
Lagrangián má len navyše nejaké parametre

teraz, v prípade rovností $h_i(\bar{x})$ , derivácia Lagrangiánu podľa parametra $\bar{\lambda}$
obmedzí množinu na ktorej hľadáme optimum na množinu ktorá presne spĺňa rovnice $h_i(\bar{x})=0$

keby bola v tvojom príklade miesto nerovností jedna rovnosť, napr. $x=3$ , tak bez nej máš problém hľadania maxima $f(x)$ na celom priestore $\mathbb{R}^2$ ,
s ňou hľadáš maximum pôvodnej funkcie na priamke $x=3$

teraz ty tam máš dve nerovnosti ale položením priamo derivácie Lagrangiánu podľa lámbd rovné nule
si k nim pristúpil ako k rovnostiam, t.j. obmedzil si hľadanie optima funkcie na jediný bod $[x,y]=[3,2]$
výsledok ti nahodou vyšiel lebo optimum je zrovna v ňom

ježek · 22. 01. 2019 11:03 — Editoval ježek (22. 01. 2019 11:07)

Už to chápu. Prostě jsem hledal maximum účelové funkce jenom na tom průsečíku. Ne na celé přípustné množině. Kdybych měl maximalizovat třeba $z=1-(x-4)^2-(y-3)^2$ za stejných vazebných podmínek, tak je globální maximum v bodě $[4;3]$ a parciální derivace podle multiplikátorů by v bodě $[4;3]$ nevyšly nulové, přestože taková účelová funkce má v bodě $[4;3]$ maximum na přípustné množině. Tím pádem nulové parciální derivace podle multiplikátorů nemůžou být součástí KKT podmínek.

jardofpr · 22. 01. 2019 12:23

↑ ježek:

presne tak, to je čo som sa snažil naznačiť, aj si si sám vymyslel pekný príklad

len jeden komentár:

ježek napsal(a):
Tím pádem nulové parciální derivace podle multiplikátorů nemůžou být součástí KKT podmínek.

Presnejšie je že parciálne derivácie podľa multiplikátoru nie sú súčasťou podmienky stacionarity pri určovaní KKT podmienok všeobecne. Oni tam určitým spôsobom vystupujú, ale v primárnej prípustnosti.

Pri označení ktoré som použil vyššie by sa dalo napísať napríklad pre minimalizačný Lagrangián že

$\frac{\partial L}{\partial \lambda_i} = h_i(\bar{x}) = 0 \\ \frac{\partial L}{\partial \mu_i} = g_i(\bar{x})\leq 0$

čo je to isté ako primárna prípustnosť. Dôležité je že nerovnosť musí ostať nerovnosťou, ako si ukázal na príklade že si pochopil.

ježek · 22. 01. 2019 13:33 — Editoval ježek (22. 01. 2019 13:35)

Díky. Ještě k těm vazbám: pokud bych položil, že multiplikátor $\mu$ musí být nezáporný, tak musím nerovnosti nulovat tak, aby $g_{i}(x)\le0$ ? Pokud bych je vynuloval tak, že $g_{i}(x)\ge 0$ , tak multiplikátor $\mu$ by měl být naopak nekladný? Alespoň mi to tak vždycky vycházelo a teď jsem si na to vzpomněl, když jsi mne nahoře upozornil na to, že ten můj výrok platí jen za standardních předpokladů, z nichž jedním je právě $g_{i}(x)\le 0$ .

jardofpr · 22. 01. 2019 14:23

ježek napsal(a):
Díky. Ještě k těm vazbám: pokud bych položil, že multiplikátor $\mu$ musí být nezáporný, tak musím nerovnosti nulovat tak, aby $g_{i}(x)\le0$ ? Pokud bych je vynuloval tak, že $g_{i}(x)\ge 0$ , tak multiplikátor $\mu$ by měl být naopak nekladný?

presne

zober si napríklad tvoju úlohu, s označením čo používam je $f(x,y)=1-x^2-y^2$ , $g_1(x,y)=3-x\leq 0$ , $g_2(x,y)=2-y\leq 0$

toto na začiatku "nevieme", že obe väzby sú aktívne keďže optimum je v bode $(3,2)$

ale v optimu $(X,Y)$ so všetkými väzbami aktívnymi je $\nabla L(X,Y,\lambda_1,\lambda_2)=0$

a teda pre maximalizačný Lagrangián $\nabla f(X,Y) = \lambda_1\nabla g_1(X,Y) + \lambda_2\nabla g_2(X,Y)$

čo dáva $(-2X,-2Y) = (-\lambda_1,0) + (0,-\lambda_2)$ tu už je vidno že tvoje lambdy sú kladné a nie je to náhoda

ako píšeš, ak by si obrátil nerovnosti na opačné zmenia smer gradienty väzieb a teda aj znamienka pre lambdy sa obrátia