線性互補(bǔ)問題解的存在性

楊泰山，姜興武，王秀玉

（1.吉林大學(xué) 數(shù)學(xué)學(xué)院，長春130012；2.吉林工商學(xué)院 基礎(chǔ)部，長春130062；3.長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院，長春130012）

線性互補(bǔ)問題是：求x≥0，使得y＝Mx＋q≥0且有xTy＝0，其中M為一個n階方陣，該互補(bǔ)問題記為LCP（M，q），稱為非齊次互補(bǔ)問題.當(dāng)q＝0時，記為LCP（M，0），稱為齊次互補(bǔ)問題.線性互補(bǔ)問題是互補(bǔ)問題的一個重要組成部分，并且二次規(guī)劃的K－K－T方程也為線性互補(bǔ)問題.

同倫方法由于具有大范圍收斂性，目前已成為求解數(shù)學(xué)問題的一個重要工具.文獻(xiàn)［1］構(gòu)造了一類同倫方程求解互補(bǔ)問題；文獻(xiàn)［2－6］對文獻(xiàn)［1］的同倫方程給出了不同條件下同倫路徑的存在性；文獻(xiàn)［7］建立了與文獻(xiàn)［1］完全不同的同倫方程，獲得了互補(bǔ)問題的可解性，但文獻(xiàn)［7］的同倫方程當(dāng)參數(shù)為零時不能回到原互補(bǔ)問題，也未給出具體條件；文獻(xiàn)［8］改進(jìn)了文獻(xiàn)［7］的結(jié)果，利用同倫方法對互補(bǔ)問題進(jìn)行求解.本文運(yùn)用文獻(xiàn)［1］的同倫方程給出半單調(diào)線性互補(bǔ)問題同倫路徑的存在性、有界性及收斂性，并給出LCP（M，q）有解與LCP（M，0）只有零解的關(guān)系.

本文用x≥0或x∈?n＋（x＞0或x∈?n＋＋）表示向量x的每個分量為非負(fù)（正數(shù)），用w＝（x，y）表示向量w＝（xT，yT）T.

1 預(yù)備知識

定義1［9］如果對任意的x≥0，x≠0，存在一個分量xk＞0，使得（Mx）k≥0，則n階方陣M∈?n×n稱為半單調(diào)矩陣.

當(dāng)M為半單調(diào)矩陣時，互補(bǔ)問題LCP（M，q）稱為半單調(diào)線性互補(bǔ)問題.

假設(shè)條件：

（H1）M∈?n×n是半單調(diào)矩陣；

（H2）y＝Mx，x≥0，y≥0，xTy＝0只有零解；

（H3）存在u∈?n＋＋，使得v＝Mu＋q＞0；

（H4）存在常數(shù)τ≥0，α≥0，1＜β＜2，使得對任意的x∈?n，y∈?n，下式成立：

例1

則M顯然為半單調(diào)矩陣.令

則M不是P0矩陣.

只有零解.M 滿足假設(shè)條件（H1），（H2）.

2 主要結(jié)果

記w＝（x，y），任取x（0）＞0，y（0）＞0及w＝（x（0），y（0）），構(gòu)造如下同倫方程：

其中X＝diag（x）.同倫方程（1）也記為Hw（0）（w，μ），并記

證明：Γw（0）的存在性由定理1可得.Γw（0）??n＋×?n＋×（0，1］顯然成立.若Γw（0）無界，則必存在子列（x（k），y（k），μk）∈Γw（0），使得當(dāng)k→∞時，有‖（x（k），y（k），μk）‖→∞，由同倫方程（1）的第二個等式得

由式（2）可知

由同倫方程（1）的第一個等式得

情形1）μ＊∈［0，1）.

由式（2）及x（＊），y（＊）的定義，對任意的i＝1，2，…，n，得

又由式（6）知（x（＊），y（＊））為齊次互補(bǔ)問題LCP（M，0）的非零解，與假設(shè)（H2）矛盾.

情形2）μ＊＝1.分兩種情形論證.

令

而由式（2）可知，對任意的i＝1，2，…，n，有

因而由式（2），（9）得

式（10）與｛x（k）｝無界性矛盾.

式（4）兩邊取極限得

再由式（2）得

由式（4）－式（13），得

將式（2）代入式（14）的分量形式，對所有的i＝1，2，…，n，得

由式（15）可知

由式（16）可知，當(dāng)x（k）i→∞時，有

且對所有的i＝1，2，…，n，有

由于｛x（k）｝為無窮序列，因而存在整數(shù)s，p，使得

顯然有

由式（18），（19）可知，對充分大的k，有

由條件（H3）知下式成立：

整理式（21）得

證明：由定理1～定理3易知Γw（0）為有界曲線.由一維流形分類定理知，Γw（0）微分同胚于單位圓周或單位區(qū)間（0，1］（證明與文獻(xiàn)［7］的定理2.1類似）.注意到

是非奇異的，得Γw（0）不能微分同胚于單位圓周，而只能微分同胚于單位區(qū)間.記（w（＊），μ＊）為Γw（0）的極限點(diǎn)，則只有下列4種情形可能發(fā)生：

［1］Kojima M，Megiddo N，Mizuno M.A General Framework of Continuation Methods for Complementarity Problems［J］.Math Oper Res，1993，18（4）：945－963.

［2］XU Qing，DANG Chang－yin.A New Homotopy Method for Solving Non－linear Complementarity Problems［J］.Optimization，2008，57：681－689.

［3］YU Qian，HUANG Chong－chao，WANG Xian－jia.A Combined Homotopy Interior Point Method for the Linear Complementarity Problem ［J］.Applied Mathematics and Computation，2006，179（2）：696－701.

［4］ZHAO Yun－bin，LI Gong－nong.Properties of a Homotopy Solution Path for Complementarity Problems with Quasi－monotone Mappings［J］.Applied Mathematics and Computation，2004，148：93－104.

［5］LI Gong－nong.Analysis for a Homotopy Path of Complementarity Problems Based onμ－Exceptional Family［J］.Applied Mathematics and Computation，2005，169（1）：657－670.

［6］WANG Xiu－yu，JIANG Xing－wu， LIU Qing－h(huán)uai.The Combined Homotopy Method for Nonlinear Complementarity Problems［J］.Acta Mathematicae Applicatae Sinica，2012，35（3）：430－440.（王秀玉，姜興武，劉慶懷.非線性互補(bǔ)問題的組合同倫算法 ［J］.應(yīng)用數(shù)學(xué)學(xué)報，2012，35（3）：430－440.）

［7］DING Jun－di，YIN Hong－you.A New Homotopy Method for Nonlinear Complementarity Problems ［J］.Numericla Mathematics，A Journal of Chinese Universities：English Series，2007，16（2）：155－163.

［8］WANG Xiu－yu， JIANG Xing－wu， LIU Qing－h(huán)uai.New Homotopy Method for Solving Nonlinear Complementarity Problems［J］.Journal of Jilin University：Science Edition，2012，50（3）：494－498.（王秀玉，姜興武，劉慶懷.求解互補(bǔ)問題的新同倫算法 ［J］.吉林大學(xué)學(xué)報：理學(xué)版，2012，50（3）：494－498.）

［9］韓繼業(yè)，修乃華，戚厚鐸.非線性互補(bǔ)理論與算法 ［M］.上海：上?？茖W(xué)技術(shù)出版社，2006.