最速下降法求最优解西安电子科技大学matlab结课大作业

1、西安电子科技大学课程论文数学软件与实验最速下降法求最优解姓名：方正阳 学号：07117020班级：071171 07112016、最速下降法求最优解MATLAB 结课大作业摘要：最速下降法,又称为梯度法，是一种重要的无约束最优化方法。它是 1847 年由著名数学家 Cauchy 给出的，其他解析方法或是它的变形，或是受它 启发而得到，因此它是最优化方法的基础。该法将 n 维问题转化为一系列 不断迭代过程中沿负梯度方向用一维搜索方法寻优的问题，本次程序设计 利用最速下降法算法，反复迭代，最终收敛于局部最优点，即为解出的二 元函数的无约束非线性规划问题 minf(x,y)。引言：最优化理论作为运筹

2、学中的一个重要理论方法，在工业生产,金融经济活 动,工商管理,国防建设,计算机应用中，都有着重要的应用。最优化理论 通过给出生产活动中的各类实际问题的数学模型，通过最优化方法，寻求 该问题的最优解或满意解。最速下降算法是最优化理论中常见的一个重要 算法，理论证明：最速下降算法在一定条件下是收敛的，它能够有效地求 解一部分无约束最优化问题。一、实验目的熟悉最速下降法算法思想和步骤，用 MATLAB 语言编程最速下降法 求最优值。二、实验要求12n ，然后在最优化计算方法中，要求解 y = f (x1, x2 ,L, xn ) 的局部最小值，可第 9 页以采用如下的方法进行迭代计算：先给出初始点

