您的位置: 首页  >  IT文章  >  精确线搜索——抛物线法

精确线搜索——抛物线法

分类: IT文章 • 2022-05-05 17:11:20

1

抛物线法

抛物线法也叫二次插值法，二次插值法的基本思想是: 在搜索区间中不断地使用二次多项式去近似目标函数, 并逐步用插值多项式的极小点去逼近线搜索问题

的极小点. 下面我们详细介绍这一方法.
设已知三点


处的函数值

上述条件保证了函数

令

这里

又

故 的全局极小点.
注意到 并重复上述计算过程, 求出新的$overline{s} 和新的overline{h}. 重复这一迭代过程, 直到得到所需的精度为止. 值得说明的是, 这一算法中目标函数的一阶导数用来隐式地确定二次插值多项式的极小点, 而算法的程序实现中并不需要使用导数值.

算法3（抛物线法）

步骤0，由进退法确定三点


设定容许误差，转步骤1.

MATLAB实现

function [s,phis,i,E,S]=paowxf(phi,a,b,delta,epsilon)
%功能: 精确线搜索之抛物线法
%输入: phi 是目标函数, a和b是搜索区间的端点
%         delta,epsilon是容许误差
%输出: i是迭代次数
%       s是近似极小点, phis是对应的近似极小值;
%          E=[ds,dphi], 分别是s和phis的误差限分别是s, phis的误差界;  
%           S是迭代向量

s0=a;s2=b;
h=(s2-s0)/2;s1=s0+h;
phi0=feval(phi,s0);phi1=feval(phi,s1);phi2=feval(phi,s2);bars=s0;
i=0;
while(1)
    i=i+1;
    S(i,:)=[s0,s1,s2,bars];
    %step1
    if (abs(s2-s0)>=epsilon) || ((phi2-phi0)>=delta)
        %step2
%         h=(s2-s0)/2;s1=s0+h;
%         phi0=feval(phi,s0);phi1=feval(phi,s1);phi2=feval(phi,s2);
        barh=h*(4*phi1-3*phi0-phi2)/(2*phi1-phi0-phi2)/2;
        bars=s0+barh;
        barphi=feval(phi,bars);
        if phi1<=barphi
            %step4
            if s1<bars
                s2=bars;
                phi2=barphi;
                h=barh-h;
                s0=s1-h;
                phi0=feval(phi,s0);

            else
                s0=bars;
                phi0=barphi;
                h=h-barh;
                s2=s1+h;
                phi2=feval(phi,s2);

            end
        else
            %step3
            if s1>bars
                if h>2*barh
                    s1=bars;h=barh;s2=s1+h;
                    phi1=barphi;phi2=feval(phi,s2);
                else
                    s1=bars;h=h-barh;s2=s1;s0=s1-h;
                    phi1=barphi;phi2=phi1;phi0=feval(phi,s0);
                end

            else
                if 2*barh<3*h
                    s0=s1;h=barh-h;s1=bars;s2=s1+h;
                    phi0=phi1;phi1=barphi;phi2=feval(phi,s2);
                else
                    s1=bars;h=2*h-barh;s0=s1-h;
                    phi1=barphi;phi0=feval(phi,s0);
                end
            end
        end
    else
        break;
    end
end

s=s1;
phis=feval(phi,s1);
ds=abs(s-s0);
dphi=abs(phi1-phi0);
E=[ds dphi];

MATLA实验结果

>> phi = @(x)3*x^2-2*tan(x);
>> delta=1e-5;epsilon=1e-4;
>> a=0;b=1;
>> [s,phis,i,E,S]=paowxf(phi,a,b,delta,epsilon);
>> [s,phis,i,E]
ans =
  Columns 1 through 3
         0.389493192257377        -0.365810354364081                         8
  Columns 4 through 5
      1.78999870481533e-10      1.11022302462516e-16

程序对于函数，进过8次迭代便可得到较高精度解。

  1. ↩

相关推荐