水平线性互补问题中常用矩阵对及其性质

王秀玉， 申海明， 李 琳

0 引 言

给定矩阵M，N∈Rn×n和向量q∈Rn，水平线性互补问题 HLCP（M，N，q）为:求向量x∈Rn和y∈Rn，使其满足:

水平线性互补问题产生于经济平衡问题、非协作竞赛、交通分配问题和优化问题中，因此在实际中有重要应用。文献［1-3］分别对单调和充分矩阵对所对应的水平线性互补问题进行了研究。为获得水平线性互补问题的可解性及数值解，有必要研究水平互补问题中的矩阵对（M，N）的性质，矩阵对（M，N）的性质决定着水平互补问题解的存在性、有界性。但现有资料中只给出了正定矩阵对的定义，其它矩阵对还很少有学者考虑。文中就研究半正定矩阵对、P＊－矩阵［4］对以及更广泛的拟P＊－矩阵对和P（τ，α）-矩阵对，并给出它们的等价定义。

1 半正定矩阵对及P＊－矩阵对等的性质

定义1 M，N为n×n矩阵，若对任意的u，v∈Rn，（u，v）≠0，满足 Mu＝Nv，有uTv＞0，则称（M，N）为正定矩阵对。正定矩阵对即为文献［2-3］中的单调矩阵对。

例1

则（M，N）为正定矩阵对。

定义2 M，N为n×n矩阵，若对任意的u，v∈Rn，（u，v）≠0，满足 Mu＝Nv，有uTv≥0，则称（M，N）为半正定矩阵对。

例2

则（M，N）为半正定矩阵对，但不为正定矩阵对。

定义3 M，N为n×n矩阵，若对任意的u，v∈Rn，（u，v）≠0，满足 Mu＝Nv，有则称（M，N）为P-矩阵对，显然正定矩阵对必为P－矩阵对。

例3

因此（M，N）为P-矩阵对，但不为正定矩阵对，如u1＝2，u2＝0，u3＝2，uTv＜0。

定理1 （M，N）为正定矩阵对⇔M为正定矩阵。即对∀u∈Rn，u≠0，有uT（Mu）＞0。

定义4 M，N为n×n矩阵，若对任意的向量u，v∈Rn，（u，v）≠0，满足 Mu＝Nv，存在常数τ≥0，使得

则称（M，N）为P＊-矩阵对。

例4

定义5 M，N为n×n矩阵，若对任意的u，v∈Rn，（u，v）≠0，满足 Mu＝Nv，有则称（M，N）为P0－矩阵对，显然P-矩阵对必为P0－矩阵对。

例5

因此有

例6

定理2 正定矩阵对（M，N）为P-矩阵对，则必为P＊－矩阵对。

证明 若（M，N）为P-矩阵对，对∀u，v∈Rn，

考虑函数

φ（u，v）在B 上连续，因此

即

其中

证毕。

定理3 （M，N）为P＊-矩阵对⇔∃τ′＞0使得

证 对任意的

若（M，N）为P＊-矩阵对，则有

情形（1）:I＋（u，v）＝／○，其中，／○为空集，即（1）成立。

情形（2）:I＋（u，v）≠／○，即，只需考虑I-（u，v）≠／○，取

即式（1）成立。

反之，若式（1）成立:

情形（1）:I＋（u，v）＝／○，由式（1）uivi＝0，i＝1，2，…，n，因而对∀τ≥0，

情形（2）:I＋（u，v）≠／○，只需考虑I- （u，v）≠／○，取

证毕。

定义6 M，N为n×n矩阵，若对任意的u，v∈Rn，（u，v）≠0，满足Mu＝Nv，存在τ≥0，α≥0，使得

则称矩阵对（M，N）为P（τ，α）-矩阵对。显然，P＊－矩阵对必为P（τ，α）-矩阵对。

例7

（M，N）不为P0矩阵对。

为使

取τ＝0，α＝5，即

即（M，N）为P（τ，α）-矩阵对。

定理4 （M，N）为P（τ，α）-矩阵对当且仅当存在常数τ′≥0，α′≥0，使得

其中

I＋（u，v）＝ ｛i｜uivi＞0，Mu＝Nv｝

I- （u，v）＝ ｛i｜uivi≤0，Mu＝Nv｝

证明 对任意的u，v∈Rn，且Mu＝Nv，若（M，N）为P（τ，α）-矩阵对［5］，即有式（2）成立，分两种情形讨论。

情形（1）:I＋（u，v）＝／○，即（2）得，uivi＝0，i＝1，2，…，n，对任意的τ′≥0，式（3）成立。

情形（2）:I＋（u，v）≠／○，只需考虑I- （u，v）≠／○，取

反之，若式（3）成立，也分两种情形讨论，取

情形（1）:

情形（2）:I＋（u，v）≠／○，只须考虑

2 P＊－矩阵对水平互补问题解集的凸性

记

定理5 若 （M，N）为P＊－矩阵对，则S为凸集［6－8］。

从而有

式（6）＋式（7）得

又由于

事实上，式（4）－式（5）得

若存在下标i，使得

而（M，N）为P＊-矩阵对，必有

式（9）与式（10）矛盾，因此，对i＝1，2，…，n均有

由式（8）知，（x（λ），y（λ））∈S，证毕。

［1］ Filiz Gurtuna，Cosmin Petra，Florian A Potra.Corrector-predictor methods for sufficient linear complementarity problems［J］.Comput Optim Appl.，2011，48:453-485.

［2］ Gowda M S.On the extended linear complementarity problem ［J］.Mathematical Programming，1996，72:33-50.

［3］ Gowda M S.Reducing a monotone horizontal LCP to an LCP［J］.Applied Mathematics Letter，1995，8（1）:97-100.

［4］ Hannu Valiaho.P＊-matrices are just sufficient［J］.Linear Algebra and its Applications，1996，239:103-108.

［5］ 徐俊彦，苗壮，谭佳伟，等.解线性互补问题的组合同伦方法［J］.长春工业大学学报:自然科学版，2010，31（3）:269-274.

［6］ 高兴宝.解水平线性互补问题的神经网络［J］.西安石油大学学报:自然科学版，2004，19（1）:85-88.

［7］ 孙洪春.求解水平线性互补问题的一个非光滑二次收敛算法［J］.四川师范大学学报:自然科学版，2007，30（5）:136-138.

［8］ 林正华，盛中平.预估－校正算法跟踪组合同伦路径［J］.计算数学，2002，24（4）:405-416.