User Tools

Site Tools


keynote:lesson16

第十六课

最优化方法 4

内容 非线性优化

主要参考书: 最优化理论与方法,袁亚湘,孙文瑜,科学出版社

1.插值法 插值法是一类重要的搜索方法,其基本思想是: 在搜索区间中不断用低次(通常不超过三次)多项式来近似目标函数,并逐步用插值多项式的极小点来逼近一维搜索问题的极小点。当函数具有比较好的解析性质时,插值方法比直接方法(0.618法或Fibonacci法)效果更好。

1.1一点二次插值(牛顿法) 利用一点处的函数值、一阶和二阶导数值构造二次插值函 数.迭代形式:

牛顿法的优点是收敛速度快,具有局部二阶收敛速度。

1.2二点二次插值法 给出两点的函数值和其中一点的导数值,构造二次插值函 数。迭代形式为:

 可证明二点二次插值法的收敛阶为1.618,超线性收敛。

1.3三点二次法(抛物线法)

 迭代时,从α1,α2,α3,α¯中选择目标函数最小的点及其左右两点,

进行下一步的迭代。

 超线性收敛,收敛阶近似为1.32。

1.4二点三次插值法 用三次多项式来逼近。比二次插值法有较好的收敛效果, 但通常要求计算导数值,且计算量较大。一般当导数易求 时,用三次插值法较好。

 收敛速度为2阶,一般优于抛物线法。

2.不精确的一维搜索方法

  • 精确一维搜索往往需要花费很大的时间。*

当迭代点远离问题的解时,精确求解通常不十分有效。很多最优化方法,如牛顿法和拟牛顿法,其收敛速度并不依赖于精确一维搜索过程。

  • 只要保证目标函数有满意的下降,可大大节省计算量。*

2.1Armijo-Goldstein准则 2.2Wolfe-Powell准则  Armijo-Goldstein准则有可能把最优步长因子排除在可接受区间外,因此更改第二个条件为 3.牛顿型方法

3.1最速下降法

  • 以负梯度方向作为极小化算法的搜索方向
  • 具有总体收敛性
  • 最速下降方向仅是局部性质

 对于许多问题并非下降方向,而且下降非常缓慢。接近极小点时,步长越小前进越慢

  • 线性收敛

3.2牛顿法

  • 牛顿法的基本思想是利用目标函数的二次Taylor展开,并将其极小化。

  • 对于正定二次函数,一步即可得最优解。
  • 由于目标函数在极点附件近似于二次函数,故在初始点接近极小点时,牛顿法收敛速度较快。
  • 牛顿法具有局部收敛性,为二阶收敛。

3.3改进牛顿法 牛顿法的主要困难在于Hesse阵Gk不正定。这时二次型模型不一定有极小点,甚至没有平稳点。 Goldstein and Price (1967)当Gk非正定时,采用最速下降方向结合方向,给出

3.3.1Goldfeld修正牛顿法 3.3.2Gill-Murray稳定牛顿法 3.3.3Levenberg-Marquardt方法 3.3.4信赖域方法

  • 不仅可以用来代替一维搜索,而且也可以解决Hessen矩阵不正定等困难
  • 主要思想:首先选择一个步长r,使得在||x-xk||<r范围内(信赖域);

目标函数用n维二次模型来逼近,并以此选择一个搜索方向sk,取xk+1=xk+sk。 

  • 具有牛顿法的快速局部收敛性,又具有理想的总体收敛性。

刘振广 2011/07/02 12:11

keynote/lesson16.txt · Last modified: 2014/05/22 08:34 (external edit)