直到进行到第n个探索点时停止。 用上述不断缩短函数f(1)的单峰区间[a,b]的办法,来求得问题(2)的近似解, 是 Kiefer((1953年)提出的,叫做 Fibonacci法,具体步骤如下 选取初始数据,确定单峰区间[ao3b],给出搜索精度δ>0,由(4)确定搜 索次数n 2°k=1,a=ao,b=b,计算最初两个搜索点,按(3)计算和t2 3° while k<n-1 f1=∫(t1),f2=f(t2) if fi<fr F(n-l-k a=l2;l2=l1,1=a+ F(n-k) b=1;1=12;2=b+F(n-1-k) F(n-k k=k+1 4°当进行至k=n-1时 h1=l2=(a+b 这就无法借比较函数值f(t1)和f(t2)的大小确定最终区间,为此,取 (a+b) l1=a+(+E)(b-a) 其中E为任意小的数。在1和12这两点中,以函数值较小者为近似极小点,相应的函数 值为近似极小值。并得最终区间[a,41]或[2b] 由上述分析可知,斐波那契法使用对称搜索的方法,逐步缩短所考察的区间,它能 以尽量少的函数求值次数,达到预定的某一缩短率。 例3试用斐波那契法求函数f()=t2-t+2的近似极小点,要求缩短后的区间 不大于区间[-1,3]的008倍 程序留作习题。 2.1.20.618法 若O>0,满足比例关系 称之为黄金分割数,其值为o=√5-1 0.6180339887 黄金分割数O和 Fibonacci分数之间有着重要的关系,它们是
-24- 直到进行到第 n 个探索点时停止。 用上述不断缩短函数 f (t) 的单峰区间 [a,b] 的办法，来求得问题（2）的近似解， 是 Kiefer(1953 年)提出的，叫做 Finbonacci 法，具体步骤如下： 1° 选取初始数据，确定单峰区间 [ , ] a0 b0 ，给出搜索精度 0 ，由（4）确定搜 索次数 n。 2° 0 0 k =1,a = a ,b = b ，计算最初两个搜索点，按（3）计算 1 t 和 2 t 。 3°while k n −1 ( ), ( ) 1 1 2 2 f = f t f = f t if 1 2 f f ( ) ( ) ( 1 ) ; ; 2 2 1 1 b a F n k F n k a t t t t a − − − − = = = + else ( ) ( ) ( 1 ) ; ; 1 1 2 2 a b F n k F n k b t t t t b − − − − = = = + end k = k +1 end 4° 当进行至 k = n −1 时， ( ) 2 1 t 1 = t 2 = a + b 这就无法借比较函数值 ( ) 1 f t 和 ( ) 2 f t 的大小确定最终区间，为此，取 = + + − = + )( ) 2 1 ( ( ) 2 1 1 2 t a b a t a b 其中 为任意小的数。在 1 t 和 2 t 这两点中，以函数值较小者为近似极小点，相应的函数 值为近似极小值。并得最终区间 [ , ] 1 a t 或 [ , ] t 2 b 。 由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能 以尽量少的函数求值次数，达到预定的某一缩短率。 例 3 试用斐波那契法求函数 ( ) 2 2 f t = t −t + 的近似极小点，要求缩短后的区间 不大于区间 [−1,3] 的 0.08 倍。 程序留作习题。 2.1.2 0.618 法 若 0 ，满足比例关系 − = 1 1 称之为黄金分割数，其值为 0.6180339887 2 5 1 = − = 。 黄金分割数 和 Fibonacci 分数之间有着重要的关系，它们是
F 2n<0< n为偶数 FO、、F n为奇数。 2°c=lim 现用不变的区间缩短率0.618,代替斐波那契法每次不同的缩短率,就得到了黄金 分割法(0.618法)。这个方法可以看成是斐波那契法的近似,实现起来比较容易,效果 也相当好,因而易于为人们所接受。 用0618法求解,从第2个探索点开始每增加一个探索点作一轮迭代以后,原单 峰区间要缩短0618倍。计算n个探索点的函数值可以把原区间[a,b]连续缩短n-1 次,因为每次的缩短率均为,故最后的区间长度为 b-a0) 这就是说,当已知缩短的相对精度为δ时,可用下式计算探索点个数n <6 当然,也可以不预先计算探索点的数目n,而在计算过程中逐次加以判断,看是否已满 足了提出的精度要求 0.618法是一种等速对称进行试探的方法,每次的探索点均取在区间长度的0.618 倍和0.382倍处 22二次插值法 对极小化问题(2),当∫()在[a,b]上连续时,可以考虑用多项式插值来进行一 维搜索。它的基本思想是:在搜索区间中,不断用低次(通常不超过三次)多项式来近 似目标函数,并逐步用插值多项式的极小点来逼近(2)的最优解。 23无约束极值问题的解法 无约束极值问题可表述为 mnf(x),x∈E(n (5) 求解问题(5)的迭代法大体上分为两种:一是用到函数的一阶导数或二阶导数, 称为解析法。另一是仅用到函数值,称为直接法。 2.3.1解析法 2.3.1.1梯度法(最速下降法) 对基本迭代格式 x +t,p 我们总是考虑从点x出发沿哪一个方向p,使目标函数∫下降得最快。微积分的知识 告诉我们,点x的负梯度方向 P 是从点x出发使∫下降最快的方向。为此,称负梯度方向-V(x2)为∫在点x处的 最速下降方向。 按基本迭代格式(6),每一轮从点x*出发沿最速下降方向-Vf(x)作一维搜索 来建立求解无约束极值问题的方法,称之为最速下降法
-25- 1° 1 1 − − n n n n F F F F ，n 为偶数， 1 1 − − n n n n F F F F ，n 为奇数。 2° n n n F F 1 lim − → = 。 现用不变的区间缩短率 0.618，代替斐波那契法每次不同的缩短率，就得到了黄金 分割法（0.618 法）。这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果 也相当好，因而易于为人们所接受。 用 0.618 法求解，从第 2 个探索点开始每增加一个探索点作一轮迭代以后，原单 峰区间要缩短 0.618 倍。计算 n 个探索点的函数值可以把原区间 [ , ] a0 b0 连续缩短 n −1 次，因为每次的缩短率均为 ，故最后的区间长度为 1 0 0 ( ) − − n b a 这就是说，当已知缩短的相对精度为 时，可用下式计算探索点个数 n ： n−1 当然，也可以不预先计算探索点的数目 n ，而在计算过程中逐次加以判断，看是否已满 足了提出的精度要求。 0.618 法是一种等速对称进行试探的方法，每次的探索点均取在区间长度的 0.618 倍和 0.382 倍处。 2.2 二次插值法 对极小化问题（2），当 f (t) 在 [a,b] 上连续时，可以考虑用多项式插值来进行一 维搜索。它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近 似目标函数，并逐步用插值多项式的极小点来逼近（2）的最优解。 2.3 无约束极值问题的解法 无约束极值问题可表述为 ( ) min ( ), n f x x E （5） 求解问题（5）的迭代法大体上分为两种：一是用到函数的一阶导数或二阶导数， 称为解析法。另一是仅用到函数值，称为直接法。 2.3.1 解析法 2.3.1.1 梯度法（最速下降法） 对基本迭代格式 k k k k x = x + t p +1 （6） 我们总是考虑从点 k x 出发沿哪一个方向 k p ，使目标函数 f 下降得最快。微积分的知识 告诉我们，点 k x 的负梯度方向 ( ) k k p = −f x ， 是从点 k x 出发使 f 下降最快的方向。为此，称负梯度方向 ( ) k −f x 为 f 在点 k x 处的 最速下降方向。 按基本迭代格式（6），每一轮从点 k x 出发沿最速下降方向 ( ) k −f x 作一维搜索， 来建立求解无约束极值问题的方法，称之为最速下降法