线性互补问题中几类特殊矩阵与半正定矩阵之间的关系

孙艳波,蒋建林

(1.南京航空航天大学金城学院,江苏南京211156;2.南京航空航天大学理学院,江苏南京211156)

线性互补问题中几类特殊矩阵与半正定矩阵之间的关系

孙艳波1,蒋建林2

(1.南京航空航天大学金城学院,江苏南京211156;2.南京航空航天大学理学院,江苏南京211156)

线性互补问题中特殊矩阵M的性质是线性互补问题中研究的重要部分之一,本文深入研究了矩阵与半正定矩阵、子正定矩阵与半正定矩阵之间的关系,并且得到了特殊矩阵是半正定矩阵的一些充分条件.

半正定矩阵;Q0矩阵;C0矩阵;矩阵;子正定矩阵

1 引言

互补问题是一类新的数学模型,此模型的应用非常广泛,比如经济学中的均衡问题、力学中的接触问题、燃料油的加工提炼问题等[1-2].

互补问题作为线性规划与二次规划的推广,如今已经发展成为数学规划理论中的一个独立分支,所以它的解的存在性研究及算法的可行性研究受到了研究者的重视.

对于线性互补问题,矩阵M的特性与互补问题的解的存在性及算法的收敛性密切相关.所以要针对不同的矩阵类来研究线性互补问题.首先定义两类矩阵:设M∈,如果对于任意的q∈,Lcp(M,q)都有解,则称M为Q矩阵;如果对于给定的使得Lcp(M,q)可行的q,Lcp(M,q)有解,则称M为Q0矩阵.(Q),(Q0)矩阵类的某些子矩阵类已经得到了研究.广义的半正定矩阵和正定矩阵(即不要求为对称矩阵),分别为Q0矩阵和Q矩阵[3].但在一些实际问题构造的Lcp(M,q)模型中,M往往都不是正定矩阵和半正定矩阵,为此,Fiedler,Ptak,Gale,Nikaido等推广了正定矩阵和半正定矩阵的概念,提出了P矩阵,P0矩阵,S矩阵.文献[3]证明了正定矩阵是P矩阵,且(P)⊂(Q),M∈(P)⇔Lcp(M,q)有唯一解.文献[4]提出了C矩阵、C0矩阵、矩阵等概念,文献[5]证明了当n=2时,若M∈()∩(Q0),则M是半正定矩阵.文献[6]提出了子正定矩阵(记为PSBD矩阵),文献[7]中给出了PSBD矩阵是半正定矩阵的一个充分条件.

本文在这些已有结论的基础上,进一步研究了这些特殊矩阵之间的关系,对于∩Q0矩阵,在取消n=2的限制下,推导了其为半正定矩阵的充分条件.PSBD矩阵作为半正定矩阵的直接推广,在二次规划算法的研究中起着重要作用,本文从两个方面给出了PSBD矩阵是半正定矩阵的充分条件.

定义2.1[4]如果对所有x≥0,xTMx≥0,则称M为C0矩阵.

定义2.2[4]如果M∈(C0),且∀x≥0,Mx≥0,xTMx=0可推出MTx≤0,则称M为矩阵.设M∈,Mαα是M相应于下标集α的主子矩阵,若Mαα非奇异,那么矩阵A定义如下:

定义2.3[4]如果M的每个基主元变换都是C0矩阵,则称M是矩阵.

引理2.1[5]设M∈∩(Q0),则M是半正定矩阵.

引理2.2[5]设M∈∩Rn×n,则下列条件等价:

(1)M∈(Q0);(2)对M的每个PPTA,aii=0⇒aij+aji=0,∀i,j∈{1,2,···,n}.

定理2.1若M∈()∩∩(Q0)且rankM=1,则M是半正定矩阵.

证明当n = 1 , 2时,由引理2 . 1知M是半正定矩阵;当n≥3 ,设M∈且rankM=1,若M的对角元中至少有一个不为零(对角元全为零的情况不可能),设

则至少存在一个i使得ai和bi同时不为0,不妨设为i=1,这时m11=a1b1>0,取α={1},A=(M),即

注2.1定理中的条件rankM=1是必要的.例如,设

且对于基主元变换:

都是C0矩阵,从而

另一方面,由于det(M+MT)<0,所以M不是半正定矩阵.

3 PSBD矩阵与半正定矩阵

定义3.1[6]若∀x∈,xTMx<0,可推出MTx≤0或MTx≥0,则称M为PSBD矩阵.

