文档介绍：第二章下降算法与线性搜索
第1页，共28页，编辑于2022年，星期一
第二章无约束问题的下降算法
与线性搜索
第一节无约束问题的最优性条件
第二节下降算法的一般步骤
第三节线性搜索第二章下降算法与线性搜索
第1页，共28页，编辑于2022年，星期一
第二章无约束问题的下降算法
与线性搜索
第一节无约束问题的最优性条件
第二节下降算法的一般步骤
第三节线性搜索
第2页，共28页，编辑于2022年，星期一
第一节无约束问题的最优性条件
第3页，共28页，编辑于2022年，星期一
第4页，共28页，编辑于2022年，星期一
第5页，共28页，编辑于2022年，星期一
第6页，共28页，编辑于2022年，星期一
第7页，共28页，编辑于2022年，星期一
第二节下降算法的一般步骤
第8页，共28页，编辑于2022年，星期一
第9页，共28页，编辑于2022年，星期一
第三节线性搜索
第10页，共28页，编辑于2022年，星期一
第11页，共28页，编辑于2022年，星期一
1. 单峰函数
定义：设
是区间
上的一元函数，
是
在
上的极小点，且对任意的
有
（a）当
时，
（b）当
.
.
.
.
.
则称是单峰函数。
.
.
一、精确线性搜索——黄金分割法( )
第12页，共28页，编辑于2022年，星期一
性质：通过计算区间
内两个不同点的函数值，就可以
确定一个包含极小点的子区间。
定理
设
是区间
上的一元函数，
是
在
上的极小点。任取点
则有
（1）如果
，则
（2）如果
则
.
.
.
.
.
第13页，共28页，编辑于2022年，星期一
2. 黄金分割法
思想
通过选取试探点使包含极小点的区间按相同比例不断缩短，
直到区间长度小到一定程度，此时区间上各点的函数
值均接近极小值。
下面推导黄金分割法的计算公式。
第14页，共28页，编辑于2022年，星期一
第15页，共28页，编辑于2022年，星期一
通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。
同理可得。
第16页，共28页，编辑于2022年，星期一
算法步骤：
第17页，共28页，编辑于2022年，星期一
黄金分割法的迭代效果：第k次后迭代后所得区间长度为
初始区间长度的
其它的试探点算法：Fibonacci算法。
第18页，共28页，编辑于2022年，星期一
二、非精确线性搜索— Armijo 型线性搜索和
Wolfe-Powell 型线性搜索
第19页，共28页，编辑于2022年，星期一
第20页，共28页，编辑于2022年，星期一
第21页，共28页，编辑于2022年，星期一
第22页，共28页，编辑于2022年，星期一
第23页，共28页，编辑于2022年，星期一
O
e
b
c
a
Armijo : [0， a ]
Wolfe-Powell: [e, c]
Goldstein: [b, c]
各种线性搜索的图例
第24页，共28页，编辑于2022年，星期一
四、下降算法的全局收敛性和超线性收敛性
第25页，共28页，编辑于2022年，星期一
第26页，共28页，编辑于2022年，星期一
第27页，共28页，编辑于2022年，星期一
上述定理说明了下降算法的收敛速度和取单位步长的重要性
第28页，共28页，编辑于2022年，星期一