Downhill simplex 方法又称为Nelder-Mead算法、Amoeba方法，由Spendley、Hext和Himsworth于1962年提出；Nelder和Mead 1965年进行了改进。该方法是一种不使用导数求解无约束极小化问题的直接搜索方法。针对的问题是：
$\min_{x\in R^n}f(x)$

$f(x)$ 是 $R^n$ 上的连续函数。

算法思想是集合迭代式的搜索，即从集合 $S_0\rightarrow S_1\rightarrow S_2,...,S_k\rightarrow,...$ 每一个集合都是一个单纯形，每次迭代使得单纯形的顶点目标函数值下降。什么是Simplex单纯形呢？举个例子，在一维中，一个线段就是一个单纯形，在二维中，一个三角形为一个单纯形，三维中一个四面体为一个单纯形.......

图1 单纯形示意图

具体定义为：
设 $V^0,V^1,...,V^n\in R^n$ ，如果 $V_j-V_0(j=1,2,3,..,n)$ 线性无关，则 $V^0,V^1,...,V^n$ 的凸组合称为由 $V^0,V^1,...,V^n$ 构成的单纯形，记 $S=\{V^0,V^1,...,V^n\}$ ,即 $S=\{V^0,V^1,...,V^n\}=\{x|\sum_{j=0}^na_jV^j,\sum_{j=0}^na_j=1,a_j>0\}$ 称为 $V^0,V^1,...,V^n$ 单纯形 $S$ 的顶点。

Downhill Simplex几个关键的定义：
$f(V^h)=max(f(V^0),f(V^1),..,f(V^n))$
$f(V^l)=min(f(V^0),f(V^1),..,f(V^n))$
$V^h$ 可称为劣点。

形心点： $\bar{V}=\frac{1}{n}\sum_{i\neq h}V^i$
反射点： $V^r=\bar{V}+\alpha(\bar{V}-V^h)$ , $\alpha$ 一般取1；

Downhill Simplex一般规则为：
如果 $f(V^r)<f(V^l)$ ，说明反射点比最小顶点还要小，这种情况，需要对单纯形进行延伸：

延伸点: $V^e=\bar{V}+\beta(V^r-\bar{V})$ ， $\beta$ 一般取2；若 $f(V^e)<f(V^l)$ ，则用 $V^e$ 代替 $V^h$ 构建新的单纯形，否则用 $V^r$ 代替 $V^h$ 构建新的单纯形。

（这里其实很很好理解，延伸点比反射点有更大的步长，如果比原来的单纯形的最小值还要小，将劣点替换点，如果延伸点没有比原单纯形的最小值小，那用反射点替换劣点，确保替换后的单纯形，替换后的点最小）。

如果 $f(V^r)\geq f(V^l)$ ，说明反射点比最小顶点要大，这种情况，需要对单纯形进行收缩。收缩有分为两种情况:

如果对于任意顶点，不包含劣点都小于或等于 $f(V^r)$ 且 $f(V^r)\leq f(V^h)$ ，则令收缩点： $V^c=\bar V+\gamma(V^r-\bar V)$ , $\gamma = 0.5$ ；若 $f(V^c)<f(V^h)$ ，则用 $V^c$ 代替 $V^h$ 构建新的单纯形；

(这种情况下，相当于反射点和劣点之间有一个谷，且极小值偏向反射点这边。)

2 . 如果 $f(V^r)>f(V^h)$ ，则收缩点定义为： $V^c=\bar V+\gamma(V^h-\bar V)$ , $\gamma = 0.5$ ，若 $f(V^c)<f(V^h)$ ，则用 $V^c$ 代替 $V^h$ 构建新的单纯形；

(这种情况下，依然是反射点和劣点之间有一个谷，且极小值偏向劣点这边)

规则都这里，还有一种情况，就是上述的两种情况的收缩点大于等于劣点情况：

当收缩点大于等于劣点时，则需要对单纯形进行压缩，向 $V^l$ 点进行棱长减半，即 $V^i=\frac{V^i+V^l}{2}(i=0,1,2,...,n)$ .

（这种情况下，收缩点的函数值大于等于劣点的函数值，说明极小值在单纯形的内部的可能性更高，将原单纯形向最小顶点进行压缩，构造新的单纯形）

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 年),其是对坐标轮换法的改进。基本思想是从初始基点开始,交替实施两种搜索:轴向搜索和模式搜索。轴向搜索依次沿 $n$ 个坐标轴的方向进行,用来确定新的基点和有利于函数值下降的方向。模式搜索则沿着相邻两个基点的连线方向进行,试图使函数值下降更快。收敛速度是线性的,原始的一维搜索采用的是后退法,也可以采用其他一维搜索方法来加速迭代。

图2 模式搜索示意图

无约束优化方法-直接方法（Downhill Simplex）

无约束优化方法-直接方法（Downhill Simplex）

模式搜索

推荐阅读更多精彩内容