改进求解凸二次规划中的Lemke算法

《改进求解凸二次规划中的Lemke算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cn改进求解凸二次规划中的Lemke算法张璐辽宁工程技术大学理学院，辽宁阜新（123000）E-mail:zhanglu85517@sohu.com摘要：通过对经典的Lemke互补转轴算法求解凸二次规划问题的分析，找到了Lemke算法的局限性。本文在Lemke算法求解线性互补问题的基础上修正了经典的Lemke算法的迭代过程，提出了一种改进的Lemke算法，通过算例证明了算法能有效克服解的局限性，减少了凸二次规划问题的迭代过程，提高了算法的效率。关键词：非线性规划；凸二次规划；线性互补问题；Lemke算法1．引言二次规划问题是最简单而又最基本的非

2、线性规划问题，其目标函数是二次函数，约束是线性等式或不等式。对于二次规划问题，可行域是凸集，所以当目标函数是凸函数时，任何K-T点都是二次规划问题的极小点。研究二次规划问题的算法不仅仅是为了解决二次规划问题本身，同时也是为了更好的求解其他非线性规划问题。因为大多数最优化方法是从二次函数模型导出的，这种类型的方法在实际中常常是有效的，其主要是因为一般函数的极小点附近常可用二次函数很好地进行近似。由于二次规划是特殊的非线性规划，因此求解非线性规划问题的方法均可用于二次规划问题的求解。同时，由于二次规划本身的特殊性，对它的求[1]解可以采用一些更有效的方法。因此，不论从数学角度还是应用角度来

3、看，二次规划问题的研究都具有重要意义。到目前为止，已经出现了很多求解二次规划问题的算法，并且现在仍有很多学者在从事这方面的研究工作。所以，需要我们对现存的有效的求解二次规划问题的算法进行改进，得到新的求解算法来克服某些算法的缺点，并且给出具体的实例显示该算法的有效性。本文主要研究凸二次规划的求解算法，以及线性互补问题的性质等相关问题。对Lemke算法进行进一步研究，对它可能出现退化的原因和迭代过程以及局限性进一步分析。本文通过分析经典的Lemke互补转轴算法求解含有等式约束的凸二次规划问题可能出现退化的原因，修正了Lemke算法的迭代步骤，提出了一种改进的Lemke算法。通过求解[2]

4、具体实例，说明了改进算法求解凸二次规划问题的有效性。2．Lemke算法介绍2.1Lemke算法的基本思想Lemke算法的基本思想是，由一个准互补基本可行解出发，通过转轴方法（即主元消去）[3]求出一个新的准互补基本可行解。这个过程可以不断地迭代，力争使变量z称为非基变量，0或者得到一个判据，说明问题(3-3)和(3-4)可行域无界。转轴方法（主元消去）遵循以下规则：（1）保持可行性按照最小比值规则确定离基变量。（2）保持准互补性若w(或z)是离基变量，则z(或w)是进基变量。iiii2.2Lemke方法的计算步骤（1）若q≥0，则停止计算，(,)(,0)wz=q是互补基本可行解；否则，

5、用表格形式表示成方程组，设-1-http://www.paper.edu.cn−=qqmax{−=⋅⋅⋅+i1,,mn}ii取s行为主行，z对应的列为主列，进行主元消去，令yz=。0ss（2）设在现行表中变量y下面的列为d．若d≤0，则停止计算；否则，按最小比sss值规则确定指标r，使qq⎧⎪⎫⎪ii=min⎨

6、d>0⎬isddrs⎩⎭⎪is⎪如果r行的基变量是z，则转步骤（4）；否则，进行步骤（3）。0（3）设r行的基变量为w或z（对于某个ls≠），变量y进基，以r行为主行，y对llss应的列为主列，进行主元消去。如果离基变量是w，则令yz=；如果离基变量是z，则lsll令yw=。转

7、步骤（2）。sl（4）变量y进基，z离基。以r行为主行，y对应的列为主列，进行主元消去。得s0s[4]到互补基本可行解，停止计算。2.3Lemke互补转轴算法的局限性分析首先，这一算法满足于一个互补基本可行解。所以用它不可能求得线性互补问题的多个解。其次，这一算法的收敛条件很强，限制了它的使用范围。此算法的收敛定理：TTT(1)∀≥z0均有zMz≥0．而且zMz=0(z≥0)蕴涵()MMz+=0。(Missaidtobecopositive-plus)；(2)每一个准互补基本可行解(almostcomplementarybasicfeasiblesolution)均非退化。若式(2)与

8、(1)相容，则Lemke互补转轴算法终止于一个互补基本可行解；若不相容，则终止于射线，条件(1)很强，而且不易检查。但可以指出：若M的主对角线上出现负元素，[5,6,7]则条件(1)必不满足。3．改进算法研究3.1改进的Lemke算法的基本思想本文研究的改进算法主要是求解线性互补问题，虽然向量q都有负向量，然而不必引入人工向量z，可以通过一个简单公式算的一个互补基本可行解。0定理3.1设矩阵M的第k列无负元素，即M>0。若对应于q的负分量(q<