信赖域算法.ppt

文档介绍：THUDAE1机械最优化设计课程机械最优化设计作业THUDAE—。信赖域法也是一种迭代算法,即从给定的初始解出发,通过逐步迭代,不断改进,直到获得满意的近似最优解为止。特点:思想新颖,具有可靠性、有效性和很强的收敛性。与线性搜索方法相比,信赖域方法直接通过模型求解得到试探步长,而不是先确定搜索方向,再寻找步长。线搜索方向可以看成是信赖域半径充分大时的信赖域步;而信赖域方法得出的信赖步可看成是将二次逼近模型加上一个惩罚项之后所导致的线搜索方向。THUDAE基本思想机械最优化设计课程3在每次迭代中给出一个信赖域,这个信赖域一般是当前迭代点的一个小邻域。然后在这个邻域内求解一个子问题,得到试探步长(trial step),接着用某一评价函数来决定是否接受该试探步长以及决定下一次迭代的信赖域。如果试探步长被接受,则:,否则,。新的信赖域的大小取决于试探步长的好坏,粗略地说,如果试探步长较好,在下一步信赖域扩大或保持不变,否则下一步减小信赖域。kkksxx???1kkxx??1THUDAE算法模型机械最优化设计课程4设当前点的邻域定义为:其中,称为信赖域半径。利用二次逼近,构造如下信赖域子问题:其中,kx??1,)(kkkxxRx??????k?2..21)()(qmin 2(k))(??????????kstssBssgxfskTTkk??????knkkkkBRxfgxxsxf,)(,)(为目标函数,或者其近似。nnkRxf???)(2THUDAE算法模型机械最优化设计课程5设是信赖域子问题(2)的解,定义目标函数第k步的真实下降量为:称二次模型函数的下降量为预测下降量:定义比值:它衡量了二次模型与目标函数的逼近程度越接近于1,表明接近程度越好。因此用它来确定下次迭代的信赖域半径。ks)(-)(kkkksxfxfAred??)(q(k)s)(q-)0(qPr(k)(k)kksed?.PrkkkedAredr?krTHUDAE信赖域半径的选择机械最优化设计课程6(1)越接近于1,表明接近程度越好,这时可以增大以扩大信赖域;(2) >0但是不接近于1,保持不变;(3)如果接近于0,减小,缩小信赖域。或者其他的选择方法(后面介绍)。krk?krk?krk?k?THUDAE信赖域算法机械最优化设计课程7Step1. 给出初始点,信赖域半径的上界Step2. 计算,如果,停止;否则,计算。Step3. (近似)求解子问题(2),得到。Step4. 计算,令Step5. 校正信赖域半径,令0x),,(,????,10,1002121????????k?????,??kgkskkkrsxf和)(?.or if,11???????kkkkkxrsxx?.6}],min{,[6),[),3)02212111111,转步骤;,转步骤(;,转步骤,(?????????????????????????kkkkkkkkkkkrifrifrif1?kBkgTHUDAE信赖域算法机械最优化设计课程8Step6. 令k=k+1,:,信赖域扩大;成功迭代:不成功迭代:,信赖域缩小。算法参数选择:1??kr;),[21,信赖域维持不变???krkkkr?????12,?.????????,或者,,,,????.0,10,1002121????????k?????,THUDAE解信赖域子问题机械最优化设计课程9信赖域方法在每步迭代中求解下列形式的子问题:其中, S为待求变量。当变化时,S的解形成一条空间曲线,称为最优曲线。 Powell[1970]给出了求解(2)的单折线法,当可逆时。用连接初始点、的单折线近似最优曲线,在折线上取点使得作为(2)的解。2..21)()(qmin 2(k))(??????????kstssBssgxfskTTkk??????knkkkkBRxfgxxsxf,)(,)(为目标函数,或者其近似,nnkRxf???)(2为信赖域半径,k?k?kB10SS及*SkS??*kSTHUDAE解信赖域子问题机械最优化设计课程10.,,Cauchy121121kkTkTkkkNkkkckNkgBggggBssgssxsskk???????????)。小点(由牛顿方法产生的极是牛顿点的极小点);点(由最速下降法产生是其中