引理3.1[7]若M∈是PSBD-矩阵且rankM≥2,那么MT∈(PSBD),且下列条件至少有一个成立:

(1)M是半正定矩阵;(2)(M+MT)≤0;(3)M∈().

引理3.2[7]设a̸=b,a,b∈,且M=abT,那么M是PSBD矩阵当且仅当下列条件之一成立:

(1)存在t>0,使得b=ta;

(2)对所有t>0,b̸=ta,且b≥0或b≤0.

引理3.3[7]设M=abT∈是PSBD矩阵,其中a,b∈,a,b̸=0.假设∀t>0,b̸=ta,有a≥0或a≤0,那么M∈(Q0)当且仅当下列条件中至少有一个成立:

(1)M是半正定矩阵;

(2)a和b有相反的符号;

(3)a和b有相同的符号且当bi=0时,ai=0,∀i∈{1,2,···,n}.

定理3.1设M∈∩(PSBD)∩(C0),rankM≥2,且M∈/则M是半正定矩阵.

证明因为M是PSBD矩阵,rankM≥2且M/∈(),由引理3.1知M是半正定矩阵或(M+MT)≤0中至少有一个成立.若(M+MT)≤0,则∀x∈,有xT(M+MT)x≤0.

又由M∈(C0)知,

注3.1定理中的M/∈()以及rankM≥2是必要的.

例如,设

则M1∈()∩(PSBD)且rankM1=2,但M1不是半正定矩阵.另一方面,设

则

且M2/∈,但M2不是半正定矩阵.

特别地,当rankM=1时,我们有:

定理3.2设M=abT,其中a,b∈,M∈()∩(PSBD),且M∈(),则M是半正定矩阵.

证明假设M不是半正定矩阵.由M∈(PSBD)知M∈(MPSBD)(即M∈(PSBD),但M不是半正定矩阵),且M=abT,又M∈()⊂(C0),从而由引理3.2知a和b有相同的符号,由M∈()知,当bi=0时,ai=0,由引理3.3知M∈(Q0),从而有M∈()∩(Q0),且rankM=1,由定理2.1知M是半正定矩阵.

注3.2在注3.1中的第二个例子说明了在rankM=1的条件下,M∈()是必要的.下面的例子说明M∈()也是必要的.

设

M3∈()∩(PSBD),M3/∈,且rankM=1,但M不是半正定矩阵.

参考文献

[1] Nagurney A,Dong J,Zhang D.A supply chain network equilibrium model[J].Transportation Research, 2002,38:281-303.

[2] 陈国庆,陈万吉,冯恩民.三维接触问题非线性互补原理及算法[J].中国科学:A辑,1995,25:1181-1190.

[3] Cottle R W,Pang J S,Stone R E.The Linear Complementarity Programming[M].Academic Press,New York,1992.

[4] Murthy G S R,Parthasarathy T.Some properties of fully semimonotone Q0-matrix[J].SIAM J.Matrix And Apl.,1995,16:1268-1286.

[5] Murthy G S R,Parthasarathy T.Fully copositive matrices[J].Math.Programming,1998,82:401-411.

[6] Crouzeix J P,Hassouni A.Positive subde fi nite matrices,generalized monoptonicity and linear compementarity problems[J].SIAM J.Matrix And Appl.,2000,22:66-85.

[7] Mohan S R,Neogy S K.Das A K.More on positive subde fi nnite matrices and the linear complementarity problem[J].Linear Algebra Appl.,2001,338:275-285.

The relationship between semi-de fi nite matrix and several types of special matrices in linear complementary problem

Sun Yanbo1,Jiang Jianlin2
(1.College of Jincheng,Nanhang Jincheng College,Nanjin211156,China; 2.College of Science,Nanhang Jincheng College,Nanjin211156,China)

The special matrix is an important part of the study of linear complementarity problem.In this paper,we study the relationship betweenmatrices and semi-de fi nite matrix,PSBD matrices and semide fi nite matrix.And we get some new conclusions about them.

semi-de fi nite matrix,Q0matrix,C0matrix,matrices,PSBD matrices

O211.1

A

1008-5513(2014)05-0480-05

10.3969/j.issn.1008-5513.2014.05.007

2014-07-10.

国家自然科学基金(11171013);江苏省自然科学基金(BK2011719).

孙艳波(1979-),硕士,讲师研究方向：线性与非线性规划.

2010 MSC:30D30