优化算法和梯度下降法ppt课件

局部优化算法之一：梯度下降法,李金屏济南大学信息科学与工程学院2006年9月,1,12,2,优化算法和运筹学,优化算法许多实际问题利用数学建模的方法得到下面常规的优化形式：minf(x)，s.t.g(x)0,xD.其中，x是一个n维矢量，D是问题的定义域，F可行域。关于f(x)：当x=(x)时，f(x)是一条曲线；当x=(x1,x2)时，f(x1,x2)是一个曲面；当x=(x1,x2,x3)时，f(x1,x2,x3)是一个体密度（或类位势函数）；当x=(x1,x2,xn)时，f(x1,x2,xn)是一个超曲面。,12,3,优化算法和运筹学,曲面，自然有许多极大值和极小值，必然各有一个全局最大值和全局最小值。超曲面，与上相同。有些算法，只能在自己的小范围内搜索极大值或极小值。这些算法称为局部优化算法，常称为经典优化算法。另有些算法，可以在整个超曲面取值范围内搜索最大值或最小值。这些算法称为全局性优化算法，又称为现代优化算法。,12,4,优化算法和运筹学,一个简单二维曲面,通常的运筹学，就是经典的局部优化算法。全局性优化算法通常是随机性搜索。,12,5,局部优化算法之一：梯度下降法,见右图。局部极小值是C点（x0）。梯度，即导数，但是有方向，是一个矢量。曲线情况下，表达式为,如果，f(x)0，则x增加，y也增加，相当于B点；如果f(x)0，则x增加，y减小，相当于A点。要搜索极小值C点，在A点必须向x增加方向搜索，此时与A点梯度方向相反；在B点必须向x减小方向搜索，此时与B点梯度方向相反。总之，搜索极小值，必须向负梯度方向搜索。,12,6,局部优化算法之一：梯度下降法,一般情况下分析：y=f(x1,x2,xn)假设只有一个极小点。初始给定参数为（x10,x20,xn0）。问题：从这个点如何搜索才能找到原函数的极小值点？方法：1、首先设定一个较小的正数，;2、求当前位置处的各个偏导数：dy/dx1,dy/dx2,dy/dxn;3、按照下述方式修改当前函数的参数值：x10x10dy/dx1,x20x20dy/dx2,xn0xn0dy/dxn;4、如果超曲面参数变化量小于，退出；否则返回2。,12,7,局部优化算法之一：梯度下降法,举例：y=x2/2-2x计算过程：任给一个初始出发点，设为x0=-4。(1)首先给定两个参数：=1.5，=0.01；(2)计算导数：dy/dx=x-2(3)计算当前导数值：y=-6(4)修改当前参数：x0=-4x1=x0-*y=-4-1.5*(-6)=5.0;,(5)计算当前导数值：y=3.0(6)修改当前参数：x1=5.0x2=5.01.5*(3.0)=0.5;,12,8,局部优化算法之一：梯度下降法,(7)计算当前导数值：y=-1.5(8)修改当前参数：x2=0.5x3=0.5-1.5*(-1.5)=2.75;(9)计算当前导数值：y=0.75(10)修改当前参数：x3=2.75x4=2.75-1.5*(0.75)=1.625;(11)计算当前导数值：y=-0.375,(12)修改当前参数：x4=1.625x5=1.625-1.5*(-0.375)=2.1875;,12,9,局部优化算法之一：梯度下降法,可见，当=1.5时，搜索呈现振荡形式，在极值点附近反复搜索。可以证明，当2.0时，搜索将围绕极值点逐渐发散，不会收敛到极值点。为了保证收敛，不应当太大。但如果过小，收敛速度将十分缓慢。可以采用自适应调节的方法加快收敛而又不至于发散。问题：为何当很小时搜索总会成功？证明：（下页）,12,10,局部优化算法之一：梯度下降法,y=f(x1,x2,xn)。假设只有一个极小点。假设当前点为(x1,x2,xn)。下面修改当前参数：x1x1+x1,x2x2+x2,xnxn+xn.显然问题在于xi(i=1,2,n)的确定。于是，当前函数值为y=f(x1+x1,x2+x2,xn+xn).可以按照泰勒级数展开为：y=f(x1,x2,xn)+f其中f=x1*(dy/dx1)+x2*(dy/dx2)+xn*(dy/dxn)如何保证f0是个小的正数。代入前式，有f=-*(dy/dx1)*(dy/dx1)-*(dy/dx2)*(dy/dx2)-*(dy/dxn)*(dy/dxn)=-*(dy/dx1)2+(dy/dx2)2+(dy/dxn)20即f0。这样就可以保证搜索到极小值。于是获得梯度下降法的搜索策略：x1=-*(dy/dx1),x2=