信赖域方法课件.ppt

《信赖域方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信赖域方法信赖域方法信赖域方法是求解最优化问题的另一类有效方法．其最初的设计思想可追溯至Levenberg和Marquart对Gauss－Newton法的修正．线搜索方法是把一个复杂的最优化问题转化成一系列简单的一维寻优问题．信赖域方法是把最优化问题转化为一系列相对简单的局部寻优问题．基本思想牛顿法的基本思想是在迭代点附近用二次函数逼近并以的的极小点修正得到：以上方法只能保证算法的局部收敛性，为了建立总体收敛性算法，我们采用了线搜索技术．虽然这种策略是成功的，但它有一个缺点，即没有进一步利用二次模型．基本思想牛顿法的基本思想是在迭代点附近用二次函数逼近并

2、以的的极小点修正得到：以上方法只能保证算法的局部收敛性，为了建立总体收敛性算法，我们采用了线搜索技术．虽然这种策略是成功的，但它有一个缺点，即没有进一步利用二次模型．信赖域方法是另一种新的保证算法总体收敛的方法．信赖域方法的模型子问题其中是Hesse阵的近似为信赖域半径．注：(1)这种方法既具有牛顿法的快速局部收敛性，又具有理想的总体收敛性．(2)不要求目标函数的Hesse阵是正定的．(3)利用了二次模型来求修正量，使得目标函数的下降比线性搜索方法更有效．(4)由于步长受到使Taylor展开式有效的信赖域的限制，故方法又称为有限步长法．信赖域半径的选择根

3、据模型函数对目标函数的拟合程度来调整信赖域半径对于问题(1)的解定义比值：它衡量模型函数与目标函数的一致性程度．注：(1)越接近于１，表明模型函数与目标函数的一致性程度越好，可以增大以扩大信赖域．(2)不接近于１，可以保持不变．(3)接近于零或取负值，表明模型函数与目标函数的一致性程度不好，可以减小以缩小信赖域．信赖域算法Step1:给出信赖域半径的上界Step2:如果停止．Step3:求解子问题(1)得到Step4:计算和令：Step5:校正信赖域半径，令：Step6:产生校正令转Step2注：参数建议取：信赖域子问题折线法基本思想如果令信赖域的半径在

4、区间内连续变化，则问题(1)的解在空间中形成一条光滑的连续曲线，记为此时，问题(1)等价于在信赖域内在最优曲线上确定一点使二次函数取极小，即：由于最优曲线的确定需要计算矩阵的所有特征值和特征向量，相当费时．折线法在于用低维空间内满足一定要求的折线，记为代替最优曲线．通过求解：得问题(1)的近似解注：(1)求解(2)的一个突出特点在于：近似折线一经确定，对于给定的无需再解任何线性方程组，即能相当有效的确定问题(1)的近似解．(2)构造近似最优曲线的折线时，一般应满足下面基本要求：当点从出发沿着折线前进时:(P1)点到的距离单调增；(P2)函数值严格单调降；

5、性质(P1)确保对任意给定的折线上的近似解惟一．性质(P2)确保在折线上所确定的近似解能满足收敛性定理的条件．折线法算法原理(1970)连接Cauchy点(由最速下降法产生的极小点C.P.)和牛顿点(即由牛顿法产生的极小点）,其连线与信赖域的边界的交点取为显然,当牛顿步的长度时，就取为对二次模型：精确线搜索下Cauchy步为：若取若再计算牛顿步若取否则取其中由方程得到．综上：双折线法(1979)让信赖域迭代中产生的点偏向牛顿方向，于是把Cauchy点和牛顿方向上的点连接起来，并将这条连线与信赖域边界的交点取为折线称为单折线．把称为双折线．在双折线情形下：

6、其中一般取例1：设在当前点试用双折线法求解：由于计算有：由于故取双折线步长为：使得解二次方程得因此所以