线性规划 §2无约束问题 2.1一维搜索方法 当用迭代法求函数的极小点时,常常用到一维搜索,即沿某一已知方向求目标函数 的极小点。一维搜索的方法很多,常用的有:(1)试探法(“成功一失败”,斐波那契法 0618法等);(2)插值法(抛物线插值法,三次插值法等);(3)微积分中的求根法(切 线法,二分法等)。 考虑一维极小化问题 min f(o) (2) ast≤b 若∫()是[an,b]区间上的下单峰函数,我们介绍通过不断地缩短[a,b]的长度,来 搜索得(2)的近似最优解的两个方法 为了缩短区间[a,b],逐步搜索得(2)的最优解r的近似值,我们可以采用以下 途径:在[a,b]中任取两个关于[a,b]是对称的点1和l2(不妨设l2<l1,并把它们叫 做搜索点),计算∫(1)和∫(l2)并比较它们的大小。对于单峰函数,若f(2)<f(1), 则必有r∈[a,l],因而[a,1]是缩短了的单峰区间;若f(t1)<f(l2),则有 t∈[l2,b,故[t2,b是缩短了的单峰区间;若∫(t2)=f(1),则[a,41]和[t2,b都是 缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较,总可以获得缩短了的单 峰区间。对于新的单峰区间重复上述做法,显然又可获得更短的单峰区间。如此进行, 在单峰区间缩短到充分小时,我们可以取最后的搜索点作为(2)最优解的近似值 应该按照怎样的规则来选取探索点,使给定的单峰区间的长度能尽快地缩短? 2.1.1 Fibonacci法 如用F表示计算n个函数值能缩短为单位长区间的最大原区间长度,可推出F满 足关系 Fo=F Fn=Fn-2+F1,n=2,3 数列{F}称为 Fibonacci数列,F称为第n个 Fibonacci数,相邻两个 Fibonacci数之 比n称为 Fibonacci分数 F 当用斐波那契法以n个探索点来缩短某一区间时,区间长度的第一次缩短率为 其后各次分别为 F 由此,若t1和t2(12<1)是单峰区间[a,b] 中第1个和第2个探索点的话,那么应有比例关系 F 从而 t1=a+2(b-a),l2=a+-n2(b-a) (3) 它们关于[a,b]确是对称的点 -36-36- 线性规划。 §2 无约束问题 2.1 一维搜索方法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数 的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法， 0.618 法等）；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切 线法，二分法等）。 考虑一维极小化问题 min f (t) a≤t≤b （2） 若 f (t) 是[a,b] 区间上的下单峰函数，我们介绍通过不断地缩短[a,b] 的长度，来 搜索得（2）的近似最优解的两个方法。 为了缩短区间[a,b] ，逐步搜索得（2）的最优解 * t 的近似值，我们可以采用以下 途径：在[a,b] 中任取两个关于[a,b] 是对称的点 1 t 和 2t （不妨设 2 1 t < t ，并把它们叫 做搜索点），计算 ( )1 f t 和 ( ) 2 f t 并比较它们的大小。对于单峰函数，若 ( ) ( ) 2 1 f t < f t ， 则必有 [ , ]1 * t ∈ a t ，因而 [ , ]1 a t 是缩短了的单峰区间；若 ( ) ( ) 1 2 f t < f t ，则有 [ , ] 2 * t ∈ t b ，故[ , ] 2t b 是缩短了的单峰区间；若 ( ) ( ) 2 1 f t = f t ，则[ , ]1 a t 和[ , ] 2t b 都是 缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单 峰区间。对于新的单峰区间重复上述做法，显然又可获得更短的单峰区间。如此进行， 在单峰区间缩短到充分小时，我们可以取最后的搜索点作为（2）最优解的近似值。 应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快地缩短？ 2.1.1 Fibonacci 法 如用 Fn 表示计算n 个函数值能缩短为单位长区间的最大原区间长度，可推出 Fn 满 足关系 F0 = F1 = 1 , 2,3, , Fn = Fn−2 + Fn−1 n = L 数列{ } Fn 称为 Fibonacci 数列， Fn 称为第n 个 Fibonacci 数，相邻两个 Fibonacci 数之 比 n n F F −1 称为 Fibonacci 分数。 当用斐波那契法以 n 个探索点来缩短某一区间时，区间长度的第一次缩短率为 n n F F −1 ，其后各次分别为 2 1 2 3 1 2 , , , F F F F F F n n n n L − − − − 。由此，若 1 t 和 ( ) 2 2 1 t t < t 是单峰区间[a,b] 中第 1 个和第 2 个探索点的话，那么应有比例关系 n n F F b a t1 a −1 = − − ， n n F F b a t2 a −2 = − − 从而 ( ) 1 1 b a F F t a n n = + − − ， ( ) 2 2 b a F F t a n n = + − − （3） 它们关于[a,b] 确是对称的点