最优化方法第三章课件_第1页
最优化方法第三章课件_第2页
最优化方法第三章课件_第3页
最优化方法第三章课件_第4页
最优化方法第三章课件_第5页
已阅读5页,还剩175页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第3章线性搜索与信赖域方法第3章线性搜索与信赖域方法1本章内容3.1线性搜索3.20.618法和Fibonacci法3.3逐次插值逼近法3.4精确线性搜索方法的收敛性3.5不精确线性搜索方法3.6信赖域方法的思想和算法框架3.7信赖域方法的收敛性3.8解信赖域子问题本章内容3.1线性搜索2§3.1线性搜索

线性搜索是多变量函数最优化方法的基础,在多变量函数最优化中,迭代格式为

其关键是构造搜索方向dk和步长因子αk.设

从xk出发,沿搜索方向dk,确定步长因子αk,使

的问题就是关于α的线性搜索问题§3.1线性搜索线性搜索是多变量函数最优化方法的基础3

理想的方法是使目标函数沿方向dk达到极小,即使得

或者选取αk>0使得

这样的线性搜索称为精确线性搜索,所得到的αk叫精确步长因子理想的方法是使目标函数沿方向dk达到极小,即使得4线性搜索算法分成两个阶段第一阶段确定包含理想的步长因子(或问题最优解)的搜索区间第二阶段采用某种分割技术或插值方法缩小这个区间线性搜索算法分成两个阶段第一阶段确定包含理想的步长因子5进退法

确定初始搜索区间的一种简单方法叫进退法,其基本思想是从一点出发,按一定步长,试图确定出函数值呈现“高低高”的三点

即φ(a)≥φ(c)≤φ(b)这里a≤c≤bacb进退法确定初始搜索区间的一种简单方法叫进退6

具体地说,就是给出初始点α0>0,初始步长h0>0,若

则下一步从新点α1=α0+h0出发,加大步长,再向前搜索,直到目标函数上升为止.

则下一步仍以α0为出发点,沿反方向同样搜索,直到目标函数上升就停止.这样便得到一个搜索区间.这种方法叫进退法.具体地说,就是给出初始点α0>0,初始步长h0>0,7进退法步骤

算法3.1.1

步1.选取初始数据.α0∈[0,∞),h0>0,加倍系数t>1(一般取t=2),计算,k=0.

步2.比较目标函数值.令,计算,若

,转步3,否则转步4.

步3.加大搜索步长,令

转步2

进退法步骤算法3.1.18

步4.反向搜索.若k=0,转换搜索方向,令转步2;否则,停止迭代,令

输出[a,b],停止.步4.反向搜索.若k=0,转换搜索方向,令9线性搜索方法分类

线性搜索方法根据是否采用导数信息分为无导数方法和导数方法.由于没有利用导数信息,无导数方法一般没有导数方法有效

典型的无导数方法0.618法和Fibonacci法线性搜索方法分类线性搜索方法根据是否采用导数信息分为无10§3.20.618法和Fibonacci法

0.618法和Fibonacci(斐波那契)法都是分割方法.

基本思想:通过取试探点和进行函数值的比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近极小值,从而各点可以看作为极小点的近似.这类方法仅需计算函数值,不涉及导数,又称直接法§3.20.618法和Fibonacci法0.61811

这些方法要求所考虑区间上的目标函数是单峰函数如果这个条件不满足,我们可以把所考虑的区间分成若干个小区间,在每个小区间上函数是单峰的.这样,我们在每个小区间上求极小点,然后选取其中的最小点这些方法要求所考虑区间上的目标函数是单峰函数12f(x)xab单峰函数定义:如果函数f(x)在区间[a,b]上只有一个极值点,则称f(x)为[a,b]上的单峰函数。

