欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最优化方法:四、一维搜索法

程序员文章站 2022-07-15 22:30:53
...

主要参考书目:

  • 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印)

迭代的基本公式是

Xk+1=Xk+tkPk;

当我们确定了搜索方向Pk,我们要做的就是确定一个步长tk,使得minf(Xk+tkPk),从而也就确定了Xk+1,记为Xk+1=ls(Xk,Pk)。寻找tk的过程即称是一维搜索。
对于一个确定的目标函数f(X),一维搜索等价于以下两式:
最优化方法:四、一维搜索法
可以证明,在Xk+1处满足f(Xk+1)TPk=0.如下图:
最优化方法:四、一维搜索法

1、一些概念

  • 搜索区间
    即是包含问题最优解的一个区间。
  • 单谷区间与单谷函数
    定义:
    最优化方法:四、一维搜索法
    有性质:
    最优化方法:四、一维搜索法
    根据此性质,我们可以将一个已知的单谷区间缩短为一个更小的单谷区间,从而无限接近于最优解。

2、进退法(加步搜索法)

该方法主要用于确定初始搜索区间。

  • 基本原理:
    最优化方法:四、一维搜索法
    我们即是要寻找如图c的情况。
  • 计算步骤
    最优化方法:四、一维搜索法
    该流程图中初始点赋的值为0,实际上可以是任意值。
  • matlab实现
function [a,b] = JinTui(f,xk0,d,th)
%进退法求搜索区间
%输入:
%       f:目标函数的句柄
%       xk0:初始值
%       d:搜索方向
%       th:初始步长
%输出:
%       [a b]得到的搜索区间
%——开始
t=th;
x1=xk0;y1=feval(f,x1);
x2=x1+t.*d;y2=feval(f,x2);
while y1==y2
    t=1.1*t;
    x2=x1+t.*d;
    y2=feval(f,x2);
end
if y2<y1
    t=2*t;
    x3=x2+t.*d;
    y3=feval(f,x3);
elseif y2>y1
    t=-t;
    %交换x1,x2
    x3=x1;y3=y1;
    x1=x2;y1=y2;
    x2=x3;y2=y3;
    x3=x2+t.*d;
    y3=feval(f,x3);
end
while 1
    while y2==y3
        t=1.1*t;
        x3=x2+t.*d;
        y3=feval(f,x3);
    end
    if y3>y2
        break;
    else
        x1=x2;y1=y2;
        x2=x3;y2=y3;
        t=2*t;
        x3=x2+t.*d;
        y3=feval(f,x3);
    end
end
a=min(x1,x3);
b=max(x1,x3);
end

2、对分法

  • 基本思路
    在一个单谷区间内,求函数f(x)的极小值即是求f(x)=0的点。此对分法即是求函数零点的对分法,不再赘述。
  • 特点
    此方法要求“单谷”,也要求原函数导数存在。

3、牛顿切线法

  • 基本思路
    与对分法类似,同样是把求函数f(x)的极小值转化为求f(x)=0的点。此时的牛顿切线法也就是求函数零点的牛顿切线法,亦不赘述。
  • 特点
    此方法同样要求“单谷”,也要求原函数二阶导数存在。
    该方法若使用恰当收敛很快,但同时也容易出现不能收敛的问题。

4、黄金分割法

  • 基本思路
    利用单谷区间的性质,缩短区间,t1,t2点选为区间的两个黄金分割点。
  • 特点
    只要求“单谷”。

5、抛物线插值法

  • 基本思路
    通过用抛物线拟合目标函数的方法求取近似极小值。
    不妨设单谷搜索区间为[t1,t2],再任取t0[t1,t2],根据此三点确定一个抛物线,求出其最小值点t,若精度不满足要求,再利用单谷区间的性质缩短区间进一步迭代。
  • 具体内容
    t=12(t02t22)f(t1)+(t22t12)f(t0)+(t12t02)f(t2)(t0t2)f(t1)+(t2t1)f(t0)+(t1t0)f(t2)

    流程如下:
    最优化方法:四、一维搜索法
相关标签: 一维搜索