This shows you the differences between two versions of the page.
keynote:lesson16 [2014/05/22 16:34] |
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> |