最优化方法第三章)课件.ppt

1、第3章线性搜索与信赖域方法本章内容v3.1 线性搜索v3.2 0.618 法和Fibonacci法v3.3 逐次插值逼近法v3.4 精确线性搜索方法的收敛性v3.5 不精确线性搜索方法v3.6 信赖域方法的思想和算法框架v3.7 信赖域方法的收敛性v3.8 解信赖域子问题3.1 线性搜索 线性搜索是多变量函数最优化方法的基础，在多变量函数最优化中，迭代格式为 其关键是构造搜索方向dk和步长因子k.设 从xk出发,沿搜索方向dk,确定步长因子k,使 的问题就是关于的线性搜索问题kkkkdxx1)()(kkdxf)0()(k 理想的方法是使目标函数沿方向dk达到极小,即使得 或者选取k0使得 这样

2、的线性搜索称为精确线性搜索,所得到的k叫精确步长因子)(min)(0kkkkkdxfdxf0)(|0minkTkkkddxf线性搜索算法分成两个阶段 第一阶段确定包含理想的步长因子(或问题最优解)的搜索区间 第二阶段采用某种分割技术或插值方法缩小这个区间 进退法 确定初始搜索区间的一种简单方法叫进退法,其基本思想是从一点出发,按一定步长,试图确定出函数值呈现“高低高”的三点 即(a)(c)(b)这里acbaacb 具体地说,就是给出初始点00,初始步长h00,若 则下一步从新点1=0+h0出发,加大步长,再向前搜索,直到目标函数上升为止.若 则下一步仍以0为出发点,沿反方向同样搜索,直到目标函

3、数上升就停止.这样便得到一个搜索区间.这种方法叫进退法.)()(000 h)()(000 h进退法步骤 算法3.1.1 步1.选取初始数据.00,),h00,加倍系数t 1(一般取t=2),计算 ,k=0.步2.比较目标函数值.令 ,计算 ,若 ,转步3,否则转步4.步3.加大搜索步长,令 转步2)(0kkkh1)(11kkkk111:,:,:kkkkkthh1:,:1kkkk 步4.反向搜索.若k=0,转换搜索方向,令 转步2;否则,停止迭代,令 输出a,b,停止.11:,:kkkhh,min,min11kkba线性搜索方法分类 线性搜索方法根据是否采用导数信息分为无导数方法和导数方法.由于

4、没有利用导数信息,无导数方法一般没有导数方法有效 典型的无导数方法0.618 法和Fibonacci法3.2 0.618法和Fibonacci法 0.618法和Fibonacci(斐波那契)法都是分割方法.基本思想：通过取试探点和进行函数值的比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近极小值,从而各点可以看作为极小点的近似.这类方法仅需计算函数值,不涉及导数,又称直接法 这些方法要求所考虑区间上的目标函数是单峰函数 如果这个条件不满足,我们可以把所考虑的区间分成若干个小区间,在每个小区间上函数是单峰的.这样,我们在每个小区间上求极小点,然后选取其中

5、的最小点f(x)xab单峰函数单峰函数定义：如果函数定义：如果函数f(x)在区间在区间a,b上只有上只有一个极值点一个极值点,则称则称f(x)为为 a,b上的上的单峰函数单峰函数。连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非单峰函数非单峰函数单峰函数具有一个重要的消去性质单峰函数具有一个重要的消去性质定理：定理：设设f(x)是区间是区间a,b上的一个单峰函数，上的一个单峰函数，x*a,b是其极小是其极小点，点，x1 和和x2是是a,b上的任意两点，且上的任意两点，且ax1 x2b，那么，那么比较比较f(x1)与与f(

6、x2)的值后，可得出如下结论：的值后，可得出如下结论：f(x)xab(I)消去消去a,x1 x*x1x2f(x)xab(II)消去消去x2,bx*x2x1(II)若若f(x1)f(x2),x*a,x2在单峰函数的区间内，计算两个点的函数值，比较大小后，就在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，如再计算另一点的函数值，比较后就可进一步缩小搜索区间如再计算另一点的函数值，比较后就可进一步缩小搜索区间。（I）若若f(x1)f(x2)，x*x1,b3.2.1 0.618法v 要介绍

7、黄金分割法有必要回顾一下古老的黄金分割问题所谓黄金分割就是将一线段分为二段的方法这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段L-x的比值(如图)v于是v则v解得v由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍v因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割xLxxL022LLxxLLx618.0215 设包含极小点*的初始搜索区间为a,b,设 在a,b 上是凸函数.0.618 法的基本思想是在搜索区间a,b 上选取两个对称点,且,通过比较这两点处的函数值()和()的大小来决定删除左半区间a,),还是删除右半区间