连续单峰函数f(x)xab不连续单峰函数f(x)xab离散单峰函数f(x)xab非单峰函数f(x)xab单峰函数定义:如果函数f(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)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]单峰函数具有一个重要的消去性质定理:设f(x)是区间[a,b143.2.10.618法一、黄金分割法基本原理要介绍黄金分割法有必要回顾一下古老的黄金分割问题.所谓黄金分割就是将一线段分为二段的方法.这样分后,要求整段长L与较长段x的比值正好等于较长段x与较短段L-x的比值(如图)3.2.10.618法一、黄金分割法基本原理15于是则解得由此可见长段的长度应为全长的0.618倍,而短段的长度应为全长的0.382倍.因为古代的人们认为按0.618的比率来分割线段是最协调,胜似黄金,故称之为黄金分割.于是16设包含极小点α*的初始搜索区间为[a,b],设

在[a,b]上是凸函数.

0.618法的基本思想是在搜索区间[a,b]上选取两个对称点λ,μ且λ<μ,通过比较这两点处的函数值φ(λ)和φ(μ)的大小来决定删除左半区间[a,λ),还是删除右半区间(μ,b]

删除后的新区间长度是原区间长度的0.618倍.

新区间包含原区间中两个对称点中的一点,我们只要再选一个对称点,并利用这两个新对称点处的函数值继续比较.重复这个过程,最后确定出极小点α*设包含极小点α*的初始搜索区间为[a,b],设17现在提出一个问题,就在[a,b]上如何选取二点使得迭代次数最小而区间缩短最快?要解决这个问题,人们想到对区间[a,b]选二点t1,t2等价于将区间长度b-a进行黄金分割,也就是将第一个搜索点t1取在[a,b]的0.618处,第二个搜索点t2取成t1的对称点即的0.382处(如图所示)黄金分割法迭代步骤现在提出一个问题,就在[a,b]上如何选取二点使得迭代次数18即要求接着计算与的值,并根据与的值的大小关系分情况讨论:(1)若,说明是好点,于是把区间划掉,保留,则内有一保留点,置新的区间;(2)若,说明是好点,于是应将划掉,保留,则内有保留点,置新的区间..即要求19(3)若则应具体分析,看极小点可能在哪一边再决定取舍,在一般情况下,可同时划掉和仅保留中间的重置新的区间.接下来是在留下的区间内找好点.重复上面的步骤,直到搜索区间小于给定的允许误差为止。这样就得到黄金分割法迭代算法:(3)若则应具体分析,看极小20已知,常数0.382,终止限.(1)确定的初始搜索区间.(2计算.(3)计算.(4)若,则打印,停机;否则,转(5).(5)判别是否满足:若满足,则置,然后转(3);否则,置然后转(4).算法3.2.1(0.618法计算步骤)已知,常数0.382,终止限.算法3.221黄金分割法算法流程如图所示黄金分割法算法流程如图所示22例

用黄金分割法求函数f(x)=x2-x+2在区间[-1,3]上的极小值,要求区间长度不大于原始区间长的0.08.例用黄金分割法求函数f(x)=x2-x+2在区间[-1,323迭代次数[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.554迭代次数[a,b]x1x2f1f2|b-a|<e0[-1,3242510/28/2022定义:

TheFibonaccinumbers

斐波那契数{fn

}=0,1,1,2,3,5,8,13,21,34,55,…

TheFibonaccinumberscanbedefined斐波那契数可被定义为:f0=0f1=1f

n=f

n-1+f

n-2for

n=2,3,4,…斐波那契数2510/22/2022定义:TheFibonacci253.2.2Fibonacci法

另一种与0.618法相类似的分割方法叫Fibonacci法.它与0.618法的主要区别之一在于:搜索区间长度的缩短率不是采用0.618而是采用Fibonacci数.Fibonacci数列满足Fibonacci法中的计算公式为3.2.2Fibonacci法另一种与0.61826

显然,这里相当于黄金分割法中的τ,每次缩短率满足

这里n是计算函数值的次数,即要求经过n次计算函数值后,最后区间的长度不超过δ,即最优化方法第三章)课件27由于故有从而

(3.2.15)由于28

给出最终区间长度的上界δ,由(3.2.15)求出Fibonacci数Fn,再根据Fn确定出n,从而搜索一直进行到第n个搜索点为止Fibonacci算法与0.618法几乎完全相同,可以证明

这表明,当n→∞时,Fibonacci法与0.618法的区间缩短率相同,因而Fibonacci法也以收敛比τ线性收敛.Fibonacci法是分割方法求一维极小化问题的最优策略,而0.618法是近似最优的,但由于0.618法简单易行,因而得到广泛应用.给出最终区间长度的上界δ,由(3.2.15)求29

一、对分法基本原理求解一维最优化问题一般可先确定它的一个有限搜索区间,把问题化为求解问题,然后通过不断缩短区间的长度,最后求得最优解.3.2.3二分法(对分法)一、对分法基本原理3.2.3二分法(对分法)30

设在已获得的搜索区间内具有连续的一阶导数.因为在上可微,故在上连续,由此知在上有最小值.令,总可求得极小点.不妨设在上是单减函数;在上是单增函数.所以时,,故;当时,亦即.对分法的原理如图.设在已获得的搜索区间31二、对分法迭代步骤已知,表达式,终止限.(1)确定初始搜索区间,要求(2)计算的中点.(3)若,则,转(4);若,则,转(5);若,则,转(4).(4)若,则,转(5);否则转(2).(5)打印,停机.二、对分法迭代步骤32Y开始确定[ab],要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示Y开始确定[ab],要求c=(a+b)/2b=ct*=(a33三、对分法有关说明对分法每次迭代都取区间的中点

a.若这点的导数值小于零,说明的根位于右半区间中,因此去掉左半区间;b.若中点导数值大于零,则去掉右半区间;c.若中点导数值正好等于零,则该点就是极小点.因为每次迭代都使原区间缩短一半,所以称为对分法或二分法.三、对分法有关说明34Newton切线法

一、Newton切线法基本原理设在已获得的搜索区间内具有连续二阶导数,求.因为在上可微,故在上有最小值,令.Newton切线法一、Newton切线法基本原理35下面不妨设在区间中经过次迭代已求得方程的一个近似根.过作曲线的切线,其方程是

然后用这条切线与横轴交点的横坐标作为根的新的近似(如图).它可由上面方程在令的解出来,即

这就是Newton切线法迭代公式.

下面不妨设在区间中经过次迭代已求得36二、Newton切线法迭代步骤已知,表达式,终止限.(1)确定初始搜索区间,要求(2)选定.(3)计算.(4)若,则,转(3);否则转(5).(5)打印,停机.二、Newton切线法迭代步骤37Newton切线法的计算流程如图所示Newton切线法的计算流程如图所示38

三、Newton切线法有关说明这种方法一旦用好,收敛速度是很高的.如果初始点选得适当,通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点:第一,需要求二阶导数.如果在多维最优化问题的一维搜索中使用这种方法,就要涉及Hesse矩阵,一般是难于求出的.三、Newton切线法有关说明39第二,当曲线在上有较复杂的弯曲时,这种方法也往往失效.如图(a)所示的迭代:结果跳出.迭代或者发散,或者找到的根并不是我们想要的结果.第三,即使曲线比较正常,在中或者上凹或者下凹,初始点的选取也必须适当.在图(b)的情况下,曲线上凹,应选点b作为初始点;而在图(c)的情况下,曲线下凹,应选点a为初始点.否则都可能失败.第二,当曲线在上有较复40§3.3逐次插值逼近法

在求一元函数的极小点问题上,我们可以利用若干点处的函数值来构造一个多项式,用这个多项式的极小点作为原来函数极小点的近似值.插值法就是一个用二次函数来逼近f(x)的方法,这也是我们常说的二次插值法.

三点二次插值法和二点二次插值法§3.3逐次插值逼近法在求一元函数的极小点问题上,我41三点二次插值法

在包含的极小点α*的搜索区间[a0,b0]中,给定三点α1,α2,α3满足(3.3.1)(3.3.2)

利用三点处的函数值构造二次函数,并要求插值条件满足

(3.3.3)三点二次插值法在包含的极小点α*的搜索区42q(a)a1a2a3q(a)a1a2a343

令.解上述方程组得

于是,二次函数q(α)的极小点为

(3.3.4)令.解上述方程组得44

上式称为三点二次插值公式

求得以后,如果,当时

或者如果,当时

则我们认为收敛准则满足

如果,则极小点估计为,否则为α2.这里通常取ε1=10-3,ε2=10-5

若终止准则不满足,则利用提供的信息,从α1,α2,α3和中选出相邻的三个点,将原来的搜索区间例如[α1,α3]缩小上式称为三点二次插值公式45算法3.3.1(1)比较和的大小,如果,则转2);否则转3)(2)如果,则转4);否则,,转4)(3)如果,则转4);否则,,转4)(4)区间收缩完毕,然后在新的搜索区间[α1,α3]上按公式(3.3.4)计算二次插值函数的极小点算法3.3.1(1)比较和的大小,如果46插值法的优缺点优点:收敛速度较快,约为1.3阶

