第8讲信赖域方法

13.6信赖域方法(Trust-RegionMethods)1.基本思想2.线性搜索与信赖域方法的联系3.信赖域方法思想4.信赖域半径的选择5.信赖域算法6.信赖域方法的收敛性7.解信赖域子问题8.优化工具箱2信赖域方法和线性搜索方法是求解非线性优化问题的两类主要的数值方法.与线性搜索方法相比，信赖域方法思想新颖，具有可靠性，有效性和很强的收敛性.鉴于信赖域方法的优点，由它来构造新的优化方法成为非线性优化界许多学者关注的焦点.单折线法；双折线法;切线折线法;信赖域自适应调整算法………31．基本思想在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代点kx的一个小邻域.然后在这个邻域内求解一个子问题，得到试探步长(trialstep)ks，接着用某一评价函数来决定是否接受该试探步以及确定下一次迭代的信赖域.如果试探步长被接受，则：1kkkxxs，否则，1kkxx.新的信赖域的大小取决于试探步的好坏，粗略地说，如果试探步较好，在下一步信赖域扩大或保持不变，否则减小信赖域.42．线性搜索与信赖域方法的联系2.1不同点:与线性搜索方法相比，信赖域方法直接通过模型求解得到试探步长，而不是先确定搜索方向，再寻找步长.2.2相同点:线搜索方向可以看成是信赖域半径充分大时的信赖域步；而信赖域方法所得出的试探步可看成是将二次逼近模型加上一个惩罚项之后所导致的线搜索方向.53．信赖域方法思想设当前点kx的邻域定义为:nkkkxRxx（1）其中,k称为信赖域半径.目标函数在极值点附近近似一个二次函数，因此对于无约束优化问题,利用二次逼近，构造如下信赖域子问题:21min()2..kTTkkkkqsfxgssBssts,（2）其中，ksxx,kg是目标函数()fx在当前迭代点kx处的梯度，nnkBR对称，是()fx在kx处Hesse阵2()kfx或者其近似.63．信赖域方法思想设ks是信赖域子问题(2)的解.我们称目标函数()fx在第k步的实际下降量(真实下降量):()()kkkkAredfxfxs(3)称二次模型函数kqs的下降量(预测下降量)：0kkkkPredqqs(4)定义比值:kkkAredrPred.(5)它衡量了二次模型与目标函数的逼近程度，kr越接近于1，表明接近程度越好.因此，我们也用这个量来确定下次迭代的信赖域半径.74．信赖域半径的选择(1).kr越接近于1，表明接近程度越好.这时可以增大k以扩大信赖域;(2).0kr但是不接近于1,保持k不变;(3).如果kr接近于0,减小k,缩小信赖域.或者其它k的选择方法：Satenaer(1997)研究了初始信赖域半径0的选取对算法有效性的影响,给出了一个自动确定初始信赖域半径的ITRR算法,其基本思想是通过二次近似模型和目标函数沿负梯度方向的近似程度,调节初始信赖域半径.Zhang(2002)等同把这一思想应用到信赖域半径的自适应.85．信赖域算法Step1.给出初始点0x，信赖域半径的上界,00,,0,1201,1201,:0k.Step2.如果kg,停止.Step3.(近似)求解子问题(2),得到ks.Step4.计算()kkfxs和kr.令11,,.kkkkkxsifrxxor.Step5.校正信赖域半径.令1110,;kkkifr1112,,;kkkkifr122,min,.kkkkifr95．信赖域算法Step6.产生1kB，校正kq，令:1kk,转Step2.很成功迭代:2kr,1kk,信赖域扩大;成功迭代:12,kr;不成功迭代:kr,信赖域缩小.算法参数选择建议:120.01,0.75,1200.5,2,1,或者00110g.106．信赖域方法的收敛性理论假设：(1).Hesse近似kB按范数一致有界,即kBM,M是某个正的常数.(2).函数:nfRR在一个有界的水平集()Lx上连续可微且有下界.(3).对于某个正的常数,2kks.对于二次模型函数(2)，定义其柯西点:kckkkkgsg,其中,31,0;min,1,.kTkkkkkTkkkifgBggorgBg11定理1二次模型子问题(2)中的精确解,近似解,Cauchy点均满足:10min,kkkkkkkgqqsgB,（6）其中,10,1.当112时,s所满足的不等式由Powell(1975)给出,信赖域方法的收敛性主要是基于试探步满足当112时的不等式(6),为了降低计算的复杂度,人们并不精确求解(2),而是计算满足(6)式的试探步ks.12定义1设10,1,0是两常数,如果nksR满足(6)式和不等式:2(1)kks(7)则称ks是子问题(2)的1,下降试探步.显然,子问题(2)的精确解是0.5,0下降试探步.定理2全局收敛性定理[袁亚湘，1994]设函数()fx在nR上连续可微,如果10，2kBM对一切k成立，则对于0信赖域算法必定经过有限次迭代后终止或者产生点列kx使得:lim()kkfx2lim0kkg中必有一个成立.137．解信赖域子问题信赖域方法在每步迭代中求解下列形式的子问题:21min()2..kTTkkkkqsfxgssBssts,（2）其中，kg是目标函数()fx在当前迭代点kx处的梯度，nnkBR对称，是()fx在kx处Hessian阵的近似.k为信赖域半径,s为待求变量.当k变化时,s的解形成一条空间曲线,称为最优曲线.Powell[1970]给出了求解(2)的单折线法,当kB可逆时,用连接初始点0s及1s,2s的单折线近似最优曲线,在该折线上取点s使得2ks作为(2)的解ks.14其中1s是Cauchy点(由最速下降法产生的极小点C.P.);2s是牛顿点(由牛顿方法产生的极小点1Nkx).两者连线与信赖域边界的交点取为1kx,即1kkkxx,当牛顿步Nks的长度小于Nkks时,1kx取为牛顿点1Nkx.1ckkkssg,12NkkkssBg,TkkkTkkkgggBg.Dennis和Mei(1979)提出双折线法,在牛顿方向上取一点3s,连接1s和3s,在该折线上取一点s,使得ks作为(2)的解ks.即是把Cauchy点与牛顿方向的N连接起来,将这条连线与信赖域边界的交点取为1kx,称为双折线.15折线1..NkkxCPx称为单折线,1ˆ..NkkxCPNx称为双折线.(信赖域迭代中产生的点偏向牛顿方向,会改善算法的性态).16单折线法总结(1)2ckks时,2kkkkgsg(1K时的Cauchy点);(2)2ckks时,再计算牛顿步Nks:2.1如果2Nkks,则Nkkss;2.2如果2Nkks,则()cNckkkkssss,其中,为方程：()cNckkkksss的解.综上所述:211,(),,ckkkkkkcNccNkkkkkkkkkcNkkkkkkkgxsgxxsssssxBgss当当且当（8）17双折线法总结2ˆˆ1ˆ1,(),,ckkkkkkcNccNkkkkkkkkkcNkkkkkkkgxsgxxsssssxBgss当当且当，（9）其中，4ˆ21,,1,kkkkNNkkTTkkkgssgBggBg.如果1，双折线法就变成了单折线法.一般的,取0.80.2.上述方法满足：(1).从点kx到Cauchy点C.P.,到ˆ1Nkx的距离单调增加;(2).从Cauchy点C.P.,到ˆ1Nkx模型函数值单调减少.18在产生Cauchy点C.P.和ˆN点后,所求的新点1kx由(9)式得出,选择,使得:222kcNckkksss.如果所得到的1kx满足下降性要求:111(())()(),0,2Tkkkkkfxfxgxx则接受1kx为新点1kx.并根据信赖域算法校正信赖域半径,否则,令1:kkxx,并缩小信赖域半径.19例题设112422()fxxxx，当前点1,1Tkx，12K，试用双折线法求1kx.解:由于1,1Tkx,则131242()2kkxxgfxx,从而,可以得到6,2Tkg.同理可得:1221220140()0202kkxGfx2013,17TNkkksGg.220.469,0.156kTkckkTkkgsggGg.由于0.496ckks，从而需要计算牛顿步ˆNks，有4221400.684325127kkTTkkkkkggGggGg.0.80.20.747,ˆ0.3200.747NNkkss.21由于ˆNkks，故取双折线步长为ˆ(),0,1cNckkkkssss,使得kks.解二次方程:2ˆ22()cNckkkksss.得0.867.因此,ˆ0.340()0.669cNckkkkssss,10.6600.331kkkxxs.228.OptimizationToolboxManyofthemethodsusedintheOptimizationToolboxarebasedontrust-regions,asimpleyetpowerfulconceptinoptimization.Thekeyquestionsindefiningaspecifictrust-regionapproachtominimizingare:(1).howtochooseandcomputetheapproximationq.(definedatthecurrentpointx),(2).howtochooseandmodifythetrustregion,(3).howaccuratelytosolvethetrust-regionsub-problem.k23[s,val,posdef,count,lambda]=TRUST(g(x),B,d);%TRUST是matlab自带的求解信赖域子问题的函数利用它信赖域方法的程序就简单多了.24作业P111.习题7.