P0線性互補(bǔ)問(wèn)題的新同倫方法

姜興武，王秀玉

(1.吉林工商學(xué)院基礎(chǔ)部，長(zhǎng)春130062;2.長(zhǎng)春工業(yè)大學(xué)基礎(chǔ)科學(xué)學(xué)院，長(zhǎng)春130012)

互補(bǔ)問(wèn)題與數(shù)學(xué)規(guī)劃、對(duì)策論、不動(dòng)點(diǎn)理論和極大極小問(wèn)題等密切相關(guān)，在工程、力學(xué)、經(jīng)濟(jì)及交通等許多實(shí)際問(wèn)題中應(yīng)用廣泛.線性互補(bǔ)問(wèn)題是互補(bǔ)問(wèn)題的一個(gè)重要分支，即考慮問(wèn)題(LCP(M，q)):求x≥0，使得y=Mx+q≥0且xTy=0，其中M為一個(gè)n階方陣.

目前，求解互補(bǔ)問(wèn)題的方法很多，其中同倫方法由于具有大范圍收斂性而成為求解互補(bǔ)問(wèn)題的重要工具.本文通過(guò)構(gòu)造與文獻(xiàn)［1-7］不同的同倫方程，對(duì)P0線性互補(bǔ)問(wèn)題進(jìn)行求解，獲得了理想的結(jié)果.x≥0(x＞0)表示向量x的每個(gè)分量為非負(fù)(正數(shù));w=(x，y)表示向量w=(xT，yT)T，xi表示向量x的第i個(gè)分量.

引理1［8］令M∈?n×n為任意矩陣，則下列情況等價(jià):

1)M∈?n×n是 P0矩陣;

2)M的所有主子式均為非負(fù)數(shù);

3)對(duì)于任意的正數(shù)ε＞0，M+εE為P矩陣，其中E是n階單位矩陣.

引理2［8］M∈?n×n為P矩陣的充分必要條件是:M的全部主子式均為正值.

假設(shè)條件:

(H1)M∈?n×n是 P0矩陣;

(H2)互補(bǔ)問(wèn)題LCP(M，0)只有零解，即y=Mx，x≥0，y≥0，xTy=0只有零解.

記w=(x，y)，任取 y(0)＞0 及 x(0)=(M+E)-1(y(0)-q)，w=(x(0)，y(0))，構(gòu)造如下同倫方程H:?n×?n→?2n:

當(dāng)μ=1時(shí)，式(1)為

證明:將y(0)視為變量，以w(0)，w，μ為自變量的同倫方程記為Hw(0)(w，μ)，它的Jacobian矩陣記為

證明:Γw(0)的存在性由定理1可得.若Γw(0)無(wú)界，則必存在子列{(x(k)，y(k)，μk)}∈Γw(0)，使得當(dāng)k→∞時(shí)，有‖(x(k)，y(k)，μk)‖→∞，由同倫方程(1)的第二個(gè)等式得

由式(2)及 μ∈(0，1］可知

將式(2)改寫(xiě)為

則由同倫方程(1)的第一個(gè)等式得

情形1)μ*∈［0，1).

可斷定μ*≠0，否則若μ*=0，則由式(7)得y(*)=Mx(*).而由式(4)可知，對(duì)任意的i=1，2，…，n，有

x(*)≥0，y(*)≥0，(x(*))Ty(*)=0，與假設(shè)條件(H2)矛盾.由引理1知，M+μ*E為P矩陣，式(7)與M+μ*E為P矩陣矛盾.

情形2)μ*=1.

① 若{(1-μk)x(k)}仍為無(wú)界序列，則式(5)兩邊同乘1-μk得

令

式(10)與M+E為P矩陣矛盾.

式(12)與{x(k)}的無(wú)界性矛盾.

將式(8)兩邊取極限得

式(14)與M+E是P矩陣矛盾.

證明:由定理1和定理2易知Γw(0)為有界曲線.由一維流形分類定理知，Γw(0)微分同胚于單位圓周或單位區(qū)間(0，1］(證明與文獻(xiàn)［6］的定理2.1類似).由

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

綜上可見(jiàn)，本文通過(guò)構(gòu)造新同倫方程，得到了P0線性互補(bǔ)問(wèn)題 LCP(M，q)有解與互補(bǔ)問(wèn)題LCP(M，0)只有零解的關(guān)系.

［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］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.

［3］XU Qing，DANG Chuang-yin.A New Homotopy Method for Solving Non-linear Complementarity Problems［J］.Optimization，2008，57(5):681-689.

［4］ZHAO Yun-bin，LI Gong-nong.Properties of a Homotopy Solution Path for Complementarity Problems with Quasimonotone Mappings［J］.Applied Mathematics and Computation，2004，148(1):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］DING Jun-di，YIN Hong-yan.A New Homotopy Method for Nonlinear Comolementarity Problems［J］.Numericla Mathematics A Journal of Chinese Universities:English Series，2007，16(2):155-163.

［7］WANG Xiu-yu，JIANG Xing-wu，LIU Qing-huai.New Homotopy Method for Solving Nonlinear Complementarity Problems［J］.Journal of Jilin University:Science Edition，2012，50(3):494-498.(王秀玉，姜興武，劉慶懷.求解互補(bǔ)問(wèn)題的新同倫算法［J］.吉林大學(xué)學(xué)報(bào):理學(xué)版，2012，50(3):494-498.)

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