缺点:对强扭曲或多峰的,收敛慢,甚至会失败,故要求函数具有较好的解析性能插值法的优缺点优点:收敛速度较快,约为1.3阶

47

例3.3.2

用二次插值法求的近似最优解(精确极小点为t*=1).设已确定其初始搜索区间为[0,3],取初始插值点t0=2,终止误差ε=0.05

解:a0=a=0,b0=b=3

第一次迭代:

代入公式(3.3.4)求得t1=0.9

例3.3.2用二次插值法求48由于φ(t1)=0.029≤φ(t0)=4,并且|t1-t0|=1.1>ε,故要继续迭代.这时迭代点t1比插值内点t0好,又t1=0.9≤t0=2,令a1:=a0=0,b1:=t0=2,t1:=t1=0.9

由于49第二次迭代:φ(a1)=2,φ(b1)=4,φ(t1)=0.029.代入公式(3.3.4)求得t2=0.82759.由于φ(t2)=0.08405≥φ(t1)=0.029,并且|t2

-t1|=0.07241>ε,要继续迭代.因t2=0.82759≤t1=0.9,故令a2:=t2=0.82759,b2:=b1=2,t2:=t1=0.9第二次迭代:50

第三次迭代:φ(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.96577≥t2=0.82759,故令a3:=t2=0.82759,b3:=b2=2,t3:=t3=0.96577.第三次迭代:51第四次迭代:φ(a3)=0.029,φ(b3)=4,φ(t3)=0.00347.代入公式(3.3.4)求得t4=0.98308.由于φ(t4)=0.00086≤φ(t3)=0.00347,并且|t4-t3|=0.01731<ε,停止迭代输出近似最优解t4=0.98308.第四次迭代:52两点二次插值法(Ⅰ)

给出不同的两点α1,α2,函数值φ(α1),φ(α2),及导数值φ’(α1)或(φ’(α2)),构造二次插值多项式

(3.3.6)

取q(α)的极小点为φ(α)的极小点的近似值.显然,令

得q(α)的极小点为(3.3.7)两点二次插值法(Ⅰ)给出不同的两点α1,α2,函数值53

考虑插值条件

(3.3.8)

记φi=φ(αi),φ’i=φ’(αi),i=1,2.解方程组(3.3.8),得考虑插值条件54从而,(3.3.9)

于是,我们得到如下迭代格式:从而,55特别,如果α1=0,α2=α0,则(3.3.9)给出最优化方法第三章)课件56两点二次插值法(Ⅱ)

