常用的无约束搜索方法 王琥 wanghu@hnu.edu.cn 湖南大学 机械与运载工程学院 汽车车身先进设计制造国家重点实验室.

Presentation on theme: "常用的无约束搜索方法 王琥 wanghu@hnu.edu.cn 湖南大学 机械与运载工程学院 汽车车身先进设计制造国家重点实验室."— Presentation transcript:

1 常用的无约束搜索方法 王琥 湖南大学 机械与运载工程学院 汽车车身先进设计制造国家重点实验室

2 搜索算法的结构 一、下降算法模型 考虑（fs） 常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算： 其中dk为第 k+1 次迭代的搜索方向，λk为沿dk搜索的最佳步长因子（通常也称作最佳步长）。 min f(x) s.t. x∈S

3 搜索算法的结构 下降方向： 设 ∈S, d ∈Rn,d≠0,若存在 使 , 称d 为 在 点的下降方向。 可行方向：
同时满足上述两个性质的方向称下降可行方向

4 算法流程 初始x(1) ∈S, k =1 对x(k)点选择下降 3 可行方向d(k) 1 k=k+1 5 线性搜索求 新点
使x(k+1)∈S no 是否满足收敛条件？ yes 停

5 收敛性 考虑（fs） min f(x) 设迭代算法产生点列{x(k)} S. s.t. x∈S
概念： 考虑（fs） 设迭代算法产生点列{x(k)} S. 理想的收敛性：设x*∈S是 g.opt(全局最优解).当x*∈ {x(k)} 或 x(k) ≠ x*, 满足 时，称算法收敛到最优解 x*。 min f(x) s.t. x∈S

6 收敛性 对于实际的工程而言，全局收敛的条件较为苛刻。因此，定义了较为实用的收敛条件 S* = { x | x 具有某种性质 }
例：S*={x|x---g.opt} S*={x|x---l.opt} S*={x| f(x)=0} S*={x|f(x)≤β } (β为给定的实数，称为阈值)

7 收敛速度 设算法产生点列{x(k)}，收敛到解x*，且x(k)≠x*， k，关于算法的收敛速度，有 线性收敛： 当k充分大时成立。
超线性收敛： 二阶收敛：   ﹥0，是 使当k充分大时有

8 收敛速度 定理：设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*， k，那么 证明：只需注意
| ||x(k+1) –x* || -|| x(k) –x* || |≤ ||x(k+1) –x(k) || ≤ ||x(k+1) –x* || +|| x(k) –x* || ，除以|| x(k) –x* || 并令k→∞,利用超线性收敛定义可得结果。 该结论导出算法的停止条件可用：

9 常用的一维搜索算法 已知 并且求出了 处的可行下降方向 从 出发, 沿方向 求如下目标函数的最优解, 或者选取 使得：

10 常用的一维搜索算法 设其最优解为 （叫精确步长因子）， 于是得到一个新点： 所以线性搜索是求解一元函数 的最优化问 题（也叫一维最优化问题或
一维搜索）。 一般地，一维优化问题可描述为： 或解

11 主要介绍的搜索方法 搜索区间的确定 黄金分割法(0.618法) 二次插值法 Newton法 1、直接法：迭代过程中只需要计算函数值；
2、微分法：迭代过程中还需要计算目标函数的导数；

12 搜索区间的确定 常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满足精度要求为止。 单峰函数 定义：如果函数f(x)在区间[a,b]上只有一个极值点, 则称f(x)为[a, b]上的单峰函数。 f(x) x a b 连续单峰函数

13 搜索区间的确定 单峰函数具有一个重要的消去性质
定理：设f(x)是区间[a,b]上的一个单峰函数, x*∈[a,b]是其极小点， x1 和x2是[a, b]上的任意两点, 且a<x1 <x2<b，那么比较f(x1)与f(x2)的值后, 可得出如下结论： f(x) x a b (I) 消去[a, x1 ] x* x1 x2 (II) 消去[x2, b] (II) 若f(x1) < f(x2), x*∈[a,x2] （I） 若f(x1)≥f(x2)，x*∈[x1,b] 在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间 .

14 进退方法 由单峰函数的性质可知, 函数值在极小点左边严格下降, 在右边严格上升。
从某个初始点出发, 沿函数值下降的方向前进, 直至发现函数值上升为止。由两边高，中间低的三点，可确定极小点所在的初始区间。 f(x) x a b x* x0 x1 x2

