Ólķnuleg bestun (09.10.66)

Vikublaš 1, 11/1/2002

Įętluš efnistök

Efnisröš ķ Bertsekas:

Įherslan veršur į k. 1 og k. 3-4. Kafla 2 veršur sleppt aš mestu en žó ekki öllu leyti.

Aš auki veriš fariš ķ ašferšir utan bókar, ž.e. ašferšir til aš finna vķšfešm lįggildi og ašferšir sem ekki krefjast afleišureikninga. Žaš efni er aš hluta til tekiš śr Bazaraa.

Efni sem fariš hefur veriš yfir ķ vikunni: 1.1 ķ Bertsekas og nokkrar skilgreiningar į lįgmörkunarašferšum, m.a. hefšbundin stigulsašferš:

(i) k:=0, x0 gefiš

(ii) Lįtum $d^k = - \nabla f (x^k)$ og skilgreinum $g(\alpha)=f(x^k + \alpha d^k)$.

(iii) Finnum $\alpha ^ k$ sem gefur $g(\alpha^k)=min_\alpha g(\alpha)$

(iv) Setjum $x^{k+1}=x^k + \alpha^k d^k$.

(v) Lįtum $k \gets k+1$ og nęst (ii).

Efni til nęsta dęmatķma: 1.1 ķ Bertsekas

Dęmi fyrir nęsta dęmatķma verša valin af eftirfarandi lista.

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

1.1: 1, 3, 11, 12

Skiladęmi. Skilist fyrir lokun VRII, 16/1:

Lķtiš į falliš $f(x_1,x_2)=x_1+x_1^2+\frac{x_2^2}{2}$.

(a) Skrifiš žetta sem $f(x)=\frac{1}{2} x'Qx+b'x$

(b) Finniš $\nabla f (x)$ og $\nabla^2 f(x)$ fyrir öll x (meš diffrun - ekki nota almenna setningu um kvašratķsk föll nema til stušnings).

(c) Finniš hugsanleg lįggildi f meš žvķ aš leysa $\nabla f (x)=0$.

(d) Sannfęriš ykkur um aš žetta sé lįggildi.

(e) Notiš ofangreinda stigulašferš til aš nįlgast lįggildiš handvirkt meš žvķ aš byrja meš x=(0,1). Athugiš aš hér er unnt aš nota nįkvęma lķnuleit, ž.e. leysa beint $g(\alpha)=0$. Lįtiš nęgja fįar ķtranir.



Gunnar Stefansson: gunnar@hi.is