第四章—牛頓法求解無約束問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上牛頓法求解無約束多維優(yōu)化問題一、基本思想牛頓法是一種線性化的方法，其基本思想是將非線性方程逐步歸結(jié)為某種顯性線性方程來求解。在鄰域內(nèi)用一個(gè)二次函數(shù)來近似代替原目標(biāo)函數(shù)，并將的極小值點(diǎn)作為對目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)。經(jīng)多次迭代，使之逼近目標(biāo)函數(shù)的極小值點(diǎn)。二、數(shù)學(xué)模型將目標(biāo)函數(shù)作二階泰勒展開，設(shè)為的極小值點(diǎn)這就是多元函數(shù)求極值的牛頓法迭代公式。對于二次函數(shù)，海塞矩陣是一個(gè)常矩陣，其中各元素均為常數(shù)，因此，無論從任何點(diǎn)出發(fā)，只需一步就可以找到極小值點(diǎn)。從牛頓法迭代公式的推導(dǎo)過程中可以看到，迭代點(diǎn)的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對于非二次

2、函數(shù)，如果采用上述牛頓迭公式，有時(shí)會(huì)使函數(shù)值上升。三、算例分析算例1、取初始點(diǎn)初步分析，目標(biāo)函數(shù)為二次函數(shù)，經(jīng)過一次迭代即可得到。編制程序及計(jì)算結(jié)果如下：syms x1 x2;f=(x1-4)2+(x2-8)2;v=x1,x2;df=jacobian(f,v); df=df.' G=jacobian(df,v); e = 1e-12;x0=1,1'g1=subs(df,x1,x2,x0(1,1),x0(2,1);G1=subs(G,x1,x2,x0(1,1),x0(2,1);k=0;while(norm(g1)>e) p=-G1g1; x0=x0+p; g1=subs(d

3、f,x1,x2,x0(1,1),x0(2,1); G1=subs(G,x1,x2,x0(1,1),x0(2,1); k=k+1; end; kx0結(jié)果：k = 1x0 = 4 8正如分析所得，迭代一次即可得出極小值點(diǎn)。算例2、取初始點(diǎn)目標(biāo)函數(shù)為三維函數(shù)，且都高于二次，海塞矩陣存在且不為常數(shù)，迭代次數(shù)大于一次。編制程序和計(jì)算結(jié)果如下：syms x1 x2 x3;f=(x1-10)2+(x2-8)4+(x3+5)3; v=x1,x2,x3;df=jacobian(f,v); df=df.' G=jacobian(df,v); e = 1e-12;x0=-1,4,1'g1=subs(

4、df,x1,x2,x3,x0(1,1),x0(2,1),x0(3,1);G1=subs(G,x1,x2,x3,x0(1,1),x0(2,1),x0(3,1);k=0;while(norm(g1)>e) p=-G1g1; x0=x0+p; g1=subs(df,x1,x2,x3,x0(1,1),x0(2,1),x0(3,1); G1=subs(G,x1,x2,x3,x0(1,1),x0(2,1),x0(3,1); k=k+1; end; kx0結(jié)果：k = 28x0 = 10.0000 8.0000 -5.0000四、結(jié)果分析牛頓迭代法主要利用二階梯度進(jìn)行求解，在針對上述算例進(jìn)行計(jì)算后，主要存在以下問題：1) 牛頓法所求極小值點(diǎn)是局部極小值點(diǎn)，對于取初值有一定要求。為了克服這一困難，引入了阻尼牛頓法以得到大范圍收斂特性。2) 對于二次的目標(biāo)函數(shù)，其海塞矩陣為常數(shù)陣，迭代一次即可得到結(jié)果，收斂速度較快。3) 對于某些方程，例如，迭代點(diǎn)的海塞矩陣為奇異，則無法求逆矩陣