《最优化下降算法与线性搜索业界研究》由会员分享，可在线阅读，更多相关《最优化下降算法与线性搜索业界研究（45页珍藏版）》请在金锄头文库上搜索。
1、最优化最优化主讲：刘陶文课件制作：刘陶文课件制作：刘陶文唯楚有材唯楚有材 於斯为於斯为盛盛学好最优化，走遍天下都不怕学好最优化，走遍天下都不怕1深层分析第二章第二章 无约束问题的下降算法无约束问题的下降算法 与线性搜索与线性搜索第一节第一节 无约束问题的最优性条件无约束问题的最优性条件第二节第二节 下降算法的一般步骤下降算法的一般步骤第三节第三节 线性搜索线性搜索2深层分析第一节第一节 无约束问题的最优性条件无约束问题的最优性条件3深层分析4深层分析5深层分析注意这个条件不是充分的。注意这个条件不是充分的。6深层分析7深层分析8深层分析9深层分析第二节第二节 下降算法的一般步骤下降算法的一般步
2、骤10深层分析11深层分析12深层分析第三节第三节 线性搜索线性搜索13深层分析一、一、 精确线性搜索精确线性搜索 14深层分析15深层分析16深层分析1. 1. 单峰函数单峰函数一、一、 精确线性搜索精确线性搜索黄金分割法黄金分割法(0.618(0.618法法 ) ) 定义：设是区间上的一元函数，是在上的极小点，且对任意的有（a）当时，（b）当则称 是单峰函数。. .17深层分析性质：通过计算区间内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理 设是区间上的单峰函数， 是在上的极小点。任取点则有（1）如果，则（2）如果则.18深层分析2. 2. 黄金分割法黄金分割法思想：思想：通
3、过选取试探点使包含极小点的区间按相同比例不断缩短，直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。下面推导黄金分下面推导黄金分割法的计算公式割法的计算公式19深层分析20深层分析通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。同理可得同理可得21深层分析算法步骤：算法步骤：22深层分析黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的其它的试探点算法：Fibonacci算法(分数法)。Fibonacci算法计算试探点的公式为：23深层分析FibonacciFibonacci法为一维极小化最优策略，而黄金法为一维极小化最
4、优策略，而黄金分割法为近似最优分割法为近似最优, ,但后者简单，因而较常用但后者简单，因而较常用24深层分析Fibonacci法是黄金分割法的推广，黄金分割法是Fibonacci法的极限25深层分析26深层分析二、二、 非精确线性搜索非精确线性搜索 Armijo Armijo 型线性搜索型线性搜索 和和 Wolfe-Powell Wolfe-Powell 型线性搜索型线性搜索27深层分析Oa可接受区间可接受区间用进退法实现用进退法实现ArmijoArmijo搜索：逐渐变小以满足搜索：逐渐变小以满足ArmijoArmijo搜索条件搜索条件28深层分析29深层分析30深层分析O可接受区间可接受区间
5、c31深层分析为什么？为什么？32深层分析O可接受区间可接受区间c33深层分析34深层分析用进退法实现Wolfe-Powell搜索：逐渐增大以满足搜索条件的第二个条件O可接受区间可接受区间c逐渐变小以满足搜索条件的第一个条件35深层分析36深层分析具体实现如下：具体实现如下：满足第一个条件满足第一个条件不满足第一个条件不满足第一个条件37深层分析作业题：用两点插值法实现作业题：用两点插值法实现Wolfe-Powell搜索搜索38深层分析第三种重要的线性搜索：Goldstein搜索 Oab39深层分析40深层分析四、下降算法的全局收敛性和超线性收敛性四、下降算法的全局收敛性和超线性收敛性41深层分析如果(2.14)成立，我们认为算法是全局收敛的. 该定理表明: 算法的收敛性与夹角有关42深层分析43深层分析44深层分析上述定理说明了下降算法的收敛速度 和取单位步长的重要性关于下降算法的收敛速度，我们有关于下降算法的收敛速度，我们有45深层分析