给出不同的两点α1,α2,函数值φ(α1),及导数值φ’(α1),φ’(α2),构造二次插值多项式.要求插值多项式满足插值条件两点二次插值法(Ⅱ)给出不同的两点α1,α2,函数值57

令φi=φ(αi),φ’i=φ’(αi),i=1,2.类似于前面的讨论可以得到

上式可写成迭代格式

上式也称为割线公式令φi=φ(αi),φ’i=φ’(αi),i=58三次插值法

类似上面的讨论,考虑利用αk-1,αk及φ(αk-1),φ′(αk-1),φ(αk),φ′(αk)构造三次多项式,并求这个三次多项式的局部极小点可得

其中三次插值法类似上面的讨论,考虑利用αk-1,α59§3.4精确线性搜索方法的收敛性

通常,采用精确线性搜索的无约束最优化算法的一般形式如下:

步1.给出

步2.计算如果,停止.

步3.计算下降方向dk.

步4.计算步长因子αk,使得步5.令

,转步2.§3.4精确线性搜索方法的收敛性通常,采用精确线性60

则显然有

如前所述,在精确线性搜索中,我们往往选取φ(α)的一个平稳点,即选取αk使得令61算法的收敛性

设θk=<dk,-gk>表示向量dk与-gk之间的夹角,即

定理3.4.2设dk是下降方向,αk是精确线性搜索的步长因子.若存在常数M>0,使得对所有α>0

则算法的收敛性设θk=<dk,-gk>表示向量dk与-62

证明由假设可知对任意α>0有令

由于αk是精确线性搜索步长因子,故有

证明由假设可知对任意α>0有63最优化方法第三章)课件64

定理3.4.3

设梯度g(x)在水平集L={x∈Rn|f(x)≤f(x0)}上存在且一致连续,采用精确线性搜索的极小化算法3.4.1产生的方向dk与-gk的夹角θk满足对某个

