Nelder-Mead 演算法

03-18

閱讀原文

預備知識　Matlab

　　 Nelder-Mead 演算法是一種求多元函數局部最小值的演算法，其優點是不需要函數可導並能較快收斂到局部最小值． Matlab 自帶的 fminsearch 函數就是使用該演算法．對 N 元函數 f $f(mathbf x)$ （這裡把函數自變數用 N 維矢量來表示），該演算法需要提供函數自變數空間中的一個初始點， $mathbf x_1$ ，演算法從該點出發尋找局部最小值．以下講解具體演算法．

　　我們先根據初始點另外生成另外 N 個初始點 $mathbf x_2dots mathbf x_{N+1}$ ，使 $mathbf x_{1+i}$ 在第的第 i 個分量比 $mathbf x_1$ 的大 5%，其他分量保持相同．如果 $mathbf x_1$ 的第 i 個分量為零，那麼 $mathbf x_{1+i}$ 的第 i 個分量設為 0.00025．得到 N+1 個初始點後，開始按照以下步驟進行循環，直到滿足特定的精度條件時退出循環．

先給這些點按照 $f(mathbf x_i)$ 從小到大的順序重新排序並重命名，使 i 越大 $f(mathbf x_i)$ 越大．
計算前 N 個點的平均位置為 $mathbf m = frac 1N sum_{i=1}^N mathbf x_i$ 　　(1)
計算 $mathbf x_{N+1}$ 關於點 $mathbf m$ 的反射點為 $mathbf r = 2mathbf m - mathbf x_{N+1}$ 　　(2)
如果 $f(mathbf x_1) leqslant f(mathbf r) < f(mathbf x_N)$ ，令 $mathbf x_{N+1} = mathbf r$ ，並進入下一個循環．
如果 $f(mathbf r) < f(mathbf x_1)$ ，計算拓展點為 $mathbf s = mathbf m + 2(mathbf m - mathbf x_{N+1})$ 　(3) 如果 $f(mathbf s) < f(mathbf r)$ ，令 $mathbf x_{N+1} = mathbf s$ 並進入下一個循環，否則令 $mathbf x_{N+1} = mathbf r$ ．並進入下一循環．
如果 $f(mathbf x_N) leqslant f(mathbf r) < f(mathbf x_{N+1})$ ，令 $mathbf c_1 = mathbf m + (mathbf r - mathbf m)/2$ 　(4) 如果 $f(mathbf c_1) < f(mathbf r)$ ，令 $mathbf x_{N+1} = mathbf c_1$ 並進入下一循環，否則執行最後一步．

（剩下部分見頂部的「閱讀原文」）