无约束优化之单纯形法（Nelder

单纯形法只需要计算目标函数值，是无需要一维搜索，也无需进行求导的一种直接法。其优点计算比较简单，几何概念清晰，适用于目标函数求导比较困难或不知道目标函数的具体表达式而仅知道其具体计算方法的情况。

一、基本思想 所谓n维欧氏空间中的单纯形，是指在n维空间中由n+1个顶点构成的简单图形或多面体。例如，在二维平面中的单纯形应具有三个顶点，即三角形。在三维空间中的单纯形应具有四个顶点，即四面体。当各顶点之间的距离相等时，这种几何图形就称为正规单纯形。 单纯形法的基本思想是：选n+1个顶点构成初始单纯形，计算并比较各顶点目标函数值的大小，确定它们当中函数值大的顶点及函数值的下降方向，再设法找到一个函数值较小的新点替换函数值最大的顶点，从而构成新的单纯形。随着这种取代过程不断进行，新的单纯形想着极小值点收缩逼近，从而求得极小值点。 迭代过程的主要步骤：反射、延伸、压缩。

二、单纯形法的方法原理 现在以二维问题为例说明单纯形方法的原理。 （1）构造初始单纯形

如图，设二维目标函数 f ( x ) = f ( x 1 , x 2 ) f(x)=f(x_1,x_2) f(x)=f(x1​,x2​)，在二维平面上选三个线性无关的顶点 x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​构成初始单纯形。计算这三个顶点处的目标函数值 f ( x 1 ) , f ( x 2 ) , f ( x 3 ) f(x_1),f(x_2),f(x_3) f(x1​),f(x2​),f(x3​)并比较其大小。若 f ( x 1 ) > f ( x 2 ) > f ( x 3 ) f(x_1)>f(x_2)>f(x_3) f(x1​)>f(x2​)>f(x3​)，把目标函数值最小的点 x 3 x_3 x3​成为最好点，用 x L x_L xL​表示；把目标函数值最大的点 x 1 x_1 x1​成为最坏点，用 x H x_H xH​表示；把目标函数值次大的点 x 2 x_2 x2​称为次坏点，用 x G x_G xG​表示。求除 x H x_H xH​以外的所有顶点的集合形心 x C x_C xC​

（2）反射 一般来说，目标函数值下降方向在最坏点 x H x_H xH​关于形心 x C x_C xC​的对称位置的方向可能性最大。故首先求反射点，以探测目标函数值的变化趋向。 求 x L , x G x_L,x_G xL​,xG​的中心点 x C x_C xC​，在 x H x_H xH​与 x C x_C xC​延长线取一点 x R x_R xR​，使 x R = x C + α ( x C − x H ) x_R=x_C+\alpha(x_C-x_H) xR​=xC​+α(xC​−xH​) 点 x R x_R xR​称为最坏点 x H x_H xH​关于形心 x C x_C xC​的反射点； α \alpha α称为反射系数，一般取 α = 1 \alpha=1 α=1，故上式变为 x R = 2 x C − x H x_R = 2x_C-x_H xR​=2xC​−xH​ 计算函数值 f ( x R ) f(x_R) f(xR​)，若 f ( x R ) < f ( x L ) f(x_R)xR​,xG​,xL​}. 若 f ( x H ) > f ( x R ) > f ( x G ) f(x_H)>f(x_R)>f(x_G) f(xH​)>f(xR​)>f(xG​)，说明反射点 x R x_R xR​比次坏点还差，表明反射点取得太远，应沿点 x R x_R xR​向点 x C x_C xC​方向压缩。

