文档介绍：
改进求解凸二次规划中的 Lemke 算法
张璐
辽宁工程技术大学理学院，辽宁阜新（123000）
E-mail:******@
摘要：通过对经典的 Lemke 互补转轴算法求解凸二次规划问题的分析，找到了 Lemke
算法的局限性。本文在 Lemke 算法求解线性互补问题的基础上修正了经典的 Lemke 算
法的迭代过程，提出了一种改进的 Lemke 算法，通过算例证明了算法能有效克服解的
局限性，减少了凸二次规划问题的迭代过程，提高了算法的效率。
关键词：非线性规划；凸二次规划；线性互补问题；Lemke 算法

1．引言
二次规划问题是最简单而又最基本的非线性规划问题，其目标函数是二次函数，约束是
线性等式或不等式。对于二次规划问题，可行域是凸集，所以当目标函数是凸函数时，任何
K-T 点都是二次规划问题的极小点。研究二次规划问题的算法不仅仅是为了解决二次规划问
题本身，同时也是为了更好的求解其他非线性规划问题。因为大多数最优化方法是从二次函
数模型导出的，这种类型的方法在实际中常常是有效的，其主要是因为一般函数的极小点附
近常可用二次函数很好地进行近似。由于二次规划是特殊的非线性规划，因此求解非线性规
划问题的方法均可用于二次规划问题的求解。同时，由于二次规划本身的特殊性，对它的求
解可以采用一些更有效的方法[1]。因此，不论从数学角度还是应用角度来看，二次规划问题
的研究都具有重要意义。到目前为止，已经出现了很多求解二次规划问题的算法，并且现在
仍有很多学者在从事这方面的研究工作。所以，需要我们对现存的有效的求解二次规划问题
的算法进行改进，得到新的求解算法来克服某些算法的缺点，并且给出具体的实例显示该算
法的有效性。本文主要研究凸二次规划的求解算法，以及线性互补问题的性质等相关问题。
对 Lemke 算法进行进一步研究，对它可能出现退化的原因和迭代过程以及局限性进一步分
析。本文通过分析经典的 Lemke 互补转轴算法求解含有等式约束的凸二次规划问题可能出
现退化的原因，修正了 Lemke 算法的迭代步骤，提出了一种改进的 Lemke 算法。通过求解
具体实例，说明了改进算法求解凸二次规划问题的有效性[2]。
2．Lemke 算法介绍
Lemke 算法的基本思想
Lemke 算法的基本思想是，由一个准互补基本可行解出发，通过转轴方法（即主元消去）
[3]
求出一个新的准互补基本可行解