最优化理论与算法(21)

Ú3. E|¢ "¦) 5 §| 2f(x(k))d= f(x(k)) d(k)"Ú4.?1 ‘|¢"¦minf(x(k)+td(k)) `Ú ½ ÉÚ tk"

t≥0

Ú5.(½# S“:"-x(k+1)=x(k)+tkd(k),k:=k+1§=Ú2"

53.4.53(½Ú tk §Q ^ `Ú § ^ ÉÚ § ¦ 3~êδ>0§¦

D=f(x(k)) f(x(k)+tkd(k))≥δ( f(x(k))Td(k))2/ d(k) 2,

f(x(k))Td(k)<0 §3 ½^ e(3.4.3)¤á"

e¡ïá{ZNewton{ ÛÂñ5½n"

½n3.4.6 f:Rn→R1 ëY ¿… —ৠ2f(x) k.§^{ZNewton{¦)(UNP)§Ù¥ε=0§¿… 3~êδ>0§¦ (3.4.3)é k¤á§

£1¤e )k S x(1),···,x(k)§K f(x(k))=0"£2¤e )Ã S x(1),x(2),···§Klim f(x(k)) =0"

k→∞

(3.4.3)

y²£1¤ â { ª O^ = "

£2¤ k=0,1,···" âf(x) —à § 3η>0§¦ 2f(x) A

λn( 2f(x))≥η,

Ïdé?¿ z∈Rn§d

zT 2f(x(k))z≥η z 2,

¿…d(k)

(3.4.4)

x∈Rn,

1= 2f(x(k)) f(x(k))´eü §S {f((k))}Âñ"é?¿ z∈Rn§d(3.4.4) §

η z 2≤zT 2f(x(k))z≤ z 2f(x(k))z ,

=

2f(x(k))z ≥η z .

3þª¥ z=d(k)

1

= 2f(x(k)) f(x(k))§K

f(x(k)) ≥η d(k) .

Ó § â 2f(x) k. § 3M>0§¦ 2f(x) <M§dd

f(x

(k)

(3.4.5)

) ≤ f(x

2(k)

1

2(k)

f(x(k)) ≤M d(k) ,) f(x)