第四次和dfp算法上二次連續(xù)可微函數(shù)

一、Newton f(x)fx)是Rn即fxC2Rnx(0 x(1 x(k x(k1 并用Qx)的極值點(diǎn)近似fx的極值點(diǎn)。f(x)Q(x)f(x(k))f(x(k))T(x1(xx(k))T2f(x(k))(xx(k))f(x(k))gT(xx(k))1(xx(k))TG(xx(k)k其 gkf(x(k)

,G k

2fxk)2令令 k若Hesse矩陣Gk正定，即 0，則G1k

x(k1)x(k

(k(k

x(k1)x(k

k d(k)G1 1step1x0)，精度0k:step2.計(jì)算gkf( )和Gk

(k(k f(k Gk

x(k1 x(k

G1 step3.由方程組Qx)gkGkxxk0解出xk1)step4||fxk1||x*xk1k:k1,轉(zhuǎn)step2例 f(x)2x24x22x x0)(2,1)T解：fx4x12x2,8x22x10 f(x(0))[6,40

1 2f(x)

G1

8 8

1 x(1)x(

G1g 1

7(2,1)T 14 1 7 f(x(k1))f(x(k)) k k問題一：如何使 f(x(k1))f(x(k))在 x(k1 x(k

G1

x(k d(k當(dāng)G0fx(kTdkfx(kTG1g gTG1g0, 當(dāng)Gk0dk) kx(k1)x(k)d(kkk:f(x(kk

d(k))minf(x(k

fx(k1fx(k (變尺度法k kx(k x(k

G1f(x(k) 中，如果我們k(kk(k x(k

f( x(k x(k)kHkf(x(k)HkIkHkG1NewtonkkHK近似G1擬NewtonkHk迭

Hk）H

HkHk(Hk

Hk

Hk

HkGk如何保證Hk0和Hk G1k如何確定Hk？擬Newtonk擬Newton條件Hk Gk分析G1需滿足的條件，并利 此條件確定 記g(x)f(x gkf(x(k)),Gkf2(x(k)),f(x)f(x(k1))f(x(k1))T(xx(k1)1(xx(k1))T2f(x(k1))(xx(k1))g(x)g(x(k1))2f(x(k1))(xx(k1)代入xxk gk

(kGk1(

(k1) G1( g)x(k1)x(k) (kHk1(g(k

(k1) gk

(kx記

gk

gk,

x(k

Hk1yksk擬Newton條件或擬Newton4、擬Newton算法0Step 給定初始點(diǎn)x(0H精度0k:0step2.計(jì)算搜索方向d(k)Hfx(kkstep

令x(k x(k

kd(k)其中fx(k)d(kminfx(kk

dkyesstopNostep5(kstep5.令gk f( )

gkf(x(k)) (k f( f( gk1 gkk xk1)xk)k Hk1HkHk計(jì)算Hk1使得Hk1滿足擬Newton或擬Newton方程：Hk1yk sk。令k:kstep2.Hk的確定三、DFP1959年Davidon1963年Fletcher和Powell Hk？Hk1HkHkHkkukuTv k，kR,uk，vk根據(jù)擬NewtonHk1yksk(HkkukuTvvT) 即：kukuT vvT 令uuTy 令 vvTy

kykuksk

uTyk1 vkHkyk vTyk uksk

, k TvkHkyk k T Hk的DFP的校 s yyTHk1

sT yT 性質(zhì)：若H00，則k,有Hk0將變尺度法的第5step 按照DFP的校 s yyTHk1

sT yT 計(jì)算Hk:k1,轉(zhuǎn)step例請(qǐng)用DFPminfxx24

2x

取H0I

fx)2x18x2

1第一步DFP算法與梯度法相同

12 18f(x(

0f(x(0)))minf(x(0)

(12)24(18)2

x(1)

0s0

x(0)yf(x(1))f(x(0))

按照DFP的校

sT yyT

0.03149H1H0 0 0