第二章下降算法与线性搜索PPT讲稿.ppt

《第二章下降算法与线性搜索PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章下降算法与线性搜索PPT讲稿.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章下降算法与线性搜索第1页，共28页，编辑于2022年，星期二第二章第二章 无约束问题的下降算法无约束问题的下降算法 与线性搜索与线性搜索第一节第一节 无约束问题的最优性条件无约束问题的最优性条件第二节第二节 下降算法的一般步骤下降算法的一般步骤第三节第三节 线性搜索线性搜索第2页，共28页，编辑于2022年，星期二第一节第一节 无约束问题的最优性条件无约束问题的最优性条件第3页，共28页，编辑于2022年，星期二第4页，共28页，编辑于2022年，星期二第5页，共28页，编辑于2022年，星期二第6页，共28页，编辑于2022年，星期二第7页，共28页，编辑于2022年，星期二第二节第二

2、节 下降算法的一般步骤下降算法的一般步骤第8页，共28页，编辑于2022年，星期二第9页，共28页，编辑于2022年，星期二第三节第三节 线性搜索线性搜索第10页，共28页，编辑于2022年，星期二第11页，共28页，编辑于2022年，星期二1.单峰函数单峰函数定义定义：设：设是区间是区间上的一元函数，上的一元函数，是是在在上的极小点，且对任意的上的极小点，且对任意的有有（a）当）当时，时，（b）当）当.则称则称 是单峰函数。是单峰函数。.一、一、精确线性搜索精确线性搜索黄金分割法黄金分割法(0.618法法)第12页，共28页，编辑于2022年，星期二性质：通过计算区间性质：通过计算区间内两个

3、不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间。确定一个包含极小点的子区间。定理定理 设设是区间是区间上的一元函数，上的一元函数，是是在在上的极小点。任取点上的极小点。任取点则有则有（1）如果）如果，则，则（2）如果）如果则则.第13页，共28页，编辑于2022年，星期二2.黄金分割法黄金分割法思想思想通过选取试探点使包含极小点的区间按相同比例不断缩短，通过选取试探点使包含极小点的区间按相同比例不断缩短，直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。值均接近极小值。下面推导黄金分割法的计算公式。下面推导

4、黄金分割法的计算公式。第14页，共28页，编辑于2022年，星期二第15页，共28页，编辑于2022年，星期二通过确定通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次迭代的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。的一个迭代点重合，从而减少算法的计算量。同理可得。同理可得。第16页，共28页，编辑于2022年，星期二算法步骤：算法步骤：第17页，共28页，编辑于2022年，星期二黄金分割法的迭代效果：第黄金分割法的迭代效果：第k次后迭代后所得区间长度为次后迭代后所得区间长度为初始区间长度的初始区间长度的其它的试探点算法：其它的试探点算法：Fibon

5、acci算法。算法。第18页，共28页，编辑于2022年，星期二二、二、非精确线性搜索非精确线性搜索 Armijo 型线性搜索型线性搜索 和和 Wolfe-Powell 型线性搜索型线性搜索第19页，共28页，编辑于2022年，星期二第20页，共28页，编辑于2022年，星期二第21页，共28页，编辑于2022年，星期二第22页，共28页，编辑于2022年，星期二第23页，共28页，编辑于2022年，星期二OebcaArmijo:0，a Wolfe-Powell:e,cGoldstein:b,c各种线性搜索的图例各种线性搜索的图例 第24页，共28页，编辑于2022年，星期二四、下降算法的全局收敛性和超线性收敛性四、下降算法的全局收敛性和超线性收敛性第25页，共28页，编辑于2022年，星期二第26页，共28页，编辑于2022年，星期二第27页，共28页，编辑于2022年，星期二上述定理说明了下降算法的收敛速度上述定理说明了下降算法的收敛速度 和取单位步长的重要性和取单位步长的重要性第28页，共28页，编辑于2022年，星期二