最速下降法原理及例题实例

最速下降法原理以及其算法的实现最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元函数的无约束非线性规划问题min()fx的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。一、最速下降法基本原理(一)无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。定理1设f:1nRR→在点nxR∈处可微。若存在npR∈，使()0Tfxp∇则向量p是f在点x处的下降方向。定理2设1:nfRR→在点nxR*∈处可微。若x*是无约束问题的局部最优解，则()0fx*∇=由数学分析中我们已经知道，使()0fx∇=的点x为函数f的驻点或平稳点。函数f的一个驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数f的鞍点。以上定理告诉我们，x*是无约束问题的的局部最优解的必要条件是：x*是其目标函数f的驻点。现给出无约束问题局部最优解的充分条件。定理3设1:nfRR→在点nxR*∈处的Hesse矩阵2()fx*∇存在。若()0fx*∇=，并且2()fx*∇正定则x*是无约束问题的严格局部最优解。一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。定理4设1:nfRR→，nxR*∈，f是nR上的可微凸函数。若有()0fx*∇=则x*是无约束问题的整体最优解。(二)最速下降法的基本思想和迭代步骤最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。设无约束问题中的目标函数1:nfRR→一阶连续可微。最速下降法的基本思想是：从当前点kx出发，取函数()fx在点kx处下降最快的方向作为我们的搜索方向kp.由()fx的Taylor展式知()()()(kkkkTkkfxfxtptfxpotp-+=-∇+‖‖)略去t的高阶无穷小项不计，可见取kp=()kfx-∇时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。解无约束问题的的最速下降法计算步骤第1步选取初始点0x，给定终止误差0e，令:0k=；第2步计算()kfx∇，若(kfxe∇≤‖)‖，停止迭代.输出kx.否则进行第三步；第3步取()kkpfx=-∇；第4步进行一维搜索，求kt，使得0()min()kkkkktfxtpfxtp≥+=+令1kkkkxxtp+=+，:1kk=+，转第2步。由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。确定最优步长kt的方法如下：方法一：采用任一种一维寻优法此时的(())kkfxtfx-∇已成为步长t的一元函数，故可用任何一种一维寻优法求出kt，即1()(())min(())kkkkkktfxfxtfxfxtfx+=-∇=-∇方法二：微分法因为(())()kktfxtfxtj-∇=所以，一些简单情况下，可令'()0tj=以解出近似最优步长kt的值。(三)最速下降法应用举例例122121122min()22fxxxxxxx=-+++给定初始点()1(0,0)TX=解：目标函数()fx的梯度112122()()142()122()()fxxxxfxxxfxx∂⎡⎤⎢⎥∂++⎡⎤⎢⎥∇==⎢⎥-++∂⎢⎥⎣⎦⎢⎥∂⎣⎦(1)1()1fX⎡⎤∇=⎢⎥-⎣⎦令搜索方向(1)(1)1()1dfX-⎡⎤=-∇=⎢⎥⎣⎦再从(1)X出发，沿(1)d方向作一维寻优，令步长变量为l，最优步长为1l，则有(1)(1)0101Xdllll--⎡⎤⎡⎤⎡⎤+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦故(1)(1)2221()()()2()2()2()fxfXdllllllllljl=+=--+-+-+=-=令'1()220jll=-=可得11l=(2)(1)(1)1011011XXdl--⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦求出(2)X点之后，与上类似地，进行第二次迭代：(2)1()1fX-⎡⎤∇=⎢⎥-⎣⎦令(2)(2)1()1dfX⎡⎤=-∇=⎢⎥⎣⎦令步长变量为l，最优步长为2l，则有(2)(2)111111Xdllll--⎡⎤⎡⎤⎡⎤+=+=⎢⎥⎢⎥⎢⎥+⎣⎦⎣⎦⎣⎦故(2)(2)2222()()(1)(1)2(1)2(1)(1)(1)521()fxfXdllllllllljl=+=--++-+-+++=--=令'2()1020jll=-=可得215l=(3)(2)(2)2110.81111.25XXdl--⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦(3)0.2()0.2fX⎡⎤∇=⎢⎥-⎣⎦此时所达到的精度(3)()0.2828fX∇≈本题最优解11.5X*-⎡⎤=⎢⎥⎣⎦，()1,25fX*=-例2用最速下降法求解无约束非线性规划问题：42112min()(2)(2)fXxxx=-+-其中12(,)TXxx=，要求选取初始点0(0,3)TX=，终止误差0.1e=.解：因311212()[4(2)2(2),4(2)]TfXxxxxx∇=-+---则0()(44,24)TfX∇=-0()50.12fXe∇=00()(44,24)TpfX=-∇=-求单变量极小化问题：0000min()min(44,324)ttfxtpftt≥≥+=-420min(442)(926)ttt≥=-+-的最优解0t，由0.618法可得00.06t=，于是1000(2.70,1.51)TXxtp=+=1()(0.73,1.28)TfX∇=1()1.47fXe∇=令11()pfX=-∇再求单变量极小化问题110min()tfXtp≥+的最优解.略去计算步骤，由表1-1给出计算结果.由表1-1可以知道，7()0.09fXe∇=，所以7(2.28,1.15)TX=为近似最优解，原问题的近似最优值为0.007.表1-1迭代次数kkX()kfX()kfX∇()kfX∇kt1kX+0(0.00,3.00)T52.00(44,24)T-50.120.06(2.70,1.51)T1(2.70,1.51)T0.34(0.73,1.28)T1.470.24(2.52,1.20)T2(2.52,1.20)T0.09(0.80,0.48)T-0.930.11(2.43,1.25)T3(2.43,1.25)T0.04(0.18,0.28)T0.330.31(2.37,1.16)T4(2.37,1.16)T0.02(0.30,0.20)T-0.360.12(2.33,1.18)T5(2.33,1.18)T0.01(0.08,0.12)T0.140.36(2.30,1.14)T6(2.30,1.14)T0.009(0.15,0.08)T-0.170.13(2.28,1.15)T7(2.28,1.15)T0.007(0.05,0.08)T0.09例3用最速下降法求解无约束问题221212131min()222fxxxxxx=+--取()1(0,0)TX=，210e-=。解：计算目标函数的梯度和Hesse阵12121232()xxgfXxxg--⎡⎤⎡⎤∇==⎢⎥⎢⎥-⎣⎦⎣⎦，231()11fXG-⎡⎤∇==⎢⎥-⎣⎦设[]()12,Tkddd=，[]()12(),TkfXgg∇=得到精确一维搜索步长112222121232kgdgddddda+=+-取()1(0,0)TX=，则[](1)()2,0TfX∇=-，所以[](1)(1)()2,0TdfX=-∇=，21221323a==×因此[][](2)(1)(1)1120,02,0,033TTTXXda⎡⎤=+=+=⎢⎥⎣⎦再计算第二轮循环，表1-2列出了各次迭代的计算结果。共计算了9个点，(9)()0.025fX∇=210-，停止计算，所以[](9)0.988,0.988TX=作为问题的最优解。表1-2k()kX()()kfX()()kfX∇()kdka1(0.000,0.000)0.000(2.000,0.000)-(2.000,0.000)0.3332(0.667,0.000)0.667-(0.000,0.667)-(0.000,0.667)1.0003(0.667,0.667)0.889-(0.667,0.000)-(0.667,0.000)0.3334(0.889,0.667)0.963-(0.000,0.222)-(0.000,0.222)1.0005(0.889,0.889)0.988-(0.222,0.000)-(0.222,0.000)0.3336(0.963,0.889)0.996-(0.000,0.074)-(0.000,0.074)1.0007(0.963,0.963)0.999-(0.074,0.000)-(0.074,0.000)0.3338(0.988,0.963)1.000-(0.000,0.025)-(0.000,0.025)1.0009(0.988,0.988)1.000-(0.025,0.000)-(四)最速下降法的缺点由于沿负梯度方向目标函数的最速下降性，很容易使人们误认为负梯度方向是最理想的搜索方向，最速下降法是一种理想的极小化方法。必须指出的是，某点的负梯度方向，通常只是在该店附近才具有这种最速下降的性质。在一般情况下，当用最速下降法寻找极小点时，其搜索路径呈直角锯齿状（图1-3），在开头几步，目标函数下降较快；但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。图1-3因此，在实用中常将最速下降法和其他方法联合应用，在前期使用最速下降法，而在接近极小点时，可改用收敛较快的其他方法。(4)xO(2)x(3)xg二、最速下降法算法实现(一)最速下降法程序流程图最速下降法的程序流程图，如图1-4所示图1-4(二)最速下降法程序清单用C语言编写的最速下降法的程序清单如下。其中R是梯度模，P是梯度方向的的单位向量，h是步长，f是目标函数。#include“math.h”开始给定初始点0nxE∈，0e:0k=计算()kkpfx=-∇kpe≤求kl使其满足0min()()kkkkkfxpfxplll≥+=+令1kkkkxxpl+=+输出：minkxx=结束是#include“stdio.h”floatx[10],y[10],p[10],f,h;intn;vodfun(){inti;for(i=1,in;i++)x[i]=y[i]-h*p[i];f=x[1]*x[1]+x[2]*x[2]-x[1]*x[2]-10*x[1]-4*x[2];f=f+60;return;}main(){floatg[10],d[10],q,r,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v;inti,k,u;printf(“inputn,e\n”)；scanf(“%d,%f”,&n,&e);x[1]=0;x[2]=0;p4:g[1]=2*x[1]-x[2]-10;g[2]=2*x[2]-x[1]-4;q=0;for(i=1;in;i++)q=g[i]*g[i]+q;r=sqrt(q);for(i=1;in;i++){y[i]=x[i];p[i]=g[i]/r;}if(re)gotop3;else{t0=1;v=0.1;h1=0;h=h1fun();f1=f;p2:u=0