8、(,b 删除后的新区间长度是原区间长度的0.618倍.新区间包含原区间中两个对称点中的一点,我们只要再选一个对称点,并利用这两个新对称点处的函数值继续比较.重复这个过程,最后确定出极小点*)()(kkdxf现在提出一个问题，就在a,b 上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间a,b选二点t1,t2等价于将区间长度b-a进行黄金分割，也就是将第一个搜索点t1取在a,b 的0.618处，第二个搜索点t2取成t1的对称点即 的0.382处(如图所示)v即要求v接着计算 与 的值，并根据 与 的值的大小关系分情况讨论：v（1）若 ,说明 是好点，于是把区间 划掉，保

9、留 ，则 内有一保留点 ，置新的区间 ；v（2）若 ，说明 是好点，于是应将 划 掉，保 留 ,则 内 有 保 留 点 ,置 新 的 区间 .)(618.01abat)(382.02abat)(1t)(2t)(1t)(2t)()(21tt1t,2ta,2bt,2bt1t112,a btb)()(21tt2t,1bt,1ta,1ta2t111,a ba tv(3)若 则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉 和 仅保留中间的 重置新的区间 v 接下来是在留下的区间 内找好点重复上面的步骤，直到搜索区间 小于给定的允许误差 为止。v这样就得到黄金分割法迭代算法：12(

10、)(),tt,2ta,1bt,12tt1121,a btt,11ba,iiba0v已知 ，常数 0.382，终止限 v(1)确定 的初始搜索区间 v(2计算 v(3)计算 v(4)若 ,则打印 ，停机；否则，转(5)v(5)判别是否满足 ：若满足，则置 ，然后转(3)；否则，置 然后转(4)(t)(t,ba)()(222tabat，1211()tabtt，221*ttt2122121at tt，11212222()()bt tttabat，|21tt算法3.2.1(0.618 法计算步骤)*,t 开 始 确 定 a,b(51)/2 2()tba 22()12tabt 11()t 2212btt

11、t*12()/2ttt*()t 结 束 N Y N Y 12tt 11212,attt222(),()tbat 12 黄金分割法算法流程如图所示12例 用黄金分割法求函数f(x)=x2-x+2在区间-1,3上的极小值,要求区间长度不大于原始区间长的0.08.迭代次数a,bx1x2f1f2|b-a|,故要继续迭代.这时迭代点t1比插值内点t0好,又t1=0.9t0=2,令 a1:=a0=0,b1:=t0=2,t1:=t1=0.9 第二次迭代:(a1)=2,(b1)=4,(t1)=0.029.代入公式(3.3.4)求得 t2=0.82759.由于 (t2)=0.08405(t1)=0.029,并且

12、|t2-t1|=0.07241,要继续迭代.因t2=0.82759t1=0.9,故令 a2:=t2=0.82759,b2:=b1=2,t2:=t1=0.9 第三次迭代:(a2)=0.08405,(b2)=4,(t2)=0.029.代入公式(3.3.4)求得 t3=0.96577.由于 (t3)=0.00347(t2)=0.82759,并且|t3-t2|=0.06577,要继续迭代.因t3=0.96577t2=0.82759,故令 a3:=t2=0.82759,b3:=b2=2,t3:=t3=0.96577.第四次迭代:(a3)=0.029,(b3)=4,(t3)=0.00347.代入公式(3.

13、3.4)求得 t4=0.98308.由于 (t4)=0.00086(t3)=0.00347,并且|t4-t3|=0.01731,停止迭代输出近似最优解t4=0.98308.两点二次插值法()给出不同的两点1,2,函数值(1),(2),及导数值(1)或(2),构造二次插值多项式 (3.3.6)取q()的极小点为()的极小点的近似值.显然,令 得q()的极小点为 (3.3.7)cbaq2)(02)(baqab2 考虑插值条件 (3.3.8)记i=(i),i=(i),i=1,2.解方程组(3.3.8),得)(2)()()()()(1112222211211baqcbaqcbaq22121121112

14、2121121)()(2,)()(ba从而,(3.3.9)于是,我们得到如下迭代格式:)()(211)(21)()(212212111211211212112112122111ab特别,如果1=0,2=0,则(3.3.9)给出1111)(21kkkkkkkkkk0020)0()0()()0(21两点二次插值法()给出不同的两点1,2,函数值(1),及导数值(1),(2),构造二次插值多项式.要求插值多项式满足插值条件)(2)()(2)()()(21211111211baqbaqcbaq 令i=(i),i=(i),i=1,2.类似于前面的讨论可以得到 上式可写成迭代格式 上式也称为割线公式121

15、2112ab111kkkkkkk三次插值法 类似上面的讨论,考虑利用k-1,k 及(k-1),(k-1),(k),(k)构造三次多项式,并求这个三次多项式的局部极小点可得 其中 2)()()()(211211uuukkkkkkk2/112121111)()()()(3)()(kkkkkkkkuuu3.4 精确线性搜索方法的收敛性 通常,采用精确线性搜索的无约束最优化算法的一般形式如下:步1.给出 步2.计算 如果 ,停止.步3.计算下降方向dk.步4.计算步长因子k,使得 步5.令 ,转步2.0:,10,0kRxn)(kxf)(kxf)(min)(0kkkkkdxfdxfkkkkdxx1 令

16、则显然有 如前所述,在精确线性搜索中,我们往往选取()的一个平稳点,即选取k使得)()(kkdxf)0()(),()0(kxf0,0)(|minkTkkkddxf算法的收敛性 设k=表示向量dk与-gk之间的夹角,即 定理3.4.2 设dk是下降方向,k是精确线性搜索的步长因子.若存在常数M0,使得对所有 0 则kkkTkkgdgdcoskMdxfkk,)(2kkkkkkgMdxfxfcos21)()(证明 由假设可知对任意0有 令 由于k是精确线性搜索步长因子,故有 222221)()(21)()(kkTkkkkkTkkTkkkkdMdgxfddxfddgxfdxf2kkTkdMdgkkkk

17、kTkkkkTkkkTkkkkkkkkgMdgdggMdMdgdMdgdxfxfdxfxf2222222222cos21)(21)(2121)()()()(定理3.4.3 设梯度g(x)在水平集L=xRn|f(x)f(x0)上存在且一致连续,采用精确线性搜索的极小化算法3.4.1产生的方向dk与-gk的夹角k满足 对某个 则或者对某个有限的k有gk=0,或者f(xk)-,或者gk02k0 证明 假定对所有k,gk0,f(xk)下有界.由于f(xk)单调下降,故极限存在,因而 (3.4.9)现在用反证法证明结论.假定gk0不成立,则存在常数0和一个子序列使得gk.从而 (3.4.10)又 (3.

18、4.11)0)()(1kkxfxf1sincosdefkkkkTkgddg)()()()()()()(kkkkTkkkkTkkkTkkkTkkkkggddgdxfdggdgxfdgxfdxf 其中 在 与 之间.由于g在水平集L上一致连续,故存在,使得当 时,(3.4.12)依次利用(3.4.11),(3.4.12)和(3.4.10)得 从而由精确线性搜索可得 这与(3.4.9)矛盾.从而有gk0.kkxkkdxkd0121)(kkgg1121)()21()()(kkkTkkkkkxfddgxfddxf1121)()()(kkkkkxfddxfxf3.5 不精确线性搜索方法 前面介绍的几种线性

19、搜索方法求的精确极小点,花费的计算量较大.一般地,在迭代过程中,没有必要把线性搜索搞得十分精确.特别是当迭代点离目标函数的最优解尚远时,过分追求线性搜索的精度反而会降低整个算法的效率.另外,一些最优化方法,例如牛顿法和拟牛顿法,其收敛速度并不依赖于精确的一维搜索过程.因此,我们可以放松对k的精确度要求,只要求目标函数在迭代的每一步都有充分的下降即可,这样可以大大节省工作量3.5.1 Goldstein 准则 Goldstein准则为 (3.5.1)(3.5.2)dk 当前点处的下降方向 当前点处的梯度方向k是搜索的步长因子kTkkkkkkkTkkkkkkdgxfdxfdgxfdxf)1()()

20、()()(Tkg210 上式中第一个不等式是充分下降条件 第二个不等式保证了k不会取得太小,因为当k 取得太小时,算法前进很慢 若设()=f(xk+dk),则(3.5.1)和(3.5.2)可以分别写成 (3.5.3)(3.5.4)0()1()0()()0()0()(kkkkkTkkkkkkkTkkkkkkdgxfdxfdgxfdxf)1()()()()(Goldstein准则的搜索步骤 步1.选取初始数据.在初始搜索区间0,+)(或0,max)中取定初始点0,计算(0),(0),给出(0,0.5),t1,k:=0.步2.检验准则(3.5.3).计算(k).若(k)(0)+k(0),转步3;否则

21、,令ak+1:=ak,bk+1:=k,转步4.步3.检验准则(3.5.4).若 (k)(0)+(1-)k(0),停止迭代,输出k;否则,令ak+1:=k,bk+1:=bk.若bk+1+(或max),转步4;否则,令k+1:=tk,k:=k+1,转步2.步4.k+1:=(ak+1+bk+1)/2,k:=k+1,转步2.3.5.2 Wolfe 准则 在Goldstein 准则中,(3.5.2)的一个缺点是可能把()=f(xk+dk)的极小点排除在可接受区间之外.为了克服这个缺点,同时保证k不是太小,Wolfe提出了下面的条件代替(3.5.2)(3.5.5)即 (3.5.6)1,(,1kTkkTkd

22、gdg)0()0()()(kTkkTkkkkdgddxg 其几何解释是在可接受点处切线的斜率(k)大于或等于初始斜率的倍.这个条件也叫做曲率条件.这样,充分下降条件和曲率条件一起构成了Wolfe准则:(3.5.7)(3.5.8)其中,0 1.kTkkTkkkkTkkkkkkdgddxgdgxfdxf)()()(强Wolfe准则 (3.5.9)(3.5.10)其中,0 0和子序列,其指标集为K,使得0coslimkkkg0limkkg0kTksgKkssgkkTk,于是,由(3.5.7),又由于f(xk)单调下降,因而是收敛的,故sk|kK收敛到零.又由(3.5.8),因此,由于sk|kK收敛到零,故由g(x)在水平集上一致连续知上式右边趋于零,从而产生矛盾.这样,(3.5.20)得证.kkkTkkkksssgsxfxf)()()(10,)()(1(ksgsxgsgkTkkkkTkKkgsxgssgkkkkkTk,)(11 进一步,若夹角条件(3.5.15)满足,则存在一个正数使得 (3.5.22)(3.5.20)和(3.5.22)立即给出(3.5.21).kk,0cos