最优化理论与算法(第二章)

1第二章一维搜索§2.1.引言一、精确与非精确一维搜索如前所述，最优化算法的迭代格式为：1kkkkxxd因而算法的关键就是选择合适的搜索方向，然后再确定步长因子k。若设()()kkfxd现在的问题是从kx出发，沿kd方向搜索，希望找到k，使得()(0)k，这就是所谓的一维搜索或称为线搜索(linesearch)问题。⑴若求得的k，使目标函数沿方向kd达到最小，即使得0()min()kkkkkfxdfxd或0()min()k，则称为最优一维搜索，或精确一维搜索。相应的k称为最优步长因子。⑵如果选取k，使目标函数获得可以接受的改善，即()()0kkkkfxfxd，则称之为近似一维搜索，或非精确一维搜索。注：精确搜索与非精确搜索在最优化算法中均广泛应用，它们存在各自的优缺点。二、一维搜索的基本框架一维搜索实际上是一元函数的极值问题，其基本的解决框架是：⑴确定包含最优解的初始搜索区间；⑵采用某些区间分割技术或插值方法不断缩小搜索区间，最后得到解。注：值得注意的是，这样得到的解大多数情况下均为近似解。因此，即便采用精确一维搜索策略，只要应用了数值方法，最终得到的结果都不一定是真正数学意义上的最佳步长因子。初始搜索区间的确定2定义2.1设:RR，*[0,)是函数()的最小值点，即*0()min()。若存在闭区间[,][0,)ab，使*[,]ab，则称[,]ab为一维极小化问题0min()的搜索区间。确定初始搜索区间的进退法基本思想：从一点出发，按一定步长探测，试图找到函数值呈高－低－高变化的三点。具体地，从初始点0出发，取初始步长为0h。若000()()h，则下一步从新点00h出发，加大步长，再向前搜索。若000()()h，则下一步仍从0出发，沿反方向搜索，直到()上升，即0()()为止。在确定了初始搜索区间后，剩下就是采用具体的一维搜索方法确定出*。后面将分别介绍几种常用的一维搜索方法，这些方法主要是针对所谓单峰函数设计的。单峰函数的定义定义2.2设:RR，[,]abR。若存在*[,]ab，使得函数()在*[,]a上单调下降，而在*[,]b上单调上升，则称[,]ab是函数()的单峰区间，()是[,]ab上的单峰函数（准确地说应是单谷函数）。单峰函数还可以等价地定义如下定义2.3如果存在唯一的*[,]ab，使得对于任意的12,[,]ab且12，有⑴若*2，则12()()；⑵若*1，则12()()。则称()是[,]ab上的单峰函数。下面定理表明，对单峰函数，可以通过简单地比较函数值，缩小搜索区间。定理2.4设()是[,]ab上的一个单峰函数，12,[,]ab，且12。⑴若12()()，则2[,]a是()的单峰区间；⑵若12()()，则1[,]b是()的单峰区间。证明：略3§2.2.精确一维搜索的收敛理论一、基于精确一维搜索的极小化算法无约束最优化问题算法的基本框架：⑴给出初始点0nxR，允许误差0，置:0k⑵计算下降方向kd⑶利用一维搜索，确定步长因子k，使0()min()kkkkkfxdfxd⑷令1kkkkxxd，若1()kfx，则停止，输出最优解*1kxx。否则，置:1kk，转⑵。在上面算法中，采用了精确一维搜索。下面证明基于精确一维搜索的极小化算法的收敛性。二、算法收敛性定理2.5设k是0min()kkfxd的解，若2()(0)kkfxdM，则有：221()()()cos,()2kkkkkkkfxfxdfxdfxM证明：由定理假设，有22()()()2TkkkkkkfxdfxfxdMd，(0)令2()TkkkdfxMd（若要0，则必须()0Tkkdfx，即kd与()kfx成锐角），22()()()()()2TkkkkkkkkkkfxfxdfxfxddfxMd22222222(())(())111()()cos,()222()TTkkkkkkkkkkkdfxdfxfxfxdfxMMMdfxd，定理证毕。注：⑴由证明过程可以看出，kd必须和()kfx成锐角。⑵给出了精确搜索前提下，每步迭代所得改进量的估计式，显然与kd有关。定理2.6设()fx是开集nDR上的连续可微函数，若某一极小化算法满足：41()()kkfxfx，()0Tkkfxd，k又设xD是序列kx的聚点，1K是满足1limkxKxx的指标集。假定存在0M，使得1kK，有kdM，又设d是序列{}kd的任意聚点，则()0Tfxd进一步，若()fx在D上二次连续可微，则还有2()0TTdfxd。证明：设21KK是满足2limkkKdd的指标集，下面用反证法证明。若定理结论不成立，即()0Tfxd，由于()0Tkkfxd，注意到2kK时，2kKxx，2kKdd则有()0Tfxd，因而必有()0Tfxd。（﹡）于是存在x的邻域()Nx和指标集32KK，使得当()xNx，3kK时，有()02Tkfxd，（由（﹡）式可得）设ˆ是一个充分小的正数，使得对所有ˆ0，及所有3kK，都有()kkxdNx，（由kxx，kd有界可得）则30110()()[()()][()()]kkkkkkKfxfxfxfxfxfx33ˆˆˆ[()()]()TkkkkkkkkKkKfxdfxfxdd(01)k3ˆ()2kK，与0()()fxfx为有限值矛盾，故必有()0Tfxd。同样地，若2()0Tdfxd5不成立，则必有2()0Tdfxd。类似地，有30ˆ()()[()()]kkkkKfxfxfxdfx322ˆ()ˆˆ[()()]2TTkkkkkkkkKfxddfxdd(01)k33222ˆˆ()()ˆ()()222TkkkkkkKkKdfxdd此矛盾表明必有：2()0Tdfxd，定理证毕。定理2.7设()fx在水平集0{()()}Lxfxfx上存在且一致连续，算法产生的方向kd与()kfx的夹角k满足：2k，（是某个正数）则或者对某个k，使()0kfx，或者有kf，或者有()0kfx。证明：若有某个k，使()0kfx，则结论已证。因此，可设k，()0kfx。又由于{()}kfx是一个下降序列，若其无下界，则有lim()kkfx，结论也成立。故可设{()}kfx有下界，因此lim()kkfx存在。从而有：1()()0kkfxfx。下证()0kfx。反证：若()0kfx，那么0，不论N多大，都存在k，kN，使得()kfx。从而1()()coscos()sin2Tkkkkkfxddfx由()()()Tkkkkkfxdfxfd（k位于kx与kkxd之间）()()[()()]TTkkkkkkfxfxdffxd()()(()())Tkkkkkkkfxdfxdffxd，注意到()fx在L上一致连续，故存在，使得当0kd时，有11()()2kkffx6若在上面的不等式中取kd，则得1()()()()2Tkkkkkkkdfxdfxfxdd11()2kfx故有111()()()2kkkkkdfxfxfxd这与1()()0kkfxfx矛盾。故必有()0kfx。注：⑴上述收敛定理不仅仅针对某一个特定算法。实际上，前述算法模式中任意算法只要满足定理所需条件中，就都是收敛的。⑵()0kfx，意味着{}kx的任何极限点均为稳定点，但它并不保证{}kx本身收敛。三、采用精确搜索的极小化算法的收敛速度引理1设函数()在闭区间[0,]b上二次连续可微，且(0)0。若()在[0,]b上的极小点*(0,)b，则*(0)M。其中0M满足()M，[0,)b。证明：构造辅助函数()(0)M，它有唯一零点(0)M。注意到00()(0)()(0)()dMd即()的图像总位于()之下，再由()是单调上升函数，由此可得：()的零点*必位于()零点的右边。即*(0)M事实上，在()零点的左边，()0。由()()，有()0。故()的零点*不可能位于的左边。故必有*。引理2设()fx在nR上二阶连续可微，则对任意向量x，ndR和任意实数，有：1220()()()(1)[()]TTfxdfxfxdtdfxtdddt.7证明：10()()[()]fxdfxdfxtd（t为积分变量）10[()](1)Tfxtdddt（再分部积分）1100(1)()(1)[()]TTtfxtddtdfxtdd1220()[()](1)TTfxddfxtddtdt.引理3设()fx在极小点*x的邻域内二阶连续可微，且存在0，和0mM，使得当*xx时，222()TmyyfxyMy，nyR.那么当*xx时，有22***11()()22mxxfxfxMxx，*()fxmxx.证明：在引理2中取*xx，再令*xdx，则*dxx1****2**0()()()()(1)[()((1))()]Tfxfxfxxxtxxftxtxxxdt注意到*()0fx及引理条件即得:22***11()()22mxxfxfxMxx.又由1*2**0()()()((1))()]fxfxfxftxtxxxdt，因此有**()()()Tfxxxxxfx1*2**0()((1))()]Txxftxtxxxdt2*mxx由此即得*()fxmxx.利用上述引理，可得下面的收敛速度定理。定理2.8设极小化算法产生的序列{}kx收敛到()fx的极小点*x，若()fx在*x的某一邻域内二阶连续可微，且存在0，和0mM，使得当*xx时，有222()TmyyfxyMy，nyR8则{}kx线性收敛。证明：由*limkkxx。故当k充分大时，有*2kxx，*12kxx，因而，存在0，使得**1()kkkkkxdxxxd(这是由于在每次迭代中，搜索方向kd可取为单位向量，故有界)。记()()kkfxd由于*()kkkxdx，*kxx故当0k时，有******()([0,1])()()(1)()()(1)()(1)kkkkkkkkkkkkkxdxxdxxxdxxxdxxx又注意到(0)()0Tkkfxd22()()TkkkkkdfxddMd，([0,])k由引理1知()()kkfxd在[0,]k上的极小点k满足22()(