最速下降法

最速下降法 数学软件与实验结课作业 ------最速下降法 班级:071111 学号:07111008 07111012 07111057 姓名:李咏 邹仁朋 宋郝开 摘要 最速下降法又称梯度法，早先求解无约束多元函数极值的数值方法，是 1847 年由著名数学家 Cauchy 给出的，它是解析法中最古老的一种，是最优化方法的基础。它工作量较少，且储存变量不多，初始点要求也不高，但效率不高。 最速下降法多用来解觉 n 元函数的无约束非线性规划问。利用负梯度方向来决定每次迭代的新的搜索方向，使得每次迭代能使待优化的目标函数逐步减小，从而最终找到最优解。 最速下降法的基本思想是:从当前点 xk 出发，取函数 fx在点 xk处下降最快的方向作为我们的搜索方向 pk，由 fx的 Taylor 展式知xk - f xk tpk -tf xkT pk o‖ tpk‖，略去 t 的高阶无穷小项不计，可见取 pk -f xk时，函数值下降得最多。从而，构造出最速下降法的迭代步骤求解。最速下降法的一种简单形式是:xk1xk-agk其中 a 称为学习速率，可以是较小的常数。g(k)是 xk的梯度。一、问题描述求解最优化问题是通常采用两种方法:1.解析解法——利用函数的导数构造迭代公式使之收敛到极值点的方法;2.直接解法——根据数学原理，用尽可能少的计算量直接比较函数值的大小，来确定函数极值的方法。在最优化计算方法中，要求解 y f x1 x2 xn 的局部最小值，选用解析解法，采用如下的方法进行迭代计算:先给出初始点 x 0 x10 x2 xn ，然后根据其梯 0 0度方向 f x0 ，计算一元函数 y λ1 min f x0 λ f x0 ，并得到 x x0 λ1 f x0 1 λ ?0 。如此反复迭代，最终收敛于局部最优点。实现该算法。直观的说，就是在一个有中心的等值线中，从初始值开始，每次沿着垂直等值线方向移动一个小的距离，最终收敛在中心。 对于某一个性能指数，我们能够运用最速下降法，使这个指数降到最小。若该指数为均方误差，我们便得到了最小均方误差算法。如图所示函数 J(a)在某点 ak 的梯度 JAk是一个向量，其方向是 J(a)增长最快的方向。显然，负梯度方向是 J(a)减少最快的方向。在最速下降法中，求某函数最大值时，沿着梯度方向走，可以最快达到极大点;反之，沿着负梯度方向走，则最快达到最小值。二、 解决问题的依据?最速下降法基本原理 无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的 依据，为此我们有以下几个定理: 定理 1 设 f : Rn R1 在点 x Rn 处可微。若存在 pRn，使 f xT p 0，则向量 p 是 f 在点 x 处的下降方向。 定理 2 设 f : Rn R1 在点 x Rn 处可微。若 x是无约束问题的局部最优解，则 f x 0。 由数学分析中我们已经知道，使 f x 0 的点 x 为函数 f 的驻点或平稳点。函数 f 的一个驻点可以是极小点;也可以是极大点;甚至也可能既不是极小点也不是极大点，此时称它为函数 f 的鞍点。以上定理告诉我们，x是无约束问题的的局部最优解的必要条件是:x是其目标函数 f 的驻点。 定理 3(充分条件) 设 f : Rn R1 在点 x Rn 处的 Hesse 矩阵 2 f x 存在。若 f x 0，并且 2 f x 正定，则 x是无约束问题的严格局部最优解。 一般而言， 无约束问题的目标函数的驻点不一定是无约束问题的最优解。 但对于其目标函数是凸函数的无约束凸规划，下面 定理证明了，它的目标函数的驻点就是它的整体最优解。 定理 4 设 f : Rn R1，x Rn， f 是 Rn 上的可微凸函数。若有 f x 0，则 x是无约束问题的整体最优解。?最速下降法的基本思想 从当前点 xk 出发，取函数 f x在点 xk 处下降最快的方向作为我们的搜索方向pk .由f x的Taylor 展式知f xk f xk tpk tf xk Tpk o‖ tpk‖略去t的高阶无穷小项不计，可见取pk f xk 时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。解无约束问题的的最速下 降法计算步骤三、 算法描述 用最速下降法求无约束多维极值问题 min f x x ? R 的算法步骤如下: n(1)取初始点 x ，精度 ε 0 ，令 k 0 0(2)计算搜索方向 v k f x k ，其中 f x k 表示函数 f x 在点 x k 处的梯度; vk ? ε 即求 λk ， k k (3)若 ，则停止计算;否则， x 从 出发， v 进行一维搜索， 沿 f x k λk v k min f x k λ v k 使得 λ ?0 。此处的一维搜索可以用黄金分割法等算法，当然也可以用 MATLAB 的 f min bnd 函数;(4)令 x k 1 λk v k k xk k 1 ，转步骤2。 如图，函数 J(a)在某点 ak 的梯度 是一个向量，其方向 J(a)增长最快的方向。显然，负梯度方向是 J(a)减少最快的方向。在最速下降法中，求函数最大值时，沿着梯度方向走，可以最快达到极大点;反之，沿着负梯度方向走，则最快达到最小点。 求函数 J(a)极小值的问题，可以选择任意初始点 a0，从 a0出发沿着负梯度方向走，可使得 J(a)下降最快。流程图: 本程序在设计时加入了一个子程序，可以在子程序中输入要计算的线性方程，在主程序中进行运算。 程序设计时用 while 循环语句查找最值，用求导函数的方法定义变量，并且将变量 x1，x2写成矩阵的形式以便进行运算。四、 计算结果展示求 fxyx-a2y-b2cxyd 的最优值，假设 a3，b2，c1，d1，则带入程序的运行结果如下:则 f(xy)x-32y-22xy1 Untitled12 最大值是: 139 最小值是: 4.6700 最优解时 x 取值 y 取值 2.6151 0.6770 5 4 120 3 2 100 1 80 0 -1 60 -2 40 -3 -4 20 -5 -5 0 5五、 问题及解决方法 开始写程序时没有考虑网格 z 的大小要小于等于 X、Y 矩阵的大小，于是出现要生成的图的点阵小于矩阵 X、Y 的点数，所以图画不出来，而且区间变量的点阵也要小于 XY 矩阵的点阵，否则程序出现错误。该程序的效率较高，容易理解，但是在函数的变量区间改变了以后随之要该矩阵 XY 的点的数目，否则区间内点阵数大于矩阵数不能运算，目前还没有找到太好的解决方案。六、 由于沿负梯度方向目标函数的最速下降性， 很容易使人们误认为负梯度方向是最理想的搜索方向， 最速下降法是一种理想的极小化方法。最速下降法算法简单，每次迭代计算量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点。必须指出的是，某点的负梯度方向，通常只是在该点附近才具有这种最速下降的性质。在一般情况下，当用最速下降法寻找极小点时，其搜索路径呈直角锯齿状，在开头几步，目标函数下降较快;但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。 其他最优化方法:牛顿法和共轭梯度法。牛顿法是利用目标函数 在迭代点处的 Taylor 展开式作为模型函数，并利用这个二次模型函数的极小点序列去逼近目标函数的极小点。 共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向 仅仅是负梯度方向 与上一次接待的搜索方向 的组合。 然而沿负梯度方向函数值下降很快的特点，容易使认为这一定是最理想的搜索方向，然而事实证明，梯度法的收敛速度并不快(特别是对于等值线，具有狭长深谷形状的函数，收敛速度更慢。其优点是工作量少，存储变量较少，初始点要求不高;缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。 它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元函数的无约束非线性规划问题min f x的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。附录:源代码:子函数: functionfdff_dfxfx1-32x2-22x1x21df12x1-3x2df22x2-2x1主函数:clearsyms x1 x2 f lmda 定义变量x1 1定义起始位置plotx1x2打印出起始点fxdff_dfxd-dfxsx1 x2将 x1 x2 写成矩阵hdhf_dfxs用循环语句比较取值大小whilesqrtdf12df220.1 xs1x1lmdad1 xs2x2lmdad2 h1composehxs1 h2composeh1xs2 dh2diffh2lmda lmsolvedh2 lmdoublelm x1x1lmd1 x2x2lmd2 plotx1x2 fxdff_dfx d-dfenda-5:0.1:5定义变量区间 b-5:0.1:5XYmeshgridabfor i1:101 for j1:101 y1Xij y2Yij Zijf_dfyz 为网格状 endendhold oncolorbarcontourXYZ88:zmaxmaxmaxZ找到最值并打印出来 zminminminZdisp区域内最大值是:dispzmaxdisp区域内最小值是:dispzmindisp最优 解时disp x 取值 y 取值disp x