15 基本算法 1、选定初始点a 和步长h; 2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况：
则步长加倍，计算f(a+3h)。若f(a+h) ≤f(a+3h)， 令 a1=a, a2=a+3h, 停止运算；否则将步长加倍，并重复上述运算。 (1) 前进运算：若f(a) ≥f(a+h), (2) 后退运算：若f(a) < f(a+h), 则将步长改为－h。计算f(a－h), 若f(a－h) ≥ f(a)， 令 a1=a－h, a2=a+h, 停止运算；否则将步长加倍，继续后退。 f(x) x f(x) x a+h a a a+7h a+h a-h a-7h a1 b1 a1 b1 a-3h a+3h

16 主要缺陷 效率低 步长选择问题 问题的局限性

17 区间消去法－黄金分割法 消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。
消去法的优点：只需计算函数值，通用性强。 消去法的设计原则：（1）迭代公式简单；（2）消去效率高； （3）对称： x1-a = b-x2 ；（4）保持缩减比：λ=(保留的区间长度／原区间长度) 不变。（使每次保留下来的节点， x1或 x2 ，在下一次的比较中成为一个相应比例位置的节点 ）。 黄金分割 x a b L λL (1－λ)L 取 “ ＋”，λ=

18 区间消去法－黄金分割法 黄金分割法的基本思想 黄金分割重要的消去性质: 设x1,x2 为[a, b] 中对称的两个黄金分割点，
x1为[a,x2]的黄金分割点 设x1,x2 为[a, b] 中对称的两个黄金分割点， a b L x1 x2 λL (1－λ)L λL (1－λ)L x2为[x1,b]的黄金分割点 黄金分割比λ  0.618，所以此法也称为0.618法。 在进行区间消去时，不管是消去[a, x1]，还是消去[x2，b]，留下来的区间中还含一个黄金分割点，只要在对称位置找另一个黄金分割点，又可以进行下一次区间消去。

19 !!! 在迭代过程中，四个点的顺序始终应该是 a<x1 < x2 <b
开始 a b x2 x1 x1 ＋x2 = a＋b 给定a0 , b0 , a=a0 ,b= b0 , = x2 =a+(b-a), x1 =a+b－x2 f2 =f(x2), f1 =f(x1) x*∈[x1, b] x*∈[a, x2] f1 f2 !!! 在迭代过程中，四个点的顺序始终应该是 a<x1 < x2 <b x*=x2, f*=f2 是 b-x1 <  否 x*=x1, f*=f1 结束 是 是 x2 –a<  a=x1, x1= x2, f1 =f2 x2 =a+b- x1, f2 =f(x2) 否 b=x2, x2= x1, f2 =f1 x1 =a+b- x2, f1 =f(x1) 否

20 需要注意的几点… 终止限不要取得太小； 使用双精度运算； 经过若干次运算后，转到算法中的第3步，重新开始。
1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好， 对多峰函数或强扭曲的，甚至不连续的，都有效; 2、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次 插值法及牛顿－拉夫森法等比较，计算量较大，收敛要慢。

21 算例 f(x)=x2, a=-1.5, b=1;精度10-5 a x1 x2 b
e e e e-005 (x1-a)/(x2-a) (b-x2)/(b-x1) e e e e-005 e e e e-005 e e e e-005 e e e e-006 x*= e-006 若用0.618效果较差

22 二分法 设 f (x)在 [a ,b]上可微，且当导数为零时是解。 tg α<0 tg α>0 α α a x b a x b
f '(x) = 0 时, x 为最小点, x= x* ; f '(x) > 0 时, x 在上升段, x* < x，去掉[x ,b] ; f' (x) < 0 时, x 在下降段, x* > x，去掉[a, x] . α a x b tg α<0 f′ ( x ) a x b α tg α>0 f′ ( x )

23 二分法 我们知道, 在极小点 , 且 时, 递减, 即 , 而当 ，函数递增, 即 。 若找到一个区间[a, b], 满足性质 ，则
的极小点 , 且 , 为找此 , 取 , 若 ， 则在 中有极小点，这时 用 作为新的区间[a, b], 继续这个过程，逐步将区间 [a, b]缩小, 当区间[a, b]的长度充分小时, 或者当 充分小时, 即可将[a, b]的中点取做极小点的近似点, 这时有估计:

