进退法

进退法

1. 算法原理

进退法是用来确定搜索区间（包含极小值点的区间）的算法，其理论依据是：f(x)为单谷函数（只有一个极值点），且[a,b]为其极小值点的一个搜索区间，对于任意如果f?x1??f?x2?，则[a如果f?x1??f?x2?，x1,x2?[a,b]，,x]2为极小值的搜索区间，则[x1,b]为极小值的搜索区间。

因此，在给定初始点x0，及初始搜索步长h的情况下，首先以初始步长向前搜索一步，计算f?x0?h?。

（1） 如果f?x0??f?x0?h?

?待求，为确定x?，后退一步计算f(x0??h)，??,x0?h]，其中x则可知搜索区间为[x*为缩小系数，且0???1，直接找到合适的?*，使得f(x0??h)?f?x0?，从而确定搜索

区间[x0??*h,x0?h]。

（2） 如果f?x0??f?x0?h?

?待求，为确定x?，前进一步计算f(x0??h)，?为?]，其中x则可知搜索区间为[x0,x**放大系数，且??1，知道找到合适的?，使得f?x0?h??f(x0??h)，从而确定搜索

区间[x0,x0??*h]。

2. 算法步骤

用进退法求一维无约束问题minf(x),x?R的搜索区间（包含极小值点的区间）的基本算法步骤如下：

（1） 给定初始点x（2） 令x(4)(0)，初始步长h0，令h?h0，x(1)?x(0)，k?0；

?x(1)?h，置k?k?1；

(4)?fx(1)，则转步骤（4）（3） 若fx，否则转步骤（5）；

????（4） 令x(2)?x(1),x(1)?x(4)，f?x(2)??f?x(1)?，f?x(1)??f?x(4)?，令h?2h，

转步骤（2）；

（5） 若k?1，则转步骤（6）否则转步骤（7）；

(2)?fx(4)，转步骤（2）（6） 令h??h，x(2)?x(4)，fx；

????（7） 令x(3)?x(2),x(2)?x(1),x(1)?x(4)，停止计算，极小值点包含于区间

[x(1),x(3)]或[x(3),x(1)]

3. 算法的MATLAB实现

在MATLAB中编程实现的进退函数为：minJT

功能：用进退法求解一维函数的极值区间。 调用格式：[minx,maxx]?minJT(f,x0,h0,eps) 其中，f：目标函数； x0：初始点； h0：初始步长； eps：精度；

x：目标函数取包含极值的区间左端点； min maxx：目标函数取包含极值的区间又端点。

进退法的MATLAB程序代码如下： function [minx,maxx]=minJT(f,x0,h0,eps) %目标函数:f; %初始点:x0; %初始步长:h0; %精度: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

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;

例：

取初始点为

0，步长为

0.1，f(t)?(t2?1)2?(t?1)2?3?t4?t2?2t?5的极值区间。解：在MATLAB命令窗口中输入： syms t;

f=t^4-t^2-2*t+5;

[x1,x2]=minJT(f,0,0.1)

所得结果为： x1 =

0.3000 x2 =

1.5000

由上面的结果可知f(t)的极值点在区间[0.3,1.5]内。

用进退法求函数

进退法

%进退法，用于确定下单峰区间.根据最优化方法（天津大学出版社）20页算法1.4.3编写。 %v1.0 author: liuxi BIT

%[left right]为下单峰区间，y为函数，x为函数y的变量，x0为初始点（默认为0）,step（>0）为初始步长（默认为0.01）

function [left right] = jintuifa(y,x,x0,step)

if nargin==3%当只有三个参数时，默认设置步长为0.01 step=0.01; end if nargin==2

x0=0;%当只有两个参数时，默认设置初始点为0 step=0.01; end

f0=subs(y,{x},{x0});%step1 求f(x0) 将函数y中变量x替换为x0 x1=x0+step;%step2 f1=subs(y,{x},{x1}); if (f1<=f0)%step3 step4 step=2*step; x2=x1+step; f2=subs(y,{x},{x2}); while(f1>f2) x0=x1; x1=x2; f0=f1; f1=f2; step=2*step; x2=x1+step; f2=subs(y,{x},{x2}); end left=x0 right=x2 else%step5 step6 step=2*step; x2=x1-step; f2=subs(y,{x},{x2});

while(f0>f2) x1=x0; x0=x2; f1=f0; f0=f2; step=2*step; x2=x1-step; f2=subs(y,{x},{x2}); end

left=x2;right=x1; end

进退法

%进退法

function [a,b]=JTF(x0,h,d,dd,q) r0=0;

y0=ff(x0+r0.*dd,q); k=0; l=1; while (l) r1=r0+h;

y1=ff(x0+r1.*dd,q); if y1

if k==0; h=-h; r=r0; else l=0; break; end end k=k+1; end

a=min(r,r1); b=max(r,r1);

进退法

function [left right] = jintuifa(y,x,x0,h)

if nargin==3%μ±??óDèy??2?êyê±￡???è?éè??2?3¤?a0.01 step=0.01; end

if nargin==2

x0=0;%μ±??óDá???2?êyê±￡???è?éè??3?ê?μ??a0 h=0.01; end

f0=subs(y,{x},{x0});%step1 ?óf(x0) ??oˉêyy?D±?á?xì????ax0 x1=x0+h;%step2 f1=subs(y,{x},{x1}); if (f1<=f0)%step3 step4 h=2*h; x2=x1+h;

f2=subs(y,{x},{x2}); while(f1>f2) x0=x1; x1=x2; f0=f1; f1=f2; h=2*h; x2=x1+h;

f2=subs(y,{x},{x2}); end left=x0 right=x2 else%step5 step6 h=2*h; x2=x1-h;

f2=subs(y,{x},{x2}); while(f0>f2) x1=x0; x0=x2; f1=f0; f0=f2; h=2*h; x2=x1-h;

f2=subs(y,{x},{x2}); end

left=x2;right=x1; end

本文来源：https://www.bwwdw.com/article/2ayv.html