最优化：下降算法与线性搜索

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