黄金分割法-进退法-原理及流程图.docx

1黄金分割法的优化问题
(1) 黄金分割法基本思路：
黄金分割法适用于［a, b］区间上的任何单股函数求极小值问题，对函 数除要求“单谷”外不做其他要求，甚至可以不连续。因此，这种方 法的适应面非常广。黄金分割法也是建立在区间消去法原理基础上的 试探方法，即在搜索区间［a, b］内适当插入两点al, a2，并计算其函 数值.al, a2将区间分成三段，应用函数的单谷性质，通过函数值大 小的比较,删去其中一段，是搜索区间得以缩小。然后再在保留下来 的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而 得到极小点的数值近似解。
(2) 黄金分割法的基本原理
一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向 求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分 割法(0.618法).该方法用不变的区间缩短率0.618代替斐波那契法 每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比 较容易，也易于人们所接受.
黄金分割法是用于一元函数f(x)在给定初始区间［a, b］内搜索 极小点a *的一种方法.它是优化计算中的经典算法，以算法简单、收 敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用 于一维区间上的凸函数⑹，即只在单峰区间内才能进行一维寻优，
其收敛效率较低.其基本原理是：依照“去劣存优”原则、对称原则、 以及等比收缩原则来逐步缩小搜索区间气具体步骤是：在区间［a,b］ 内取点:al ,a2 把［a,b］分为三段.如果 f(a1)〉f(a2),令 a=a1,a1=a2, a2二a+r 夫(b—a)；如果 f (a1)<f (a2)，令 b=a2,a2=a1,a1=b— r* (b—a)，如果I (b-a)/b I和I (y1-y2)/y2 |都大于收敛精度e 重新开始.因为［a, b］为单峰区间，这样每次可将搜索区间缩小0。 618倍或0.382倍，处理后的区间都将包含极小点的区间缩小，然后 在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区［a, b］逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的 近似最优解。黄金分割法原理如图1所示，
(3) 程序流程如下：
4实验所编程序框图

给定a=-3,b=5,收敛精度e =0.1

#define f(x) x 大 x+2 大 x double calc(double 大 a, double *b,double e,int *n)
( double xl, x2,s；
if(fabs (*b—*a)〈=e)
s=f((大 b+大 a)/2);
else
( x1=*b-0。618* (大b—大 a);
x2=*a+0.618* (*b-*a);
if (f (x1)>f(x2))
*a=x1;
else
大 b=x2;
大 n=*n+1；
s=calc (a,b, e, n)；
}
return s；
}
main()
( double s,a, b,e；
int n=0；
scanf("%lf %lf %lf",&a,&b,&e);
s=calc (&a, &b, e, &n);
printf("a=%lf,b=%lf, s=%lf, n=%d\n”，a,b, s,n);
}
5程序运行结果如下图：
2进退法
(1)算法原理
进退法是用来确定搜索区间(包含极小值点的区间)的算法，其理论依据是:为单谷函 数(只有一个极值点)，且为其极小值点的一个搜索区间，对于任意,如果，则为极小值的搜索 区间，如果，则为极小值的搜索区间.
因此，在给定初始点，及初始搜索步长的情况下，首先以初始步长向前搜索一步，计算.
(1) 如果
则可知搜索区间为，其中待求，为确定，后退一步计算，为缩小系数，且，直接找到合 适的，使得，从而确定搜索区间。
(2) 如果
则可知搜索区间为，其中待求，为确定,前进一步计算，为放大系数，且，知道找到合适的， 使得，从而确定搜索区间。
进退法求极值
基本思想：
对f (x)任选一个初始点xi及初始步长h(),通过比较这两点函数值的 大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高一低 一高〃形态。
算法原理
1。试探搜索：
选定初始点 n 松=xi+ ho,计算 yi = f (xi), y2=f(X2)
(a) 如yi>y2,转2向右前进；
(b) 如yi<y2,转3向左后退；
图8. 1
2。前进搜索
加大步长h = 2 h ,产生新点心=X2+ 2ho ；
(a)如y2〈方，则函数在［xi,X3］内必有极小点，令a= xi,b= X3搜索区间为［a, b］;
(b)如 y2>y3,
令 X1 =X2 , yi=y2;
X2二X3 , y2二y3 ；
h=2h
重新构造新点X3=X2+h,并比较y2、y3的大小，直到争〈"
图8. 2
3。后退搜索
令 h=—棚,令 x3=xi , y3=yi ； xi=x2, yi=y2； x2=x3 , y2=y3 ； h=2h;
产生新点X3=X2+ h ；
(a^ %〈y，则函数在［xi, X3^内必有极小点，令a= X3, b= xi,搜索区 间为［a, b］
(b)如 y2>y3,
令 xi=X2, yi=y2 ； X2=X3 , y2=y3 ； h=2h
重新构造新点X3=X2+h,并比较y2、y3的大小，直到y<y令a= xi, b二％, 搜索区间为［a,b］；
图8. 3
(2) 算法步骤
用进退法求一维无约束问题的搜索区间(包含极小值点的区间)的基本算法步骤如下:
(1) 给定初始点，初始步长，令,,；
(2) 令，置；
(3) 若，则转步骤(4),否则转步骤(5)；
(4) 令，，，令，转步骤(2)；
(5) 若，则转步骤(6)否则转步骤(7)；
(6) 令，，，转步骤⑵；
(7 )令，停止计算,极小值点包含于区间
(3) 算法的MATLAB实现
在MATLAB中编程实现的进退函数为：
功能:用进退法求解一维函数的极值区间。
调用格式：
其中，：目标函数；
:初始点；
：初始步长；
:精度；
：目标函数取包含极值的区间左端点；
：目标函数取包含极值的区间又端点.
进退法的MATLAB程序代码如下：
function ［minx,maxx］=minJT(f, x0,h0, eps)
%目标函数:f；
%初始点:x0；
%初始步长：h。；
%精度:eps；
%目标函数取包含极值的区间左端点:minx；
%目标函数取包含极值的区间又端点：maxx;
format long;
if nargin==3
eps=1.0e—6；
end
x1=x0;
k=0;
h=h0；
while 1
x4=x1+h; %试探步
k=k+1;
f4=subs (f, findsym(f),x4);
f1=subs (f, findsym (f), x1);
if f4〈fl
x2=x1;
x1=x4；
f2=f1 ；
f1=f4；
h=2大h；%加大步长
else
if k==1
h=—h;%反向搜索
x2=x4;
f2=f4;
else
x3=x2;
x2=x1；
x1=x4;
break；
end
end
end
minx=min(x1, x3);
maxx=x1+x3—minx;
format short;
流程图如下：