User Tools

Site Tools


keynote:lesson16

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
keynote:lesson16 [2011/07/02 12:12]
21021209
keynote:lesson16 [2023/08/19 21:02] (current)
Line 1: Line 1:
 +====== 第十六课 ======
 +**最优化方法 4**
  
 +**内容
 +**非线性优化 ​    
 +
 +**主要参考书:
 +**最优化理论与方法,袁亚湘,孙文瑜,科学出版社
 +
 +**1.插值法**
 +插值法是一类重要的搜索方法,其基本思想是:​
 +在搜索区间中不断用低次(通常不超过三次)多项式来近似目标函数,并逐步用插值多项式的极小点来逼近一维搜索问题的极小点。当函数具有比较好的解析性质时,插值方法比直接方法(0.618法或Fibonacci法)效果更好。  ​
 +
 +**1.1一点二次插值(牛顿法)**
 +利用一点处的函数值、一阶和二阶导数值构造二次插值函
 +数.迭代形式:{{:​keynote:​16-1.png|}}
 +
 +  牛顿法的优点是收敛速度快,具有局部二阶收敛速度。
 +**1.2二点二次插值法
 +**
 +给出两点的函数值和其中一点的导数值,构造二次插值函
 +数。迭代形式为:{{:​keynote:​16-2.png|}}
 +   ​可证明二点二次插值法的收敛阶为1.618,超线性收敛。
 +**1.3三点二次法(抛物线法)**
 +{{:​keynote:​16-3.png|}}
 +   ​迭代时,从α1,α2,α3,α¯中选择目标函数最小的点及其左右两点,
 +进行下一步的迭代。
 +   ​超线性收敛,收敛阶近似为1.32。
 +**   ​1.4二点三次插值法**
 +用三次多项式来逼近。比二次插值法有较好的收敛效果,
 +但通常要求计算导数值,且计算量较大。一般当导数易求
 +时,用三次插值法较好。
 +{{:​keynote:​16-5.png|}}
 +   ​收敛速度为2阶,一般优于抛物线法。
 +**2.不精确的一维搜索方法**
 +  * 精确一维搜索往往需要花费很大的时间。* ​
 +  当迭代点远离问题的解时,精确求解通常不十分有效。很多最优化方法,如牛顿法和拟牛顿法,其收敛速度并不依赖于精确一维搜索过程。
 +  * 只要保证目标函数有满意的下降,可大大节省计算量。* ​
 +**2.1Armijo-Goldstein准则
 +**
 +{{:​keynote:​16-6.png|}}
 +**2.2Wolfe-Powell准则
 +** Armijo-Goldstein准则有可能把最优步长因子排除在可接受区间外,因此更改第二个条件为
 +{{:​keynote:​16-7.png|}}
 +**3.牛顿型方法**
 +
 +
 +**3.1最速下降法**
 +  * 以负梯度方向作为极小化算法的搜索方向
 +  * 具有总体收敛性
 +  * 最速下降方向仅是局部性质
 +        对于许多问题并非下降方向,而且下降非常缓慢。接近极小点时,步长越小前进越慢
 +  * 线性收敛
 +**3.2牛顿法**
 +  * 牛顿法的基本思想是利用目标函数的二次Taylor展开,并将其极小化。
 +{{:​keynote:​16-8.png|}}
 +  * 对于正定二次函数,一步即可得最优解。
 +  * 由于目标函数在极点附件近似于二次函数,故在初始点接近极小点时,牛顿法收敛速度较快。
 +  * 牛顿法具有局部收敛性,为二阶收敛。
 +**3.3改进牛顿法**
 +牛顿法的主要困难在于Hesse阵Gk不正定。这时二次型模型不一定有极小点,甚至没有平稳点。
 +Goldstein and Price (1967)当Gk非正定时,采用最速下降方向结合方向,给出
 +
 +{{:​keynote:​16-9.png|}}
 +**3.3.1Goldfeld修正牛顿法**
 +{{:​keynote:​16-10.png|}}
 +**3.3.2Gill-Murray稳定牛顿法**
 +{{:​keynote:​16-11.png|}}
 +**3.3.3Levenberg-Marquardt方法
 +**
 +{{:​keynote:​16-12.png|}}
 +**3.3.4信赖域方法
 +**
 +  * 不仅可以用来代替一维搜索,而且也可以解决Hessen矩阵不正定等困难
 +  * 主要思想:首先选择一个步长r,使得在||x-xk||<​r范围内(信赖域);
 +  目标函数用n维二次模型来逼近,并以此选择一个搜索方向sk,取xk+1=xk+sk。
 +
 +  * 具有牛顿法的快速局部收敛性,又具有理想的总体收敛性。
 +<note important>​ --- //​[[you@zju.edu.cn|刘振广]] 2011/07/02 12:​11//</​note>​