局部优化算法之一： 梯度下降法 李金屏 济南大学信息科学与工程学院 2006年9月.

Presentation on theme: "局部优化算法之一： 梯度下降法 李金屏 济南大学信息科学与工程学院 2006年9月."— Presentation transcript:

1 局部优化算法之一： 梯度下降法 李金屏 济南大学信息科学与工程学院 2006年9月

2 优化算法和运筹学 优化算法 许多实际问题利用数学建模的方法得到下面常规的优化形式： min f(x)，s.t. g(x) ≥0, x∈D.
其中，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) 假设只有一个极小点。初始给定参数为
从这个点如何搜索才能找到原函数的极小值点？ 方法： 1、首先设定一个较小的正数，; 2、求当前位置处的各个偏导数：dy/dx1, dy/dx2, …, dy/dxn; 3、按照下述方式修改当前函数的参数值： x10x10   dy/dx1, x20x20   dy/dx2, …, xn0xn0   dy/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=-4  x1= x0 - *y’ =-4-1.5*(-6)=5.0; (5) 计算当前导数值：y’=3.0 (6) 修改当前参数： x1=5.0  x2=5.0 – 1.5*(3.0) =0.5; 12

8 局部优化算法之一：梯度下降法 (7) 计算当前导数值： y’=-1.5 (8) 修改当前参数：
x2=0.5x3= *(-1.5) =2.75; (9) 计算当前导数值：y’=0.75 (10) 修改当前参数： x3=2.75 x4 = *(0.75) =1.625; (11) 计算当前导数值： y’=-0.375 (12) 修改当前参数：x4=1.625 x5 = *(-0.375)=2.1875; … 12

9 局部优化算法之一：梯度下降法 可见，当=1.5时，搜索呈现振荡形式，在极值点附近反复搜索。可以证明，当<1.0时，搜索将单调地趋向极值点，不会振荡；当>2.0时，搜索将围绕极值点逐渐发散，不会收敛到极值点。 为了保证收敛，不应当太大。但如果过小，收敛速度将十分缓慢。可以采用自适应调节的方法加快收敛而又不至于发散。 问题：为何当很小时搜索总会成功？ 证明：（下页） 12

10 局部优化算法之一：梯度下降法 y=f (x1, x2, …, xn)。假设只有一个极小点。
x1x1+x1, x2x2+x2, …, xnxn+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) 如何保证f<0? (搜索极小值) 12

11 局部优化算法之一：梯度下降法 可以按照下述方式： x1= - *(dy/dx1), x2= - *(dy/dx2), …,
xn= - *(dy/dxn). 其中>0是个小的正数。代入前式，有 f = - *(dy/dx1)*(dy/dx1) - *(dy/dx2)*(dy/dx2) - … - *(dy/dxn)*(dy/dxn) = - *[(dy/dx1)2 + (dy/dx2)2 + (dy/dxn)2] <0 即f<0。这样就可以保证搜索到极小值。 于是获得梯度下降法的搜索策略： 12

12 总结和作业 局部优化算法之一：梯度下降法 用于BP神经网络，Hopfield神经网络，模式分类，求函数极值等。 相关内容：共轭梯度法 12