第四章—牛顿法求解无约束问题.doc

牛顿法求解无约束多维优化问题一、基本思想牛顿法是一种线性化的方法，其基本思想是将非线性方程f(x)€0逐步归结为某种显性线性方程来求解在xk邻域内用一个二次函数申(x)来近似代替原目标函数，并将申(x)的极小值点作为对目标函数f(x)求优的下一个迭代点xk,1经多次迭代，使之逼近目标函数f(x)的极小值点二、数学模型将目标函数f(x)作二阶泰勒展开,f(x)…申(x)€f(xk)+Vf(xk)T(x一xk)+f(x一xk)TV2f(xk)(x一xk)设xk+1为申(x)的极小值点(xk+1)€0Vf(xk)+V2f(xk)(xk+1一xk)=0xk+1€xk-[V2f(xk)]„1Vf(xk)(k€0,1,2,3)这就是多元函数求极值的牛顿法迭代公式对于二次函数，海塞矩阵H是一个常矩阵，其中各元素土均为常数•因此，无论从任何点出发，只需一步就可以找到极小值点从牛顿法迭代公式的推导过程中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念因此对于非二次函数，如果采用上述牛顿迭公式，有时会使函数值上升三、算例分析算例1、f(x)€(x―4)2+(x―8)212取初始点x€[1,1]初步分析，目标函数为二次函数，经过一次迭代即可得到。

编制程序及计算结果如下：symsx1x2;f=(x1-4)A2+(x2-8)A2;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=-G1\g1;x0=x0+p;g1=subs(df,{x1,x2},{x0(1,1),x0(2,1)});G1=subs(G,{x1,x2},{x0(1,1),x0(2,1)});k=k+1;end;kx0结果：1x0=48正如分析所得，迭代一次即可得出极小值点算例2、f(x)€(x-10)2,(x-8)4,(x,5)3123取初始点x€[-1,4,1]t目标函数为三维函数，且都高于二次，海塞矩阵存在且不为常数，迭代次数大于一次编制程序和计算结果如下：symsx1x2x3;f=(x1-10)A2+(x2-8)A4+(x3+5)A3;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,1)});G1=subs(G,{x1,x2,x3},{x0(1,1),x0(2,1),x0(3,1)});k=0;while(norm(g1)>e)p=-G1\g1;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结果：k=28x0=10.00008.0000-5.0000四、结果分析牛顿迭代法主要利用二阶梯度进行求解，在针对上述算例进行计算后，主要存在以下问题：1) 牛顿法所求极小值点是局部极小值点，对于取初值有一定要求。

为了克服这一困难，引入了阻尼牛顿法以得到大范围收敛特性2) 对于二次的目标函数，其海塞矩阵为常数阵，迭代一次即可得到结果，收敛速度较快3) 对于某些方程，例如f(x)€(x-10)2,(x-8)4,(x,5),迭代点的海塞123矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向4) 牛顿法在计算过程中，计算量偏大，不仅要计算梯度，还需要计算海塞矩阵及其逆矩阵，计算量和存储量大。