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

最优化主讲：刘陶文课件制作：刘陶文唯楚有材於斯为盛学好最优化，走遍天下都不怕最优化主讲：刘陶文课件制作：刘陶文唯楚有材1第二章无约束问题的下降算法与线性搜索第一节无约束问题的最优性条件第二节下降算法的一般步骤第三节线性搜索第二章无约束问题的下降算法第一节无约束问题的最优性条件2第一节无约束问题的最优性条件第一节无约束问题的最优性条件3最优化：下降算法与线性搜索ppt课件4最优化：下降算法与线性搜索ppt课件5注意这个条件不是充分的。●注意这个条件不是充分的。●6最优化：下降算法与线性搜索ppt课件7最优化：下降算法与线性搜索ppt课件8最优化：下降算法与线性搜索ppt课件9第二节下降算法的一般步骤第二节下降算法的一般步骤10最优化：下降算法与线性搜索ppt课件11最优化：下降算法与线性搜索ppt课件12第三节线性搜索第三节线性搜索13一、精确线性搜索

一、精确线性搜索14最优化：下降算法与线性搜索ppt课件15最优化：下降算法与线性搜索ppt课件161.单峰函数一、精确线性搜索——黄金分割法(0.618法)

定义：设是区间上的一元函数，是在上的极小点，且对任意的有（a）当时，（b）当则称是单峰函数。.......1.单峰函数一、精确线性搜索——黄金分割法(0.61817性质：通过计算区间内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理设是区间上的单峰函数，是在上的极小点。任取点则有（1）如果，则（2）如果则.....性质：通过计算区间内两个不同点的函数值，就可以确定一个包含极182.黄金分割法思想：通过选取试探点使包含极小点的区间按相同比例不断缩短，直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。下面推导黄金分割法的计算公式2.黄金分割法思想：通过选取试探点使包含极小点的区间按相同19最优化：下降算法与线性搜索ppt课件20通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。同理可得通过确定的取值，使上一次迭代剩余的迭代点恰与下同理可得21算法步骤：算法步骤：22黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的其它的试探点算法：Fibonacci算法(分数法)。Fibonacci算法计算试探点的公式为：黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长23Fibonacci法为一维极小化最优策略，而黄金分割法为近似最优,但后者简单，因而较常用Fibonacci法为一维极小化最优策略，而黄金分割法为近似24Fibonacci法是黄金分割法的推广，黄金分割法是Fibonacci法的极限Fibonacci法是黄金分割法的推广，黄金分割法25最优化：下降算法与线性搜索ppt课件26二、非精确线性搜索—Armijo型线性搜索和Wolfe-Powell型线性搜索二、非精确线性搜索—Armijo型线性搜索27Oa可接受区间用进退法实现Armijo搜索：逐渐变小以满足Armijo搜索条件Oa可接受区间用进退法实现Armijo搜索：逐渐变小以满足28最优化：下降算法与线性搜索ppt课件29最优化：下降算法与线性搜索ppt课件30O可接受区间cO可接受区间c31为什么？为什么？32O可接受区间cO可接受区间c33最优化：下降算法与线性搜索ppt课件34用进退法实现Wolfe-Powell搜索：逐渐增大以满足搜索条件的第二个条件O可接受区间c逐渐变小以满足搜索条件的第一个条件用进退法实现Wolfe-Powell搜索：逐渐增大以满足搜索35最优化：下降算法与线性搜索ppt课件36具体实现如下：满足第一个条件不满足第一个条件具体实现如下：满足第一个条件不满足第一个条件37作业题：用两点插值法实现Wolfe-Powell搜索作业题：用两点插值法实现Wolfe-Powell搜索38第三种重要的线性搜索：Goldstein搜索Oab第三种重要的线性搜索：Goldstein搜索Oab39最优化：下降算法与线性搜索ppt课件40四、下降算法的全局收敛性和超线性收敛性四、下降算法的全局收敛性和超线性收敛性41如果(2.14)成立，我们认为算法是全局收敛的.该定理表明:算法的收敛性与夹角有关如果(2.14)成立，我们认为算法是全局收敛的.42最优化：下降算法与线性搜索