信赖域方法学习教案

1、会计学1信赖信赖(xnli)域方法域方法第一页，共27页。信赖域算法全局收敛算法这一节，将介绍另一种二次模型函数。但它没有进一步的使用。该方法具有整体收敛性法，长，这个就是阻尼牛顿从而得到一个缩短的步作一维搜索，）（）（沿着搜索方向）正定时，（，）（对它做了改进，即当局收敛算法，取有关），为了得到全（收敛性与初始点的选部收敛算法，传统的牛顿法属于局上一节，学习了牛顿法）（）（）（）（）（-xfxf-dxf0 xfk2kkk2k第1页/共26页第二页，共27页。第2页/共26页第三页，共27页。）（）（）（）（）（）（，产生新的迭代点选择选择适当的步长向，然后沿着这个搜索方向后，先确定一个搜索方

2、给定点化方法，一般策略是在前面介绍的无约束最优kkk1kkkkkdxxddx第3页/共26页第四页，共27页。）（）（）（）（）（）（）（，或产生新的迭代点模型函数近似解（二次模型函数）得到目标函数的二次逼近式在这个信赖域内，优化步的信赖半径是第这里定义当前点的邻域k1kkk1kkkkknkxxdxxdkrr|x-x| |xR第4页/共26页第五页，共27页。就减小。大，反之，信赖域半径则信赖域半径可适当扩问题，模型比较好的逼近于原如果在一次迭代中近似步调节，半径的大小通过迭代逐）的最小值点。信赖域（们可以找到上过程，用这种方法我函数的新模型。继续以附近建立目标，然后在一个点适当的位移，移动到

