《改进求解凸二次规划中的lemke算法》由会员分享，可在线阅读，更多相关《改进求解凸二次规划中的lemke算法（10页珍藏版）》请在金锄头文库上搜索。
1、 http:/ - 1 - 改进求解凸二次规划中的改进求解凸二次规划中的 Lemke 算法算法 张璐 辽宁工程技术大学理学院，辽宁阜新（123000） E-mail: 摘摘 要：要： 通过对经典的 Lemke 互补转轴算法求解凸二次规划问题的分析， 找到了 Lemke 算法的局限性。本文在 Lemke 算法求解线性互补问题的基础上修正了经典的 Lemke 算 法的迭代过程，提出了一种改进的 Lemke 算法，通过算例证明了算法能有效克服解的 局限性，减少了凸二次规划问题的迭代过程，提高了算法的效率。 关键词：关键词：非线性规划；凸二次规划；线性互补问题；Lemke 算法 1引言引言 二次规划问
2、题是最简单而又最基本的非线性规划问题， 其目标函数是二次函数， 约束是线性等式或不等式。对于二次规划问题，可行域是凸集，所以当目标函数是凸函数时，任何K-T 点都是二次规划问题的极小点。 研究二次规划问题的算法不仅仅是为了解决二次规划问题本身， 同时也是为了更好的求解其他非线性规划问题。 因为大多数最优化方法是从二次函数模型导出的， 这种类型的方法在实际中常常是有效的， 其主要是因为一般函数的极小点附近常可用二次函数很好地进行近似。 由于二次规划是特殊的非线性规划， 因此求解非线性规划问题的方法均可用于二次规划问题的求解。同时，由于二次规划本身的特殊性，对它的求解可以采用一些更有效的方法1。因
3、此，不论从数学角度还是应用角度来看，二次规划问题的研究都具有重要意义。到目前为止，已经出现了很多求解二次规划问题的算法，并且现在仍有很多学者在从事这方面的研究工作。 所以， 需要我们对现存的有效的求解二次规划问题的算法进行改进， 得到新的求解算法来克服某些算法的缺点， 并且给出具体的实例显示该算法的有效性。本文主要研究凸二次规划的求解算法，以及线性互补问题的性质等相关问题。对 Lemke 算法进行进一步研究，对它可能出现退化的原因和迭代过程以及局限性进一步分析。本文通过分析经典的 Lemke 互补转轴算法求解含有等式约束的凸二次规划问题可能出现退化的原因，修正了 Lemke 算法的迭代步骤，提
4、出了一种改进的 Lemke 算法。通过求解具体实例，说明了改进算法求解凸二次规划问题的有效性2。 2Lemke 算法介绍算法介绍 2.1 Lemke 算法的基本思想算法的基本思想 Lemke 算法的基本思想是， 由一个准互补基本可行解出发， 通过转轴方法 （即主元消去）求出一个新的准互补基本可行解3。 这个过程可以不断地迭代， 力争使变量0z称为非基变量，或者得到一个判据， 说明问题(3-3)和(3-4)可行域无界。 转轴方法 （主元消去） 遵循以下规则： （1）保持可行性 按照最小比值规则确定离基变量。 （2）保持准互补性 若iw(或iz)是离基变量，则iz(或iw)是进基变量。 2.2 L
5、emke 方法的计算步骤方法的计算步骤 （1）若0q ，则停止计算，( , )( ,0)w zq=是互补基本可行解；否则，用表格形式表示成方程组，设 http:/ - 2 - max1,iiqq imn=+ 取s行为主行，0z对应的列为主列，进行主元消去，令ssyz=。 （2）设在现行表中变量sy下面的列为sd若0sd ，则停止计算；否则，按最小比值规则确定指标r，使 min|0ii is rsisqqddd=如果r行的基变量是0z，则转步骤（4） ；否则，进行步骤（3） 。 （3）设r行的基变量为lw或lz（对于某个ls） ，变量sy进基，以r行为主行，sy对应的列为主列，进行主元消去。如果
6、离基变量是lw，则令slyz=；如果离基变量是lz，则令slyw=。转步骤（2） 。 （4）变量sy进基，0z离基。以r行为主行，sy对应的列为主列，进行主元消去。得到互补基本可行解，停止计算4。 2.3 Lemke 互补转轴算法的局限性分析互补转轴算法的局限性分析 首先， 这一算法满足于一个互补基本可行解。 所以用它不可能求得线性互补问题的多个解。 其次，这一算法的收敛条件很强，限制了它的使用范围。 此算法的收敛定理： (1) 0z 均有0Tz Mz 而且0(0)Tz Mzz=蕴涵()0TMMz+=。 (M is said to be copositive-plus)； (2) 每一个准互补
7、基本可行解(almost complementary basic feasible solution)均非退化。 若式(2)与(1)相容，则 Lemke 互补转轴算法终止于一个互补基本可行解；若不相容，则终止于射线，条件(1)很强，而且不易检查。但可以指出：若M的主对角线上出现负元素，则条件(1)必不满足5,6,7。 3改进算法研究改进算法研究 3.1 改进的改进的 Lemke 算法的基本思想算法的基本思想 本文研究的改进算法主要是求解线性互补问题，虽然向量q都有负向量，然而不必引入人工向量0z，可以通过一个简单公式算的一个互补基本可行解。 定理 3.1 设矩阵M的第k列无负元素，即0kM。若
8、对应于q的负分量(0iq，而且 max0ik i ikkkqqqmm，0iikkiwm zq=+，1, ,ip ik=。因而由(3-2)给出线性互补问题的一个互补基本可行解（非基变量均为零） 。 下面讨论离基变量的选取与进基变量的确定。 设初始解(0)(0)(0)(0)(0) 11(,)nnZwwzz=其中(0)(0)0iiwz=(1, )in=，不妨设其中的两个分量(0) tw和(0) sz()ts为负数（对一个或多个分量为负的情形可以类推）。显然，离基变量要在(0) tw和(0) sz中产生。同时，进基变量要在(0) sw和(0) tz中产生。由矩阵的初等行变换知识可知，(0) tz和(0
9、) sw进基后理论上的值应为(1).t t t tqzM=或(1)s s ssqwM=（其中ijM为系数矩阵M中元素）。显然，进基后的(1) tz或(1) sw的值为非负时，解的结构才有所改善。若(1)0tz，(1)0sw。 若对应于q的负分量(0iq，而且 max0ik i ikkkqqqmm=则线性互补问题有一个互补基本可行解 /kkkkiikkizqmwm zq= =+，1, ,ip ik= 其余变量均为零。若矩阵 M 有多个列都为正元素，则可有多个互补基本可行解，选取最优解。 第三步 若不满足0q，且矩阵M的每列不全为负元素，设 (0)(0)(0)min0,1,riiqqqip= 取r
10、行为主行，则取(0) rz作为入基变量，对应的(0) rw作为出基变量(1,rp=)，即取主元(0) rrd。对系数矩阵作进行主元消去变换，令(0)(0) rrwz=。对基向量中( )k tz或( )k tw有负分量，求出其负分量的互补变量( ) ( ) ( ) .k kt tk t tqwM=或( ) ( ) ( ) .k kt tk t tqzM=（其中( )k ijm，( )k tq分别为第k次迭代时M的系数矩阵和右端列中负元素，且tj），置0k=。若( )k tq均为非负元素，则停止计算取基向量的值为( )k tq。设否则，转第三步。 http:/ - 5 - 第四步 在第三步中，在互
11、补变量中挑选出最大的正分量( )k tw或( )k tz(tr)作为入基变量，对应的( )k tz或( )k tw作为出基变量，取( )k ttd为主元对系数矩阵作消元变换。置1kk=+，转第三步。 4改进算法在求解凸二次规划中的实例分析改进算法在求解凸二次规划中的实例分析 例 4.1 求解下面的凸二次规划 22 112212121212min( )2812810. .210242,0f xxx xxxxstxxxxx x=+ 解：本题中已知数据如下 24 412H=，8 10c=，12 24A=，10 2b=， 化成线性互补问题得到 0012 00024 1224 24412TAMAH =，
12、10 2 8 10bqc = ， ywv = ，uzx = 解法一：根据经典的 Lemke 互补转轴算法，在引入人工变量后，经过 4 次迭代过程，得到互补基本可行解(14,6,0,6) ,(0,0,4,0)TTwz=。 解法二：根据改进的算法，矩阵M的第三列无负元素，而且 33332 8 10max0max /,2 24i i iqqqmm=利用算法的步骤二，线性互补问题有一个基本可行解 3333/4zqm= =，14 4 1014w = +=，22 426w = = 44 4 106w = =，31240wzzz= 即(14,6,0,6) ,(0,0,4,0)TTwz=为线性互补问题的一个基
13、本可行解。所以最优解(4,0)x=。 例 4.2 求解如下凸二次规划问题： 22 1122121212min( )221010. .326,0f xxx xxxxstxxx x=+ 解：有本题得到如下数据 http:/ - 6 - 21 1 10H=，1 10c=，32A = ，6b= 化成线性互补问题有： 21311020320THAMA= ，110 6cqb= 1122332131110210 3206wzwzwz = + 0Tw z =，0w, 0z, 3,w zR 解法一：利用原始的 Lemke 互补转轴算法求得 表 4-1 经典的 Lemke 算法的初始表 Tab.4-1 The i
14、nitial table of classical Lemke algorithm 基向量 w1 w2 w3 z1 z2 z3 z0 q w1 1 0 0 -2 1 -3 -1 -1 w2 0 1 0 1 -10 -2 -1 -10 w3 0 0 1 3 2 0 -1 6 表 4-2 经典的 Lemke 算法的迭代表 1 Tab.4-2The first iterated table of classical Lemke algorithm 基向量 w1 w2 w3 z1 z2* z3 z0 q w1 1 -1 0 -3 11* -1 0 9 z0 0 -1 0 -1 10 2 1 10 w3 0 -1 1 2 12 2 0 16 表 4-3 经典的 Lemke 算法的迭代表 2 Tab.4-3 The second iterated table of classical Lemke algorithm 基向量 w1 w2 w3 z1* z2 z3 z0 q z2 1/11 -1/11 0 -3/11 1 -1/11 0 9/11 z0 -10/11 -1/11 0 19/11* 0 32/11 1 20/11 w3 -12/11 1/11 1 58/11 0 34/11 0 68/11 表 4-4 经典的 Lemke
