lnuleg bestun (09.10.66). Vikubla 5, 13/3/2002

Verkefni 2 (gildir 10% af einkunn). Vinni verkefni 2-3 saman. Skilist 25. mars.

Lti fllin

f(x,y)=ln(4x2+2y2+4xy-2y-8x+5) + x,

h(x,y)= x+y,

$g(x,y)= x-xy-\frac{5}{2}$

og k(x,y,z)=g(x,y)-z2.

Lgmrkunarverkefni er a finna min f(x,y) m.t.t. h(x,y)=0 og $g(x,y) \geq 0$, en finna skal fyrst skora lggildi, lggildi m.t.t. $g(x,y) \geq 0$, aeins m.t.t. h(x,y)=0 og a lokum me bum skorum, .e. leysa skal eftirfarandi dmi:

(1) min f(x,y)

(2) min f(x,y) m.t.t. h(x,y)=0 (byrjunargildi (-1,0), lti $S=\{(x,y)':y\leq 0\}$).

(3) min f(x,y) m.t.t. $g(x,y) \geq 0$

(4) min f(x,y) m.t.t. h(x,y)=0 og $g(x,y) \geq 0$.

Setji upp MATLAB fll til a finna skora lggildi. Eftirfarandi skal skoa sem tillgu a uppsetningu. Muni a prfa lausnirnar me v a reyna a leysa hvert verkefni lka beint `` hndunum'', en a er flestum tilvikum gerlegt.

I. Fyrir (1) m nota t.d. BFGS. Prfi lka a finna rttu lausnina pappr og teikna jafnharlnur fallsins f samt skorunum.

II. Fyrir (2) m nota trekaa lgmrkun fallanna

\begin{displaymath}
L_{c^k}(x,y,\lambda^k)=f(x,y)+\lambda^k h(x,y)+\frac{c^k}{2}\vert\vert h(x,y)\vert\vert^2
\end{displaymath} (1)

me t.d. BFGS, og f annig runu af lausnum, xk. hverri slkri trun (k) m htta egar t.d. $\vert\vert\nabla_\mathbf{x}
L_{c^k}(\mathbf{x},\lambda^k)\vert\vert<\epsilon _k$ ar sem $\epsilon_k$ er einhver runa af tlum, sem stefna nll fr hgri og x=(x,y). Noti t.d. $c^{k+1}:=\beta
c^k$ me t.d. $\beta \in [5,10]$, c0=lti, $\lambda^{k+1}:=\lambda^k+c^kh(\mathbf{x}^k)$.

III. Fyrir (3) m bta vi z, annig a lgmrkun er yfir $\mathbf{x}=(x,y,z)\in\mathbf{R}^3$ og v uppfra me:

$c^{k+1}:=\beta
c^k$ og $\lambda^{k+1}:=\lambda^k+c^kk(\mathbf{x}^k)$

Athugi a skoran g ``snr ekki eins'' og oftast fyrirlestrum, og af eim skum er k skilgreint aeins ruvsi.

IV. sasta hlutanum m san setja saman r II og III - en athugi a $\mathbf{\lambda}$ verur nna tveggja staka vigur og uppfrslan getur veri annig:


\begin{displaymath}
\mathbf{\lambda}^{k+1}:=\mathbf{\lambda}^k+c^k \left [ \begi...
...}{l}
h (\mathbf{x}^k) \\
k (\mathbf{x}^k)
\end{array}\right ]
\end{displaymath} (2)

(en m gera heldur betur me v a nota uppfrslujfnur bls 406 Bertsekas, sem byggja v a leysa z-lgmrkunina ur en vandamli er sett upp, sbr bls 395-396).

Einnig m nota msar Newton aferir (t.d. 4.44 bls 412 og uppfrslu xk bls 413 ea jfnur 4.118-119 bls 459) en til ess arf a nota Hessian fylki Lc, sem arf ekki ef notast er vi BFGS afer innri lgmrkuninni.


Gunnar Stefansson: gunnar@hi.is