24 二分法 其中区间[a, b]的确定,一般可采用“进退法”。 假设 f(x) 是具有极小点的单峰函数，
则必存在区间[a, b]，使f '(a)<0, f '(b)>0。 由f '(x)的连续性可知，必有x*(a, b)，使f '(x)=0 f '(x) x a b a1 b1 a2 b2 优点：计算量较少，总能找到最优点 缺点：要计算导数值，收敛速度较慢，收敛速度为一阶

25 梯度法 迭代的基本公式 如何选择下降最快的方向？

26 梯度法 梯度法的基本思路 梯度法的基本步骤

27 梯度法 解：

28 梯度法 收敛性

29 梯度法的锯齿现象 最速下降法仅是算法的局部性质。对于许多问题，全局看最速下降法并非“最速下降”，而是下降的较缓慢。数值试验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快，后来由于出现“锯齿”现象，下降就比较缓慢。

30 梯度法的锯齿现象 其原因就是精确一维搜索（最优步长）满足 f(x(k+1)) T dk =0，
即 f(x(k+1)) T f(x(k)) =dk+1Tdk =0， 这表明在相邻的两个迭代点上函数f(x)的两个梯度方向是互相直交的，即，两个搜索方向互相直交，这就产生了锯齿形状。当接近极小点时，步长愈小，前进愈慢。 这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。 这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路，因此反而是不好的。

31 梯度法 例：问题： 为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发现了不少方法，如： (1) 选择不同初始点 取初点
为求 ， 沿 方向从 出发求 的极小点 即进行线搜索 则 解得

32 梯度法 然后再从 开始新的迭代，经过10次迭代，得最优解 计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点时，步长很小，目标函数值下降很慢。如果不取初点为 而取 虽然后一初点较前一初点离最优点 远，但迭代中不会出现上面的锯齿现象。这时： 可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。 一步就得到了极小点。

33 梯度法 （2）采用不精确的一维搜索：用一维搜索求出的步长为 时，我们不取 ，而用 的一个近似值作为 , 这样可使相邻两个迭代点处的梯度不正交，从而改变收敛性。 对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长λ的方法，称为固定步长最速下降法。只要λ充分小，总有： 但λ到底取多大，没有统一的标准， λ取小了，收敛太慢，而λ取大了，又会漏掉极小点。——不精确线搜索解决这个问题

34 几何意义 下面说明最速下降法收敛 性的几何意义。考虑具有对称正定矩阵的函数 其中 这个函数的等值线为 (c＞0) ，改写为：

35 几何意义 这是以 和 为半轴的橢圆，从下面的分析可见 两个特征值的相对大小决定最速下降法的收敛性。
这是以 和 为半轴的橢圆，从下面的分析可见 两个特征值的相对大小决定最速下降法的收敛性。 （1）当 时，等值线变为圆 此时 因而由上述定理知： 即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标函数时，从任意初始点出发，只需迭代一步就到了极小点。 （2）当 时, 等值线为椭圆。此时对于一般的初始点将产生锯齿现象。

36 几何意义 （3）当 ， 等值线是很扁的椭圆，此时 对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。

37 Newton法 （一）基本Newton法 设函数f(x)是二次可微函数， 又设函数x(k)是f(x)的极小点的一个
由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别好的方向，有没有更好的方向 （一）基本Newton法 设函数f(x)是二次可微函数， 又设函数x(k)是f(x)的极小点的一个 估计，我们把设函数f(x)在x(k)展成Taylor级数，并取二阶近似： 取 f(∆x; x(k))的平稳点作为f(x) 最优点的一个近似点 f(x)在x(k)处的 二次近似函数 令f (∆x; x(k)) = f (x(k))+ 2f (x(k))x = 0 设函数f(x)的Hesse矩阵可逆，由上式可得：

38 Newton法 x－ x(k) = x = －2f (x(k))－1f (x(k)) Newton法迭代公式：
x(k+1) = x(k)－2f (x(k))－1f (x(k)) 或 x(k+1) = x(k)－H(x(k))－1g(x(k)) f(x; x(k)) 这样，知道x(k)后，算出在这一点处目标函数的梯度和Hesse矩阵的逆，代入便得到后继点x(k+1) 。 －H(x(k))－1g(x(k)) x(k+1) x(k) ! 当f(x)是单变量函数时，本方法即为一维搜索的Newton法！ ! 当f(x)是二次函数时，一次迭代就可达到平稳点 ！

