统计计算 课件 第一章第二节优化算法2

爬山法是一种优化算法，一般从一个随机的解开始，逐步找到一个最优解（局部最优）。我们想从山脚爬到山顶，有很多种爬山的方法。爬山法指的是不管迈步的方向如何，要保证下一步始终比这一步的高度高，离山顶更近即可。找到一个可行解后，从这个解的附近找其他的解，满足对应的函数值要大于这个解的函数值。爬山时从这一步的落脚点的附近（邻域）中找下一个落脚点，要保证下一个落脚点的海拔高度高于该落脚点的高度，即每一步都比上一步要高。1.2.4爬山法求极值例1函数y=x1x2+x3，x1是区间[-2,5]中的整数，x2是区间[2,6]中的整数，x3是区间[-5,2]中的整数。使用爬山法，找到使得y取值最大的解。假设初值为[0,3,1]。所求函数有3个参数，在使用爬山法逐步获得最优解的过程中可以依次分别将某个自变量的值增加或者减少一个单位，即寻找周围的点，找出周围一系列的点，比较对应的函数值的大小，找出函数值最大的那组自变量的值作为本次迭代的最优解，即找出周围被选中的最高的落脚点。轮数解集函数值最大值最优解1{(0,3,1),（-1，3,1),（1,3,1),（0,2,1),（0,4,1),(0,3,0),(0,3,2)}1,-2,4,1,1,0,24(1,3,1)2{(1,3,1),(0,3,1),(2,3,1),(1,2,1),(1,4,1),(1,3,0),(1,3,2)}4,1,7,3,5,3,57(2,3,1)3{(2,3,1),(1,3,1),(3,3,1),(2,2,1),(2,4,1),(2,3,0),(2,3,2)}7,4,10,5,9,6,510(3,3,1)4{(3,3,1),(2,3,1),(4,3,1),(3,2,1),(3,4,1)(3,3,0)(3,3,2)}10,7,13,7,13,9,1113(4,3,1)5{(4,3,1),(3,3,1),(5,3,1),(4,2,1),(4,4,1),(4,3,0),(4,3,2)}13,10,16,17,9,12,1417(4,4,1)6{(4,4,1),(3,4,1),(5,4,1),(4,3,1),(4,5,1),(4,4,0),(4,4,2)}17,13,21,13,21,16,1821(5,4,1)7{(5,4,1),(4,4,1),(5,3,1),(5,5,1),(5,4,0),(5,4,2)}21,17,16,26,20,2226(5,5,1)8{(5,5,1),(4,5,1),(5,4,1),(5,6,1),(5,5,0),(5,5,2)}26,21,21,31,25,2731(5,6,1)}9{(5,6,1),(4,6,1),(5,5,1),(5,6,0),(5,6,2)}31,25,26,30,3232(5,6,2)10{(5,6,2),(4,6,2),(5,5,2),(5,6,1),(5,6,0)}32,26,27,31,3032(5,6,2)爬山法是求的局部极值，如果该山只有一个山峰，肯定会到达山峰，此时为全局最高。如果山峰不止一个，那么使用爬山法爬山的时候，很可能会爬到一个小山峰，发现周围没有比它更高的了，从而停止爬山，陷入局部最高。求最小值可以采取下山法，即每次都找比当前的函数值小的点.练习：有函数y=x1+x2-x3，x1是区间[-2,5]中的整数，x2是区间[2,6]中的整数，x3是区间[-5,2]中的整数。使用爬山法，找到使得y取值最小的解。假设初值为[3,5,2]。1.2.5牛顿法求一元函数的极值使用牛顿法求一元函数f(x)的极值问题可以转化为求例5已知x为正数，则当x为多少时，取得极小值，精度要为10-4。解：此时驻点为迭代公式为取初值为0.5最后两次迭代得到的x2，x3误差的绝对值为0.00003，小于设定的阈值0.0001。因此当x为0.57735时，函数取得极小值。精确值为迭代的轮数i输出值对应的函数值绝对误差10.58333-1.38480.000120.57738-1.38490.000030.57735-1.3849

1.2.6