3、下们选择一个为了得到要求的点，我代表目标函数，接下来大致的某个邻域内这个模型假定在目标函数的模型，并且，在其附近建立对于给定的初始点求逼近模型的最优点。某个邻域内题就是在当前迭代点的近似模型，信赖域子问于原目标函数的始点附近构造一个近似首先给出初始点，在初）（：对于问题：）（）（）（）（xfxxxxxfmin2211第5页/共26页第六页，共27页。)df(xd21d)(f)(fx-xd)x-)(xf(xx-x21x-x)(f)(fxfxxfxxfmink)2T)()(kk(k)k)2Tkk)()(kn（）（）（）（）（）（），得到二次模型（取）（）（）（处展开，取二次近似）在给定点（将），（

4、：考虑无约束问题：TkkTkkxxdxx第6页/共26页第七页，共27页。寻优问题）一些列相对简单的局部化为是将复杂的最优问题转（可以看出信赖域算法）（：一系列子问题为解）的极小点问题就归结（这样，求函数问题并求极值）这个简单模型近似于原内建立一个简单模型，代点的某个邻域的取值实质是在当前迭（由此可以看出，限定步的信赖域半径就是前面提到的第即的取值，令限定），（）近似（附近用为了在（）（）（kk)2T)()(k(k)kkkr|d| s.t.)df(xd21d)()(minxfdkrr|x-x|,r|ddxfdxTkkkkkxfxfdd）（10.5.3第7页/共26页第八页，共27页。|xfIx

5、f|d|10.5.5Ixfr|d|00-r|d|xf-ddxfddd0-r|d|0dddxfdxf10.5.3dk1 -k2kk2kkkkkk2k21kkkk21kkkkk2kkkk）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）得到可逆，有（）（设）（）（）（为最优解的必要条件得到）（记：）（）（）（）（，使得子）的最优解，则存在乘是（若是关键的求解信赖域子问题显然TT第8页/共26页第九页，共27页。k1kk1kkk1kkk1kkkkkkk)(kkkkk2rrrrdxxr21rxd-xf)dx(f-fxfddxd或且，后继点比较大，则逼近成功，若；

6、，且信赖域半径功，后继点仍取太小，就认为逼近不成）（）（）（与预测下降量之比，即如果函数值实际下降量）是否成功来确定。（）逼近（还要根据用解，能否作为原问题的近似后，点求出信赖子问题）（）（）（）（）（）（）（）（）（）（）（kx第9页/共26页第十页，共27页。第10页/共26页第十一页，共27页。最近的点，以此类推。第11页/共26页第十二页，共27页。kk)2T)()(kk2kkkk11r|d| s.t.)df(xd21d)x(f)x(fmin.3xfx|xf|.xfxf.21k434110 x.1（）（）（）（）（）（）（）（：求解子问题）（）（；否则，计算则停止计算，得到解，）（若）

7、（），（计算）（，置）及精度要求，（一般，参数，信赖域半径给定可行点）（Tkkd第12页/共26页第十三页，共27页。），转步骤（置）（，令；如果令；如果，令如果）（令，；如果，令如果）（）（）（）（，令得到子问题的最优解）（）（）（）（）（）（）（）（）（）（21kk.62rrrrr21r.5dxxxx.4d-xf)dx(f-fdk1kkk1kkk1kkkk1kkk1kkkkkkk)(kkkx第13页/共26页第十四页，共27页。优解，试用信赖域方法求最，取信赖域半径取初点）（：）（43411r,00 x54x-xxxxfmin112222141第14页/共26页第十五页，共27页。1dd

8、. .dd4d-5dmin1| . .dxfd21dxfxf defdmin2002xfesse4-0 xf5xf2221222121121111211tsdtsHTT）（：即求解）（）（）（）（：解子问题）（矩阵，）（，目标函数的梯度）（解：经计算得到函数值）（）（）（）（）（）（第15页/共26页第十六页，共27页。22rr10dxx12-52-5d-xfdxf-xf2d2dxf10ddd121121111111111112111，逼近成功，令）（）（）（）（量之比实际下降量与预测下降）（，）（函数值点，也是最优解得到子问题的）（）（）（）（）（）（）（）（）（）（）（）（）（）（TK第1

9、6页/共26页第十七页，共27页。是最优解）（，）（得到经过第三次迭代。计算，令降量之比，实际下降量与预测下）（）（，算的得到子问题的解）（：，解子问题）（）（，）（算得到进行第二次迭代，经计）（）（）（）（）（）（）（）（）（）（）（）（）（20 x00 xf1xf42rr20dxx21-20-21d0dxf10d4dd . .dd2d-2dmin2002xf,20 xf2xf3332322322222222212221222222ts第17页/共26页第十八页，共27页。的子列（反证法）。再证不存在不收敛到的子列（反证法），先证存在收敛到。的子列，推出矛盾即可假定存在不收敛到法，的子列即可

10、。使用反证不收敛到证明思路：证明不存在）（，则列用信赖域方法求得的序上连续，）在（），（），（是有界闭集，）（）（是给定的初始点，上的实函数，）是（定理：设）（）（）（）（00000.|xf|limxxfxfxfxfxf |xxxfkkk211nSS第18页/共26页第十九页，共27页。方向的下降量。自然不会小于沿着任何域上最大的下降量，根据定义，这是在信赖）。（）（量次迭代函数的预测下降首先估计第矛盾是某个正数，下面推出，均有对所有充分大的的子列。反证法，假定存在收敛到）（先证明有对每个，使得上连续，因此存在正数）在（是有界闭集，由于）（），（为简便，记证明：）（）（）（）（d-xf|f|k

11、0|xf|M.|f|xf.xffxffkkkkk22k2k2kkkkMSS第19页/共26页第二十页，共27页。r|f|21r|f|2fff2-r|f|f|rfff10.5.9r2|f|fff2|f|r00dfff|f|, 0|f|2fff-|f|f|f-f|f|f-21)|f|f- (f(f -xfff-xf|f|f-dk2k2kkk2kk2k3kkkk2kk2kkk2k4kkkk2k3k22kkk2kkk2kk2k2kk2kk2)(kk2kkkk2kTTTTTTTkQMQQxQ下降量）式，即时，根据（当）时，下降量，（当是最速下降方向，因此由于得到平稳点）（令）（）（）（）（）（）（时的下

12、降量沿着这个方向步长为向个下界，取最速下降方为给出最大下降量的一）（）（）（10.5.8）（10.5.9）（10.5.10）（10.5.11）（10.5.12第20页/共26页第二十一页，共27页。0.rlim0.rlim. 0010.5.15xf|f|minr21xf-xf10.5.14,|f|k|f|minr|f|21d-xf xf-xfd-xfxf-xf|f|minr|f|21d-xf10.5.1210.5.10kkkkkkk1kkkkkkkkk1kkkkk1kkkkkkkki。综上分析均导致信赖域半径减小间的不成功步，对于任意两个成功步之由此可见，对于成功步，从而右端也趋于）式左端趋于

13、时，（列，必有极限，由此当）为单调减有下界数（由于（，）（）（）式得到由此由（，有根据假设，对充分大的，）（）（）（）（由此得到）（）（）（）（对于成功步，）（）（）式，预测下降量）式和（综合（）（）（）（）（）（）（）（）（）（）（）（）（）（kMMM）（10.5.13）（10.5.14）（10.5.15第21页/共26页第二十二页，共27页。k2k2kkkkkk2kkkkk2kkkk2kkkkk2kkk2kkkkkkkk2kkkkkkkkkkkkkkkkkkkkkkkkkkkkr21|d|21|d|21d-xf|dfd21ddxfd21-|1-|dfd21ddxfd21-dfd21dfxf

14、 ddxfd21dfxf -ddxf -r21r|f|21d-xf10.5.13,d-xfddxf -1-d-xfdxf -xf1-MMkTTTTTTTT）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（因此）（）（）（）（）（）（分子，）（）（分母）式知上式得有（对于充分大的）（）（）（）（）（）（）（）（）（10.5.16第22页/共26页第二十三页，共27页。3minr61xf-xf10.5.14k.31|f|k.31|f|0|xf|.|f|,f0|xf|lim0

15、|xf|.1lim0rlimr1.lim0rlim.r2k1kkikiiikkkkkkkkkkkkkkkkkiiiMkkkkMiii，）（）（）式得到步迭代成功，则由（且第如果，有对每个，有对每个，集的子列，因此存在指标存在收敛到）（根据前面证明，有对每个及正数子序列，用反证法，假设存在）（下面证明的子列。存在收敛到）（因此，矛盾时非减，这与时，义，当另一方面，根据算法定，因此前面已经证明了）（）（）（）（）（）（10.5.17）（10.5.18第23页/共26页第二十四页，共27页。0|xf|lim323131|f|f-f|ff-f|f|10.5.2010.5.1810.5.1731|f-f

16、|i0.|f-f|0 x-xxf. 00 xf-xfxf-xf xf-xf xf-xf |x-x|x-x|x-x|61|x-x|6110.5.19.k10.5.19xx|,x-x|61xf-xf0kkkkkkkkkkkkkkkkkkik1kk1k1kkiiiiiiiiiiiiiiii1 - i2i1i1iii1 - i2i1i1iiii）（因此矛盾。）式得出）式和（），（由（能保证，因此取充分大的指标趋于时，趋于当上连续，）在有界集（由于，因此左端也趋于式右端趋于当指标趋于无穷时，上）（）（）（）（）（）（）（）（）（）式推得利用（成立）式对每个，因此（由于对不成功步）（）（，因此有由于不等式左端趋于）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（