则或者对某个有限的k有gk=0,或者f(xk)→-∞,或者gk→0定理3.4.3设梯度g(x)在水平集L={x∈Rn|65证明假定对所有k,gk≠0,f(xk)下有界.由于{f(xk)}单调下降,故极限存在,因而(3.4.9)

现在用反证法证明结论.假定gk→0不成立,则存在常数ε>0和一个子序列使得‖gk‖≥ε.从而(3.4.10)又(3.4.11)证明假定对所有k,gk≠0,f(xk)下有界66

其中在与之间.由于g在水平集L上一致连续,故存在,使得当时,(3.4.12)

依次利用(3.4.11),(3.4.12)和(3.4.10)得

从而由精确线性搜索可得

这与(3.4.9)矛盾.从而有gk→0.其中在与之间67§3.5不精确线性搜索方法

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

Goldstein准则为(3.5.1)(3.5.2)dk当前点处的下降方向当前点处的梯度方向αk是搜索的步长因子3.5.1Goldstein准则Goldstein准则69

上式中第一个不等式是充分下降条件第二个不等式保证了αk不会取得太小,因为当αk

取得太小时,算法前进很慢上式中第一个不等式是充分下降条件70

若设φ(α)=f(xk+αdk),则(3.5.1)和(3.5.2)可以分别写成(3.5.3)(3.5.4)若设φ(α)=f(xk+αdk),则(3.5.1)71Goldstein准则的搜索步骤步1.选取初始数据.在初始搜索区间[0,+∞)(或[0,αmax])中取定初始点α0,计算φ(0),φ’(0),给出ρ∈(0,0.5),t>1,k:=0.

步2.检验准则(3.5.3).计算φ(αk).若φ(αk)≤φ(0)+αkφ’(0),转步3;否则,令ak+1:=ak,bk+1:=αk,转步4.Goldstein准则的搜索步骤步1.选取初始数据.72

步3.检验准则(3.5.4).若φ(αk)≥φ(0)+(1-ρ)αkφ’(0),停止迭代,输出αk;否则,令ak+1:=αk,bk+1:=bk.若bk+1<+∞(或αmax),转步4;否则,令αk+1:=tαk,k:=k+1,转步2.

步4.αk+1:=(ak+1+bk+1)/2,k:=k+1,转步2.步3.检验准则(3.5.4).若733.5.2Wolfe准则

在Goldstein准则中,(3.5.2)的一个缺点是可能把φ(α)=f(xk+αdk)的极小点排除在可接受区间之外.为了克服这个缺点,同时保证αk不是太小,Wolfe提出了下面的条件代替(3.5.2)(3.5.5)即

(3.5.6)3.5.2Wolfe准则在Goldstein准则74

其几何解释是在可接受点处切线的斜率φ’(αk)大于或等于初始斜率的σ倍.这个条件也叫做曲率条件.这样,充分下降条件和曲率条件一起构成了Wolfe准则:(3.5.7)(3.5.8)

其中,0<ρ<σ<1.其几何解释是在可接受点处切线的斜率φ’(αk)大于或等75强Wolfe准则

(3.5.9)(3.5.10)

其中,0<ρ<σ<1.这样,当σ→0时,(3.5.10)的极限便是精确线性搜索.

一般地,σ愈小,线性搜索愈精确.不过,σ愈小,工作量愈大.而不精确线性搜索不要求过小的σ,通常取ρ=0.1,σ∈[0.6,0.8].强Wolfe准则76Wolfe准则的步骤

步1.选取初始数据.给定初始搜索区间令,计算,取步2.计算.若,转步3;否则,由二次步插值公式(3.3.10)计算令转步2Wolfe准则的步骤步1.选取初始数据.给定初始搜索77

步3.计算.若,则令,输出,停;否则,由二次插值公式(3.3.13)计算:令转步2步3.计算783.5.3Armijo准则

设dk是f(x)在xk处的下降方向,给定设mk是使得下述不等式(3.5.11)

成立的最小非负整数,则令

(3.5.12)

由于dk是下降方向,当m充分大时,不等式(3.5.11)总是成立的,因此上述mk总是存在的3.5.3Armijo准则设dk是f(x)在xk处的79

由于mk是使得不等式(3.5.11)成立的最小非负整数,因而αk

不会太小,从而保证了目标函数f(x)的充分下降.实际上,(3.5.11)就是充分下降条件

(3.5.13)

如果上式满足,则终止搜索;否则,我们可以缩小αk,或者在区间[0,αk]上用二次插值公式(3.3.11)求近似极小点

将其作为新的αk,这是一个插值法与充分下降条件组合起来的线性搜索方法.由于mk是使得不等式(3.5.11)成立的最小非负整数80总结一维搜索的方法利用导数的方法仅用函数值的方法二分法精确方法不精确方法Fibonacci方法黄金分割法求初始区间的方法进退法二次插值法Goldstein算法Wolfe算法Armijo算法总结一维搜索的方法利用导数的方法仅用函数值的方法二分法精确方813.5.4不精确线性搜索的收敛性

为了保证方法的下降性,我们要求避免搜索方向sk=αkdk和负梯度方向-gk几乎直交的情形,即要求sk偏离-gk的正交方向远一点.否则sk几乎不是下降方向

我们假定sk和-gk的夹角θk满足其中定义为3.5.4不精确线性搜索的收敛性为了保证方法的下降性82不精确线性搜索准则的一般下降算法的形式步1.给出步2.如果,则停止;否则,求出下降方向dk,使其满足

步3.利用Goldstein准则(3.5.1)-(3.5.2)或Wolfe准则(3.5.7)-(3.5.8)求出步长因子αk.

步4.令,转步2.不精确线性搜索准则的一般下降算法的形式步1.给出83

引理3.5.4设函数f(x)连续可微,梯度g(x)满足Lipschitz连续条件(3.5.17)

如果下有界,,则对满足Wolfe准则(3.5.7)(3.5.8)的任何均有(3.5.18)

证明由Lipschitz条件和(3.5.8)得即(3.5.19)

引理3.5.4设函数f(x)连续可微,梯度g(x)84

利用(3.5.7)和(3.5.19),有

不精确线性搜索在单步中至少下降的界.

两个定理分别讨论采用不精确线性搜索Goldstein准则和Wolfe准则的一般下降算法的总体收敛性利用(3.5.7)和(3.5.19),有85

定理3.5.5

设在算法3.5.3中采用Goldstein准则(3.5.1)(3.5.2)求步长因子

,并设夹角条件(3.5.15)满足.如果g(x)存在,且在水平集{x|f(x)≤f(x0)}上一致连续,那么,或者对某个k,有gk=0,或者f(xk)→-∞,或者gk→0.

证明假定f(xk)下有界,同时对所有的k,由此得到sk≠0和f(xk)-f(xk+1)→0.因此,由(3.5.1)得到

今假定不成立,则存在和一个子列使得.由于,故定理3.5.5设在算法3.5.3中采用Goldste86因而但Taylor公式给出其中ξk位于线段(xk,xk+1)上.由g(x)的一致连续性,当sk→0时,g(ξk)→gk.这样,由此有这与(3.5.2)矛盾.因此gk→0最优化方法第三章)课件87

