Ólķnuleg bestun (09.10.66)

Vikublaš 7, 8/4/2002

(vikublaš 6 var handskrifaš og dreift i tima)

Efni sem fariš hefur veriš yfir s.l. vikur: Kaflar ķ Bertsekas: 3.1-3.3, 4.1-4.2, 5.1 (ekki žó fylgt nįkvęmlega, sumt skiliš eftir til heimalesturs og żmislegt tekiš fyrir utan bókar (ašallega Bazaraa) eša a.m.k. meš öšrum efnistökum en ķ bókinni). Nįnari lżsingu į helstu efnisatrišum er aš finna hér į eftir.

Undirstöšuatriši stęršfręšilegrar fiskifręši kynnt, ž.e. ašferšir viš stofnmat og mat į afrakstursgetu stofna.

Skuggagildi śtskżrš meš Taylor nįlgunum fyrir m=1 og fariš ķ setningu 3.2.2 sem lķtur į breytta lįgmörkunarverkefniš,


min</SUB>x   f(x) (1)
m.t.t.   h(x)=u (2)

og tengir frumfalliš, p, sem lżsir lausn annars verkefnis,


$\displaystyle p(\mathbf{u}):=\textrm{inf} \{f(\mathbf{x}):\mathbf{x}\in \mathbf{R}^n, h(\mathbf{x})=\mathbf{u}\},$     (3)

viš skuggagildin $\boldsymbol{\lambda^*}$ meš žvķ aš lķta į lausnirnar, x(u) og $\boldsymbol{\lambda}(\mathbf{u})$ į breytta verkefninu, svo aš

p(u):=f(x(u).     (4)

Ef skilyrši setningarinnar eru uppfyllt gildir aš


$\displaystyle \nabla p(\mathbf{u})=-\boldsymbol{\lambda} (\mathbf{u})$     (5)

og žarmeš aš $\nabla p(\mathbf{0})=
-\boldsymbol{\lambda} ^*$.

Lokiš aš mestu viš Lagrange margfaldara meš žvķ aš fara ķ ójöfnuskoršurnar (kafli 3.3), sérķlagi setningar 3.3.1 (Karush-Kuhn-Tucker) og 3.3.2 (nęgjanleg skilyrši)

Nykurverkefni tekin fyrir: Hefšbundiš nykurverkefni lķnulegrar bestunar rifjaš upp og almenna nykurverkefniš skilgreint eins og ķ eftirfarandi.

Lįtum frumverkefniš vera


$\displaystyle \textrm{min}_{\mathbf{x}\in \mathbf{X}}$   f(x) (6)
m.t.t.   h(x)=0 (7)
og   $\displaystyle \mathbf{g}(\mathbf{x})\leq \mathbf{0},$ (8)

svo aš Lagrange falliš er skilgreint meš


$\displaystyle L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}):= f(\mathbf{x...
...mbol{\lambda}'\mathbf{h}(\mathbf{x}) + \boldsymbol{\mu}' \mathbf{g}(\mathbf{x})$     (9)

og nykurfalliš er


$\displaystyle q(\boldsymbol{\lambda},\boldsymbol{\mu}) := \textrm{inf}_{\mathbf{x}\in \mathbf{X}} L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})$     (10)

Žį er nykurverkefniš skilgreint meš


min   $\displaystyle q(\boldsymbol{\lambda},\boldsymbol{\mu})$ (11)
m.t.t.   $\displaystyle \boldsymbol{\lambda}\in \mathbf{R}^m$ (12)
og   $\displaystyle \boldsymbol{\mu}\geq \mathbf{0},$ (13)

Sżnt var aš almenna nykurverkefniš veršur aš nykurverkefninu viš lķnulega bestunarverkefniš ef h og g eru lķnuleg. Einnig fundiš nykurverkefni kvašratiska bestunarverkefnisins.

