改进求解凸二次规划中的Lemke算法
- 格式：pdf
- 大小：371.20 KB
- 文档页数：10
http://www.paper.edu.cn
- 1 - 改进求解凸二次规划中的Lemke算法
张璐
辽宁工程技术大学理学院，辽宁阜新（123000）
E-mail:zhanglu85517@sohu.com
摘 要：通过对经典的Lemke互补转轴算法求解凸二次规划问题的分析，找到了Lemke
算法的局限性。本文在Lemke算法求解线性互补问题的基础上修正了经典的Lemke算
法的迭代过程，提出了一种改进的Lemke算法，通过算例证明了算法能有效克服解的
局限性，减少了凸二次规划问题的迭代过程，提高了算法的效率。
关键词：非线性规划；凸二次规划；线性互补问题；Lemke算法
1．引言
二次规划问题是最简单而又最基本的非线性规划问题，其目标函数是二次函数，约束是
线性等式或不等式。对于二次规划问题，可行域是凸集，所以当目标函数是凸函数时，任何
K-T点都是二次规划问题的极小点。研究二次规划问题的算法不仅仅是为了解决二次规划问
题本身，同时也是为了更好的求解其他非线性规划问题。因为大多数最优化方法是从二次函
数模型导出的，这种类型的方法在实际中常常是有效的，其主要是因为一般函数的极小点附
近常可用二次函数很好地进行近似。由于二次规划是特殊的非线性规划，因此求解非线性规
划问题的方法均可用于二次规划问题的求解。同时，由于二次规划本身的特殊性，对它的求
解可以采用一些更有效的方法[1]
。因此，不论从数学角度还是应用角度来看，二次规划问题
的研究都具有重要意义。到目前为止，已经出现了很多求解二次规划问题的算法，并且现在
仍有很多学者在从事这方面的研究工作。所以，需要我们对现存的有效的求解二次规划问题
的算法进行改进，得到新的求解算法来克服某些算法的缺点，并且给出具体的实例显示该算
法的有效性。本文主要研究凸二次规划的求解算法，以及线性互补问题的性质等相关问题。
对Lemke算法进行进一步研究，对它可能出现退化的原因和迭代过程以及局限性进一步分
析。本文通过分析经典的Lemke互补转轴算法求解含有等式约束的凸二次规划问题可能出
现退化的原因，修正了Lemke算法的迭代步骤，提出了一种改进的Lemke算法。通过求解
具体实例，说明了改进算法求解凸二次规划问题的有效性[2]
。
2．Lemke算法介绍
2.1 Lemke算法的基本思想
Lemke算法的基本思想是，由一个准互补基本可行解出发，通过转轴方法（即主元消去）
求出一个新的准互补基本可行解[3]
。这个过程可以不断地迭代，力争使变量
0z
称为非基变量，
或者得到一个判据，说明问题(3-3)和(3-4)可行域无界。转轴方法（主元消去）遵循以下规则：
（1）保持可行性 按照最小比值规则确定离基变量。
（2）保持准互补性 若
iw
(或
iz
)是离基变量，则
iz
(或
iw
)是进基变量。
2.2 Lemke方法的计算步骤
（1）若0q≥
，则停止计算，(,)(,0)wzq=
是互补基本可行解；否则，用表格形式表
示成方程组，设 http://www.paper.edu.cn
- 2 - max{1,,}
iiqqimn−=−=⋅⋅⋅+
取s
行为主行，
0z
对应的列为主列，进行主元消去，令
ssyz=
。
（2）设在现行表中变量
sy
下面的列为
sd
．若0
sd≤
，则停止计算；否则，按最小比
值规则确定指标r
，使
min|0ii
is
rsisqq
d
dd⎧⎫
⎪⎪
=>
⎨⎬
⎪⎪
⎩⎭
如果r
行的基变量是
0z
，则转步骤（4）；否则，进行步骤（3）。
（3）设r
行的基变量为
lw
或
lz
（对于某个ls≠
），变量
sy
进基，以r
行为主行，
sy
对
应的列为主列，进行主元消去。如果离基变量是
lw
，则令
slyz=
；如果离基变量是
lz
，则
令
slyw=
。转步骤（2）。
（4）变量
sy
进基，
0z
离基。以r
行为主行，
sy
对应的列为主列，进行主元消去。得
到互补基本可行解，停止计算[4]
。
2.3 Lemke互补转轴算法的局限性分析
首先，这一算法满足于一个互补基本可行解。所以用它不可能求得线性互补问题的多个
解。
其次，这一算法的收敛条件很强，限制了它的使用范围。
此算法的收敛定理：
(1) 0z∀≥
均有0T
zMz≥
．而且0(0)T
zMzz=≥
蕴涵()0T
MMz+=
。(M
is said to
be copositive-plus)；
(2) 每一个准互补基本可行解(almost complementary basic feasible solution)均非退化。
若式(2)与(1)相容，则Lemke互补转轴算法终止于一个互补基本可行解；若不相容，则
终止于射线，条件(1)很强，而且不易检查。但可以指出：若M
的主对角线上出现负元素，
则条件(1)必不满足[5,6,7]
。
3．改进算法研究
3.1改进的Lemke算法的基本思想
本文研究的改进算法主要是求解线性互补问题，虽然向量q
都有负向量，然而不必引入
人工向量
0z
，可以通过一个简单公式算的一个互补基本可行解。
定理3.1 设矩阵M
的第k
列无负元素，即0
kM>
。若对应于q
的负分量(0
iq<
)，都
有0
ikm>
，而且
max0ik
i
ikkkqq
q
mm⎧⎫
−−
<=
⎨⎬
⎩⎭ （3-1）
则线性互补问题有一个互补基本可行解
/
kkkk
iikkizqm
wmzq=−
=+ ，1,,,ipik=⋅⋅⋅≠
（3-2） http://www.paper.edu.cn
- 3 - 其余变量均为零。
证明：将线性互补问题列表(如表3-1)
表3-1 互补问题基本表格
Tab.3-1 Complementary problem basis table
基 w
1 … w
k … w
p z
1 … z
k … z
p
q
w
1 1 … 0 … 0 -m
11 … -m
1k … -m
1p q
1
… … … … … … … … … … … …
w
k 0 … 1 … 0 -m
k1 … -m
kk … -m
kp q
k
… … … … … … … … … … … …
w
p 0 … 0 … 1 -m
p1 … -m
pk … -m
pp q
p
以
kkm−
为主元迭代一次后，基变量的值即为(3-2)。由(3-1)和(3-2)可以得到
0
kz>
，0
iikkiwmzq=+>
，1,,,ipik=⋅⋅⋅≠
。因而由(3-2)给出线性互补问题的一个互补
基本可行解（非基变量均为零）。
下面讨论离基变量的选取与进基变量的确定。
设初始解(0)(0)(0)(0)(0)
11(,,,,,)
nnZwwzz=⋅⋅⋅⋅⋅⋅
其中(0)(0)
0
iiwz=(1,,)in=⋅⋅⋅
，不妨设其中
的两个分量(0)
tw
和(0)
sz()ts≠
为负数（对一个或多个分量为负的情形可以类推）。显然，离
基变量要在(0)
tw
和(0)
sz
中产生。同时，进基变量要在(0)
sw
和(0)
tz
中产生。由矩阵的初等行变
换知识可知，(0)
tz
和(0)
sw进基后理论上的值应为(1)
.t
t
ttq
z
M=或(1)
s
s
ssq
w
M=
（其中
ijM
为系数
矩阵M
中元素）。显然，进基后的(1)
tz
或(1)
sw
的值为非负时，解的结构才有所改善。若
(1)
0
tz≥
，(1)
0
sw<
，则选取(0)
tw
为离基变量；若(1)
0
tz<
，(1)
0
sw≥
，则选取(0)
sz
为离基变
量。不妨记以上离基规则为最大正互补变量规则。
3.2改进的Lemke算法的算法证明
（1）算法的可行性分析
定义3.1：如果基本可行解中只有一对分量都不是基变量，而其余各对分量都有一个，
而且刚好有一个为基变量的，称为特互补基本可行解。其中，一对分量指
iw
，
iz
，即w
，z
有相同的足标的一对分量。
定义3.2：一个特互补基本可行解中如果大于0的分量个数少于原互补问题的阶数，则
称为其退化的互补基本可行解。
定义3.3：取非基对的一个变量足标定为主元列号，经一个主元消去步骤便可得出另一
个特互补基本可行解。用这种方法得到的新的特互补基本可行解称为相邻的特互补基本可行
解。
定理3.2：一个线性互补问题，若它是非退化的，则任何一个特互补基本可行解最多有
两个相邻的特互补基本可行解。
证明：我们只要证明对于非退化问题进行一个主元消去步时，主元行号唯一就可以了。
事实上，
