MATLAB多维极值之单纯形法

一、算法原理

1、问题引入

在之前讲解过的多维极值的算法中(最速下降法、牛顿法、共轭梯度法、拟牛顿法等),我们都利用了目标函数的导数值,因为函数的导数值是函数性态的反应。但在实际的工程应用中,会出现目标函数复杂导致求导麻烦甚至无法求导的情况。

单纯形法就解决了该问题,可以在不求导的情况下,根据若干个点的函数值大小关系,判断目标函数的变化趋势,为寻找目标函数的极值方向提供依据,这样经过若干次迭代,找到极值点。

例如,在求一维极值时我们用过的黄金分割法,就是根据函数值的大小关系,不断缩小搜索区间,直至满足精度,退出循环。

在求解多维极值时,我们可以使用单纯形法。

2、原理

我们以求二元函数f(x,y)极小值为例,对于二元函数需要2+1个点的函数值,构造一个三角形。

构造初始单纯性(三角形)

首先选定初始点x0=(a,b),初始步长h0;

接着按照不同的坐标方向(x方向和y方向)和步长h0选取不同的两个点x1,x2,

x1=x0+e1*h0,x2=x0+e2*h0,式中e1,e2为步长。

以x0,x1,x2三点为顶点的三角形,即为函数f(x,y)的二维单纯形。

     判断顶点处函数值

判断f(x0),f(x1),f(x2)的大小关系,将最大点记为H点,最小点记为L点,剩下的次小点即为G点。

我们要求的时f(x,y)的极小值,显然函数值越大,该点离目标点越远,反之函数值越小离目标点越近。所以我们将H点称为最坏点,L点成为最好点,G成为次好或者次坏点。

     搜索方向的确定(反射)

显然,最坏点H的关于边GL的对称方向的点的函数值可能会有所改善,因此将该方向作为下一个搜索方向,这里将H点的对称点R作为下一个搜索点。

扩张和收缩

判断R点与H点的函数值大小,若R点的函数值<H点的函数值,说明该方向函数值有所下降,可以尝试让R点再走远一点(扩张)。
若R点的函数值>H点的函数值,说明走的太远了,让R点收缩。

最后可以将原来的H点舍弃,选择RGL作为新的单纯形,进行上述迭代。

缩小

如果若R点的函数值>H点的函数值,收缩也不能改变函数的变化趋势,也可以将原来的单纯性HGL缩小,取GL和HL的重点C、F将CFL作为新的单纯形,进行上述迭代。

《MATLAB多维极值之单纯形法》《MATLAB多维极值之单纯形法》

matlab代码

%% 单纯形
syms x1 x2 x3 x
f=x1.^2+x2.^2-x1*x2-10*x1-4*x2+60+(x3-2)^2;
X=DCX(f,[0 0 0],1.5,1.7,0.5,1e-10,100)

function minx=DCX(f,x0,h,gama,beta,eps,k)
% f  函数符号表达式
% x0 初始点
% h  初始单纯形构造因子
% gama 扩张因子
% beta 收缩因子
% eps
% k 

x0=x0';
X(:,1)=x0;%初始点x存储在顶点X的第一列
Num_var_f=length(symvar(f));%几维函数
%% 构造初始单纯形
for i = 1:Num_var_f %三维函数,需要四个顶点坐标
    x = zeros(Num_var_f,1);
    x(i) = x0(i) + h;
    X(:,i+1)=x;% 将单纯形按列存储
end

n=1;
tol = 1 ;
while n < k && tol > eps
    %% 计算函数值
    for i = 1:Num_var_f+1
        F_val(i)=double(subs(f,symvar(f),X(:,i)'));
    end
    [F_sort,F_index]=sort(F_val);%从小到大
    %最好点
    f_best=F_sort(1);
    X_best=X(:,F_index(1));
    %最差点
    f_bad=F_sort(end);
    X_bad=X(:,F_index(end));
    %次差点
    f_nextbad=F_sort(end-1);
    X_nextbad=X(:,F_index(end-1));
    % 计算形心
    tol=abs((f_bad-f_best)/f_best); 
    Xc=1/Num_var_f*sum(X(:,F_index(1:end-1)),2);
    
    %% 反射
    flag = 0;
    X_reflect=Xc+(Xc-X_bad);
    f_reflect=double(subs(f,symvar(f),X_reflect'));
    %比较反射之后 
    if f_best > f_reflect  % 反射点R<最好点,可以扩张
         X_reflect_expand=Xc+gama*(Xc-X_bad);%扩张
         f_reflect_expand=double(subs(f,symvar(f),X_reflect_expand'));
         if f_reflect_expand < f_reflect %扩张点继续缩小
             X(:,F_index(end)) = X_reflect_expand; %将其作为单纯性的新顶点
         else %否则
             X(:,F_index(end)) = X_reflect; %采用扩张前的点作为单纯形的新顶点
         end
         flag = 1; %反射成功标志位
    end
    if flag == 0  %说明没有反射成功
        if f_reflect < f_nextbad  %反射点<次差点
            X(:,F_index(end)) = X_reflect;%采用该反射点作为新的顶点
        else  % f_reflect >= f_nextbad
            if f_reflect < f_bad % 反射点要比最差点好一些
                X_reflect_shrink=Xc+beta*(X_reflect-Xc);% 收缩点
                f_reflect_shrink=double(subs(f,symvar(f),X_reflect_shrink'));
            else
                X_reflect_shrink=Xc+beta*(X_bad-Xc);% 收缩点
                f_reflect_shrink=double(subs(f,symvar(f),X_reflect_shrink'));
            end
            if f_reflect_shrink < f_bad
                X(:,F_index(end)) = X_reflect_shrink;
            else % 缩短边长
                X = X_best + 1/2 * (X-X_best);
            end
            
        end
    end
    n=n+1;
end
minx=X_best;
end

 

 

 

 

 

    原文作者:天涯铭
    原文地址: https://blog.csdn.net/STM89C56/article/details/105725205
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