定理3.5.6

设f:Rn→R在Rn上连续可微和下有界.g(x)在水平集Ω={x|f(x)≤f(x0)}上一致连续.设不精确线性搜索方法采用Wolfe准则(3.5.7)(3.5.8),则(3.5.20)

如果夹角条件(3.5.15)满足,则(3.5.21)

证明由于,又由于f下有界,因此序列{xk}是有定义的,且在水平集Ω中.

现在用反证法证明(3.5.20).假定(3.5.20)不成立,则存在ε>0和子序列,其指标集为K,使得定理3.5.6设f:Rn→R在Rn上连续可微和下有界88于是,由(3.5.7),

又由于{f(xk)}单调下降,因而是收敛的,故{sk|k∈K}收敛到零.

又由(3.5.8),

因此,

由于{sk|k∈K}收敛到零,故由g(x)在水平集上一致连续知上式右边趋于零,从而产生矛盾.这样,(3.5.20)得证.于是,由(3.5.7),89

进一步,若夹角条件(3.5.15)满足,则存在一个正数δ使得(3.5.22)(3.5.20)和(3.5.22)立即给出(3.5.21).进一步,若夹角条件(3.5.15)满足,则存在一个90第3章线性搜索与信赖域方法第3章线性搜索与信赖域方法91本章内容3.1线性搜索3.20.618法和Fibonacci法3.3逐次插值逼近法3.4精确线性搜索方法的收敛性3.5不精确线性搜索方法3.6信赖域方法的思想和算法框架3.7信赖域方法的收敛性3.8解信赖域子问题本章内容3.1线性搜索92§3.1线性搜索

线性搜索是多变量函数最优化方法的基础,在多变量函数最优化中,迭代格式为

其关键是构造搜索方向dk和步长因子αk.设

从xk出发,沿搜索方向dk,确定步长因子αk,使

的问题就是关于α的线性搜索问题§3.1线性搜索线性搜索是多变量函数最优化方法的基础93

理想的方法是使目标函数沿方向dk达到极小,即使得

或者选取αk>0使得

这样的线性搜索称为精确线性搜索,所得到的αk叫精确步长因子理想的方法是使目标函数沿方向dk达到极小,即使得94线性搜索算法分成两个阶段第一阶段确定包含理想的步长因子(或问题最优解)的搜索区间第二阶段采用某种分割技术或插值方法缩小这个区间线性搜索算法分成两个阶段第一阶段确定包含理想的步长因子95进退法

确定初始搜索区间的一种简单方法叫进退法,其基本思想是从一点出发,按一定步长,试图确定出函数值呈现“高低高”的三点

即φ(a)≥φ(c)≤φ(b)这里a≤c≤bacb进退法确定初始搜索区间的一种简单方法叫进退96

具体地说,就是给出初始点α0>0,初始步长h0>0,若

则下一步从新点α1=α0+h0出发,加大步长,再向前搜索,直到目标函数上升为止.

则下一步仍以α0为出发点,沿反方向同样搜索,直到目标函数上升就停止.这样便得到一个搜索区间.这种方法叫进退法.具体地说,就是给出初始点α0>0,初始步长h0>0,97进退法步骤

算法3.1.1

步1.选取初始数据.α0∈[0,∞),h0>0,加倍系数t>1(一般取t=2),计算,k=0.

步2.比较目标函数值.令,计算,若

,转步3,否则转步4.

步3.加大搜索步长,令

转步2

进退法步骤算法3.1.198

步4.反向搜索.若k=0,转换搜索方向,令转步2;否则,停止迭代,令

输出[a,b],停止.步4.反向搜索.若k=0,转换搜索方向,令99线性搜索方法分类

线性搜索方法根据是否采用导数信息分为无导数方法和导数方法.由于没有利用导数信息,无导数方法一般没有导数方法有效

