单纯形法和拟牛顿法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“牛顿法与拟牛顿法”。
拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。
拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton's Method)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
拟牛顿法的基本思想如下。首先构造目标函数在当前迭代$x_k$的二次模型：m_k(p)=f_k+g_k^T p+p^T B_k p/2，这里f_k=f(x_k)，g_k=▽f(x_k)，B_k是一个对称正定矩阵。于是我们取这个二次模型的最优解p_k=-B_k^{-1} g_k作为搜索方向，并且得到新的迭代点x_{k+1}=x_k+a_k p_k，其中我们要求步长a_k满足Wolfe条件。这样的迭代类似与牛顿法，区别就在于用近似的Hee矩阵B_k代替真实的Hee矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵B_k的更新。现在假设得到一个新的迭代x_{k+1}，并得到一个新的二次模型：m_{k+1}(p)=f_{k+1}+g_{k+1}^T p + p^T B_{k+1} p/2。我们尽可能地利用上一步的信息来选取B_{k+1}。具体地，我们要求g_{k+1}-g_k=a_k B_{k+1} p_k，从而得到B_{k+1}s_k=y_k，其中s_k=x_{k+1}-x_k，y_k=g_{k+1}-g_k。这个公式被称为割线方程。下面主要介绍这几种方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。
纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得
