MATLAB多维极值之单纯形法

本文主要是介绍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代码

%% 单纯形
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;% 将单纯形按列存储
endn=1;
tol = 1 ;
while n < k && tol > eps%% 计算函数值for i = 1:Num_var_f+1F_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; %采用扩张前的点作为单纯形的新顶点endflag = 1; %反射成功标志位endif flag == 0  %说明没有反射成功if f_reflect < f_nextbad  %反射点<次差点X(:,F_index(end)) = X_reflect;%采用该反射点作为新的顶点else  % f_reflect >= f_nextbadif f_reflect < f_bad % 反射点要比最差点好一些X_reflect_shrink=Xc+beta*(X_reflect-Xc);% 收缩点f_reflect_shrink=double(subs(f,symvar(f),X_reflect_shrink'));elseX_reflect_shrink=Xc+beta*(X_bad-Xc);% 收缩点f_reflect_shrink=double(subs(f,symvar(f),X_reflect_shrink'));endif f_reflect_shrink < f_badX(:,F_index(end)) = X_reflect_shrink;else % 缩短边长X = X_best + 1/2 * (X-X_best);endendendn=n+1;
end
minx=X_best;
end

 

 

 

 

 

这篇关于MATLAB多维极值之单纯形法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---