Fjallaš var nokkuš ķtarlega um tengslin milli frum- og nykurverkefnianna (aš mestu utan viš bók, en sjį žó kafla 5.1, bls 477...). Fariš nįkvęmlega ķ dęmi um tengslin.

Nykursetningar: Fariš hefur veriš yfir helstu nykursetningar, sjį blaš/vefsķšu.

Frumfalliš: Haldiš var įfram meš frumfalliš og teiknuš żmis lausnarmengi m.m., sérstaklega mišaš viš ójöfnuskoršur.

Erfša/žróunaralgrķm: Dęmi hafa veriš gefin um notkun erfša/žróunaralgrķma viš bestun.

Efni nęstu tķma:

Reiknięfingar, dęmi um lausnarašferšir, upprifjun, fjölstofnalikan, notkun frumfalls og nykurfalls.

Dęmi fyrir nęstu dęmatķma verša valin af eftirfarandi lista (ekki eru sett fyrir skiladęmi enda verkefni 3 ķ gangi).

Athugiš aš nśmer dęma vķsa til nżjustu śtgįfu Bertsekas!

1.5: 1

3.1: 1, 7

3.2: 1, 4

3.3: 1 (einfölduš śtgįfa, meš föstum stušlum)

4.2: 1

5.1: 1, 2, 3

Višbętur:

1: Leysiš verkefni 2 ķ höndunum meš Lagrange ašferš, liš fyrir liš, og finniš frumfalliš og nykurfalliš eftir žvķ sem mögulegt er. Snśiš fallinu g viš ef meš žarf, til aš sś skorša verši virk. Athugiš aš ekki er sjįlfgefiš aš unnt sé aš leysa allar jöfnurnar nįkvęmlega. Žetta var aš hluta ķ verkefni 2 en viš gerum žetta lķka ķ tķma.

2: Lķtiš į eftirfarandi dęmi:


minx,y   (x-1)2 + (y-2)2 +xy (14)
m.t.t.   $\displaystyle 0 \leq x \leq 1$ (15)
og   x + y = 1 (16)

sem mį rita žannig


min</SUB>x   f(x) (17)
m.t.t.   h(x)=0 (18)
og   $\displaystyle \mathbf{g}(\mathbf{x})\leq \mathbf{0},$ (19)

ef viš skilgreinum


f(x) =f(x,y) = (x-1)2 + (y-2)2 +xy (20)
h(x) =h(x,y) = x+y-1 (21)
$\displaystyle \mathbf{g}(\mathbf{x}) = \left [ \begin{array}{l}
g_1 (x,y) \\
g_2 (x,y)
\end{array}\right ]$ = $\displaystyle \left [ \begin{array}{l}
-x \\
x-1
\end{array}\right ]$ (22)

2.1 Notiš Lagrange falliš til aš leysa dęmiš. Finniš $x^*, y^*,
\lambda^*, \mu_1^* og \mu_2^*$.

2.2 Notiš ķsetningu til aš leysa dęmiš og fį sama lausnarpunkt, x*, y*.

2.3 Finniš frumfalliš, p(u, v1, v2) og reikniš p(0,0,0) įsamt $\nabla p(0,0,0)$. Geriš grein fyrir tengslum žessara nišurstašna viš svör ķ 2.1.

2.4 Finniš nykurfalliš, $q(\lambda, \mu_1, \mu_2)$.

2.5 Leysiš nykurverkefniš og geriš grein fyrir tengslum žeirra nišurstašna viš lausnir frumverkefnisins.

2.6 Breytiš verkefninu meš žvķ aš fella nišur jöfnuskoršuna og nota eingöngu žį ójöfnuskoršu, sem var virk ķ lausninni. Teikniš mengiš $G=\{(g(x,y),f(x,y)):(x,y) \in \mathbf{R}^2\}$ (mišaš viš nżtt g) og leysiš nżja verkefniš meš žvķ aš lesa lausnina śt śr myndinni.



Gunnar Stefansson: gunnar@hi.is