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