如果要求经过一系列探索点搜索之后,使最后的探索点和最优解之间的距离不超 过精度δ>0,这就要求最后区间的长度不超过δ,即 据此,我们应按照预先给定的精度δ,确定使(4)成立的最小整数n作为搜索次数, 直到进行到第n个探索点时停止 用上述不断缩短函数∫(1)的单峰区间[a,b]的办法,来求得问题(2)的近似解, 是 Kiefer(1953年)堤提出的,叫做 Fibonacci法,具体步骤如下: 1°选取初始数据,确定单峰区间[ao,b。],给出搜索精度δ>0,由(4)确定搜 索次数n 2°k=1,a=a0,b=b,计算最初两个搜索点,按(3)计算1和12。 3° while k<n-1 f1=∫(1),f2=f(t2) f1<f2 a=l2;l2=l1;l1=a+ F(-1-k)b-a) F(n-k) else b=1;1=12l2=b+ FO F(n-k) d k=k+1 4°当进行至k=n-1时, 这就无法借比较函数值∫(1)和∫(12)的大小确定最终区间,为此,取 t1=a+(~+E)(b-a) 其中E为任意小的数。在1和L2这两点中,以函数值较小者为近似极小点,相应的函数 值为近似极小值。并得最终区间[a,1]或[2,b 由上述分析可知,斐波那契法使用对称搜索的方法,逐步缩短所考察的区间,它能 以尽量少的函数求值次数,达到预定的某一缩短率 例3试用斐波那契法求函数f(1)=12-1+2的近似极小点,要求缩短后的区间 不大于区间[-1,3]的0.08倍。 程序留作习题 2.120.618法 若@>0,满足比例关系
-37- 如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超 过精度δ > 0 ，这就要求最后区间的长度不超过δ ，即 ≤ δ − Fn b a （4） 据此，我们应按照预先给定的精度δ ，确定使（4）成立的最小整数n 作为搜索次数， 直到进行到第n 个探索点时停止。 用上述不断缩短函数 f (t) 的单峰区间[a,b] 的办法，来求得问题（2）的近似解， 是 Kiefer(1953 年)提出的，叫做 Finbonacci 法，具体步骤如下： o 1 选取初始数据，确定单峰区间[ , ] a0 b0 ，给出搜索精度δ > 0 ，由（4）确定搜 索次数n 。 o 2 0 0 k = 1,a = a ,b = b ，计算最初两个搜索点，按（3）计算 1 t 和 2t 。 o 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 o 4 当进行至k = n −1时， ( ) 2 1 t1 = t2 = a + b 这就无法借比较函数值 ( )1 f t 和 ( ) 2 f t 的大小确定最终区间，为此，取 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = + + − = + )( ) 2 1 ( ( ) 2 1 1 2 t a b a t a b ε 其中ε 为任意小的数。在 1 t 和 2t 这两点中，以函数值较小者为近似极小点，相应的函数 值为近似极小值。并得最终区间[ , ]1 a t 或[ , ] 2t b 。 由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能 以尽量少的函数求值次数，达到预定的某一缩短率。 例 3 试用斐波那契法求函数 ( ) 2 2 f t = t − t + 的近似极小点，要求缩短后的区间 不大于区间[−1,3]的 0.08 倍。 程序留作习题。 2.1.2 0.618 法 若ω > 0 ，满足比例关系
称之为黄金分割数,其值为0=206180339887…。 黄金分割数O和 Fibonacci分数之间有着重要的关系 0=lm 现用不变的区间缩短率0618,代替斐波那契法每次不同的缩短率,就得到了黄金 分割法(0618法)。这个方法可以看成是斐波那契法的近似,实现起来比较容易,效果 也相当好,因而易于为人们所接受 用0618法求解,从第2个探索点开始每增加一个探索点作一轮迭代以后,原单 峰区间要缩短0.618倍。计算n个探索点的函数值可以把原区间[ao,b]连续缩短n-1 次,因为每次的缩短率均为,故最后的区间长度为 b-a0) 这就是说,当已知缩短的相对精度为δ时,可用下式计算探索点个数n: n-<δ 当然,也可以不预先计算探索点的数目n,而在计算过程中逐次加以判断,看是否已满 足了提出的精度要求。 0.618法是一种等速对称进行试探的方法,每次的探索点均取在区间长度的0618 倍和0382倍处。 22二次插值法 对极小化问题(2),当f()在[a,b上连续时,可以考虑用多项式插值来进行一 维搜索。它的基本思想是:在搜索区间中,不断用低次(通常不超过三次)多项式来近 似目标函数,并逐步用插值多项式的极小点来逼近(2)的最优解 23无约束极值问题的解法 无约束极值问题可表述为 minf(x),x∈E" 求解问题(5)的迭代法大体上分为两点:一是用到函数的一阶导数或二阶导数 称为解析法。另一是仅用到函数值,称为直接法。 2.31解析法 梯度法(最速下降法) 对基本迭代格式 TRp (6) 我们总是考虑从点x出发沿哪一个方向p,使目标函数∫下降得最快。微积分的知识 告诉我们,点x的负梯度方向 p=-Vf(x"), 是从点x出发使∫下降最快的方向。为此,称负梯度方向-Vf(x2)为∫在点x处的 最速下降方向。 38-
-38- ω ω −ω = 1 1 称之为黄金分割数，其值为 0.6180339887L 2 5 1 = − ω = 。 黄金分割数ω 和 Fibonacci 分数之间有着重要的关系 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),每一轮从点x4出发沿最速下降方向-Vf(x)作一维搜索 来建立求解无约束极值问题的方法,称之为最速下降法 这个方法的特点是,每轮的搜索方向都是目标函数在当前点下降最快的方向。同 时,用V(x2)=0或Nf(x)≤E作为停止条件。其具体步骤如下 1°选取初始数据。选取初始点x°,给定终止误差,令k:=0 2求梯度向量。计算v(x),若|/(x2)≤,停止选代,输出x否则, 进行3°。 3°构造负梯度方向。取 p=-Vf(x) 4°进行一维搜索。求l,使得 f(x+trp)=minf(x+tp") 例4用最速下降法求解无约束非线性规划问题 min f(x)=xi+25x2 其中x=(x1,x2),要求选取初始点x=(2,2)。 解(i)Vf(x)=(2x1,50x2) 编写M文件 deaf. m,定义函数∫(x)及其梯度列向量如下 function [f, df]=deaf(x)i f=x(1)^2+25+x(2)^2 df=[2+x(1 50*x(2) (i)编写主程序文件 zulu.m如下 lc x=[2;2]; [fo,g]=deaf(x)i while norm(g)>0.000001 p=-g/norm(g)i t=l 0; f=deaf (x+t*p)i while f>fo t=t/ f=deaf (x+t*p)i for g]=deaf(x) 23.12 Newton法 考虑目标函数∫在点x处的二次逼近式 f(x)=o(x)=f(x)+Vf(x)(x-x)+o(x-x)Vf(x)x-x) 假定Hess阵
-39- 按基本迭代格式（6），每一轮从点 k x 出发沿最速下降方向 ( ) k − ∇f x 作一维搜索， 来建立求解无约束极值问题的方法，称之为最速下降法。 这个方法的特点是，每轮的搜索方向都是目标函数在当前点下降最快的方向。同 时，用∇ ( ) = 0 k f x 或 ∇ ( ) ≤ ε k f x 作为停止条件。其具体步骤如下： 1°选取初始数据。选取初始点 0 x ，给定终止误差，令k := 0 。 2°求梯度向量。计算 ( ) k ∇f x ， 若 ∇ ( ) ≤ ε k f x ，停止迭代，输出 k x 。否则， 进行 3°。 3° 构造负梯度方向。取 ( ) k k p = −∇f x . 4° 进行一维搜索。求 kt ，使得 ( ) min ( ) 0 k k t k k k f x + t p = f x + tp ≥ 令 , : 1, 1 = + = + + x x t p k k k k k k 转 2°。 例 4 用最速下降法求解无约束非线性规划问题 2 2 2 min f (x) = x1 + 25x 其中 T x (x , x ) = 1 2 ，要求选取初始点 T x (2,2) 0 = 。 解 （i） T f (x) (2x ,50x ) ∇ = 1 2 编写 M 文件 detaf.m，定义函数 f (x) 及其梯度列向量如下 function [f,df]=detaf(x); f=x(1)^2+25*x(2)^2; df=[2*x(1) 50*x(2)]; （ii）编写主程序文件zuisu.m如下： clc x=[2;2]; [f0,g]=detaf(x); while norm(g)>0.000001 p=-g/norm(g); t=1.0;f=detaf(x+t*p); while f>f0 t=t/2; f=detaf(x+t*p); end x=x+t*p; [f0,g]=detaf(x); end x,f0 2.3.1.2 Newton 法 考虑目标函数 f 在点 k x 处的二次逼近式 ( ) ( )( ) 2 1 ( ) ( ) ( ) ( ) ( ) k k T k k T 2 k k f x ≈ Q x = f x + ∇f x x − x + x − x ∇ f x x − x 假定 Hesse 阵