发布时间 : 星期五 文章最优化Armijo算法确定步长的最速下降法资料更新完毕开始阅读2f168a5475232f60ddccda38376baf1ffc4fe3d5
数学与计算科学学院
实 验 报 告
实验项目名称 使用非精确线搜索Armijo算法确定步长
的
最速下降法
所属课程名称 最优化方法 实 验 类 型 算法编程 实 验 日 期
班 级 学 号 姓 名
成 绩
一、实验概述： 【实验目的】 1.通过实验掌握最速下降法的Matlab算法的基本步骤； 2.通过实验掌握Armijo算法确定步长； 3.掌握最速下降法的思想及迭代步骤。 【实验原理】 1.最速下降法： 最古老的优化方法，十九世纪中叶由Cauchy提出 思想 ：每次沿负梯度方向进行搜索 * ● 等值线(面) ● k?1 ??f(xk) ● k 负梯度方向也称为最速下降方向： 举例： 事实上，对任意p?Rn且||p||??, 由Cauchy-Schwarz不等式得 ?f(xk)TP?-||?f(xk)||?||P||?-||?f(xk)|| -?f(xk)-?f(xk)当取p?时等号成立，即 p?是下列问题 ||?f(xk)||||?f(xk)|| 的解 min?f(xk)TP||p||?? 算法步骤： xxx 1
步1给定初始点x0?Rn,精度??0.令k?0;步2若||?f(xk)||??，则得解xk,算法终止.否则计算dk?-?f(xk),然后转步3；步3由线性搜索计算步长?k;步4令xk?1?xk??kdk,k:?k?1,转步2. 优点： 对于简单的二元二次函数极小化问题，最速下降法在有限次迭代并没有求出其精确最优解,但能以较慢的速度无限接近最优解.最速下降法的收敛性： 全局收敛性： 由于最速下降法的搜索方向与负梯度方向一致,即?k?0,且 ||?f(xk)|| ? ||dk||所以,我们很容易得到最速下降算法的全局收敛性. 采用精确搜索, 或Armijo搜索或Wolfe-Powell搜索的最速下降法产生的迭代序列{xk}满足 lim||?f(xk)||?0k?? 由例子看到,最速下降法的收敛速度至多是线性的, 收敛速度估计： 设矩阵Q对称正定,q?Rn.记?max和?min分别是Q的最大和最小特征值,??问题：1TxQx?qTx2则由采用精确搜索的最速下降法产生的点列{xk}满足 minf(x)???-1?* ||xk?1-x*||Q?? （3.2）?||xk-x||Q ???1?其中x是问题的惟一解,||x||Q?xQx*?max.考察如下二次函数极小化?min?T?12 2
对于二次函数,由于?f(x)?Qx?q且在x*处 ?f(x*)?Qx*?q?0112则 f(x)-f(x*)?(x-x*)TQ(x-x*)?||x-x*||Q22所以(3.2)可以改写成??-1?* f(xk?1)-f(x*)???[f(xk)-f(x)]???1?由收敛速度估计式(3.2)看到,最速下降的收敛速度与矩阵Q的条件数?有关,当?接近于1,最速下降收敛很快, 特别, 当??1即Q的所有特征值相等时,算法只需一次迭代即可求出最优解. 而当?较大时(Q接近病态）,算法收敛很慢. 2结论：最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步. 【实验环境】 Win 7； Matlab7.0 二、实验内容： 【实验方案】 1、求梯度； 2、向梯度相反的方向移动x，其中 为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。 3、循环迭代步骤2，直到x的值变化到使得0.00000001，也就是说，直到两次迭代计算出来的到局部最小值了。 4、此时，输出x，这个x就是使得函数最小时的x的取值 。 在两次迭代之间的差值足够小，比如基本没有变化，则说明此时已经达【实验过程】 梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。 其迭代公式为 ,其中 代表梯度负方向， 表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的 即可。
3