梯度下降法当我们站在只有一个山峰的山峰上想下山时，到底向哪个方向走才能使得我们以最短的路程下山。必须选择合适的方向。若想走最短的路程就能到达山脚，此时应沿最陡峭的方向迈出，以此类推，直至到达山脚。步伐不易太大，控制不好容易错过山脚，步伐也不宜太小，花费的时间太长。梯度表示的是函数在空间某个点处的各个维度的陡峭程度，即导数或者说是变化率。梯度的方向是函数增长最快的方向，梯度的反方向是函数减少最快的方向一元函数的梯度代表的是图像斜率的变化，指明哪里下山最快。而多元函数中，梯度代表的是向量，变化最快的地方，即最陡峭的方向，指明哪个方向上下山最快。除了下山的方向以外，还有下山的步长问题。当然，步长太大很容易越过最优值而产生振荡，计算量相对较小。而步长太小则计算量大，耗时长，但比较精准，可以确定一个合适的步长能够顺利的以最快的速度下山。当然最好的步长是先大步下山，在山的最低处小步，不断逼近最低处。还要确定一个阈值，使得迭代满足条件时即可停止循环。使用梯度下降法求函数的最小值的步骤如下：（1）给出x的初值和步长（学习率）。

（2）给出迭代公式：取初值为10，学习率为1，多次迭代后，虽然一直在移动，但始终在-10到10之间摆动，没有达到最小值。如果将学习率调大到一个较大值，比如1.05，多次迭代后，不仅不会降到最低点，甚至还会越走越高。如果将学习率调低到一个较小值，比如0.02，每次迭代后，位置确实是在降低，但降低的幅度比较小，迭代很多次都没到达谷底附近。将学习率调0.2,迭代10次后，基本就能降到谷底了例2

求函数

的最小值。（1）给出x的初值，不妨设x0=0。

（2）步长取为0.25第六次迭代的结果为-0.9844，第七次迭代的结果为-0.9922，第八次迭代的结果为-0.9961，第九次迭代的结果为-0.9980。下表列出了为了保证前后两次迭代结果的绝对误差小于0.001，所需要的迭代次数学习率（步长）0.20.250.30.40.50.60.01迭代次数1297715150

当步长为0.6时，迭代了5次，就能保证前后两次迭代结果的绝对误差小于0.001，此时观察迭代的5次结果：-1.2，-0.96，-1.008，-0.9984，-1.00032。会发现结果在x=1附近左右摆动，这就是步长过大的后果。例3函数为初值为（-3.5，-3.5），步长为0.1迭代公式为迭代后的位置为迭代公式为每次迭代后的位置为将终止条件设为梯度值小于等于0.01

,则迭代到第16次时满足要求

练习：使用梯度下降法求二元函数的近似根。选取值为(2,2)，学习率α=0.3。解：当(x,y）=(1,0)。二元函数取得最小值，为0一元线性回归为例，使用梯度下降法求出回归直线的系数，设回归直线方程为损失函数为迭代公式为梯度下降法求非凸函数的极值时容易陷入局部极值。Himmelblau

函数为研究参数的初始值对梯度下降方向的影响，从而得到不同的局部极小值问题。#使用梯度下降法求极值fromsympyimportsymbols,diffdeff(x0,y0):#求偏导数x,y=symbols('xy',real=True)w=(x**2+y-11)**2+(x+y**2-7)**2#多元函数求y的偏导z1=diff(w,x)z2=diff(w,y)#计算多元函数在（x0,y0）处的对y求的偏导数值t1=z1.subs({x:x0,y:y0})t2=z2.subs({x:x0,y:y0})returnt1,t2x0=-2y0=2alpha=0.01N=200foriinrange(N):t1,t2=f(x0,y0)x=x0-alpha*t1y=y0-alpha*t2ifabs(x-x0)<0.0001andabs(y-y0)<0.0001:breakw=(x**2+y-11)**2+(x+y**2-7)**2print('迭代次数',i,x,y,w)x0=xy0=y（1）初值为（4，0），学习率为0.01。迭代次数403.58435656457706-1.847340116977268.94196357084690e-6迭代次数413.58437714467867-1.847565604085264.54980137716182e-6迭代次数423.58439182652081-1.847726465814552.31459740917551e-6迭代次数433.58440229925460-1.847841210029871.17734540386876e-6得到的极小值为0，此时（x,y）=(3.584,-1.848)。（2）初值为（1，0），学习率为0.01。迭代次数343.000304854740261.999263460014638.16758031668205e-6迭代次数353.000226534902991.999452789602494.50889819277735e-6迭代次数363.000168321649021.999593466230322.48885923320543e-6迭代次数373.000125059614651.999697985890661.37371054938081e-6得到的极小值为0，此时（x,y）=(3,2)。（3）初值为（-4，0），学习率为0.01。迭代次数23-3.77633205246572-3.278372081512020.00113132534456683迭代次数24-3.77843175894933-3.281769893844869.81480389323343e-5迭代次数25-3.77905283736059-3.282770480787788.44619901285985e-6迭代次数26-3.77923471937618-3.283064321923477.25107549614849e-7得到的极小值为0，此时（x,y）=(-3.779,-3.283)。（4）初值为（-2，2），学习率为0.01。迭代次数6-2.802748532216473.131000752803190.0001