信赖域方法.

信赖域方法15721546马广庆前言信赖域算法全局收敛算法这一节，将介绍另一种二次模型函数。但它没有进一步的使用。该方法具有整体收敛性法，长，这个就是阻尼牛顿从而得到一个缩短的步作一维搜索，）（）（沿着搜索方向）正定时，（，）（对它做了改进，即当局收敛算法，取有关），为了得到全（收敛性与初始点的选部收敛算法，传统的牛顿法属于局上一节，学习了牛顿法）（）（）（）（）（-xfxf-dxf0xfk2kkk2k信赖域方法1.信赖域方法与常规方法区别2.信赖域基本思想3.信赖域方法4.算法步骤5.例题分析6.收敛性分析1.信赖域方法与常规方法的区别常规方法先确定方向，再确定步长）（）（）（）（）（）（，产生新的迭代点选择选择适当的步长向，然后沿着这个搜索方向后，先确定一个搜索方给定点化方法，一般策略是在前面介绍的无约束最优kkk1kkkkkdxxddx1.信赖域方法与常规方法的区别信赖域方法相当于直接确定了位移）（）（）（）（）（）（）（，或产生新的迭代点模型函数近似解（二次模型函数）得到目标函数的二次逼近式在这个信赖域内，优化步的信赖半径是第这里定义当前点的邻域k1kkk1kkkkknkxxdxxdkr}r||x-x|||{xR2.信赖域算法的基本思想就减小。大，反之，信赖域半径则信赖域半径可适当扩问题，模型比较好的逼近于原如果在一次迭代中近似步调节，半径的大小通过迭代逐）的最小值点。信赖域（们可以找到上过程，用这种方法我函数的新模型。继续以附近建立目标，然后在一个点适当的位移，移动到下们选择一个为了得到要求的点，我代表目标函数，接下来大致的某个邻域内这个模型假定在目标函数的模型，并且，在其附近建立对于给定的初始点求逼近模型的最优点。某个邻域内题就是在当前迭代点的近似模型，信赖域子问于原目标函数的始点附近构造一个近似首先给出初始点，在初）（：对于问题：）（）（）（）（xfxxxxxfmin22113.信赖域算法)df(xd21d)(f)(fx-xd)x-)(xf(xx-x21x-x)(f)(fxfxxfxxfmink)2T)()(kk(k)k)2Tkk)()(kn（）（（）（）（）（）（），得到二次模型（取）（）（）（处展开，取二次近似）在给定点（将），（：考虑无约束问题：TkkTkkxxdxx3.信赖域算法寻优问题）一些列相对简单的局部化为是将复杂的最优问题转（可以看出信赖域算法）（：一系列子问题为解）的极小点问题就归结（这样，求函数问题并求极值）这个简单模型近似于原内建立一个简单模型，代点的某个邻域的取值实质是在当前迭（由此可以看出，限定步的信赖域半径就是前面提到的第即的取值，令限定），（）近似（附近用为了在（）（）（kk)2T)()(k(k)kkkr||d||s.t.)df(xd21d)()(minxfdkrr||x-x||,r||||ddxfdxTkkkkkxfxfdd）（10.5.3||xfIxf||||d||10.5.5Ixfr||d||00-r||d||xf-ddxfdddˆ0-r||d||0dddˆxfdxfˆ10.5.3dk1-k2kk2kkkkkk2k21kkkk21kkkkk2kkkk）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（（））（（）得到可逆，有（）（设）（）（）（为最优解的必要条件得到）（记：）（）（）（）（，使得子）的最优解，则存在乘是（若是关键的求解信赖域子问题显然TT3.信赖域算法k1kk1kkk1kkk1kkkkkkk)(kkkkk2rrrrdxxr21rxd-xf)dx(f-fxfddxd或且，后继点比较大，则逼近成功，若；，且信赖域半径功，后继点仍取太小，就认为逼近不成）（）（）（与预测下降量之比，即如果函数值实际下降量）是否成功来确定。（）逼近（还要根据用解，能否作为原问题的近似后，点求出信赖子问题）（）（）（）（）（）（）（）（）（）（）（kx3.信赖域算法特点：不要求目标函数的Hesse矩阵正定，在非正定的情况下也能处理。既有牛顿法的快速局部收敛性，也有理想的全局收敛性。算法利用二次模型来修正步长，使得目标函数的下降比线搜索方法更有效。由于位移长度受到Taylor展开式有效的信赖域的限制，此方法又称为有限步长法3.信赖域方法要从上海火车站去人民广场，有两种方法：①可以先定一个方向，比如先向西走，走着走着发现方向有点不对（人民广场应该是时尚地标啊，怎么越走感觉越郊区了呢），就调整一下方向，变成向东南方向走，诸如此类。②用信赖域算法，就比如，我先划一个圈，然后在这个圈里面找离人民广场可能最接近的点，之后在这个点为中心再画一个圈，在这个圈内找离人民广场可能最近的点，以此类推。4.算法步骤步骤如下：kk)2T)()(kk2kkkk11r||d||s.t.)df(xd21d)x(f)x(fmin.3xfx||xf||.xfxf.21k434110x.1（）（）（）（）（）（）（）（：求解子问题）（）（；否则，计算则停止计算，得到解，）（若）（），（计算）（，置）及精度要求，（一般，参数，信赖域半径给定可行点）（Tkkd4.算法步骤），转步骤（置）（，令；如果令；如果，令如果）（令，；如果，令如果）（）（）（）（，令得到子问题的最优解）（）（）（）（）（）（）（）（）（）（21kk.62rrrrr21r.5dxxxx.4d-xf)dx(f-fdk1kkk1kkk1kkkk1kkk1kkkkkkk)(kkkx5.例题讲解例题：无约束问题优解，试用信赖域方法求最，，取信赖域半径取初点）（：）（43411r,00x54x-xxxxfmin1122221415.例题讲解1dd..dd4d-5dmin1||||..dxfd21dxfxfdefdmin2002xfesse4-0xf5xf2221222121121111211tsdtsHTT）（：即求解）（）（）（）（：解子问题）（矩阵，）（，目标函数的梯度）（解：经计算得到函数值）（）（）（）（）（）（5.例题讲解22rr10dxx12-52-5d-xfdxf-xf2d2dxf10ddd121121111111111112111，逼近成功，令）（）（）（）（量之比实际下降量与预测下降）（，）（函数值点，也是最优解得到子问题的）（）（）（）（）（）（）（）（）（）（）（）（）（）（TK5.例题讲解是最优解）（，）（得到经过第三次迭代。计算，令降量之比，，实际下降量与预测下）（）（，算的得到子问题的解）（：，解子问题）（）（，）（算得到进行第二次迭代，经计）（）（）（）（）（）（）（）（）（）（）（）（）（20x00xf1xf42rr20dxx21-20-21d0dxf10d4dd..dd2d-2dmin2002xf,20xf2xf3332322322222222212221222222ts6.收敛性分析的子列（反证法）。再证不存在不收敛到的子列（反证法），先证存在收敛到。的子列，推出矛盾即可假定存在不收敛到法，的子列即可。使用反证不收敛到证明思路：证明不存在）（，则列用信赖域方法求得的序上连续，）在（），（），（是有界闭集，）（）（是给定的初始点，上的实函数，）是（定理：设）（）（）（）（00000.||xf||lim}{xxfxfxf}xfxf|x{xxfkkk211nSS6.收敛性分析方向的下降量。自然不会小于沿着任何域上最大的下降量，根据定义，这是在信赖）。（）（量次迭代函数的预测下降首先估计第矛盾是某个正数，下面推出，均有对所有充分大的的子列。反证法，假定存在收敛到）（先证明有对每个，使得上连续，因此存在正数）在（是有界闭集，由于）（），（为简便，记证明：）（）（）（）（d-xf||f||k0||xf||M.||f||xf.xffxffkkkkk22k2k2kkkkMSS6.收敛性分析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-dk2k2kkk2kk2k3kkkk2kk2kkk2k4kkkk2k3k'22kkk2kkk2kk2k2kk2kk2)(kk2kkkk2kTTTTTTTkQMQQxQ下降量）式，即时，根据（当）时，下降量，（当是最速下降方向，因此由于得到平稳点）（令）（）（）（）（）（）（时的下降量沿着这个方向步长为向个下界，取最速下降方为给出最大下降量的一）（）（）（10.5.8）（10.5.9）（10.5.10）（10.5.11）（10.5.126.收敛性分析0.rlim0.rlim.0010.5.15xf}||f||min{r21xf-xf10.5.14,||f||k}||f||min{r||f||21]d-xf[xf-xfd-xfxf-xf}||f||min{r||f||21d-xf10.5.1210.5.10kkkkkkk1kkkkkkkkk1kkkkk1kkkkkkkki。综上分析均导致信赖域半径减小间的不成功步，对于任意两个成功步之由此可见，对于成功步，从而右端也趋于）式左端趋于时，（列，必有极限，由此当））为单调减有下界数（由于（，）（）（）式得到由此由（，有根据假设，对充分大的，）（）（）（）（由此得到）（）（）（）（对于成功步，，）（）（）式，预测下降量）式和（综合（）（）（）（）（）（）（）（）（）（）（）（）（）（kMMM）（10.5.13）（10.5.14）（10.5.156.收敛性分析k2k2kkkkkk2kkkkk2kkkk2kkkkk2kkk2kkkkkkkk2kkkkkkkkkkkkkkkkkkkkkkkkkkkkr21||d||21||d||21d-xf||dfd21ddxfd21-||||1-||dfd21ddxfd21-]dfd21dfxf[]ddxfd21dfxf[-ddxf-r21r||f||21d-xf10.5.13,d-xfddxf-1-d-xfdxf-xf1-MMkTTTTTTTT）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（因此）（）（）（）（）（）（分子，）（）（分母）式知上式得有（对于充分大的）（）（）（）（）（）（）（）（）（10.5.166.收敛性分析}3min{r61xf-xf10.5.14k.31||f||k.31||f||}{0||}xf{||.||f||,}f{0||xf||lim0||}xf{||.1lim0rlimr1.lim0rlim.r2k1kkikiiikkkkkkkkkkkkkkkkkiiiMkkkkMiii