下载文档原格式
牛顿法求解无约束多维优化问题一、基本思想牛顿法是一种线性化的方法，其基本思想是将非线性方程()0f x =逐步归结为某种显性线性方程来求解。
在k x 邻域内用一个二次函数()x ϕ来近似代替原目标函数，并将()x ϕ的极小值点作为对目标函数()f x 求优的下一个迭代点1k x +。
经多次迭代，使之逼近目标函数()f x 的极小值点。
二、数学模型将目标函数()f x 作二阶泰勒展开，设1k x +为()x ϕ的极小值点1()0k x ϕ+∇=21()()()0k k k k f x f x x x +∇+∇-=121[()]()(0,1,2,3)k k k k x x f x f x k +-=-∇∇= 这就是多元函数求极值的牛顿法迭代公式。
对于二次函数，海塞矩阵H 是一个常矩阵，其中各元素均为常数，因此，无论从任何点出发，只需一步就可以找到极小值点。
从牛顿法迭代公式的推导过程中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。
因此对于非二次函数，如果采用上述牛顿迭公式，有时会使函数值上升。
三、算例分析算例1、2212()(4)(8)f x x x =-+-取初始点[1,1]T x =2()()()()()1()()()2k k T k k T k k f x x f x f x x x x x f x x x ϕ≈=+∇-+-∇-初步分析，目标函数为二次函数，经过一次迭代即可得到。
编制程序及计算结果如下：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=-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结果：k =1x0 =48正如分析所得，迭代一次即可得出极小值点。
无约束优化方法1. 最速下降法（Gradient Descent Method）最速下降法是一种基于梯度信息的迭代优化算法。
其基本思想是从任意初始点开始，沿着目标函数的梯度方向进行迭代，直到达到收敛条件。
最速下降法的迭代更新公式如下：x_{k+1}=x_k-t_k*∇f(x_k)其中，x_k是第k次迭代的解向量，t_k是第k次迭代的步长（也称为学习率），∇f(x_k)是目标函数在x_k处的梯度向量。
最速下降法的步骤如下：1）选取初始点x_0。
2）计算目标函数的梯度∇f(x_k)。
3）计算步长t_k。
4）更新解向量x_{k+1}。
5）判断迭代终止条件，如果满足则停止迭代；否则返回第2步。
最速下降法的优点是易于实现和理解，收敛性较好。
然而，最速下降法存在的问题是收敛速度较慢，特别是对于目标函数呈现狭长或弯曲形状的情况下。
这导致了在高维优化问题中，最速下降法的性能较差。
2. 牛顿法（Newton's Method）牛顿法是一种基于二阶导数信息的迭代优化算法。
它使用目标函数的一阶和二阶导数信息构造一个二次近似模型，然后求解该模型的最小值。
牛顿法的迭代更新公式如下：x_{k+1}=x_k-H_k^{-1}*∇f(x_k)其中，H_k是目标函数在x_k处的海森矩阵，∇f(x_k)是目标函数在x_k处的梯度向量。
牛顿法的步骤如下：1）选取初始点x_0。
2)计算目标函数的梯度∇f(x_k)和海森矩阵H_k。
3）计算更新方向H_k^{-1}*∇f(x_k)。
4）更新解向量x_{k+1}。
5）判断迭代终止条件，如果满足则停止迭代；否则返回第2步。
牛顿法的优点是收敛速度快，尤其是在目标函数曲率大的地方。
然而，牛顿法也存在一些问题。
首先，计算海森矩阵需要大量的计算资源，特别是在高维空间中。
其次，当海森矩阵不可逆或近似不可逆时，牛顿法可能会失效。
综上所述，最速下降法和牛顿法是两种常用的无约束优化方法。
最速下降法简单易实现，但收敛速度较慢；牛顿法收敛速度快，但计算量大且可能遇到海森矩阵不可逆的问题。
无约束优化算法无约束优化算法问题，是指优化问题的可行集为nR ，无约束的标准形式为： min ():n f x f R R →1. 最优性条件（1） 极小值点的一阶必要条件设():n f x R R →为连续可微函数，如果*x 为局部极小值点，则*x 为驻点，即梯度*()0f x ∇=。
（2） 极小值的二阶必要条件设():n f x R R →为二阶连续可微函数，如果*x 为局部极小值点，则*x 为驻点，即梯度*()0f x ∇=，二阶hesse 2*()f x ∇半正定。
（3） 极小值点的二阶充分条件设():n f x R R →为二阶连续可微函数，如果梯度*()0f x ∇=，二阶h e s s e 2*()f x ∇正定，则*x 为f 的局部极小值点，*n x R ∈。
以上三个定理为搜索最优点以及判断一个点是否为最优点的基本依据。
经典的优化算法的停止条件为*()0f x ∇=，例如在程序中*8()110f x -∇≤⨯ ，即在导数范数小于某特定误差限时停止。
误差限较大，则算法迭代次数减少，计算时间缩短，但解得质量降低；误差限较小，则算法迭代次数增加，计算时间增加，但解的质量提高；误差限一般为8110-⨯，可以根据实际情况设定合适的误差限。
当然，还有极小值点的二阶必要条件与极小值点的二阶充分条件，对2*()f x ∇的判断，由于目标函数比较复杂，二阶导数矩阵的计算量极大，所以一般算法都在迭代过程中对2()()k f x∇进行修正，得到2(1)()k f x +∇，在修正的过程中始终保持2*()f x ∇的正定性，以此方法解决极小值点的二阶条件问题。
2. 最速下降法2.1 算法原理最速下降法是早期的优化算法，其理论根据函数的一阶泰勒展开： 由()()()()Tf x d f x f x d d ααοα+=+∇+ 得到()()()()T f x d f x f x d d ααοα+-=∇+根据下降要求()()0f x d f x α+-≤ 故()()0Tf x d d αοα∇+≤实际中要求()0T f x d α∇≤根据上式选取合适的d ，得()0T f x d α∇≤。
运筹学Operations Research无约束最优化方法西南交通大学经济管理学院§1.最速下降法§2.Newton法§3.共轭梯度法§4.变尺度法§5.直接法)()()()(0)(,,1,P o P X f X f P X f X f X f P E P T k k k k kn λλλ+∇+=+≠∇=∈非零：处的梯度它在是连续可微的函数即是单位向量设P X f o P X f X f P X f P f P X X f T k T k k k k)()()(lim )()(lim )(00∇=+∇=−+=∂∂→→λλλλλλλ的方向导数为：处关于方向在点k k k k T k kk T k X f P X f P X f P X f P P X f θθθcos )(cos )()()()(∇=⋅∇=∇∇∇之间的夹角，则和为。
记就是使下降最快的方向取最小的使处的最速下降方向。
在点通常把它叫做下降最快的方向。
出发使是从点时，上式最小，所以可知，当k kk k k X f f X X f P )(:−∇==πθ下降的搜索方向。
再去寻找使处不需要在点这时的点局部最优解的必要条件的已是满足的驻点。
是，则若f X X f X X f k k k k ,,)NP (0)(=∇:,)(,,,;,,,,,1的最佳步长，即作为点最小的确定使来的一维搜索即通过在负梯度方向上最佳步长方法采用振荡的情况。
所以一般在极值点附近出现来回则若步长选得大计算次数较多则收敛慢长选得小若步。
选择用固定步长时还要确定步长方向之后在选定了搜索得到下一个近似点为了由点＋kk k k X X f X X λλ))((min ))((0kk k k k X f X f X f X f ∇−=∇−>λλλ§1.最速下降法)()()()()(0)()()()()())(()()()(21)()()())((2k k T k k T k k k k T k k T k k k k k T k kT k k k k X f X H X f X f X f X f X H X f X f X f d X f X df X f X H X f X f X f X f X f X f ∇∇∇∇==∇∇+∇−∇=∇−∇∇+∇∇−≈∇−λλλλλλλλ得：求导并令其等于零，则对§1.最速下降法Step1.。
第四章 无约束优化方法——最速下降法，牛顿型方法概述在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。
尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。
因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。
为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。
（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。
（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。
根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。
一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。
二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。
无约束优化问题的一般形式可描述为：求n 维设计变量 []12Tn n X x x x R =∈使目标函数 ()min f X ⇒目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。
无约束优化问题的求解： 1、解析法可以利用无约束优化问题的极值条件求得。
即将求目标函数的极值问题变成求方程0)(min *=X f的解。
也就是求Ｘ＊使其满足解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。
但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。
由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。
因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。
2、数值方法数值迭代法的基本思想是从一个初始点)0(X出发，按照一个可行的搜索方向)0(d搜索，确定最佳的步长0α使函数值沿)0(d 方向下降最大，得到)1(X 点。
最速下降法与牛顿法结合求无约束最优值（mtlab动画演示）2009-04-05 9:54最速下降法能找出全局最优点，但在接近最优点的区域内就会陷入“齿型”迭代中，使其每进行一步迭代都要花掉非常久的时间，这样长久的等待是无法忍受的，不信你就在我那个程序的第一步迭代中把精度取得很小如：0.000000001等，其实我等过一个钟都没有什么结果出来。
再者我们考究一下牛顿迭代法求最优问题，牛顿法相对最速下降法的速度就快得多了，而且还有一个好处就是能高度逼近最优值，而不会出现死等待的现象。
如后面的精度，你可以取如：0.0000000000001等。
但是牛顿法也有缺点，就是要求的初始值非常严格，如果取不好，逼近的最优解将不收敛，甚至不是最优解。
就算收敛也不能保证那个结就是全局最优解，所以我们的出发点应该是：为牛顿法找到一个好的初始点，而且这个初始点应该是在全局最优点附近，这个初始点就能保证牛顿法高精度收敛到最优点，而且速度还很快。
思路概括如下：1。
用最速下降法在大范围找到一个好的初始点给牛顿法：（最速下降法在精度不是很高的情况下逼近速度也是蛮快的）2。
在最优点附近改用牛顿法，用最速下降法找到的点为牛顿法的初始点，提高逼近速度与精度。
3。
这样两种方法相结合，既能提高逼近的精度，还能提高逼近的速度，而且还能保证是全局最优点。
这就充分吸收各自的优点，扬长避短。
得到理想的结果了。
ticclc;clear;syms x1 x2G=[];G=input('请输入想x1^2,x2^2,x1*x2,x1,x2,常系数,如[1,2,3,4,5,6] 系数向量=:');a=G(1,1);b=G(1,2);c=G(1,3);d=G(1,4);e=G(1,5);g=G(1,6);f=a*x1^2+b*x2^2+c*x1*x2+d*x1+e*x2+g;%画出原始图像figure;x11=-100:0.5:100;x22=x11;[x11,x22]=meshgrid(x11,x22);f11=a.*x11.^2+b*x22.^2+c*x11.*x22+d.*x11+e.*x22+g;surf(f11),grid on,hold on;%画出原始图像df1=diff(f,x1);df2=diff(f,x2);%对函数进行求一阶导DF=[df1;df2];df11=diff(df1,x1);df12=diff(df1,x2);df21=diff(df2,x1);df22=diff(df2,x2);%这里进行求函数二阶导数DEE=[df11,df12;df21,df22];x=input('请输入x的初始值为x=[x1,x2],x=:');x=x';E=input('请输入你所要求的最速下降法的精度数（一般取3～5）E=:'); %这里进行一些相关初始值的计算T=[];d=T;T(:,1)=subs(DF,[x1,x2],[x(1),x(2)]);TH=subs(DEE,[x1,x2],[x(1),x(2)]);%这里进行一些相关初始值的计算disp('由于你输入的初始值，这里将开始最速下降法搜寻：');for k=1:100000d(:,1)=-T(:,1);%d(k)是x(k+1)=x(k)+A(k)*d(k)A(1)=(T(:,1)'*T(:,1))/(T(:,1)'*TH*T(:,1));TH=subs(DEE,[x1,x2],[x(1,k),x(2,k)]);T(:,k)=subs(DF,[x1,x2],[x(1,k),x(2,k)]);d(:,k+1)=-T(:,k);A(k)=(T(:,k)'*T(:,k))/(T(:,k)'*TH*T(:,k));KLJ(:,k)=norm(T(:,k));GG(k)=subs(f,[x1,x2],[x(1,k),x(2,k)]);if norm(T(:,k))<Edisp('有这里你就进入牛顿法求最优了');disp(' ');disp('FX就是最速下的解 ')FX=subs(f,[x1,x2],[x(1,k),x(2,k)])disp(' ');disp('对应的x值为 ');x(:,k)break;endx(:,k+1)=x(:,k)+A(k)*d(:,k);endtoc%画出最速下降迭代点最终停留位置figure;plot3(x11,x22,f11,'r'),grid on;for tk=1:kh1=line( 'Color' ,[0 1 0], 'Marker' , '.' , 'MarkerSize' ,20, 'EraseMode' , 'xor' );set(h1, 'xdata' ,x(1,tk), 'ydata' ,x(2,tk), 'zdata' , GG(tk)); drawnow; % 刷新屏幕pause(0.1);endfop1=getframe(gcf)image(fop1.cdata)%画出最速下降迭代点最终停留位置ticY=x(:,k);EE=input('请输入牛顿最终的精度系数EE=：');TT(:,1)=subs(DF,[x1,x2],[Y(1),Y(2)]);THH=subs(DEE,[x1,x2],[Y(1),Y(2)]);aa=1;disp('程序可以运行到这里');for kk=1:10000dd(:,kk)=-inv(THH)*TT(:,kk);Y(:,kk+1)=Y(:,kk)+ aa*dd(:,kk);THH=subs(DEE,[x1,x2],[Y(1,kk),Y(2,kk)]);TT(:,kk+1)=subs(DF,[x1,x2],[Y(1,kk+1),Y(2,kk+1)]);PP=norm(TT(:,kk));GG1(kk)=subs(f,[x1,x2],[Y(1,kk),Y(2,kk)]);if PP<EEdisp('到这里您已经得到全局最优解了');FXX=subs(f,[x1,x2],[Y(1,kk),Y(2,kk)])disp(' ');disp('对应的x值为： ');Y(:,kk)break;endendFXX=subs(f,[x1,x2],[Y(1,kk),Y(2,kk)])toc%画出最终极值点停留位置figure;plot3(x11,x22,f11,'r'),grid on;for J=1:kkh2=line( 'Color' ,[0 1 0], 'Marker' , '.' , 'MarkerSize' ,40, 'EraseMode' , 'xor' );set(h2, 'xdata' ,Y(1,J), 'ydata' ,Y(2,J), 'zdata' , GG1(1,J));pause(0.1);fop=getframe(gcf);image(fop.cdata);enddisp('现在程序已经结束了');%画出最终极值点停留位置转自《研学论坛》。
