第三章线 性 搜 索问题描述已知,kx 并且求出了 kx 处的可行下降方向,kp
从 kx 出发,沿方向 kp 求目标函数的最优解，
或者选取
00 m inm in kk pxf
0?k? 使得：
00m in kTkkk ppxf
设其最优解为 k? （叫精确步长因子），
kkkk pxx 1
所以线性搜索是求解一元函数
的最优化问 题（也叫一维最优化问题）。
我们来求解：
于是得到一个新点：
xfbxamin
一般地，线性搜索算法分成两个阶段：
第一阶段确定包含理想的步长因子
（或问题最优解）的搜索区间；
第二阶段采用某种分割技术或插值方法缩小这个区间。
进退法（寻找下单峰区间）
在线搜索之前，必须先知道一个
0; 121 fxfxfxf
xf
单峰区间。
的下我们将求出xf 的一个形如b,0
形式的下单峰区间。
因为我们关心的问题是,
00 m inm in kk pxf
我们的目的是找出两个点,21 xx? 使得：
0x
给定初始点,0
0?x
初始步长 xxxx
01,0
（１）
01 xfxf?
1x 对应着图上用红线标出的一部分下面分两种情况讨论：
0x
此时
1x
我们加大步长向右搜索，
xxxxx 12,2
若,
21 xfxf20,xx
（１）
01 xfxf?
x?
1x
x?2
2x
取值小，
取则我们要找的区间即为
0x
（１）
01 xfxf?
x?
1x
x?2
2x
若继续往下判断，直到满足
,21 xfxf? 则我们取的步长偏小。
令 xxxxxxx
1221,2,
.21 xfxf?
2x
1x
0x
此时
1x
我们缩小步长向左搜索，
xxxxxxx 2112,,2/
若,
01 xfxf20,xx
（２）
01 xfxf?
1x 2x
取值大，
取则我们要找的区间即为
1x
否则继续缩小区间，直到满足.
01 xfxf?
算法 3.1 进退法
Step1
给定初始点,0
0?x
初始步长0x
计算,
0xf
转 Step２
Step2,
01 xxx 计算,1xf
若,
01 xfxf? 则转 Step３； 否则 转 Step５。
Step3 令,,2 12 xxxxx 计算.
2xf
若,21 xfxf? 则得区间
20,xx 为初始区间，停；
若,21 xfxf? 则转 Step4。
Step4
Step5
令,,
2121 xfxfxx
令转 Step３。
,,1212 xfxfxx 转 Step6。
Step6 令,,2/
21 xxxxx 计算,1xf
若,
01 xfxf? 则得区间20,xx 为初始区间，停；
若,
01 xfxf? 则转 Step5。
作业（上机）
用进退法求函数 22 xxxf
形如的一个
b,0 的初始区间。
§ 3.1 区间分割法设xf 在ba,上为下单峰函数,即有唯一的极小点,*x 在 *x 左边xf 严格下降,在 *x
右边xf 严格上升。
在ba,内任取,21 xx?
若,21 xfxf? 则2*,xax?
若,21 xfxf? 则bxx,1*?
Fibonacci法为了尽快得到结果，希望区间缩小的尽量小。
如果在区间只有一个试点，我们无法将区间缩小。
如果知道两个试点,21 xx? 根据21,xfxf 的大小关系,可以得到缩小的区间2,xa 或者.,
1 bx
下面我们考虑任给一个另外一种思维方式为，
xf 的单峰区间,,ba
如果给定试点的个数,n 如何使最后确定的包含最优值的区间尽量的小。
按什么方式取点，
求 n 次函数值之后,可最多将多长的原始区间长度缩小为,1 设
nL
为试点个数为,n 最终区间长度为 1 时,原始区间ba,的最大可能长度。
设最初两个试点为
1x 和,2x
若极小点在
1,xa
内,至多还有 2?n 个试点，
则,
21 nLax
若极小点在bx,1 内,包括 2x 在内可以有 1?n
个试点,则,
11 nLxb
因此，,
21 nnn LLL
如果我们采取合适的技巧，可以使得：
,21 nnn LLL 另外,显然,.110 LL
从而
nL
满足差分方程：
1
2
10
21
LL
nLLL nnn
此为 Fibonacci数列，一般写为：
1
2
10
21
FF
nFFF nnn
若原始区间为,,ba 要求最终区间长度,
则,
abF
n
由此可确定,n 区间缩短之后与之前的比依次为：
2
1,
3
2,
5
3,,,
1
21?
n
n
n
n
F
F
F
F
n 确定之后，最初两个试点分别为：
ab
F
Faxab
F
Fax
n
n
n
n 1
2
2
1
21,xx 关于ba,对称上述过程完成了依次迭代，新区间仍记为
1?i
ba,
若已经进行了 次迭代,第 i 次迭代时,还有
1in 个试点（包括已经计算过的函数值的一个）
abF FaxabFFax
in
in
in
in
1
2
1
1
1
注意,
（２）若在一定的误差范围内,,21 xfxf?
则认为 *x 在21,xx 内
（１）最后的两个试点的选取方式：
abxxabx 1.0,2/ 121
例 3.1（ Fibonacci法）
用 Fibonacci法求函数 22 xxxf 在区间
3,1? 上的极小点。 要求最终区间长度不大于原始区间长度的 0.08倍．
解,函数xf 在区间3,1? 上为下单峰函数，
32.008.013
由,5.1208.0/1
nF
可知 n 应取６.13
6?F
第一次迭代：
3,1 ba
ab
F
Fax
6
4
1
41351
538.0?
4 6 2.14
13
81
6
5
2 abF
Fax
675.2,751.1 21 ff
,21 ff? 缩短后区间为462.1,1?
第二次迭代：
4 6 2.1,1 ba
538.02?x
751.12?f
0 7 7.014 6 2.11
5
3
1 F
Fx
083.21?f
,21 ff? 缩短后区间为4 6 2.1,0 7 7.0?
第三次迭代：
4 6 2.1,1 ba 538.01?x 751.11?f
846.0077.0462.1077.0
4
3
2 F
Fx 870.1
2?f
,21 ff? 缩短后区间为846.0,077.0?
第四次迭代：
846.0,1 ba 538.02?x 751.12?f
231.0077.0846.0077.0
3
1
1 F
Fx 822.11?f
,21 ff? 缩短后区间为846.0,231.0
第五次迭代：
8 4 6.0,2 3 1.0 ba 538.02?x 751.12?f
4 7 7.02 3 1.08 4 6.01.021 xx 751.11?f
,21 ff? 取最优解 50 8.0
2
21* xxx
Fibonacci方法评价
Fibonacci法的优点
（１）如果缩小的区间包含原来的试点，则该试点在下一步被利用；
（２）效率最高，有限个试点的情况下，可将最优点所在的区间缩小到最小．
Fibonacci法的缺点
（１）搜索前先要计算搜索的步数；
（２）每次搜索试点计算的公式不一致．
黄金分割法我们希望保留 Fibonacci法的优点（效率最高是不可能保留的），改进其缺点．
若第一次选取的试点为,21 xx? 则下一步保留的区间为2,xa 或,,
1 bx 两者的机会是均等的．
因此我们选取试点时希望,12 xbax
设,1 abpax 则.12 abpax
另外，我们希望如果缩小的区间包含原来的我们希望原来的试点，则该试点在下一步被利用．若保留的区间为,,
2xa 前一次的试点 1x 在这个区间内．
1x 在缩小的区间内成为新的,2x 我们根据这条件来计算,p
计算 2x 的公式为,abpax 12
因此我们希望,abpax 12
即,aabpapaabpa 11
化简得：
618.01382.0
2
530132 pppp
若保留区间为,,
1 bx
我们得到的结果是一致的,该方法称为黄金分割法，实际计算取：
abaxabax 618.0382.0 21
所以黄金分割法又称为 0.618法．
黄金分割法每次缩小区间的比例是一致的，
每次将区间长度缩小到原来的 0.618倍．
算法 3.2 黄金分割法
Step1
给定baba?,以及 0
令,,3 8 2.0 111 xffabax
Step2
Step3
转 Step２,
令,,6 1 8.0 222 xffabax 转 Step３,
若, ab 则,
2
* bax 停； 否则 转 Step４,
Step4 若,21 ff? 则,,,
12122 ffxxxb
,,3 8 2.0 111 xffabax 转 Step3.
算法 3.2 黄金分割法
Step4 若,
21 ff? 则,,21 xbxa
,,3 8 2.0 111 xffabax
,,6 1 8.0 222 xffabax 转 Step3.
若,21 ff? 则,,,
21211 ffxxxa
,,6 1 8.0 222 xffabax 转 Step3.
例 3.2（黄金分割法）
用黄金分割法求函数 22 xxxf 在区间
3,1? 上的极小点。 要求最终区间长度不大于原始区间长度的 0.08倍．
解,函数xf 在区间3,1? 上为下单峰函数，
32.008.013
第一次迭代：
3,1 ba 528.0382.01 abax 751.11?f
4 7 2.16 1 8.02 abax 695.22?f
,21 ff? 缩短后区间为472.1,1?
第二次迭代：
4 7 2.1,1 ba 528.012 xx 7 5 1.112 ff
059.21?f
,21 ff? 缩短后区间为4 7 2.1,0 5 6.0?
0 5 6.03 8 2.01 abax
迭代次数
０ 0.528 1.472 1.751 2.695 否
１ -0.056 0.528 2.059 1.751 否
２ 0.528 0.888 1.751 1.901 否
３ 0.305 0.528 1.788 1.751 否
４ 0.528 0.665 1.751 1.777 否
５ 0.443 0.528 1.753 1.751 否
６ 0.528 0.580 1.751 1.757 是
ba,1x 2x 1f 2f ab
3,1?
472.1,1?
4 7 2.1,0 5 6.0?
888.0,056.0?
888.0,305.0
665.0,305.0
665.0,443.0
5 5 4.02/6 6 5.04 4 3.0*x
黄金分割法和 Fibonacci法之间的关系
6 18.0
2
15lim 1
n
n
n F
F
0.618法为 Fibonacci法的极限形式作业：黄金分割法（上机）
测试用,例 3.2
计算用,P111 T3(1)
二分法若xf 的导数存在且容易计算,则线性搜索的速度可以得到提高,下面的二分法每次将区间缩小至原来的二分之一．
设xf 为下单峰函数,若xf 在ba,内具有连续的一阶导数,且 0,0 bfaf
取,2/bac 若,0 cf 则 c 为极小点；
若,0 cf 则以ca,代替ba,
若,0 cf 则以cb,代替ba,
§ 3.2 插值法抛物线法在求一元函数的极小点问题上,我们可以用若干点处的函数值来构造一个多项式,用这个多项式的极小点作为原来函数极小点的近似值．
抛物线法就是一个用二次函数来逼近xf
的方法,这也是我们常说的二次插值法．
设在已知的三点 201 xxx 处对应的函数值
,ii fxf? 且满足,,2001 ffff
过三点
220011,,,,,fxfxfx 作二次函数,xy
即作一条抛物线,则可推导出：
2
1202
10
0
2010
21
1
2101
20 f
xxxx
xxxxf
xxxx
xxxxf
xxxx
xxxxx
为求x? 的极小点,令 0 x? 得：
210021102
2
2
1
2
00
2
2
2
11
2
0
2
2
2
1
fxxfxxfxx
fxxfxxfxxx
若 x 充分接近,
0x
即, xx 0
则把 x 作为近似极小点．
否则计算,fxf? 找出
0f
和 f 之间的大者，
去掉
1x
或,
2x
使新的三点仍具有两端点的函数值大于中间点的函数值的性质,利用新的点再构造二次函数,继续进行迭代．
算法 3.3 抛物线法（二次插值法）
Step2
已知三点,
201 xxx
对应的函数值满足
,201 fff 控制误差,0,0 21
Step1 若,
121 xx 则转 Step10;否则转 Step２ ;
若,2210021102 fxxfxxfxx
则转 Step10;否则转 Step3;
Step3 按公式计算,x 并计算xff? 转 Step4;
Step4 若,00 ff 则转 Step６；
若,00 ff 则转 Step７；若若,00 ff 则转 Step５；
Step5 若,
0 xx? 则令,,,,002002 ffffxxxx
转 Step1;否则,,,,001001 ffffxxxx 转 Step1;
Step6 若,
0 xx?
则,,22 ffxx 转 Step1;
否则,,11 ffxx 转 Step1;
Step7 若,0 xx? 则,
2,,
21
0201
xxxxxxx
,,201 ffff 计算,00 xff? 转 Step1;
若,
0 xx?
则转 Step8;
若,0 xx? 则转 Step9;
Step8 令,
2?
01 xxx 计算; xff?
若,?
0ff?
则,?,,?,002002 ffffxxxx
则转 Step1;
,0 xx?
Step8 若,?
0ff?
则,
2,,?
21
0021
xxxxxxx
,,? 021 ffff 计算,00 xff? 转 Step1;
若,?
0ff? 则,?,? 11 ffxx 转 Step1;
Step9 令,,,
2,,021
21
0021 ffff
xxxxxxx
计算,
00 xff? 转 Step1;
Step10令,,
0*0* ffxx
停．
§ 3.3 不精确的线搜索前面介绍的几种线搜索方法,都是为了获得一元函数xf 的最优解，
线搜索一般很难得到线搜索．
在解非线性规划问题中，
真正的精确值．
所以习惯上称为精确因此,不精确的线搜索开始日益受到重视．
不精确线搜索就是,即在 kx 点确定了下降方向 kp 后,只计算少量的几次函数就可以得到一个满足
kk xfxf 1
的近似点,1?kx
不精确线搜索要求产生的点列具有某种收敛性,所以除了对下降方向 kp 有要求之外，
对步长
k?
也有要求,即要求目标函数要：,充分的下降,,
Wolfe原则设xf 可微,取,1,,
2
1,0
选取
0?k? 使：
1.3.3kTkkkkkk pgpxfxf
2.3.3kTkkTkkk pgppxf
或用下面更强的条件代替（ 3.3.2）式：
3.3.3kTkkTkkk pgppxf
Wolfe原则的解释给定,xf 迭代点,kx 下降方向,kp
我们要求解
kk pxfm in 的近似极小值．
我们首先要求,
,kkkk xfpxf
即,0k
k? 的取值对应于曲线上红色的部分．
kk pxf 的图形在实际计算中,我们不仅要求函数值下降，
而且下降的量有一定的要求．
如果0,负的比较多,,我们希望下降的多，
另外,如果取得比较大,我们也希望下降量大．
通常的要求是原则一：
00 kkk xf
从图形上看,k? 的合理取值对应于曲线上位于一条直线下方的部分．
1 时,对应的直线是曲线在 0 处的切线．
为了保证直线在曲线的上方,? 的取值应小于１．
另外,如果直线偏下（取值接近于１）,可能导致? 的取值范围过小,不利于线搜索,通常取
在０到 1/2之间．
从图形可以看出,在我们上面所要求的?
的范围内,函数值的下降还有可能比较小．
我们还希望达到比较高的下降效率．
如果
k 的导数,负得比较大,,说明函数值还可以继续下降．
因此我们通常还要求 有一个下界,此下界通常比0 小一些，我们要求：
100 k
因此我们又有如下的原则：
100 k
另外，如果? 的取值过小，则
k?
另外，如果 的取值范围过小,同样不利于线搜索（已接近于精确线搜索）．
通常取? 在? 与１之间．
由于原则二的限制，
k?
的取值范围缩小．
从上面的图形还可以看出，在
k?
的容许取值范围内，还有一段曲线上升的部分，可能导致函数值下降不大．
因此我们还要求
k
的值不能,正,的太大．
于是原则二改为：
10 k
利用改进的原则，函数值下降的效果可以让人接受．这里原则一是不可缺少的，它严格地划定了原则二搜索的范围．
原则一2/100 kkk xf
原则二10
k
改进的原则二10
k
由于
k
T
kkkk ppxf 于是得到：
原则一2/10 kTkkkkkk pfxfpxf
原则二1
kTkk
T
kkk pfppxf
改进的原则二1
k
T
kk
T
kkk pfppxf
关于满足 Wolfe原则的步长
k?
的存在性：
定理,设xf 有下界且,0?kTk pg 令,
2
1,1?
,1, 则存在区间,0,,2121 cccc
使得21,cc 均满足式（ 3.3.1)和
3.3.2（也满足 3.3.3）．
不精确的线搜索 Wolfe算法问题,设已知,kx 下降方向,kp 求问题：
kk pxf 0m in
的近似值
,1,,
2
1,0
使 k? 满足 (3.3.1)和 (3.3.2)
算法 3.4 不精确的线搜索 Wolfe算法
step1,给定 令
0,1,,0 jba?
,k?
Step2：,
1 kkk pxx 计算 11, kk gf
若? 满足 (3.3.1)和 (3.3.2)式,则令,k
若? 不满足 (3.3.1),则令 j=j+1,转 Step3
若? 不满足 (3.3.2),则令 j=j+1,转 Step4
Step3,令
2,
ab 转 Step2
Step4,令
2
,2m in,ba 转 Step2
停例 3.3（不精确线搜索）
用不精确线搜索求 Rosenbrock函数：
解：
212212 1100 xxxxf
在点T
kx 0,0?
沿方向Tkp 0,1? 的近似步长
k?
2
12
11
22
12
2 0 0
124 0 0
xx
xxxxxf
2,0,2,10,0 kTkTkk pggff
Step1,给定 5.0,1.0
令 0,1,,0 jba?
Step2, 1000,1,0,1
11 ffpxx k
T
kkk?
因为 2.0991 kTkkk pgff
所以（ 3.3.1）不成立，转 Step3
Step3,令,5.02/012/,1 ab
转 Step2,重新计算
1?kx
计算过程见下表：
条件
(1)
条件
(2)
0 1 1 100 不成立
1 1 0.5 6.25 不成立
2 1 0.25 0.953 不成立
3 1 0.125 0.790 成立 成立
j kx kf? 1?kx 1?kf
T0,0
T0,0
T0,0
T0,0
T0,1
T0,5.0
T0,25.0
T0,125.0
与黄金分割法对比：初始区间 [0,1],精度 0.001
迭代次数
0 [0,1] 0.382 0.618 2.511 14.732
1 [0,0.618] 0.236 0.382 0.894 2.511
2 [0,0.382] 0.146 0.236 0.775 0.894
3 [0,0.236] 0.090 0.146 0.834 0.775
4 [0.090,0.236] 0.146 0.180 0.775 0.778
5 [0.090,0.180] 0.125 0.146 0.790 0.775
ba,1x 2x 1f 2f
迭代次数
6 [0.125,0.180] 0.146 0.159 0.774 0.771
7 [0.146,0.180] 0.159 0.167 0.771 0.772
8 [0.146,0.167] 0.154 0.159 0.772 0.771
9 [0.154,0.167] 0.159 0.162 0.771 0.771
10 [0.159,0.167] 0.162 0.164 0.771 0.771
ba,1x 2x 1f 2f
作业：不精确线搜索 Wolfe算法（上机）
测试用,例 3.3
计算用,例 3.3中,T
k
T
k px 1,1,1,1
并和黄金分割法对比．
从 kx 出发,沿方向 kp 求目标函数的最优解，
或者选取
00 m inm in kk pxf
0?k? 使得：
00m in kTkkk ppxf
设其最优解为 k? （叫精确步长因子），
kkkk pxx 1
所以线性搜索是求解一元函数
的最优化问 题（也叫一维最优化问题）。
我们来求解：
于是得到一个新点：
xfbxamin
一般地，线性搜索算法分成两个阶段：
第一阶段确定包含理想的步长因子
（或问题最优解）的搜索区间；
第二阶段采用某种分割技术或插值方法缩小这个区间。
进退法（寻找下单峰区间）
在线搜索之前，必须先知道一个
0; 121 fxfxfxf
xf
单峰区间。
的下我们将求出xf 的一个形如b,0
形式的下单峰区间。
因为我们关心的问题是,
00 m inm in kk pxf
我们的目的是找出两个点,21 xx? 使得：
0x
给定初始点,0
0?x
初始步长 xxxx
01,0
（１）
01 xfxf?
1x 对应着图上用红线标出的一部分下面分两种情况讨论：
0x
此时
1x
我们加大步长向右搜索，
xxxxx 12,2
若,
21 xfxf20,xx
（１）
01 xfxf?
x?
1x
x?2
2x
取值小，
取则我们要找的区间即为
0x
（１）
01 xfxf?
x?
1x
x?2
2x
若继续往下判断，直到满足
,21 xfxf? 则我们取的步长偏小。
令 xxxxxxx
1221,2,
.21 xfxf?
2x
1x
0x
此时
1x
我们缩小步长向左搜索，
xxxxxxx 2112,,2/
若,
01 xfxf20,xx
（２）
01 xfxf?
1x 2x
取值大，
取则我们要找的区间即为
1x
否则继续缩小区间，直到满足.
01 xfxf?
算法 3.1 进退法
Step1
给定初始点,0
0?x
初始步长0x
计算,
0xf
转 Step２
Step2,
01 xxx 计算,1xf
若,
01 xfxf? 则转 Step３； 否则 转 Step５。
Step3 令,,2 12 xxxxx 计算.
2xf
若,21 xfxf? 则得区间
20,xx 为初始区间，停；
若,21 xfxf? 则转 Step4。
Step4
Step5
令,,
2121 xfxfxx
令转 Step３。
,,1212 xfxfxx 转 Step6。
Step6 令,,2/
21 xxxxx 计算,1xf
若,
01 xfxf? 则得区间20,xx 为初始区间，停；
若,
01 xfxf? 则转 Step5。
作业（上机）
用进退法求函数 22 xxxf
形如的一个
b,0 的初始区间。
§ 3.1 区间分割法设xf 在ba,上为下单峰函数,即有唯一的极小点,*x 在 *x 左边xf 严格下降,在 *x
右边xf 严格上升。
在ba,内任取,21 xx?
若,21 xfxf? 则2*,xax?
若,21 xfxf? 则bxx,1*?
Fibonacci法为了尽快得到结果，希望区间缩小的尽量小。
如果在区间只有一个试点，我们无法将区间缩小。
如果知道两个试点,21 xx? 根据21,xfxf 的大小关系,可以得到缩小的区间2,xa 或者.,
1 bx
下面我们考虑任给一个另外一种思维方式为，
xf 的单峰区间,,ba
如果给定试点的个数,n 如何使最后确定的包含最优值的区间尽量的小。
按什么方式取点，
求 n 次函数值之后,可最多将多长的原始区间长度缩小为,1 设
nL
为试点个数为,n 最终区间长度为 1 时,原始区间ba,的最大可能长度。
设最初两个试点为
1x 和,2x
若极小点在
1,xa
内,至多还有 2?n 个试点，
则,
21 nLax
若极小点在bx,1 内,包括 2x 在内可以有 1?n
个试点,则,
11 nLxb
因此，,
21 nnn LLL
如果我们采取合适的技巧，可以使得：
,21 nnn LLL 另外,显然,.110 LL
从而
nL
满足差分方程：
1
2
10
21
LL
nLLL nnn
此为 Fibonacci数列，一般写为：
1
2
10
21
FF
nFFF nnn
若原始区间为,,ba 要求最终区间长度,
则,
abF
n
由此可确定,n 区间缩短之后与之前的比依次为：
2
1,
3
2,
5
3,,,
1
21?
n
n
n
n
F
F
F
F
n 确定之后，最初两个试点分别为：
ab
F
Faxab
F
Fax
n
n
n
n 1
2
2
1
21,xx 关于ba,对称上述过程完成了依次迭代，新区间仍记为
1?i
ba,
若已经进行了 次迭代,第 i 次迭代时,还有
1in 个试点（包括已经计算过的函数值的一个）
abF FaxabFFax
in
in
in
in
1
2
1
1
1
注意,
（２）若在一定的误差范围内,,21 xfxf?
则认为 *x 在21,xx 内
（１）最后的两个试点的选取方式：
abxxabx 1.0,2/ 121
例 3.1（ Fibonacci法）
用 Fibonacci法求函数 22 xxxf 在区间
3,1? 上的极小点。 要求最终区间长度不大于原始区间长度的 0.08倍．
解,函数xf 在区间3,1? 上为下单峰函数，
32.008.013
由,5.1208.0/1
nF
可知 n 应取６.13
6?F
第一次迭代：
3,1 ba
ab
F
Fax
6
4
1
41351
538.0?
4 6 2.14
13
81
6
5
2 abF
Fax
675.2,751.1 21 ff
,21 ff? 缩短后区间为462.1,1?
第二次迭代：
4 6 2.1,1 ba
538.02?x
751.12?f
0 7 7.014 6 2.11
5
3
1 F
Fx
083.21?f
,21 ff? 缩短后区间为4 6 2.1,0 7 7.0?
第三次迭代：
4 6 2.1,1 ba 538.01?x 751.11?f
846.0077.0462.1077.0
4
3
2 F
Fx 870.1
2?f
,21 ff? 缩短后区间为846.0,077.0?
第四次迭代：
846.0,1 ba 538.02?x 751.12?f
231.0077.0846.0077.0
3
1
1 F
Fx 822.11?f
,21 ff? 缩短后区间为846.0,231.0
第五次迭代：
8 4 6.0,2 3 1.0 ba 538.02?x 751.12?f
4 7 7.02 3 1.08 4 6.01.021 xx 751.11?f
,21 ff? 取最优解 50 8.0
2
21* xxx
Fibonacci方法评价
Fibonacci法的优点
（１）如果缩小的区间包含原来的试点，则该试点在下一步被利用；
（２）效率最高，有限个试点的情况下，可将最优点所在的区间缩小到最小．
Fibonacci法的缺点
（１）搜索前先要计算搜索的步数；
（２）每次搜索试点计算的公式不一致．
黄金分割法我们希望保留 Fibonacci法的优点（效率最高是不可能保留的），改进其缺点．
若第一次选取的试点为,21 xx? 则下一步保留的区间为2,xa 或,,
1 bx 两者的机会是均等的．
因此我们选取试点时希望,12 xbax
设,1 abpax 则.12 abpax
另外，我们希望如果缩小的区间包含原来的我们希望原来的试点，则该试点在下一步被利用．若保留的区间为,,
2xa 前一次的试点 1x 在这个区间内．
1x 在缩小的区间内成为新的,2x 我们根据这条件来计算,p
计算 2x 的公式为,abpax 12
因此我们希望,abpax 12
即,aabpapaabpa 11
化简得：
618.01382.0
2
530132 pppp
若保留区间为,,
1 bx
我们得到的结果是一致的,该方法称为黄金分割法，实际计算取：
abaxabax 618.0382.0 21
所以黄金分割法又称为 0.618法．
黄金分割法每次缩小区间的比例是一致的，
每次将区间长度缩小到原来的 0.618倍．
算法 3.2 黄金分割法
Step1
给定baba?,以及 0
令,,3 8 2.0 111 xffabax
Step2
Step3
转 Step２,
令,,6 1 8.0 222 xffabax 转 Step３,
若, ab 则,
2
* bax 停； 否则 转 Step４,
Step4 若,21 ff? 则,,,
12122 ffxxxb
,,3 8 2.0 111 xffabax 转 Step3.
算法 3.2 黄金分割法
Step4 若,
21 ff? 则,,21 xbxa
,,3 8 2.0 111 xffabax
,,6 1 8.0 222 xffabax 转 Step3.
若,21 ff? 则,,,
21211 ffxxxa
,,6 1 8.0 222 xffabax 转 Step3.
例 3.2（黄金分割法）
用黄金分割法求函数 22 xxxf 在区间
3,1? 上的极小点。 要求最终区间长度不大于原始区间长度的 0.08倍．
解,函数xf 在区间3,1? 上为下单峰函数，
32.008.013
第一次迭代：
3,1 ba 528.0382.01 abax 751.11?f
4 7 2.16 1 8.02 abax 695.22?f
,21 ff? 缩短后区间为472.1,1?
第二次迭代：
4 7 2.1,1 ba 528.012 xx 7 5 1.112 ff
059.21?f
,21 ff? 缩短后区间为4 7 2.1,0 5 6.0?
0 5 6.03 8 2.01 abax
迭代次数
０ 0.528 1.472 1.751 2.695 否
１ -0.056 0.528 2.059 1.751 否
２ 0.528 0.888 1.751 1.901 否
３ 0.305 0.528 1.788 1.751 否
４ 0.528 0.665 1.751 1.777 否
５ 0.443 0.528 1.753 1.751 否
６ 0.528 0.580 1.751 1.757 是
ba,1x 2x 1f 2f ab
3,1?
472.1,1?
4 7 2.1,0 5 6.0?
888.0,056.0?
888.0,305.0
665.0,305.0
665.0,443.0
5 5 4.02/6 6 5.04 4 3.0*x
黄金分割法和 Fibonacci法之间的关系
6 18.0
2
15lim 1
n
n
n F
F
0.618法为 Fibonacci法的极限形式作业：黄金分割法（上机）
测试用,例 3.2
计算用,P111 T3(1)
二分法若xf 的导数存在且容易计算,则线性搜索的速度可以得到提高,下面的二分法每次将区间缩小至原来的二分之一．
设xf 为下单峰函数,若xf 在ba,内具有连续的一阶导数,且 0,0 bfaf
取,2/bac 若,0 cf 则 c 为极小点；
若,0 cf 则以ca,代替ba,
若,0 cf 则以cb,代替ba,
§ 3.2 插值法抛物线法在求一元函数的极小点问题上,我们可以用若干点处的函数值来构造一个多项式,用这个多项式的极小点作为原来函数极小点的近似值．
抛物线法就是一个用二次函数来逼近xf
的方法,这也是我们常说的二次插值法．
设在已知的三点 201 xxx 处对应的函数值
,ii fxf? 且满足,,2001 ffff
过三点
220011,,,,,fxfxfx 作二次函数,xy
即作一条抛物线,则可推导出：
2
1202
10
0
2010
21
1
2101
20 f
xxxx
xxxxf
xxxx
xxxxf
xxxx
xxxxx
为求x? 的极小点,令 0 x? 得：
210021102
2
2
1
2
00
2
2
2
11
2
0
2
2
2
1
fxxfxxfxx
fxxfxxfxxx
若 x 充分接近,
0x
即, xx 0
则把 x 作为近似极小点．
否则计算,fxf? 找出
0f
和 f 之间的大者，
去掉
1x
或,
2x
使新的三点仍具有两端点的函数值大于中间点的函数值的性质,利用新的点再构造二次函数,继续进行迭代．
算法 3.3 抛物线法（二次插值法）
Step2
已知三点,
201 xxx
对应的函数值满足
,201 fff 控制误差,0,0 21
Step1 若,
121 xx 则转 Step10;否则转 Step２ ;
若,2210021102 fxxfxxfxx
则转 Step10;否则转 Step3;
Step3 按公式计算,x 并计算xff? 转 Step4;
Step4 若,00 ff 则转 Step６；
若,00 ff 则转 Step７；若若,00 ff 则转 Step５；
Step5 若,
0 xx? 则令,,,,002002 ffffxxxx
转 Step1;否则,,,,001001 ffffxxxx 转 Step1;
Step6 若,
0 xx?
则,,22 ffxx 转 Step1;
否则,,11 ffxx 转 Step1;
Step7 若,0 xx? 则,
2,,
21
0201
xxxxxxx
,,201 ffff 计算,00 xff? 转 Step1;
若,
0 xx?
则转 Step8;
若,0 xx? 则转 Step9;
Step8 令,
2?
01 xxx 计算; xff?
若,?
0ff?
则,?,,?,002002 ffffxxxx
则转 Step1;
,0 xx?
Step8 若,?
0ff?
则,
2,,?
21
0021
xxxxxxx
,,? 021 ffff 计算,00 xff? 转 Step1;
若,?
0ff? 则,?,? 11 ffxx 转 Step1;
Step9 令,,,
2,,021
21
0021 ffff
xxxxxxx
计算,
00 xff? 转 Step1;
Step10令,,
0*0* ffxx
停．
§ 3.3 不精确的线搜索前面介绍的几种线搜索方法,都是为了获得一元函数xf 的最优解，
线搜索一般很难得到线搜索．
在解非线性规划问题中，
真正的精确值．
所以习惯上称为精确因此,不精确的线搜索开始日益受到重视．
不精确线搜索就是,即在 kx 点确定了下降方向 kp 后,只计算少量的几次函数就可以得到一个满足
kk xfxf 1
的近似点,1?kx
不精确线搜索要求产生的点列具有某种收敛性,所以除了对下降方向 kp 有要求之外，
对步长
k?
也有要求,即要求目标函数要：,充分的下降,,
Wolfe原则设xf 可微,取,1,,
2
1,0
选取
0?k? 使：
1.3.3kTkkkkkk pgpxfxf
2.3.3kTkkTkkk pgppxf
或用下面更强的条件代替（ 3.3.2）式：
3.3.3kTkkTkkk pgppxf
Wolfe原则的解释给定,xf 迭代点,kx 下降方向,kp
我们要求解
kk pxfm in 的近似极小值．
我们首先要求,
,kkkk xfpxf
即,0k
k? 的取值对应于曲线上红色的部分．
kk pxf 的图形在实际计算中,我们不仅要求函数值下降，
而且下降的量有一定的要求．
如果0,负的比较多,,我们希望下降的多，
另外,如果取得比较大,我们也希望下降量大．
通常的要求是原则一：
00 kkk xf
从图形上看,k? 的合理取值对应于曲线上位于一条直线下方的部分．
1 时,对应的直线是曲线在 0 处的切线．
为了保证直线在曲线的上方,? 的取值应小于１．
另外,如果直线偏下（取值接近于１）,可能导致? 的取值范围过小,不利于线搜索,通常取
在０到 1/2之间．
从图形可以看出,在我们上面所要求的?
的范围内,函数值的下降还有可能比较小．
我们还希望达到比较高的下降效率．
如果
k 的导数,负得比较大,,说明函数值还可以继续下降．
因此我们通常还要求 有一个下界,此下界通常比0 小一些，我们要求：
100 k
因此我们又有如下的原则：
100 k
另外，如果? 的取值过小，则
k?
另外，如果 的取值范围过小,同样不利于线搜索（已接近于精确线搜索）．
通常取? 在? 与１之间．
由于原则二的限制，
k?
的取值范围缩小．
从上面的图形还可以看出，在
k?
的容许取值范围内，还有一段曲线上升的部分，可能导致函数值下降不大．
因此我们还要求
k
的值不能,正,的太大．
于是原则二改为：
10 k
利用改进的原则，函数值下降的效果可以让人接受．这里原则一是不可缺少的，它严格地划定了原则二搜索的范围．
原则一2/100 kkk xf
原则二10
k
改进的原则二10
k
由于
k
T
kkkk ppxf 于是得到：
原则一2/10 kTkkkkkk pfxfpxf
原则二1
kTkk
T
kkk pfppxf
改进的原则二1
k
T
kk
T
kkk pfppxf
关于满足 Wolfe原则的步长
k?
的存在性：
定理,设xf 有下界且,0?kTk pg 令,
2
1,1?
,1, 则存在区间,0,,2121 cccc
使得21,cc 均满足式（ 3.3.1)和
3.3.2（也满足 3.3.3）．
不精确的线搜索 Wolfe算法问题,设已知,kx 下降方向,kp 求问题：
kk pxf 0m in
的近似值
,1,,
2
1,0
使 k? 满足 (3.3.1)和 (3.3.2)
算法 3.4 不精确的线搜索 Wolfe算法
step1,给定 令
0,1,,0 jba?
,k?
Step2：,
1 kkk pxx 计算 11, kk gf
若? 满足 (3.3.1)和 (3.3.2)式,则令,k
若? 不满足 (3.3.1),则令 j=j+1,转 Step3
若? 不满足 (3.3.2),则令 j=j+1,转 Step4
Step3,令
2,
ab 转 Step2
Step4,令
2
,2m in,ba 转 Step2
停例 3.3（不精确线搜索）
用不精确线搜索求 Rosenbrock函数：
解：
212212 1100 xxxxf
在点T
kx 0,0?
沿方向Tkp 0,1? 的近似步长
k?
2
12
11
22
12
2 0 0
124 0 0
xx
xxxxxf
2,0,2,10,0 kTkTkk pggff
Step1,给定 5.0,1.0
令 0,1,,0 jba?
Step2, 1000,1,0,1
11 ffpxx k
T
kkk?
因为 2.0991 kTkkk pgff
所以（ 3.3.1）不成立，转 Step3
Step3,令,5.02/012/,1 ab
转 Step2,重新计算
1?kx
计算过程见下表：
条件
(1)
条件
(2)
0 1 1 100 不成立
1 1 0.5 6.25 不成立
2 1 0.25 0.953 不成立
3 1 0.125 0.790 成立 成立
j kx kf? 1?kx 1?kf
T0,0
T0,0
T0,0
T0,0
T0,1
T0,5.0
T0,25.0
T0,125.0
与黄金分割法对比：初始区间 [0,1],精度 0.001
迭代次数
0 [0,1] 0.382 0.618 2.511 14.732
1 [0,0.618] 0.236 0.382 0.894 2.511
2 [0,0.382] 0.146 0.236 0.775 0.894
3 [0,0.236] 0.090 0.146 0.834 0.775
4 [0.090,0.236] 0.146 0.180 0.775 0.778
5 [0.090,0.180] 0.125 0.146 0.790 0.775
ba,1x 2x 1f 2f
迭代次数
6 [0.125,0.180] 0.146 0.159 0.774 0.771
7 [0.146,0.180] 0.159 0.167 0.771 0.772
8 [0.146,0.167] 0.154 0.159 0.772 0.771
9 [0.154,0.167] 0.159 0.162 0.771 0.771
10 [0.159,0.167] 0.162 0.164 0.771 0.771
ba,1x 2x 1f 2f
作业：不精确线搜索 Wolfe算法（上机）
测试用,例 3.3
计算用,例 3.3中,T
k
T
k px 1,1,1,1
并和黄金分割法对比．
