Downhill simplex 方法又称为Nelder-Mead算法、Amoeba方法，由Spendley、Hext和Himsworth于1962年提出；Nelder和Mead 1965年进行了改进。该方法是一种不使用导数求解无约束极小化问题的直接搜索方法。针对的问题是：
是
上的连续函数。
算法思想是集合迭代式的搜索，即从集合每一个集合都是一个单纯形，每次迭代使得单纯形的顶点目标函数值下降。什么是Simplex单纯形呢？举个例子，在一维中，一个线段就是一个单纯形，在二维中，一个三角形为一个单纯形，三维中一个四面体为一个单纯形.......
具体定义为：
设，如果
线性无关，则
的凸组合称为由
构成的单纯形，记
,即
称为
单纯形
的顶点。
Downhill Simplex几个关键的定义：
可称为劣点。
形心点：
反射点：,
一般取1；
Downhill Simplex一般规则为：
如果，说明反射点比最小顶点还要小，这种情况，需要对单纯形进行延伸：
延伸点:
，
一般取2；若
，则用
代替
构建新的单纯形，否则用
代替
（这里其实很很好理解，延伸点比反射点有更大的步长，如果比原来的单纯形的最小值还要小，将劣点替换点，如果延伸点没有比原单纯形的最小值小，那用反射点替换劣点，确保替换后的单纯形，替换后的点最小）。
如果，说明反射点比最小顶点要大，这种情况，需要对单纯形进行收缩。收缩有分为两种情况:
- 如果对于任意顶点，不包含劣点都小于或等于
且
，则令收缩点：
,
；若
，则用
代替
(这种情况下，相当于反射点和劣点之间有一个谷，且极小值偏向反射点这边。)
2 . 如果
，则收缩点定义为：
,
(这种情况下，依然是反射点和劣点之间有一个谷，且极小值偏向劣点这边)
规则都这里，还有一种情况，就是上述的两种情况的收缩点大于等于劣点情况：
当收缩点大于等于劣点时，则需要对单纯形进行压缩，向
点进行棱长减半，即
.
（这种情况下，收缩点的函数值大于等于劣点的函数值，说明极小值在单纯形的内部的可能性更高，将原单纯形向最小顶点进行压缩，构造新的单纯形）
function [x_min,f_min] = AmoebaMethod(func,x0,options)
if nargin<3
options.tol = 1e-12;
options.iterNum = 1000;
options.bracketMethod = '';
options.linearSrcMethod = '';
options.plot2.Flag = 0;
options.plot2.x = [];
options.plot2.y = [];
options.plot2.z = [];
end
tol = options.tol;
iterNum = options.iterNum;
plot2 = options.plot2;
if length(x0)~=2
plot2.Flag = 0;
end
x_min = x0;
f_min = func(x0);
%step1构建初始单纯形
n = length(x0);
E = eye(length(x0));
S = zeros(n,n+1);
f_S = zeros(1,n+1);
S(:,1) = x0;
f_S(1) = f_min;
sigma = 0.5;
afa = 1;
beta = 2;
gama = 0.5;
for i=1:1:n
S(:,i+1) = S(:,i)+sigma.*E(:,i);
f_S(i+1) = func(S(:,i+1));
end
[f_S,sIdx]=sort(f_S,'descend'); %将顶点按照函数值进行排序，劣点Vh放在最前面
S = S(:,sIdx);
if plot2.Flag == 1
figure,subplot(1,2,1),axis equal, hold on;
contourf(plot2.x,plot2.y,plot2.z,30,'linestyle','-')
colormap('jet');
plot([S(1,1),S(1,2),S(1,3),S(1,1)],[S(2,1),S(2,2),S(2,3),S(2,1)],'-o');
tempf =f_min;
end
while(iterNum)
Vh = S(:,1);f_Vh = f_S(1); %step2 计算劣点和形心点
Vl = S(:,end);f_Vl = f_S(end);
Vx = mean(S(:,2:end),2);
Vr = Vx+afa.*(Vx-Vh);f_Vr = func(Vr);%step 3 计算反射点
if f_Vr<f_Vl %step4 延伸步
Ve = Vx+beta.*(Vx-Vh);f_Ve = func(Ve);
if f_Ve<f_Vl
S(:,1) = [];S = [S,Ve];
f_S(1) = [];f_S = [f_S,f_Ve];
else
S(:,1) = [];S = [S,Vr];
f_S(1) = [];f_S = [f_S,f_Vr];
end
elseif f_Vr<f_S(2)%step5收缩步
idx=find(f_S<f_Vr);
f_S(1:idx(1)-2)=f_S(2:idx(1)-1);
S(:,1:idx(1)-2) = S(:,2:idx(1)-1);
f_S(idx(1)-1) = f_Vr;
S(:,idx(1)-1) = Vr;
elseif f_Vr<=f_Vh
Vc = Vx+gama.*(Vr-Vx);f_Vc = func(Vc);
if f_Vc<f_Vr %or f_Vh
idx=find(f_S<f_Vc);
if isempty(idx)
S(:,1) = [];S = [S,Vc];
f_S(1) = [];f_S = [f_S,f_Vc];
else
f_S(1:idx(1)-2)=f_S(2:idx(1)-1);
S(:,1:idx(1)-2) = S(:,2:idx(1)-1);
f_S(idx(1)-1) = f_Vc;
S(:,idx(1)-1) = Vc;
end
else
[S,f_S] = halfSimplex(S,func);
end
else
Vc = Vx+gama.*(Vh-Vx);f_Vc = func(Vc);
if f_Vc<f_Vh
idx=find(f_S<f_Vc);
if isempty(idx)
S(:,1) = [];S = [S,Vc];
f_S(1) = [];f_S = [f_S,f_Vc];
else
f_S(1:idx(1)-2)=f_S(2:idx(1)-1);
S(:,1:idx(1)-2) = S(:,2:idx(1)-1);
f_S(idx(1)-1) = f_Vc;
S(:,idx(1)-1) = Vc;
end
else
[S,f_S] = halfSimplex(S,func);
end
end
if plot2.Flag == 1
tempf = [tempf,f_S(end)];
subplot(1,2,1),plot([S(1,1),S(1,2),S(1,3),S(1,1)],[S(2,1),S(2,2),S(2,3),S(2,1)],'-o');
subplot(1,2,2),plot(tempf,'-b.','LineWidth',2); grid on;
axis([0,60,0,func(x0)]);
xlabel('Step');
ylabel('Objective Function Value');
pause();
end
if sqrt(sum((S(:,1)-S(:,end)).^2))<=tol
break;
end
iterNum = iterNum-1;
end
x_min = mean(S,2);
f_min = func(x_min);
end
function [S,f_S] = halfSimplex(S,func)
S(:,1:end-1) = (S(:,1:end-1)+S(end))./2;
f_S = zeros(1,size(S,2));
for i=1:1:size(S,2)
f_S(i) = func(S(:,i));
end
end
Downhill Simplex 方法就像变形虫在一个山谷里面，为了达到谷底，变形虫通过几个顶点的试探，不断的改变自己的形状，或伸缩，或收缩。所以这种方法又叫Amoeba方法。其收敛速度较慢，但对于目标函数的要求并不苛刻，在不确定具体表达式的情况下可以采用此方法。
模式搜索
直接方法，最后再简单介绍一种简单的搜索方法，叫模式搜索。模式搜索和 powell 方法非常相似,也称作步长加速法,hooke-jeeves 法,比 powell 方法更早提出(1961 年),其是对坐标轮换法的改进。基本思想是从初始基点开始,交替实施两 种搜索:轴向搜索和模式搜索。轴向搜索依次沿 个坐标轴的方向进行,用来确定新的基点 和有利于函数值下降的方向。模式搜索则沿着相邻两个基点的连线方向进行,试图使函数值 下降更快。收敛速度是线性的,原始的一维搜索采用的是后退法,也可以采用其他一维搜索 方法来加速迭代。