39 Newton法 开始 给定x(0) ,  , 令 k=0 计算g(k) =f( x(k ) ) 是 ||g(k )|| < 
x*=x(k) 是 结束 否 计算 H(x(k)) p(k) =－H(x(k))－1g(k) x(k+1) = x(k) +p(k) k=k+1

40 Newton法 例子 例 用基本Newton法求函数 f (x1, x2)＝8x12+4x1x2+5x22 的极小点。
初始点取为x(0)=[10, 10]T 。 解： f (x)＝[16x1+4x2, 4x1+10x2 ]T 2f (x)＝H(x)= H(x)－1 = － 4 － 1 144 x(1) = x(0)－H(x(0))－1f (x(0)) 10 = － ＝ － 4 － 1 144 200 140 因为f(x)是二次函数，所以一步迭代就达到平稳点，又因为H(x(1))是正定矩阵，所以x(1)是极小点。

41 Newton法 例子 例：用Newton法求 的极小点。 解：取初点 则： 代入Newton迭代公式得： 此即为问题的最优点

42 Newton法的几点说明 1、基本Newton法要求Hesse矩阵具有逆矩阵。
如果H(x(k))是正定的，则H(x(k))－1必存在，从而算法是可行的，并且保证求得 的平稳点是极小点。 然而在迭代过程中要求H(x(k))是正定的这一条件不一定能保证，只有当初始 点合适时才能满足。一般在极小点附近的Hesse矩阵容易为正定的。 所以基本Newton法在极小点附近才比较有效。 2、 Newton法的搜索方向－H (x)－1f (x)不一定是下降方向。 因为若是下降方向，则应有f (x)T[－H (x)－1f (x)]<0，即 f (x)TH (x)－1f (x)>0，但由于H (x)－1不一定是正定的，所以上式不一定成立。

43 Newton法的几点说明 3、Newton法的最大优点是：当初始点选得合适时收敛很快，具有二阶收敛速度，是目前讲过的算法中最快的一种，且不需一维搜索。 对初始点要求高，一般要求初始点离极小点较近，否则不收敛。有时即使是收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。 4、方向－H (x)－1f (x)称为Newton方向，是一个好方向，对二次函数此方向直指平稳点。 对于目标函数是二次函数的无约束优化问题，从任意初始点出发，利用Newton法一步迭代即可得到最优解，也就是Newton法具有二次终止性。

44 沿Newton方向一维搜索得到的最优步长
固定的步长因子不能保证目标函数有合理的改善，甚至不能保证算法下降，因此有必要对牛顿算法作一些改进，一个最直接的改进是：在牛顿算法中加入一维搜索。 修正(阻尼)Newton法 修正Newton迭代公式： x(k+1) = x(k)－ tk H(x(k))－1f (x(k)) 沿Newton方向一维搜索得到的最优步长 保证了 f(x(k+1)) ≤f(x(k)) ， 且不必要求H(x)为正定矩阵。 ? 出现 (1) H(x(k)) －1不存在；或(2) tk =0 时怎么办 ？ 改用最速下降法 ，即 p(k) =－ f (x(k)) 修正Newton法与基本Newton法的优点是： 收敛快，程序简单。前者更实用可靠。 缺点：要求计算Hesse矩阵及其逆矩阵，计算量大，尤其当维数n较大时。

45 要求计算导数的插值法 优缺点 1、优点：收敛速度快；在f'(x)=0的单根处，是2阶收敛；在f'(x)=0的重根处，是线性收敛。
2、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛 速度； 收敛性还依赖于初始点及函数性质。 f ’(x) x !!! 通常在计算程序中规定最大迭代次数，当次数达到K还不能满足精度时， 则认为不收敛，要换一个初始点。

46 要求计算导数的插值法 二点二次插值 三次插值 割线法——基本思想：用割线代替Newton法中的切线，并与区间消去法相结合。
a f ’(x) x b 割线法——基本思想：用割线代替Newton法中的切线，并与区间消去法相结合。 c x* 三次插值 基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值） 构造一个三次多项式P3(x)，用P3(x)的极小点近似目标函数的极小点x*