—牛頓法求解無約束問題

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

2、式，有時會使函數(shù)值上升。三、算例分析算例1、取初始點初步分析，目標函數(shù)為二次函數(shù)，經(jīng)過一次迭代即可得到。編制程序及計算結(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(df,x1,x2,x0(1,1),x0(2,1);

3、G1=subs(G,x1,x2,x0(1,1),x0(2,1); k=k+1; end; kx0結(jié)果：k = 1x0 = 4 8正如分析所得，迭代一次即可得出極小值點。算例2、取初始點目標函數(shù)為三維函數(shù)，且都高于二次，海塞矩陣存在且不為常數(shù)，迭代次數(shù)大于一次。編制程序和計算結(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(df,x1,x2,x3,x0(1,1),x0(2,1),x0(3,

4、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é)果分析牛頓迭代法主要利用二階梯度進行求解，在針對上述算例進行計算后，主要存在以下問題：1) 牛頓法所求極小值點是局部極小值點，對于取初值有一定要求。為了克服這一困難，引入了阻尼牛頓法以得到大范圍收斂特性。2) 對于二次的目標函數(shù)，其海塞矩陣為常數(shù)陣，迭代一次即可得到結(jié)果，收斂速度較快。3) 對于某些方程，例如，迭代點的海塞矩陣為奇異，則