典型的无导数方法0.618法和Fibonacci法线性搜索方法分类线性搜索方法根据是否采用导数信息分为无100§3.20.618法和Fibonacci法

0.618法和Fibonacci(斐波那契)法都是分割方法.

基本思想:通过取试探点和进行函数值的比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近极小值,从而各点可以看作为极小点的近似.这类方法仅需计算函数值,不涉及导数,又称直接法§3.20.618法和Fibonacci法0.618101

这些方法要求所考虑区间上的目标函数是单峰函数如果这个条件不满足,我们可以把所考虑的区间分成若干个小区间,在每个小区间上函数是单峰的.这样,我们在每个小区间上求极小点,然后选取其中的最小点这些方法要求所考虑区间上的目标函数是单峰函数102f(x)xab单峰函数定义:如果函数f(x)在区间[a,b]上只有一个极值点,则称f(x)为[a,b]上的单峰函数。

连续单峰函数f(x)xab不连续单峰函数f(x)xab离散单峰函数f(x)xab非单峰函数f(x)xab单峰函数定义:如果函数f(x)在区间[a,b]103单峰函数具有一个重要的消去性质定理:设f(x)是区间[a,b]上的一个单峰函数,x*∈[a,b]是其极小点,x1和x2是[a,b]上的任意两点,且a<x1<x2<b,那么比较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]单峰函数具有一个重要的消去性质定理:设f(x)是区间[a,b1043.2.10.618法一、黄金分割法基本原理要介绍黄金分割法有必要回顾一下古老的黄金分割问题.所谓黄金分割就是将一线段分为二段的方法.这样分后,要求整段长L与较长段x的比值正好等于较长段x与较短段L-x的比值(如图)3.2.10.618法一、黄金分割法基本原理105于是则解得由此可见长段的长度应为全长的0.618倍,而短段的长度应为全长的0.382倍.因为古代的人们认为按0.618的比率来分割线段是最协调,胜似黄金,故称之为黄金分割.于是106设包含极小点α*的初始搜索区间为[a,b],设

在[a,b]上是凸函数.

0.618法的基本思想是在搜索区间[a,b]上选取两个对称点λ,μ且λ<μ,通过比较这两点处的函数值φ(λ)和φ(μ)的大小来决定删除左半区间[a,λ),还是删除右半区间(μ,b]

删除后的新区间长度是原区间长度的0.618倍.

新区间包含原区间中两个对称点中的一点,我们只要再选一个对称点,并利用这两个新对称点处的函数值继续比较.重复这个过程,最后确定出极小点α*设包含极小点α*的初始搜索区间为[a,b],设107现在提出一个问题,就在[a,b]上如何选取二点使得迭代次数最小而区间缩短最快?要解决这个问题,人们想到对区间[a,b]选二点t1,t2等价于将区间长度b-a进行黄金分割,也就是将第一个搜索点t1取在[a,b]的0.618处,第二个搜索点t2取成t1的对称点即的0.382处(如图所示)黄金分割法迭代步骤现在提出一个问题,就在[a,b]上如何选取二点使得迭代次数108即要求接着计算与的值,并根据与的值的大小关系分情况讨论:(1)若,说明是好点,于是把区间划掉,保留,则内有一保留点,置新的区间;(2)若,说明是好点,于是应将划掉,保留,则内有保留点,置新的区间..即要求109(3)若则应具体分析,看极小点可能在哪一边再决定取舍,在一般情况下,可同时划掉和仅保留中间的重置新的区间.接下来是在留下的区间内找好点.重复上面的步骤,直到搜索区间小于给定的允许误差为止。这样就得到黄金分割法迭代算法:(3)若则应具体分析,看极小110已知,常数0.382,终止限.(1)确定的初始搜索区间.(2计算.(3)计算.(4)若,则打印,停机;否则,转(5).(5)判别是否满足:若满足,则置,然后转(3);否则,置然后转(4).算法3.2.1(0.618法计算步骤)已知,常数0.382,终止限.算法3.2111黄金分割法算法流程如图所示黄金分割法算法流程如图所示112例

用黄金分割法求函数f(x)=x2-x+2在区间[-1,3]上的极小值,要求区间长度不大于原始区间长的0.08.例用黄金分割法求函数f(x)=x2-x+2在区间[-1,3113迭代次数[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.554迭代次数[a,b]x1x2f1f2|b-a|<e0[-1,311411510/28/2022定义:

TheFibonaccinumbers

斐波那契数{fn

}=0,1,1,2,3,5,8,13,21,34,55,…

TheFibonaccinumberscanbedefined斐波那契数可被定义为:f0=0f1=1f

n=f

n-1+f

n-2for

n=2,3,4,…斐波那契数2510/22/2022定义:TheFibonacci1153.2.2Fibonacci法

另一种与0.618法相类似的分割方法叫Fibonacci法.它与0.618法的主要区别之一在于:搜索区间长度的缩短率不是采用0.618而是采用Fibonacci数.Fibonacci数列满足Fibonacci法中的计算公式为3.2.2Fibonacci法另一种与0.618116

显然,这里相当于黄金分割法中的τ,每次缩短率满足

这里n是计算函数值的次数,即要求经过n次计算函数值后,最后区间的长度不超过δ,即最优化方法第三章)课件117由于故有从而

(3.2.15)由于118

给出最终区间长度的上界δ,由(3.2.15)求出Fibonacci数Fn,再根据Fn确定出n,从而搜索一直进行到第n个搜索点为止Fibonacci算法与0.618法几乎完全相同,可以证明

这表明,当n→∞时,Fibonacci法与0.618法的区间缩短率相同,因而Fibonacci法也以收敛比τ线性收敛.Fibonacci法是分割方法求一维极小化问题的最优策略,而0.618法是近似最优的,但由于0.618法简单易行,因而得到广泛应用.给出最终区间长度的上界δ,由(3.2.15)求119

一、对分法基本原理求解一维最优化问题一般可先确定它的一个有限搜索区间,把问题化为求解问题,然后通过不断缩短区间的长度,最后求得最优解.3.2.3二分法(对分法)一、对分法基本原理3.2.3二分法(对分法)120

设在已获得的搜索区间内具有连续的一阶导数.因为在上可微,故在上连续,由此知在上有最小值.令,总可求得极小点.不妨设在上是单减函数;在上是单增函数.所以时,,故;当时,亦即.对分法的原理如图.设在已获得的搜索区间121二、对分法迭代步骤已知,表达式,终止限.(1)确定初始搜索区间,要求(2)计算的中点.(3)若,则,转(4);若,则,转(5);若,则,转(4).(4)若,则,转(5);否则转(2).(5)打印,停机.二、对分法迭代步骤122Y开始确定[ab],要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示Y开始确定[ab],要求c=(a+b)/2b=ct*=(a123三、对分法有关说明对分法每次迭代都取区间的中点

a.若这点的导数值小于零,说明的根位于右半区间中,因此去掉左半区间;b.若中点导数值大于零,则去掉右半区间;c.若中点导数值正好等于零,则该点就是极小点.因为每次迭代都使原区间缩短一半,所以称为对分法或二分法.三、对分法有关说明124Newton切线法

一、Newton切线法基本原理设在已获得的搜索区间内具有连续二阶导数,求.因为在上可微,故在上有最小值,令.Newton切线法一、Newton切线法基本原理125下面不妨设在区间中经过次迭代已求得方程的一个近似根.过作曲线的切线,其方程是

然后用这条切线与横轴交点的横坐标作为根的新的近似(如图).它可由上面方程在令的解出来,即

这就是Newton切线法迭代公式.

下面不妨设在区间中经过次迭代已求得126二、Newton切线法迭代步骤已知,表达式,终止限.(1)确定初始搜索区间,要求(2)选定.(3)计算.(4)若,则,转(3);否则转(5).(5)打印,停机.二、Newton切线法迭代步骤127Newton切线法的计算流程如图所示Newton切线法的计算流程如图所示128

三、Newton切线法有关说明这种方法一旦用好,收敛速度是很高的.如果初始点选得适当,通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点:第一,需要求二阶导数.如果在多维最优化问题的一维搜索中使用这种方法,就要涉及Hesse矩阵,一般是难于求出的.三、Newton切线法有关说明129第二,当曲线在上有较复杂的弯曲时,这种方法也往往失效.如图(a)所示的迭代:结果跳出.迭代或者发散,或者找到的根并不是我们想要的结果.第三,即使曲线比较正常,在中或者上凹或者下凹,初始点的选取也必须适当.在图(b)的情况下,曲线上凹,应选点b作为初始点;而在图(c)的情况下,曲线下凹,应选点a为初始点.否则都可能失败.第二,当曲线在上有较复130§3.3逐次插值逼近法

在求一元函数的极小点问题上,我们可以利用若干点处的函数值来构造一个多项式,用这个多项式的极小点作为原来函数极小点的近似值.插值法就是一个用二次函数来逼近f(x)的方法,这也是我们常说的二次插值法.

三点二次插值法和二点二次插值法§3.3逐次插值逼近法在求一元函数的极小点问题上,我131三点二次插值法

在包含的极小点α*的搜索区间[a0,b0]中,给定三点α1,α2,α3满足(3.3.1)(3.3.2)

利用三点处的函数值构造二次函数,并要求插值条件满足

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论