众所周转,单纯形法是求解线性规划问题最常用、最有效的算法之一,一些做优化的软件比如lingo都有对应很成熟的实现库,该方法的提出是由Spendley、Hext和Himswor等人在1962年提出的,它虽然是一个代数计算过程,但是本质还是基于几何原理,且它不需要计算目标函数的梯度,也就避免了一系列的求导操作,也是优化领域较为奠基的方法之一。
通过几何思想构建单纯形,找到每次迭代中的最小值顶点,通过比如反射、延伸等操作构建新的单纯形尽可能挖掘出更多的点看是否比当前最小值点小进行迭代,直到算法收敛
凸集
当初始单纯形构造好后,核心思想其实就是不断改变这个单纯形使其能够朝向函数极小点收敛,所以需要不断地迭代,在迭代过程中都需要根据单纯形的每个点计算目标函数值,因为约定求得是最小值问题,所以此时目标函数值大的点将被另外的目标函数更小的点代替,且在迭代过程中是不断找到比当前最小值点目标函数更小的点,如果不满足条件则继续迭代,直到收敛到极小点
过程最全包含反射、延伸、外收缩、内收缩、压缩过程
引入压缩因子
,根据公式
,产生除最大值以外的各维度的n个新值,即单纯形中其他各点与最大值的距离减半,由此产生新的点,构建新的单纯形
以上通过各种操作不断更新单纯形进行迭代,之所以每次迭代时将最小值排除就是想着在剩下的顶点中看是否能找到新的比当前最小值更小的顶点,如果找到(找的核心方法是反射,其他方法是对它的一些逻辑的处理,之所以和重心值反射是希望可以跳出局部极值,且机会均等)的话那之间的最小值就没有讨论意义故需排除,最终单纯形不断向极小值收敛,每次在反射时迭代都会判断是否达到了先验知识已知的最小值或者迭代次数上限从而决定是否继续用反射值代替最小值进行迭代