工程优化第4章-5

信赖域方法信赖域方法是求解最优化问题的另一类有效方法。其最初的设计思想可追溯至Levenberg和Marquart对Gauss-Newton法的修正。线搜索方法是把一个复杂的最优化问题转化成一系列简单的一维寻优问题。信赖域方法是把最优化问题转化为一系列相对简单的局部寻优问题。信赖域方法------基本思想牛顿法的基本思想：在迭代点kx附近用二次函数逼近原函数,21sGssgfsqxfkTTkkk并以sqk的的极小点ks修正,kx得到：.1kkksxx以上方法只能保证算法的局部收敛性，为了建立全局收敛性算法，阻尼Newton法采用精确一维搜索技术，信赖域方法是另一种新的保证算法全局收敛的方法。ksxx21()()()()()2TTkkkkkkfxfxgxxxxfxxx但它没有进一步利用二次模型。在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代点的一个小邻域。然后在这个邻域内求解一个子问题，得到，接着用某一评价函数来决定是否接受该以及确定下一次迭代的信赖域。kxksks信赖域方法------基本思想如果试探步长被接受，则1,kkkxxs否则，1kkxx新的信赖域的大小取决于试探步的好坏，粗略地说，如果试探步较好，下一步否则信赖域扩大或保持不变，减小信赖域。信赖域扩大或不变；信赖域变小。信赖域方法------基本思想在每次迭代中给出一个信赖域，这个信赖域一般是当前迭代点的一个小邻域。然后在这个邻域内求解一个子问题，得到，接着用某一评价函数来决定是否接受该以及确定下一次迭代的信赖域。kxksks如果试探步长被接受，则1,kkkxxs否则，1kkxx信赖域扩大或不变；信赖域变小。信赖域方法------基本思想这个信赖域一般是当前迭代点的一个小邻域。接着用以及kx在每次迭代中给出一个信赖域，然后在这个邻域内求解一个子问题，得到，ks某一评价函数来决定是否接受该ks确定下一次迭代的信赖域。信赖域方法的模型子问题1min12TTkkkkqsfgssGs.ksts其中,,kkkxfgxxskG是Hesse阵kxf2的近似0k为信赖域半径．注：(1)这种方法既具有牛顿法的快速局部收敛性，又具有理想的全局收敛性。(2)不要求目标函数的Hesse阵是正定的。(3)利用了二次模型来求修正步长，使得目标函数的下降比线性搜索方法更有效。(4)由于步长受到使Taylor展开式有效的信赖域的限制，故方法又称为有限步长法。1min2TTkkkkqsfgssGs.ksts信赖域半径的选择根据模型函数sqk与目标函数xf的拟合程度来调整信赖域半径.k给定问题(1)的解,ks定义比值：0kkkkkkkkkfxfxsAredrqqsPred它衡量模型函数sqk与目标函数xf的一致性程度。,21sGssgfsqxfkTTkkkksxx1+kkkxxs1min(1)2TTkkkkqsfgssGs.ksts注：(1)kr越接近于１，表明模型函数与目标函数的一致性程度越好，可以增大k以扩大信赖域。(2)0kr不接近于１，可以保持k不变。(3)kr接近于零或取负值，表明与目标函数的一致性程度不好，可以减小k以缩小信赖域．()kqs()fx()fx()kqs0kkkkkkkkkfxfxsAredrqqsPred信赖域算法步骤1:给出,0nRx信赖域半径的上界,,0,012120,01,01,0.k步骤2:如果,kg停止．步骤3:求解子问题(1)得到.ks步骤4:计算kksxf和,kr令：othersxrsxxkkkkk111min12TTkkkkqsfgssGs.ksts0kkkkkkkkkfxfxsAredrqqsPred步骤5:校正信赖域半径，令：2212111111,min,),[,,0kkkkkkkkkkkrrr步骤6:产生1,kG校正(s),kq令,1kk转步骤2注：参数建议取：1,2,5.0,75.0,01.00212112TTkkkkqsfgssGs步骤2:如果,kg停止．步骤3:求解子问题(1)得到.ks步骤4:计算kksxf和,kr令：1min12TTkkkkqsfgssGs.ksts信赖域子问题折线法基本思想如果令信赖域的半径k在区间,0内连续变化，则问题(1)的解ks在空间nR中形成一条光滑的连续曲线，记为.kop此时，问题(1)等价于在信赖域内并且在最优曲线kop上确定一点使二次函数取极小，即sqkkkopksstssq,.min由于最优曲线的确定需要计算矩阵kG的所有特征值和特征向量，相当费时。1min12TTkkkkqsfgssGs.ksts用低维空间内满足一定要求的折线，记为,k代替最优曲线。通过求解：min2.,kkkqsstss得问题(1)的近似解.ks注：1:求解(2)的一个突出特点在于：近似折线k一经确定，对于给定的,k无需再解任何线性方程组，即能相当有效地确定问题(1)的近似解。折线法：2：构造近似最优曲线kop的折线时，一般应满足：当点x从kx出发沿着折线前进时:性质1：点x到kx的距离单调增加；性质2：函数值sqk严格单调下降；性质1确保对任意给定的,k折线上的近似解惟一。性质2确保在折线上所确定的近似解ks能满足收敛性定理的条件。折线法算法原理(1970)连接Cauchy点C.P.和牛顿点1,Nkx与信赖域的边界的交点,取为.1kx显然,.1kkkxxCauchy点：由最速下降法迭代一步产生的点，记为C.P.Newton点：由牛顿法迭代一步产生的点，记为,kqs折线NkkxPCx1..称为单折线．:kkx..CP()kfx1kx1Nkx针对二次函数从当前迭代点出发，1,Nkxkx折线法算法原理(1970)连接Cauchy点C.P.和牛顿点1,Nkx其连线与信赖域的边界的交点取为.1kx显然,.1kkkxxCaushy点=?Newton点=?1=kx？kx..CP()kfx1kx1Nkx精确一维搜索求最佳步长.2kkTkkkgGggCauchy步为：ckkksdCaushy点：=(+)kkkqxd=-,kkdg12TTkkkkqsfgssGs221=2TkkkkkkkkqxgfxggGg令'=0,得1.TcckkkkkkkTkkkggxxsxggGgCaushy点为：.TkkkkkTkkkgggggGgNewton步为：Nkkksd12TTkkkkqsfgssBsNewton点：11.NNkkkkkkxxsxGg1,kkkdGg1,k1,kkGgNewton点为其中由方程1cNckkkkkkxxsss得到。Cauchy步为：1.TckkkkkTkkkggxxggGgCaushy点为：,TckkkkTkkkggsggGgNewton步为：11.NkkkkxxGg1,NkkksGgNewton点为.1kkkxx111=1cNkkkxxx=1cNkkkxss=cNckkkkxsss折线法算法原理(1970)当Newton步的长度kNks时，111;NkkkkkxxxGg当ckks取,kkkkggs1;kkkkkxxgg时，综上：11,,ckkkkkkcNccNkkkkkkkkkcNkkkkkkkxgsgxxsssssxGgss双折线法(1979)让信赖域迭代中产生的点偏向牛顿方向，于是把Cauchy点和牛顿方向上的Nˆ点连接起来，并将这条连线与信赖域边界的交点取为.1kxNkkxNPCx1ˆ..称为双折线．折线1..NkkxCPx称为单折线,1ˆ..NkkxCPNx称为双折线(信赖域迭代中产生的点偏向牛顿方向,会改善算法的性态).在双折线情形下：kNkkckkkkkNkkckckNkckkkckkkkkkssgGxsssssxsggxxˆ1ˆˆ1,,其中.,1,,14ˆkkTkkkTkkNkNkgGggGggss一般取.2.08.0例1：设,222141xxxxf在当前点,1,1Tkx,21k试用双折线法求.1kx解：1401,1,6,2,02TTkkkxgGTkkNkgGs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[s,val,posdef,count,lambda]=TRUST(g(x),B,d);TRUST是matlab自带的求解信赖域子问题的函数，利用它信赖域方法的程序就简单多了。课件下载邮箱邮箱名：[e-mail](xd+工程优化的小写全拼)密码：xidian123