第4章 一维搜索法

三、单谷区间与单谷函数
由于以后要介绍的一些维搜索方法，主要 适用于问题（4.3）在搜索区间中只有唯一的最 优解的情况，为此，我们再给出下面单谷区间 与单谷函数概念．
三、单谷区间与单谷函数
由于以后要介绍的一些维搜索方法，主要适 用于问题（4.3）在搜索区间中只有唯一的最优 解的情况，为此，我们再给出下面单谷区间与 单谷函数概念． 定义4.2 ，闭区间 [a, b] ⊂ R1．若存在 定义4.2 设 ϕ : R1 → R1 * ϕ( t * ∈ [a, b]，使得ϕ (t ) [a, t ]上严格递减， t ) 在 点 在 [t * , b上严格递增，则称 [a, b] 是函数 ϕ (t ) 的单谷区 ] 单谷区 单谷函数． 间，ϕ (t ) 是 [a, b] 上单谷函数 单谷函数 由定义4.2易知，一个区间是某函数的单谷区间 意味着，在该区间中函数
0≤t ≤t max
0≤t ≤t max
min ϕ (t )
若存在闭区间 [a, b] ⊂ [0, + ∞)([a, b] ⊂ [0, t max ]) ， 使 t * ∈ [ a, b，则称 [a, b] 是问题（4.3）的搜索区间． ] 定义４.１简言之，一个一维最优化问题的搜索区间， 就是包含该问题最优解的一个闭区间．通常，在进行 一维搜索时，一般要先确定出问题的一个搜索区间， 然后再此区间中进行搜索求解．
第四章 一维搜索法
由第一章关于求解最优化问题概述中我们知道， 从已知迭代点 出发按照基本迭代格式 X k ∈ Rn X k +1 = X k + t k Pk 来求解最优化问题，其关键在于如何构造一个 搜索方向 和确定一个步长 R n ，使下 Pk ∈ X k +1 tk ∈ 一迭代点 R 1 处的目标函数值下降， 即 f ( X k +1．现在我们来讨论，当搜索 ) < f (X k ) 方向 已经确定的情况下，如何来确定步长 ？ Pk tk 步长因子的选取有多种方法，如取步长为常数， 但这样选取的步长并不最好，如何选取最好步 长呢？实际计算通常采用一维搜索来确定最优 步长．
令 ϕ ′(t ) = 0 ，总可求得极小点 t * ．不妨设ϕ (t ) 在 (a, t * ) 上是单减函数；在 (t * , b) 上是单增函 ϕ 数．所以t ∈ (a, t * )时， ′(t ) < 0 ，故 ϕ ′(a) < 0 ；当 t ∈ (t * , b) 时，ϕ ′(t ) > 0 ，亦即 ϕ ′(b) > 0 ．对分法 的原理如图4.5所示．
Y
h k = − h k t=k+1
a = min{t , tk +1 }
结束
图4.2
另外，从定义4.2还可知，某区间上的单谷函数在 该区间上不一定是连续函数，而凸函数在所给 区间上必然是单谷函数（如图4.3所示）．由定 义4.1和定义4.2知，函数的单谷区间总是相应 问题（4.3）的一个搜索区间（如图4.3所示）， 但反之不然（如图4.4所示）． 单谷区间和单谷函数有如下有用的性质： 定理4.1 设 ϕ : R 1 → R 1 , [a, b]是的单谷区间，任取 t1 , t 2 ∈ [a, b] 并且 t 2 < t1 ． （1）若有 ϕ (t 2 ) ≤ ϕ (t1 ) ，则 [a, t1 ]是 ϕ (t )的单谷区 间． （2）若有 ϕ (t 2 ) ≥ ϕ (t1 ) ，则 [t 2 , b] 是ϕ (t )的单谷区 间．
f ( X + t0 P) = min f ( X + tP) = min ϕ (t )， Z = X + t0 P．
下面进一步解释迭代点 X k +1 = X k + t k Pk 的空间位 置．容易证明，若从 X k出发，沿Pk方向进步一 维搜索得极小点 X k +1 = X k + t k Pk ，则该点处的 X = X k +1 梯度方向 f ( X k +1 )与搜索方向之间应满足 ∇ ∇f ( X k +1 ) T Pk = 0 (4.2) t 事实上，设ϕ (t ) = f ( X k + tPk )，对 求导有 ϕ ′(t ) = ∇f ( X k + tPk ) T Pk 令 ϕ ' (t ) = 0 ，即 ∇f ( X k + tPk ) T Pk = 0 ， 所以 ∇f ( X k +1 ) T Pk = 0 ．
， 当已知迭代点 X k和下降方向 Pk 时，要确定适当的 步长 t k使 f ( X k +1 ) = f ( X k + t k Pk ) 比 f ( X k )有所下降，即相当于对于参变量 t 函数
X∈R
对无约束最优化问题 min f ( X ) n
要在区间[0, + ∞] 上选取t = t k 使 f ( X k +1 ) < f ( X k ) 即 ϕ (t k ) = f ( X k + t k Pk ) < f ( X k ) = ϕ (0) ． 由于这种从已知点 X k 出发，沿某一下降的探索 方向 Pk 来确定步长 t k 的问题，实质上是单变 量函数ϕ (t )关于变量 t 的一维搜索选取问题， 故通常叫做一维搜索．
h0 > 0 ,加步系数α > 1 ,令 k=0
ϕ0 = ϕ (t0 ) ,比较目标函数值 tk +1 = tk + hk ,ϕ k +1 = ϕ (tk =1 )
ϕ k +1 < ϕ k
Y
N
hk +1 = α hk ,t = tk ,tk
= tk +1 ,
ϕk = ϕ k +1 ,k=k+1
N
ห้องสมุดไป่ตู้
k=0
ϕ (t ) = f ( X k + tPk )
按这种方法确定的步长 t k 又称为最优步长，这 种方 法的优点是，它使目标函数值在搜索方向 上下降得最多． 今后为了简便起见，我们用记号 Z = l s ( X , P) （4.1） 表示从点X出发沿方向对目标函数作直线搜索 所 得 到 的 极 小 点 是 ． 其 中 和 分 别 是 Linear search（直线搜索）两词的词首．在目标函数 f (X 已确定的条件下（4.1）等价于如下两式： )
式（4.2）的几何意义是明显的．从某一点出发 沿方向对目标函数作直线搜索，所得到的极小 点为．式（4.2）指出，梯度必与搜索方向正 交．又因为与目标函数过点的等值面正交，所 以进一步看到，搜索方向民这个等值面在点处 相切（如图4.1所示）．
§4.1 搜索区间及其确定方法
一、搜索区间
设一维最优化问题为 （4.3） 为了求解问题（4.3），我们引入如下的搜索区间概 念． ϕ : R 1 → R 1 , t * ∈ [0, + ∞)(t * ∈ [0, t max ]) 定义4.1 设 ，并且 定义 ϕ (t * ) = min ϕ (t )
图4.3
图4.4
证明略． 定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较 小的单谷区间．换句话说利用这个定理可以把搜索区间无限缩 小，从而求到极小点．以下介绍的几种一维搜索方法都是利用 这个定理通过不断地缩短搜索区间的长度，来求得一维最优化 问题的近似最优解．
§4.2 对分法
一、对分法基本原理 求解一维最优化问题min ϕ (t ) 一般可先确定它的 一个有限搜索区间 [a, b] ，把问题化为求解问 min 题 a≤t ≤b ϕ (t ) ，然后通过不断缩短区间的长度，最 后求得最优解． 设 ϕ：R1 → R1 在已获得的搜索区间 [a, b] 内具有连 ϕ 续的一阶导数．因为 (t )在 [a, b]上可微，故ϕ (t ) 在 [a, b]上连续，由此知ϕ (t )在[a, b]上有最小值．
二、加步探索法
下面，介绍一个确定问题(4.3)的搜索区间的简单方 法．这个方法的思想是：先选定一个初始点 t0 ∈ [0, + ∞) (或 t0 ∈ [0, tmax ])和初始步长 h > 0 ．然后，沿着 0 轴的正方向探索前进一个步长，得到新点 t 0 + h0．若目 标函数在新点处的值是下降了，即 ϕ (t 0 + h0 ) < ϕ (t 0 ) ， 则下一步就从新点 t 0 + h0出发加大步长，再向前探 者．若目标函数在新点自制 值上升，即 ϕ (t 0 + h0 ) > ϕ (t 0 ) ， 则下一步仍以 t 0 为出发点以原步长开始向 t 轴的负方 向同样探索．当达到目标函数上升的点时，就停止探 索，这时便得到问题（4.3）的一个搜索区间．这种以 加大步长进行探索来寻找探索区间的方法叫做加步探 索法．
图4.5
二、对分法迭代步骤 ϕ 已知ϕ (t ) ， ′(t )表达式，终止限 ε ． (1) 确定初始搜索区间[a, b]，要求 ． ϕ '(a) < 0，ϕ '(b) > 0 1 (2) 计算 [a, b] 的中点 c = (a + b) ． 2 <0 (3) 若 ϕ ′(c) ，则 a = c ，转(4)； 若ϕ ′(c) = 0 ，则 t * = c，转(5)；若 ϕ ′(c) > 0，则 b = c ，转(4)． 1 * = (a + b) ，转(5)；否则 (4) 若 | a − b |< ε ，则 t 2 转(2)． (5) 打印 t * ，停机． 对分法的计算流程如图4.6所示．
t*= c t*=(a+b) /2 输出t* 结束
图4.6
b=c Y N
§4.3 Newton
一、Newton切线法基本原理 切线法基本原理 设 ϕ : R 1 → R1在已获得的搜索区间 [a, b] 内具有连 续二阶导数，求 min ϕ (t ) ． a ≤ t ≤b 因为ϕ (t ) 在 [a, b] 上可微，故 ϕ (t ) 在 [a, b] 上有最 小值，令 ϕ ′(t ) = 0 ． 下面不妨设在区间 [a, b] 中经过 k 次迭代已求得方 程ϕ ′(t ) = 0 的一个近似根 t k ．过(t k , ϕ ′(t k )) 作曲线 的切线 y = ϕ ′(t ) ,其方程是 y − ϕ ′(t k ) = ϕ ′′(t k )(t − t k ) （4.4）