（4）压缩 压缩点 x S x_S xS​，其表达式为 x S = x C + β ( x R − x C ) x_S=x_C+\beta(x_R-x_C) xS​=xC​+β(xR​−xC​) 式中 β \beta β为压缩系数，通常取 β = 0.5 \beta=0.5 β=0.5或0.25~0.75. 若 f ( x S ) < f ( x H ) f(x_S)xS′​,xG​,xL​};否则： 当 x H x C x_Hx_C xH​xC​连线上所有点的函数值 f ( x ) f(x) f(x)都大于 f ( x H ) f(x_H) f(xH​)时，说明沿反射方向探索失败，此时应将单纯形想最好点 x L x_L xL​收缩。即以 x L x_L xL​为基点，将单纯形边长减半，得到新的单纯形，其新的顶点表达式为 x G ′ = x L + 0.5 ( x G − x L ) x H ′ = x L + 0.5 ( x H − x L ) \begin{aligned} x_{G^{'}} &=x_L+0.5(x_G-x_L) \\ x_{H^{'}} &=x_L+0.5(x_H-x_L) \end{aligned} xG′​xH′​​=xL​+0.5(xG​−xL​)=xL​+0.5(xH​−xL​)​

三、单纯形法的计算步骤 单纯形法算法步骤：

步1 构造初始单纯形：设目标函数 f ( x ) f(x) f(x)为n维函数，取n+1个顶点 x 1 , x 2 , ⋯   , x n + 1 x_1,x_2,\cdots,x_{n+1} x1​,x2​,⋯,xn+1​，要保证 x j − x i , ( j = 2 , 3 , ⋯   , n + 1 ) x_j-x_i,(j=2,3,\cdots,n+1) xj​−xi​,(j=2,3,⋯,n+1)为n个向量线性无关，否则将导致搜索过程在一个较低维的空间内进行，可能漏掉真正的极小值点。具体方法是：选取初始顶点 x 1 ( 0 ) x_1^{(0)} x1(0)​，从 x 1 ( 0 ) x_1^{(0)} x1(0)​出发沿各坐标轴方向以步长h找其余n个顶点 x j ( 0 ) = x 1 ( 0 ) + h e i , e i = [ 0 , ⋯   , 0 , 1 , 0 , ⋯   , 0 ] T , ( j = i + 1 , , i = 1 , 2 , ⋯   , n ) x_j^{(0)}=x_1^{(0)}+he_i,e_i=[0,\cdots,0,1,0,\cdots,0]^T, (j=i+1,,i=1,2,\cdots,n) xj(0)​=x1(0)​+hei​,ei​=[0,⋯,0,1,0,⋯,0]T,(j=i+1,,i=1,2,⋯,n) 式中，h为步长，一般取 h = 0.5   15 h=0.5~15 h=0.5 15，初始取 h = 1.6   1.7 h=1.6~1.7 h=1.6 1.7； 步2 计算各顶点的目标函数值，按大小排队，找出函数最大的最坏点 x H ( k ) x_H^{(k)} xH(k)​，函数值第二大的次坏点 x G ( k ) x_G^{(k)} xG(k)​，函数值最小的最好点 x L ( k ) x_L^{(k)} xL(k)​，k为迭代的轮数； 步3 求反射点 x n + 3 ( k ) x_{n+3}^{(k)} xn+3(k)​，求除最坏点 x L ( k ) x_L^{(k)} xL(k)​外其余各点几何图形的形心 x n + 2 ( k ) x_{n+2}^{(k)} xn+2(k)​. 形心点： x n + 2 ( k ) = 1 n ( ∑ j = 1 n + 1 x j ( k ) − x H ( k ) ) x_{n+2}^{(k)}=\frac{1}{n}(\sum_{j=1}^{n+1}x_j^{(k)}-x_H^{(k)}) xn+2(k)​=n1​(∑j=1n+1​xj(k)​−xH(k)​) 反射点： x n + 3 ( k ) = 2 x n + 2 ( k ) − x H ( k ) x_{n+3}^{(k)}=2x_{n+2}^{(k)}-x_H^{(k)} xn+3(k)​=2xn+2(k)​−xH(k)​ 步4 延伸（扩张）：若 f ( x n + 3 ( k ) ) < f ( x L ( k ) ) f(x_{n+3}^{(k)})