Downhill simplex 方法又稱為Nelder-Mead算法迹蛤、Amoeba方法民珍，由Spendley、Hext和Himsworth于1962年提出盗飒；Nelder和Mead 1965年進(jìn)行了改進(jìn)嚷量。該方法是一種不使用導(dǎo)數(shù)求解無約束極小化問題的直接搜索方法。針對的問題是：
是
上的連續(xù)函數(shù)逆趣。
算法思想是集合迭代式的搜索蝶溶，即從集合每一個集合都是一個單純形，每次迭代使得單純形的頂點(diǎn)目標(biāo)函數(shù)值下降宣渗。什么是Simplex單純形呢抖所？舉個例子，在一維中痕囱，一個線段就是一個單純形田轧，在二維中，一個三角形為一個單純形鞍恢，三維中一個四面體為一個單純形.......
具體定義為：
設(shè)傻粘，如果
線性無關(guān)，則
的凸組合稱為由
構(gòu)成的單純形帮掉，記
,即
稱為
單純形
的頂點(diǎn)弦悉。
Downhill Simplex幾個關(guān)鍵的定義：
可稱為劣點(diǎn)。
形心點(diǎn)：
反射點(diǎn)：,
一般取1蟆炊；
Downhill Simplex一般規(guī)則為：
如果稽莉，說明反射點(diǎn)比最小頂點(diǎn)還要小，這種情況涩搓，需要對單純形進(jìn)行延伸：
延伸點(diǎn):
污秆，
一般取2后室；若
，則用
代替
構(gòu)建新的單純形混狠，否則用
代替
（這里其實很很好理解疾层，延伸點(diǎn)比反射點(diǎn)有更大的步長将饺，如果比原來的單純形的最小值還要小，將劣點(diǎn)替換點(diǎn)痛黎，如果延伸點(diǎn)沒有比原單純形的最小值小予弧，那用反射點(diǎn)替換劣點(diǎn)，確保替換后的單純形湖饱，替換后的點(diǎn)最幸锤颉）。
如果井厌，說明反射點(diǎn)比最小頂點(diǎn)要大蚓庭，這種情況，需要對單純形進(jìn)行收縮仅仆。收縮有分為兩種情況:
- 如果對于任意頂點(diǎn)器赞，不包含劣點(diǎn)都小于或等于
且
，則令收縮點(diǎn)：
,
墓拜；若
港柜，則用
代替
(這種情況下咳榜，相當(dāng)于反射點(diǎn)和劣點(diǎn)之間有一個谷夏醉，且極小值偏向反射點(diǎn)這邊。)
2 . 如果
涌韩，則收縮點(diǎn)定義為：
,
(這種情況下释树，依然是反射點(diǎn)和劣點(diǎn)之間有一個谷，且極小值偏向劣點(diǎn)這邊)
規(guī)則都這里擎淤，還有一種情況奢啥，就是上述的兩種情況的收縮點(diǎn)大于等于劣點(diǎn)情況：
當(dāng)收縮點(diǎn)大于等于劣點(diǎn)時，則需要對單純形進(jìn)行壓縮嘴拢，向
點(diǎn)進(jìn)行棱長減半桩盲，即
.
（這種情況下，收縮點(diǎn)的函數(shù)值大于等于劣點(diǎn)的函數(shù)值席吴，說明極小值在單純形的內(nèi)部的可能性更高赌结，將原單純形向最小頂點(diǎn)進(jìn)行壓縮捞蛋，構(gòu)造新的單純形）
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構(gòu)建初始單純形
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'); %將頂點(diǎn)按照函數(shù)值進(jìn)行排序，劣點(diǎn)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 計算劣點(diǎn)和形心點(diǎn)
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 計算反射點(diǎn)
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 方法就像變形蟲在一個山谷里面柬姚，為了達(dá)到谷底拟杉，變形蟲通過幾個頂點(diǎn)的試探，不斷的改變自己的形狀量承，或伸縮搬设，或收縮。所以這種方法又叫Amoeba方法撕捍。其收斂速度較慢拿穴，但對于目標(biāo)函數(shù)的要求并不苛刻，在不確定具體表達(dá)式的情況下可以采用此方法忧风。
模式搜索
直接方法默色，最后再簡單介紹一種簡單的搜索方法，叫模式搜索狮腿。模式搜索和 powell 方法非常相似,也稱作步長加速法,hooke-jeeves 法,比 powell 方法更早提出(1961 年),其是對坐標(biāo)輪換法的改進(jìn)腿宰。基本思想是從初始基點(diǎn)開始,交替實施兩 種搜索:軸向搜索和模式搜索蚤霞。軸向搜索依次沿 個坐標(biāo)軸的方向進(jìn)行,用來確定新的基點(diǎn) 和有利于函數(shù)值下降的方向酗失。模式搜索則沿著相鄰兩個基點(diǎn)的連線方向進(jìn)行,試圖使函數(shù)值 下降更快。收斂速度是線性的,原始的一維搜索采用的是后退法,也可以采用其他一維搜索 方法來加速迭代昧绣。
