黄金分割法也称为0.618 法, 其基本思想是通过试探点函数值得比较,是包含极小点的搜索区间不断缩小. 该方法仅需要计算函数值, 适用范围广, 使用方便. 下面我们来推导0.618 法的计算公式.
设
其中. 根据单峰函数的性质, 可能会出现如下两种情形之一:
（1） 若；
（2） 若；
我们要求两个试探点满足下述两个条件:
（1）
（2）区间长度的缩短率相同, 即
从而可得
步0 确定初始搜索区间
function [s,phis,i,G,E]=huanjfg(phi,a,b,delta,epsilon)
%功能: 0.618法精确线搜索
%输入: phi是目标函数, a, b 是搜索区间的两个端点
% epsilon delta分别是自变量和函数值的容许误差
%输出: s, phis分别是近似极小点和极小值, G是nx4矩阵,
% 其第i行分别是a,p,q,b的第i次迭代值[ak,pk,qk,bk],
% E=[ds,dphi], 分别是s和phis的误差限.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 步0 确定初始搜索区间$[a_0,b_0]$和容许误差$0leq epsilon leq1$.
% 令$t=frac{sqrt(5)-1}{2}$计算初始试探点$$p_0=a_0+(1-t)(b_0-a_0), q_0=a_0+t(b_0-a_0)$$
% 及相应的函数值$phi(p_0),phi(q_0)$。令$i=0$
% 步1 若$phi(p_i)leqphi(q_i)$，转步骤2；否则，转步骤3
% 步2 计算左试探点. 若$left | q_i-a_i
ight |leq epsilon$，停算，输出$p_i$；否则，令
% $$a_{i+1}=a_i, b_{i+1}=q_i, phi(q_{i+1})=phi(p_i),\
% q_{i+1}=p_i, p_{i+1}=a_{i+1}+(1-t)(b_{i+1}-a_{i+1}).$$
% 计算$phi(p_{i+1}), i=i+1,$转步骤1
% 步3 计算右试探点.若$left | b_i-p_i
ight |leq epsilon$，停算，输出$q_i$；否则，令
% $$a_{i+1}=p_i, b_{i+1}=b_i, phi(p_{i+1})=phi(q_i),\
% p_{i+1}=q_i, q_{i+1}=a_{i+1}+t(b_{i+1}-a_{i+1}).$$
% 计算$phi(q_{i+1}), i=i+1,$转步骤1
t=(sqrt(5)-1)/2;
p=a+(1-t)*(b-a);q=a+t*(b-a);
phip=feval(phi,p);phiq=feval(phi,q);
i=0;
G(i+1,:)=[a p q b];
while(1)
%step 1
if phip<=phiq
%step 2
if (abs(b-a)>epsilon)||(abs(phib-phia)>delta)
% a=a;
b=q;phib=phiq;
phiq=phip;
q=p;
p=a+(1-t)*(b-a);
phip=feval(phi,p);
else
break;
end
else
%step 3
if (abs(b-a)>epsilon)||(abs(phib-phia)>delta)
a=p;phia=phip;
% b=b;
phip=phiq;
p=q;
q=a+t*(b-a);
phiq=feval(phi,q);
else
break;
end
end
i=i+1;
G(i+1,:)=[a p q b];
end
if phip<=phiq
s=p;
phis=phip;
else
s=q;
phis=phiq;
end
% E=[ds,dphi]
ds=abs(b-a);dphi=abs(phib-phia);
E=[ds,dphi];>> phi=@(x)((x-1)^2);
>> [a,b,k]=bfm(phi,0,0.1)
a =
0.3
b =
1.5
k =
3
>> delta=0.001;epsilon=0.001;
>> [s,phis,i,G,E]=huanjfg(phi,a,b,delta,epsilon);
>> [s,phis,i]
ans =
0.999974521703027 6.49143616637166e-10 15
取函数为0.001，
大概迭代16次可得极小点