《最优化:下降算法与线性搜索ppt课件.ppt》由会员分享,可在线阅读,更多相关《最优化:下降算法与线性搜索ppt课件.ppt(45页珍藏版)》请在三一办公上搜索。
1、最优化,主讲:刘陶文,课件制作:刘陶文,唯楚有材 於斯为盛,学好最优化,走遍天下都不怕,第二章 无约束问题的下降算法 与线性搜索,第一节 无约束问题的最优性条件第二节 下降算法的一般步骤第三节 线性搜索,第一节 无约束问题的最优性条件,注意这个条件不是充分的。,第二节 下降算法的一般步骤,第三节 线性搜索,一、精确线性搜索,1.单峰函数,一、精确线性搜索黄金分割法(0.618法),性质:通过计算区间,内两个不同点的函数值,就可以,确定一个包含极小点的子区间。,定理,设,是区间,上的单峰函数,,是,在,上的极小点。任取点,则有,(1)如果,,则,(2)如果,则,.,.,.,.,.,2.黄金分割法
2、,思想:,通过选取试探点使包含极小点的区间按相同比例不断缩短,直到区间长度小到一定程度,此时区间上各点的函数值均接近极小值。,下面推导黄金分割法的计算公式,通过确定 的取值,使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合,从而减少算法的计算量。,同理可得,算法步骤:,黄金分割法的迭代效果:第k次后迭代后所得区间长度为初始区间长度的,其它的试探点算法:Fibonacci算法(分数法)。,Fibonacci算法计算试探点的公式为:,Fibonacci法为一维极小化最优策略,而黄金分割法为近似最优,但后者简单,因而较常用,Fibonacci法是黄金分割法的推广,黄金分割法是Fibonacci
3、法的极限,二、非精确线性搜索 Armijo 型线性搜索 和 Wolfe-Powell 型线性搜索,用进退法实现Armijo搜索:逐渐变小以满足Armijo搜索条件,O,可接受区间,c,为什么?,用进退法实现Wolfe-Powell搜索:,逐渐增大以满足搜索条件的第二个条件,逐渐变小以满足搜索条件的第一个条件,具体实现如下:,满足第一个条件,不满足第一个条件,作业题:用两点插值法实现Wolfe-Powell搜索,第三种重要的线性搜索:Goldstein搜索,O,a,b,四、下降算法的全局收敛性和超线性收敛性,如果(2.14)成立,我们认为算法是全局收敛的.该定理表明:算法的收敛性与夹角有关,上述定理说明了下降算法的收敛速度 和取单位步长的重要性,关于下降算法的收敛速度,我们有,