3、x0 = (x0 , x0 ,L, x0 )根据其梯度方向Ñf (x0 )，计算一元函数y(l1 ) = min f (xl³00 -l×Ñf (x0 )，并100得到 x = x-l1 ×Ñf (x) 。如此反复迭代，最终收敛于局部最优点。 实现该算法，求 的最优值，a,b,c,d 自定（非 0）三、实验假设考虑到参数的随机性、代表性，验证程序的正确性、典型性，在此 我们从两个角度出发，一是在 abcd 值确定的情况下改变初始搜索位置 x0,看函数最优解是否相同；二是初始搜索位置 x0 相同，abcd 值不同的 情况下，看函数最优解

4、是否相同。1. 不妨令 a,b,c,d 分别为 1,2,3,4，即f ( x, y ) = ( x -1)2 + 3( y - 2)2 + 3xy + 4求其梯度函数（代码行间距已缩小）>> clear>> syms x y>> f=inline('(x-1).2+3*(y-2).2+3*x*y+4','x','y') f =Inline function:f(x,y) = (x-1).2+3*(y-2).2+3*x*y+4>> grad=diff(f(x,y),x),diff(f(x,y),y)

5、grad = 2*x + 3*y - 2, 3*x + 6*y - 122. 令 a,b,c,d 分别为 4,3,2,1，即f ( x, y ) = ( x - 4)2 + 3( y - 3)2 + 2xy +1求其梯度函数（代码行间距已缩小）>> clear>> syms x y>> f=inline('(x-4).2+3*(y-3).2+2*x*y+1','x','y');>> grad=diff(f(x,y),x),diff(f(x,y),y) grad = 2*x + 2*y - 8, 2*

6、x + 6*y - 18四、程序设计1. 无约束问题的最优性条件原理 1：设 f : Rn ® R1 在点 x Î Rn 处可微。若存在 p Î Rn ，使 Ñf (x)T p < 0 ， 则向量 P 是 f 在点 x 处的下降方向。原理 2：设 f : Rn ® R1 在点 x* Î Rn 处可微。若 x* 是无约束问题的局部最 优解，则Ñf (x* ) = 0 ，由数学分析中我们已经知道，使Ñf (x) = 0的点 x 为函数 f 的驻点或平稳点。函数 f 的一个驻点可以是极小 点；也可以是极大点；甚至也

7、可能既不是极小点也不是极大点， 此时称它为函数 f 的鞍点。以上定理告诉我们， x 是无约束问题的的局部最优解的必要条件是： x 是其目标函数 f 的驻点。 原理 3：设 f : Rn ® R1 在点 x* Î Rn 处的 Hesse 矩阵 Ñ2 f (x* ) 存在。若Ñf (x* ) = 0 ，并且 Ñ2 f (x* ) 正定，则 x* 是无约束问题的严格局部最优解。 一般而言，无约束问题的目标函数的驻点不一定是无约束问题的 最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理 证明了，它的目标函数的驻点就是它的整体最优解。原理 4 ：

8、 设 f : Rn ® R1 ， x* Î Rn ， f 是 Rn 上的可维凸函数。 若有Ñf (x* ) = 0 ，则 x* 是无约束问题的整体最优解。 2.最速下降法算法思想1 任一点的负梯度方向是函数值在该点下降最快的方向；2 将 n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题；3 极值点导数性质知，该点梯度=0，终止条件也就是梯度尽可能逼近 0，极值即当搜寻区间非常逼近极值点时， Ñf (a) ® 0 Þ f (a) ® f ( x)即为所求。 3.最速下降法算法迭代步骤，f (a)第 1 步 选取初始点

9、 x0，给定终止误差<0,令 k=0;第 2 步 计算Ñf (xk ) , 若| Ñf(xk ) |，停止迭代.输出 xk ，否则进行第 3 步；第 3 步 取搜索方向 pk =Ñf(xk ) ；第 4 步 进行一维搜索，求 tk ，使得 f ( x+ t p) = min f ( x+ tp )，kkkkkt ³0xk +1= xk + t pkk=k+1, 转至第 2 步；k由以上计算步骤可知，最速下降法迭代终止时，求得的是目 标函数驻点的一个近似点4.确定最优步长 tk此时的 f (xk - tÑf ( xk ) 已成为步长 t 的

10、一元函数，故可用任何一种一维寻优法，此程序中采用线性搜索法求出 tk即f (xk +1 )=f (xk- tk Ñf (xk )=mintf (xk- tÑf (xk )5.主要的参数说明grad:梯度函数；x0：搜索初始值；TolX:最优值点间的误差阈值； TolFun:函数的误差阈值；dist0:初始步长；MaxIter:最大的迭代次数；xo：最优化点值； fo:函数在点 xo 处的函数值。%迭代计算求最优解确定搜寻方向代码： for k=1:MaxIterg=feval(grad,X);g=g/norm(g);%求点 x 处的梯度%线性搜索方法确定步长的部分代码： d

11、ist=dist*2;fx1=feval(f,X-dist*2*g); for k1=1:kmax1fx2=fx1;fx1=feval(f,X-dist*g);iffx0>fx1+TolFun && fx1<fx2-TolFun %fx0>fx1<fx2, den=4*fx1-2*fx0-2*fx2;num=den-fx0+fx2; %二次逼近法 dist=dist*num/den;X=X-dist*g;fx=feval(f,X);%确定下一点注：在此为了简便，判断输入的变量数，设定一些变量为默认值(用户可自 己定义)，不妨设为 TolX=1e-4；To

12、lFun=1e-9；MaxIter=100；dist0=1;五、测试结果实验结果一、a,b,c,d 分别为 1,2,3,4；x0=2,4实验结果二、a,b,c,d 分别为 1,2,3,4；x0=1,1实验结果三、a,b,c,d 分别为 4,3,2,1；x0=2,4实验结果四、a,b,c,d 分别为 4,3,2,1；x0=1,1六、结果评价本次测试分别从两组不同的初始搜索位置，两组不同 a,b,c,d 值出发， 两两比较可得结论：测试用例 abcd 为某些特定值时，不同初始搜索位置可 以得到相同的最优解；测试用例当初搜索位置相同时，abcd 分别取两组数时 得到的最优解是不同的。从结果上来看本例

13、函数始终取到相同最优值，达到 了题目要求，只是在最优点位置有略微差异，这个问题产生原因是与最优值 点间的误差阈值自定义值有关，精度越高最优值越准确。七、程序评价1. 最速下降法算法简单，初始点可以任意选，每次迭代计算量小，即使从 一个不好的初始点出发，往往也能收敛到局部极小点。2. 由于在远离极小点的地方每次迭代可以使目标函数值有较大的下降，但 是在接近极小点的地方，由于锯齿现象，会导致每次行进距离缩短，从 而使收敛速度不快。即全局收敛，线性收敛，易产生扭摆现象而造成早 停。3. 最速下降法是一种理想的极小化方法。必须指出的是，某点的负梯度方 向，通常只是在该店附近才具有这种最速下降的性质。4

14、. 在实用中常将最速下降法和其他方法联合应用，在前期使用最速下降法， 而在接近极小点时，可改用收敛较快的其他方法，这样能使计算速度更 快，结果更准确。八、心得体会通过这次结课大作业，加深了我对 MATLAB 记忆和理解，真正做到了理论 和实践相结合，锻炼了自己分析，处理实际问题的能力，也认识到了自己的 不足。编程存在问题很大，主要细节错误找不出，M 文件的编写后调用运用 的不好，也让我认识到编写好 M 文件的重要性。在以后的学习中，要注重细 节和改错，多上机操作，切实提高编程能力。九、附录fun.m 文件function xo,fo=fun(f,grad,x0)%f:函数名；%grad:梯度函

15、数；%x0：搜索初始值；%TolX:最优值点间的误差阈值；%TolFun:函数的误差阈值；%dist0:初始步长；%MaxIter:最大的迭代次数；%xo：最优化点值；%fo:函数在点 xo 处的函数值。%判断输入的变量数，设定一些变量为默认值TolX=1e-4; TolFun=1e-9;MaxIter=100; dist0=1;if nargin<7MaxIter=100; %最大的迭代次数默认为 10endif nargin<6dist0=10;%初始步长默认为 10 endif nargin<5TolFun=1e-8;%函数值误差为 1e-8 endif nargin&

16、lt;4TolX=1e-6;%自变量距离误差 endx=x0; fx0=feval(f,x0); fx=fx0; dist=dist0;kmax1=25;%线性搜索法确定步长的最大搜索次数warning=0;%迭代计算求最优解 for k=1:MaxIter g=feval(grad,x);g=g/norm(g);%求点 x 处的梯度%线性搜索方法确定步长 dist=dist*2;fx1=feval(f,x-dist*2*g); for k1=1:kmax1fx2=fx1; fx1=feval(f,x-dist*g);if fx0>fx1+TolFun && fx1<

17、;fx2-TolFun %fx0>fx1<fx2, den=4*fx1-2*fx0-2*fx2;num=den-fx0+fx2; %二次逼近法dist=dist*num/den;x=x-dist*g;fx=feval(f,x);%确定下一点 breakelsedist=dist/2;end endif k1>=kmax1 warning=warning+1;%无法确定最优步长elsewarning=0; endif warning>=2|(norm(x-x0)<TolX&&abs(fx-fx0)<TolFun)break; end x0=x; fx0=fx; endxo=x;fo=fx;if k=MaxIterfprintf('Just best in %d iteration',MaxIter); end命令窗口输入：以测试结果一为例>> syms