如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超 过精度6>0，这就要求最后区间的长度不超过6，即 b-as8 (4) F 用上述不缩短函数f()的单蜂区间[a,b]的办法，来求得问题(2)的近似解， 是Kiefer1(953年)提出的，叫做Finbonacei法，具体步骤如下 1°选取初始数据，确定单峰区间[a,b,],给出搜索精度6>0，由(4)确定搜 索次数n。 2°k=l,a=ao,b=b,计算最初两个搜索点，按(3)计算4和52 3°while k<n-1 万=f4),52=f) if< a=4;4=14=a+Fn-1-b-a） F(n-k) else 6==5:5=b+Fn-1- F(n-k)(a-b) kl end 4°当进行至k=n-1时， 4=4=(a+b) 这就无法借比较函数值∫（化，）和∫化，)的大小确定最终区间，为此，取 5=a+b) =a+(+Xb-a) 其中6为任意小的数。在（和1，这两点中，以函数值较小者为近似极小点，相应的函数 值为近似极小值。并得最终区间[a,4]或[，b]· 由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能 以尽量少的函数求值次数，达到预定的某一缩短率。 例3试用斐波那契法求函数f()=子-1+2的近似极小点，要求缩短后的区间 不大于区间[-1,3引的0.08倍。 程序留伦习题 2.120.618法 若0>0，满足比例关系 -37
-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_1-0 1 将之为黄金分做。其查为0-5-0613039g87。 黄金分割数o和Fibonacei分数之间有着重要的关系 o-lim. 用06品于为人门所接深专点开检每一个探索点作一轮法代以后店 也相当好，因 蜂区间要缩短0.618倍。计算n个探索点的函数值可 以把原区间[a,】连续缩短n-】 次，因为每次的缩短率均为，故最后的区间长度为 (-a)"- 这就是说，当已知缩短的相对精度为6时，可用下式计算探索点个数： ≤ò 当然，也可以不预先计算探索点的数目n,而在计算过程中逐次加以判断，看是否已满 足了提出的精府求 0.618法是一种等速对称进行试探的方法，每次的探索点均取在区间长度的0.618 倍和0.382倍处。 一小次辅当了0在a上连线时，可以老忠用多顶式插值来进行 过三次)多项式来近 2.3无约束极值问题的解法 无约束极值问题可表述为 min f(x).xE() 求解问题(5)的迭代法大体上分为两点： 一是用到函数的一阶导数或二阶导数， 称为解析法。另一是仅用到函数值，称为直接法 31解折法 23.11梯度法（最速下降法） 对基本迭代格式 x=x+lp (6 我们总是考虑从点x出发沿哪一个方向p*,使目标函数∫下降得最快。微积分的知识 告诉我们，点的负梯度方向 p=-f(x*), 是从点x出发使∫下降最快的方向。为此，称负梯度方向-Vf(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)，每一轮从点x出发沿最速下降方向-f(x)作一维搜案， 来建立求解无约束极值问愿的方法，称之为最速下降法 这个方法的特点是，每轮的搜索方向都是目标函数在当前点下降最快的方向。同 时，用f(x)=0或f(x)≤ε作为停止条件。其具体步骤如下： 1°选取初始数据。选取初始点x”,给定终止误差，令k=0。 ”求梯度向量。计算f(x),若f(x*)川≤6，停止迭代，输出x。否则， 进行3 构造负梯度方向。取 p*=-vf(x) 4°进行一维搜索。求14，使得 f(x+hp)=minf(x+) 令x川=x+1D,k=k+1,转2°. 例4用最速下降法求解无约束非线性规划问题 min f(x)=x+25x 其中x=(x1,x2)了，要求选取初始点x°=(2,2)7。 解(i)Vfx)=(2x1,50x2)/ 编写M文件detaf.m,定义函数f(x)及其梯度列向量如下 *x(1 while f>f0 =detaf(x+t*p); x=p [f0,g]-detaf(x) x, 2.3.1,2 Newton法 考虑目标函数∫在点x处的二次逼近式 f(x)=Q(x)=f(x)+Vf(x)(x-x*)+(x-x)vf(x')(x-x) 假定Hesse阵
-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 阵