信赖域方法

信赖域方法信赖域方法信赖域方法是求解最优化问题的另一类有效方法．其最初的设计思想可追溯至Levenberg和Marquart对Gauss－Newton法的修正．线搜索方法是把一个复杂的最优化问题转化成一系列简单的一维寻优问题．信赖域方法是把最优化问题转化为一系列相对简单的局部寻优问题．基本思想牛顿法的基本思想是在迭代点kx附近用二次函数逼近,21sGssgfsqxfkTTkkk并以sqk的的极小点ks修正,kx得到：.1kkksxx以上方法只能保证算法的局部收敛性，为了建立总体收敛性算法，我们采用了线搜索技术．虽然这种策略是成功的，但它有一个缺点，即没有进一步利用二次模型．基本思想牛顿法的基本思想是在迭代点kx附近用二次函数逼近,21sGssgfsqxfkTTkkk并以sqk的的极小点ks修正,kx得到：.1kkksxx以上方法只能保证算法的局部收敛性，为了建立总体收敛性算法，我们采用了线搜索技术．虽然这种策略是成功的，但它有一个缺点，即没有进一步利用二次模型．信赖域方法是另一种新的保证算法总体收敛的方法．信赖域方法的模型子问题121minsBssgfsqkTTkkkksts.其中,,kkkxfgxxskB是Hesse阵kxf2的近似0k为信赖域半径．注：(1)这种方法既具有牛顿法的快速局部收敛性，又具有理想的总体收敛性．(2)不要求目标函数的Hesse阵是正定的．(3)利用了二次模型来求修正量，使得目标函数的下降比线性搜索方法更有效．(4)由于步长受到使Taylor展开式有效的信赖域的限制，故方法又称为有限步长法．信赖域半径的选择根据模型函数sqk对目标函数xf的拟合程度来调整信赖域半径.k对于问题(1)的解,ks定义比值：kkkkkkkkksqqsxfxfredPAredr0它衡量模型函数sqk与目标函数xf的一致性程度．注：(1)kr越接近于１，表明模型函数与目标函数的一致性程度越好，可以增大k以扩大信赖域．(2)0kr不接近于１，可以保持k不变．(3)kr接近于零或取负值，表明模型函数与目标函数的一致性程度不好，可以减小k以缩小信赖域．信赖域算法Step1:给出,0nRx信赖域半径的上界,,0,0.0,10,10,02121kStep2:如果,kg停止．Step3:求解子问题(1)得到.ksStep4:计算kksxf和,kr令：othersxrsxxkkkkk11Step5:校正信赖域半径，令：2212111111,min,),[,,0kkkkkkkkkkkrrrStep6:产生,1kB校正,kq令,1kk转Step2注：参数建议取：1,2,5.0,75.0,01.002121信赖域子问题折线法基本思想如果令信赖域的半径k在区间,0内连续变化，则问题(1)的解ks在空间nR中形成一条光滑的连续曲线，记为.kop此时，问题(1)等价于在信赖域内在最优曲线kop上确定一点使二次函数sqk取极小，即：kkopksstssq,.min由于最优曲线的确定需要计算矩阵kB的所有特征值和特征向量，相当费时．折线法在于用低维空间内满足一定要求的折线，记为,k代替最优曲线．通过求解：kkksstssq,.2min得问题(1)的近似解.ks注：(1)求解(2)的一个突出特点在于：近似折线k一经确定，对于给定的,k无需再解任何线性方程组，即能相当有效的确定问题(1)的近似解．(2)构造近似最优曲线kop的折线时，一般应满足下面基本要求：当点x从kx出发沿着折线前进时:(P1)点x到kx的距离单调增；(P2)函数值sqk严格单调降；性质(P1)确保对任意给定的,k折线上的近似解惟一．性质(P2)确保在折线上所确定的近似解ks能满足收敛性定理的条件．折线法算法原理(1970)连接Cauchy点(由最速下降法产生的极小点C.P.)和牛顿点(即由牛顿法产生的极小点Nkx1）,其连线与信赖域的边界的交点取为.1kx显然,.1kkkxx当牛顿步Nks的长度kNks时，1kx就取为.1Nkx对二次模型：kkTkkkkkkgGggxfgxq2221精确线搜索下.2kkTkkkgGggCauchy步为：.kkkTkkTkkkckggGggggs若,kkkckgs取,kkkkggs若,kkkckgs再计算牛顿步,1kkNkgGs若,kNks取,1kkNkkgGss否则取,ckNkckkssss其中由方程kckNkcksss得到．综上：kNkkckkkkkNkkckckNkckkkckkkkkkssgGxsssssxsggxx,,11双折线法(1979)让信赖域迭代中产生的点偏向牛顿方向，于是把Cauchy点和牛顿方向上的Nˆ点连接起来，并将这条连线与信赖域边界的交点取为.1kx折线NkkxPCx1..称为单折线．把NkkxNPCx1ˆ..称为双折线．在双折线情形下：kNkkckkkkkNkkckckNkckkkckkkkkkssgGxsssssxsggxxˆ1ˆˆ1,,其中.,1,,14ˆkkTkkkTkkNkNkgGggGggss一般取.2.08.0例1：设,222141xxxxf在当前点,1,1Tkx,21k试用双折线法求.1kx解：214,2,6,1,1kTkTkGgxTkkNkgGs1,731156.0469.026512402kkkTkkckggGggs由于,kcks计算,ˆNks有：684.073251240214kkTkkkTkkgGggGgg747.02.08.0747.0320.0ˆNkNkss由于,813.0ˆkNks故取双折线步长为：1,0ˆckNkckkssss使得,kks解二次方程22ˆkckNkcksss得.867.0因此669.0340.0867.0ˆckNkckkssss所以331.0660.01kkksxx