最优化方法第三章

第3章线性搜索与信赖域方法本章内容3.1线性搜索3.20.618法和Fibonacci法3.3逐次插值逼近法3.4精确线性搜索方法的收敛性3.5不精确线性搜索方法3.6信赖域方法的思想和算法框架3.7信赖域方法的收敛性3.8解信赖域子问题§3.1线性搜索线性搜索是多变量函数最优化方法的基础，在多变量函数最优化中，迭代格式为其关键是构造搜索方向dk和步长因子αk.设从xk出发,沿搜索方向dk,确定步长因子αk,使的问题就是关于α的线性搜索问题kkkkdxx1)()(kkdxf)0()(k理想的方法是使目标函数沿方向dk达到极小,即使得或者选取αk0使得这样的线性搜索称为精确线性搜索,所得到的αk叫精确步长因子)(min)(0kkkkkdxfdxf}0)(|0min{kTkkkddxf线性搜索算法分成两个阶段第一阶段确定包含理想的步长因子(或问题最优解)的搜索区间第二阶段采用某种分割技术或插值方法缩小这个区间进退法确定初始搜索区间的一种简单方法叫进退法,其基本思想是从一点出发,按一定步长,试图确定出函数值呈现“高低高”的三点即φ(a)≥φ(c)≤φ(b)这里a≤c≤bacb具体地说,就是给出初始点α00,初始步长h00,若则下一步从新点α1=α0+h0出发,加大步长,再向前搜索,直到目标函数上升为止.若则下一步仍以α0为出发点,沿反方向同样搜索,直到目标函数上升就停止.这样便得到一个搜索区间.这种方法叫进退法.)()(000h)()(000h进退法步骤算法3.1.1步1.选取初始数据.α0∈[0,∞),h00,加倍系数t1(一般取t=2),计算,k=0.步2.比较目标函数值.令,计算,若,转步3,否则转步4.步3.加大搜索步长,令转步2)(0kkkh1)(11kkkk111:,:,:kkkkkthh1:,:1kkkk步4.反向搜索.若k=0,转换搜索方向,令转步2;否则,停止迭代,令输出[a,b],停止.11:,:kkkhh},min{},,min{11kkba线性搜索方法分类线性搜索方法根据是否采用导数信息分为无导数方法和导数方法.由于没有利用导数信息,无导数方法一般没有导数方法有效典型的无导数方法0.618法和Fibonacci法§3.20.618法和Fibonacci法0.618法和Fibonacci(斐波那契)法都是分割方法.基本思想：通过取试探点和进行函数值的比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近极小值,从而各点可以看作为极小点的近似.这类方法仅需计算函数值,不涉及导数,又称直接法这些方法要求所考虑区间上的目标函数是单峰函数如果这个条件不满足,我们可以把所考虑的区间分成若干个小区间,在每个小区间上函数是单峰的.这样,我们在每个小区间上求极小点,然后选取其中的最小点f(x)xab单峰函数定义：如果函数f(x)在区间[a,b]上只有一个极值点,则称f(x)为[a,b]上的单峰函数。连续单峰函数f(x)xab不连续单峰函数f(x)xab离散单峰函数f(x)xab非单峰函数单峰函数具有一个重要的消去性质定理：设f(x)是区间[a,b]上的一个单峰函数，x*∈[a,b]是其极小点，x1和x2是[a,b]上的任意两点，且ax1x2b，那么比较f(x1)与f(x2)的值后，可得出如下结论：f(x)xab(I)消去[a,x1]x*x1x2f(x)xab(II)消去[x2,b]x*x2x1(II)若f(x1)f(x2),x*∈[a,x2]在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，如再计算另一点的函数值，比较后就可进一步缩小搜索区间。（I）若f(x1)≥f(x2)，x*∈[x1,b]3.2.10.618法一、黄金分割法基本原理要介绍黄金分割法有必要回顾一下古老的黄金分割问题．所谓黄金分割就是将一线段分为二段的方法．这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段L-x的比值(如图)于是则解得由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍．因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割．xLxxL022LLxxLLx618.0215设包含极小点α*的初始搜索区间为[a,b],设在[a,b]上是凸函数.0.618法的基本思想是在搜索区间[a,b]上选取两个对称点λ,μ且λμ,通过比较这两点处的函数值φ(λ)和φ(μ)的大小来决定删除左半区间[a,λ),还是删除右半区间(μ,b]删除后的新区间长度是原区间长度的0.618倍.新区间包含原区间中两个对称点中的一点,我们只要再选一个对称点,并利用这两个新对称点处的函数值继续比较.重复这个过程,最后确定出极小点α*)()(kkdxf现在提出一个问题，就在[a,b]上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间[a,b]选二点t1,t2等价于将区间长度b-a进行黄金分割，也就是将第一个搜索点t1取在[a,b]的0.618处，第二个搜索点t2取成t1的对称点即的0.382处(如图所示)黄金分割法迭代步骤即要求接着计算与的值，并根据与的值的大小关系分情况讨论：（1）若,说明是好点，于是把区间划掉，保留，则内有一保留点，置新的区间；（2）若，说明是好点，于是应将划掉，保留,则内有保留点,置新的区间．.)(618.01abat)(382.02abat)(1t)(2t)(1t)(2t)()(21tt1t],[2ta],[2bt],[2bt1t112[,][,]abtb)()(21tt2t],[1bt],[1ta],[1ta2t111[,][,]abat(3)若则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉和仅保留中间的重置新的区间．接下来是在留下的区间内找好点．重复上面的步骤，直到搜索区间小于给定的允许误差为止。这样就得到黄金分割法迭代算法：12()(),tt],[2ta],[1bt],[12tt1121[,][,]abtt],[11ba],[iiba0已知，常数0.382，终止限．(1)确定的初始搜索区间．(2计算．(3)计算．(4)若,则打印，停机；否则，转(5)．(5)判别是否满足：若满足，则置，然后转(3)；否则，置然后转(4)．)(t)(t],[ba)()(222tabat，1211()tabtt，221*ttt2122121attt，，11212222()()bttttabat，，，，||21tt算法3.2.1(0.618法计算步骤)**,t开始确定[a,b](51)/22()tba22()12tabt11()t2212bttt*12()/2ttt**()t结束NYNY12tt11212,,attt222(),()tbat12黄金分割法算法流程如图所示12例用黄金分割法求函数f(x)=x2-x+2在区间[-1,3]上的极小值,要求区间长度不大于原始区间长的0.08.迭代次数[a,b]x1x2f1f2|b-a|e0[-1,3]0.5281.4721.7512.695否1[-1,1.472]-0.0560.5282.0591.751否2[-0.056,1.472]0.5280.8881.7511.901否3[-0.056,0.888]0.3050.5281.7881.751否4[0.305,0.888]0.5280.6651.7511.777否5[0.305,0.665]0.4430.5281.7531.751否6[0.443,0.665]0.5280.5801.7511.757是最优解x*=(0.443+0.665)/2=0.554252020/2/23定义:TheFibonaccinumbers斐波那契数{fn}=0,1,1,2,3,5,8,13,21,34,55,…TheFibonaccinumberscanbedefined斐波那契数可被定义为：f0=0f1=1fn=fn-1+fn-2forn=2,3,4,…斐波那契数3.2.2Fibonacci法另一种与0.618法相类似的分割方法叫Fibonacci法.它与0.618法的主要区别之一在于:搜索区间长度的缩短率不是采用0.618而是采用Fibonacci数.Fibonacci数列满足Fibonacci法中的计算公式为2,1,111k10kFFFFFkk))(1(1kkknknkkabFFa显然,这里相当于黄金分割法中的τ,每次缩短率满足这里n是计算函数值的次数,即要求经过n次计算函数值后,最后区间的长度不超过δ,即1,,2,1),(1,,2,1),(111nkabFFankabFFakkknknkkkkknknkk1knknFF)(111kkknknkkabFFabnnab由于故有从而(3.2.15))(1)()(11111132211121abFabFFFFFFabFFabnnnnnnn)(1111abFn)(11abFn给出最终区间长度的上界δ,由(3.2.15)求出Fibonacci数Fn,再根据Fn确定出n,从而搜索一直进行到第n个搜索点为止Fibonacci算法与0.618法几乎完全相同,可以证明这表明,当n→∞时,Fibonacci法与0.618法的区间缩短率相同,因而Fibonacci法也以收敛比τ线性收敛.Fibonacci法是分割方法求一维极小化问题的最优策略,而0.618法是近似最优的,但由于0.618法简单易行,因而得到广泛应用.215lim1kkkFF一、对分法基本原理求解一维最优化问题一般可先确定它的一个有限搜索区间，把问题化为求解问题，然后通过不断缩短区间的长度，最后求得最优解．min()t],[ba)(mintbta3.2.3二分法(对分法)设在已获得的搜索区间内具有连续的一阶导数．因为在上可微，故在上连续，由此知在上有最小值．令，总可求得极小点．不妨设在上是单减函数；在上是单增函数．所以时，，故；当时，亦即．对分法的原理如图．0)(t*t)(t),(*ta),(*bt*(,)tat0)(t0)(a),(*btt0)(t0)(b11RR：],[ba)(t],[ba)(t],[ba)(t],[ba二、对分法迭代步骤已知，表达式，终止限．(1)确定初始搜索区间，要求(2)计算的中点．(3)若，则，转(4)；若，则，转(5)；若，则，转(4)．(4)若，则，转(5)；否则转(2)．(5)打印，停机．)(t)(t],[ba'()0'()0ab，],[ba)(21bac0)(cca0)(cct*0)(ccb||ba)(21*bat*tY开始确定[ab],要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示'()0'()0ab，0)(c()0c||ba三、对分法有关说明对分法每次迭代都取区间的中点a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正好等于零