李 園

(內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院，內(nèi)蒙古通遼028043)

一個(gè)求解H－矩陣絕對(duì)值線性互補(bǔ)問(wèn)題的罰方法

李 園

(內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院，內(nèi)蒙古通遼028043)

考慮一類新的線性互補(bǔ)問(wèn)題，即絕對(duì)值線性互補(bǔ)問(wèn)題.通過(guò)構(gòu)造與絕對(duì)值線性互補(bǔ)問(wèn)題相等價(jià)的罰方程給出了一個(gè)求解此類絕對(duì)值線性互補(bǔ)問(wèn)題的罰方法.并證明了當(dāng)絕對(duì)值線性互補(bǔ)問(wèn)題的矩陣為H－矩陣時(shí)算法的全局收斂性.最后，通過(guò)數(shù)值試驗(yàn)表明了該算法的有效性.

運(yùn)籌學(xué)；絕對(duì)值線性互補(bǔ)問(wèn)題；H－矩陣；罰方法；收斂

線性互補(bǔ)問(wèn)題(簡(jiǎn)記作LCP(A，b))定義為，求x＝(x1，x2，…，xn)T∈?n，使得:

其中A∈?n×n，b∈?n.

線性互補(bǔ)問(wèn)題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)的一個(gè)交叉研究領(lǐng)域，已經(jīng)廣泛應(yīng)用于力學(xué)、交通、經(jīng)濟(jì)、金融、控制等領(lǐng)域中出現(xiàn)的許多數(shù)學(xué)模型，例如障礙和自由邊界問(wèn)題、供應(yīng)鏈問(wèn)題、交通分配問(wèn)題、經(jīng)濟(jì)均衡問(wèn)題、非均衡博弈論等，這使得線性互補(bǔ)問(wèn)題成為數(shù)學(xué)規(guī)劃中的一個(gè)十分熱門(mén)的研究課題.許多學(xué)者對(duì)線性互補(bǔ)問(wèn)題的求解進(jìn)行了深入的研究，提出了許多算法[1－5]，例如:投影法、光滑牛頓法、非光滑牛頓法、松弛法、內(nèi)點(diǎn)法、非光滑方程法、預(yù)條件迭代法等.進(jìn)一步掌握和研究互補(bǔ)問(wèn)題的各類算法不僅具有理論意義，而且具有實(shí)際意義.隨著對(duì)LCP(A，b)這一領(lǐng)域研究的不斷深入，Noor等[6]于2012年提出了一類新的線形互補(bǔ)問(wèn)題，即絕對(duì)值線性互補(bǔ)問(wèn)題，這也是本文要研究的問(wèn)題.絕對(duì)值線性互補(bǔ)問(wèn)題(簡(jiǎn)記作AVLCP(A，b))為:求向量x＝(x1，x2，…，xn)T∈Rn，使得:

關(guān)于AVLCP(A，b)的研究，目前只有Noor等[6]提出的廣義AOR迭代法和2014年李園等[7]提出的基于罰方程的廣義牛頓法，該廣義牛頓法的研究基于如下的非線形罰方程:求xλ∈?n，滿足:

其中:λ>1是懲罰因子，k>0是參數(shù)，[u]＋＝max{ u，0}.對(duì)任意的y＝(y1，y2，…，yn)T∈?n和任意實(shí)數(shù)α，有yα.鑒于此，對(duì)于AVLCP(A，b)的理論和算法的研究還有待進(jìn)一步深入.因此，本文進(jìn)一步研究求解AVLCP(A，b)的算法.

1984年，Glowinski[4]研究了一類與?n中變分不等式相等價(jià)的罰方程，證明了在變分不等式的矩陣為對(duì)稱正定時(shí)罰方程的收斂性.2006年，Wang等[8]將美國(guó)期權(quán)問(wèn)題轉(zhuǎn)化成LCP(A，b)，將文獻(xiàn)[4]提出的罰方程進(jìn)行了推廣，證明了線性互補(bǔ)問(wèn)題的矩陣為正定時(shí)新的罰方程的解收斂到互補(bǔ)問(wèn)題的解.2008年，Yang等[9]利用文獻(xiàn)[8]中構(gòu)造的罰方程，在線性互補(bǔ)問(wèn)題的矩陣為正定，主對(duì)角元素大于零，其余元素均小于等于零的條件下證明了當(dāng)懲罰因子λ趨向于無(wú)窮大時(shí)非線性罰方程的解指數(shù)次收斂到線性互補(bǔ)問(wèn)題的解.同年，Wang等[10]提出了一個(gè)帶有擾動(dòng)項(xiàng)的求解非線性拋物型互補(bǔ)問(wèn)題的非線性罰方程，但是罰方程的解收斂到互補(bǔ)問(wèn)題的解仍需正定性假設(shè).鑒于上述罰函數(shù)方法的收斂性均依賴于線性互補(bǔ)問(wèn)題的矩陣的正定性假設(shè)，李園等[11－12]將上述罰方法進(jìn)行了推廣，在線性互補(bǔ)問(wèn)題的矩陣為P－矩陣時(shí)證明了罰方程的解指數(shù)次收斂到LCP(A，b)的解.

本文首先利用李園等[7]提出的非線性罰方程[4]，證明了當(dāng)AVLCP(A，b)中的矩陣A為H－矩陣時(shí)非線性罰方程[4]的解指數(shù)次收斂到AVLCP(A，b)的解.其次，通過(guò)數(shù)值試驗(yàn)表明了本文所提出的算法的有效性.

1 預(yù)備知識(shí)

為方便起見(jiàn)，本文給出如下記號(hào).設(shè)A＝(aij)∈?n×n為n×n實(shí)矩陣.矩陣A≥0當(dāng)且僅當(dāng)aij≥0，i，j＝1，2，…，n.矩陣A的F－范數(shù)記為表示n維歐式空間.?n中所有向量均為列向量.向量x與y的內(nèi)積記為xTy.對(duì)于實(shí)數(shù)p>1，向量的p－范數(shù)記為當(dāng)p＝2時(shí)，p－范數(shù)即為2－范數(shù)‖x‖＝(xTx)12，2－范數(shù)也稱為歐式范數(shù).

定義1[1]設(shè)A＝(aij)∈?n×n，若A的全部主子式均是正值，則稱A為P－矩陣.

定義2[13]設(shè)A∈?n×n.

1)若aii≥0，i＝1，2，…，n，aij≤0，i，j＝1，2，…，n，i≠j，則稱矩陣A為L(zhǎng)－矩陣；

2)若aij≤0，i，j＝1，2，…，n，i≠j，則稱矩陣A為Z－矩陣；

3)設(shè)〈A?＝(a～ij)∈?n×n，其中則稱矩陣〈A?為矩陣A的比較矩陣.

定義[13]設(shè)A為Z－矩陣，A可逆且A－1≥0，則稱A為非奇異的M－矩陣.

定義4[13]設(shè)A∈?n×n，如果A的比較矩陣是非奇異的M－矩陣，則稱A為非奇異的H－矩陣，簡(jiǎn)稱H－矩陣.

定義5[13]設(shè)A∈?n×n，如果:則稱A為行對(duì)角占優(yōu)矩陣.

定義6[13]設(shè)A∈?n×n，如果對(duì)任意的x∈?n，存在常數(shù)β>0，使得‖Ax‖≤β‖x‖成立，則稱矩陣A有界.

引理1[1]若A∈?n×n為對(duì)角元素均為正數(shù)的H－矩陣，則A為P－矩陣.

引理2[7]設(shè)K是?n中的閉凸集，則存在常數(shù)ρ>0，x∈K是絕對(duì)值變分不等式(3)的解的充要條件是x∈K是方程:的解，其中PK為?n到閉凸集K上的投影.

引理3[3]A∈?n×n是P－矩陣的充要條件是:存在一常數(shù)c>0，對(duì)于任意向量x∈?n，存在一下表k＝ k(x)，1≤k≤n，滿足:

其中:xk表示x的第k個(gè)分量，(Ax)k表示Ax的第k個(gè)分量.

引理4 設(shè)A∈?n×n是P－矩陣.若則絕對(duì)值變分不等式(3)存在唯一解.

證明 唯一性的證明同文獻(xiàn)[5]中定理2.4，下面只證存在性.設(shè)x∈K是絕對(duì)值變分不等式(3)的解，

下面證明映射(5)存在不動(dòng)點(diǎn)，只須證明映射(5)是緊映射即可.對(duì)于任意的x1≠x2∈K，

情況Ⅰ:若〈x1－x2，A(x1－x2)?＝(x1－x2)1[A(x1－x2)]1＋(x1－x2)2[A(x1－x2)]2＋…＋(x1－x2)n[A(x1－x2)]n中所有分量(x1－x2)i[A(x1－x2)]i，i＝1，2，…，n均非負(fù)，則根據(jù)引理3，存在常數(shù)c>0，使得〈x1－x2，A(x1－x2)?≥c‖x1－x2‖2，故:

情況Ⅱ:若〈x1－x2，A(x1－x2)?＝(x1－x2)1[A(x1－x2)]1＋(x1－x2)2[A(x1－x2)]2＋…＋(x1－x2)n[A(x1－x2)]n中分量(x1－x2)i[A(x1－x2)]i，i＝1，2，…，n既有正又有負(fù)，則不妨假設(shè)前k個(gè)分量

(x1－x2)i[A(x1－x2)]i≤0，i＝1，2，…，k，后(n－k)個(gè)分量(x1－x2)i[A(x1－x2)]i≥0，i＝k＋1，k＋2，…，n，則根據(jù)引理3，對(duì)于后(n－k)個(gè)分量，必存在一個(gè)分量(x1－x2)m[A(x1－x2)]m，m∈{k＋1，k＋2，…，n}，使得存在常數(shù)c>0，有(x1－x2)m[A(x1－x2)]m≥c‖x1－x2‖2，則:

因此:

引理5(H?lder不等式)[12]設(shè)x，y∈?n，中p和q均大于1且滿

關(guān)于矩陣A的F－范數(shù)‖·‖F(xiàn)與向量的歐式范數(shù)‖·‖的相容性，有如下結(jié)論:

引理6[4]設(shè)A∈?m×n，x∈?n，則

2 非線性罰方程(4)的收斂性質(zhì)

本文將討論非線性罰方程(4)的收斂性質(zhì)，給出非線性罰方程(4)的解收斂于絕對(duì)值線性互補(bǔ)問(wèn)題(2)的解.本節(jié)對(duì)AVLCP(A，b)中的矩陣A作如下假設(shè):

(A1)A∈?n×n是有界的H－矩陣且行對(duì)角占優(yōu)；

(A3)矩陣A的奇異值大于1.

根據(jù)引理1、引理4以及上面的假設(shè)，知絕對(duì)值線性互補(bǔ)問(wèn)題(2)有唯一解.根據(jù)上面的假設(shè)，首先建立下面的定理.根據(jù)上述假設(shè)，可以得到如下結(jié)論:

定理1 設(shè)xλ＝(u1，u2，…，un)T∈?n是非線性罰方程(4)的解.如果xλ滿足如下條件之一:

i)xλ的分量均非正；ii)xλ僅有一個(gè)正分量，其余分量均非正；

iii)xλ有m(2≤m

則存在一個(gè)與n，xλ和λ均無(wú)關(guān)的正數(shù)C，滿足:

(A2)矩陣A的元素滿足

證明 i)若xλ的分量均非正，這時(shí)[xλ]＋＝(0，0，…，0)T，于是則式(6)和 (7)顯然成立；下面只證明情況iii)，對(duì)于情況ii)類似可證.

iii)若xλ有m(2≤m0，um＋1，um＋2，…，un≤0.令＝(u1，u2，…，um)T∈?m，＝(um＋1，um＋2，…，un)T∈?n－m，用分別左乘非線性罰方程(4)的兩端后，得:

將式(9)展開(kāi)，得:

根據(jù)題設(shè)矩陣A為行嚴(yán)格對(duì)角占優(yōu)及ui≥uj(1≤i

由定理1，可以得到下面的收斂性結(jié)論.

定理2 設(shè)x∈?n和xλ∈?n分別是AVLCP(A，b)和非線性罰方程(4)的解，其中xλ滿足定理1的條件.若rλ＝x＋[xλ]－＝(r1，r2，…，rn)T≤0且其任意兩個(gè)不為零的分量ri和rj均存在一個(gè)與n，

x，xλ和λ均無(wú)關(guān)的常數(shù)C>0，使得:

其中[xλ]－＝－min xλ，0{}，λ和k是非線性罰方程(4)中定義的參數(shù).

證明 設(shè)根據(jù)[xλ]＋和[xλ]－的定義，有xλ＝[xλ]＋－[xλ]－，于是:

其中rλ＝x＋[xλ]－.令ω＝x－rλ，由rλ的定義知ω＝x－rλ＝[xλ]－≤0，于是ω∈K，在式(3)中令y＝ω后，得:

將非線性罰方程(4)兩端同時(shí)左乘rTλ后，有:

將式(11)和式(12)相加后得:

i)若r1＝r2＝…＝rn＝0時(shí)

ii)若r1，r2，…，rn不全為零，不妨設(shè)r1，r2，…，rk≠0，rk＋1＝rk＋2＝…＝rn＝0，根據(jù)假設(shè)條件，對(duì)任意的1≤i

4 數(shù)值試驗(yàn)

本節(jié)中，將通過(guò)數(shù)值例子來(lái)說(shuō)明本文所建立的算法的有效性.運(yùn)用Matlab 7.5進(jìn)行計(jì)算，運(yùn)行環(huán)境為: CPU為Intel(R)Core(TM)2×2.70GHz，內(nèi)存為2.0GB.

當(dāng)懲罰因子λ→＋∞時(shí)，xλ→x?，且‖x?－xλ‖≤C/λ4.

x?＝.在罰方程(4)中取k＝1，解得:

當(dāng)懲罰因子λ→＋∞時(shí)，xλ→x?，且‖x?－xλ‖2≤C/λ2.

從例1、例2、例3可以看出，隨著懲罰因子λ趨于無(wú)窮大時(shí)，罰方程(4)的解收斂到AVLCP(A，b)的解，這也正好驗(yàn)證了本文的結(jié)論.

5 總結(jié)

本文首先利用李園等[6]提出的非線性罰方程(4)，證明了當(dāng)AVLCP(A，b)中的矩陣A為H－矩陣時(shí)非線性罰方程(4)的解指數(shù)次收斂到AVLCP(A，b)的解.其次，通過(guò)數(shù)值試驗(yàn)表明了本文所提出的算法的有效性.

[1] COTTLE R W，PANG J S，STONE R E.The Linear Complementarity Problems[M].Academic Press，San Diego，CA，1992.

[2] FACCHINEI F，PANG J S.Finite－dimensional variational inequalities and complementarity problems[M].Vol.I and II.New York:Springer，2003.

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

[4] GLOWINSKI R.Numerical methods for nonlinear variational problems[M].New York:Springer－Verlag，1984.

[5] 蘭英，韓海山，岳織鋒.線性互補(bǔ)問(wèn)題的一個(gè)新的迭代算法[J].內(nèi)蒙古民族大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014，29(6):624－626.

[6] NOOR M A，IQBAL J，NOOR K I，et al.Generalized AOR method for solvung absolute Complementarity problems[J].Journal of Applied Mathematics，2012:1－14.

[7] LI Y，HAN H S，YANG D D.A penalized－equation－based generalized Newton method for solving absolute－value linear complementarity problems [J].Journal of Mathematics，2014:1－10.

[8] WANG S，YANG X Q，TEO K L.Power penalty method for a linear complementarity problems arising from American option valuation[J].Journal of Optimization Theory and Applications，2006，129(2):227－254.

[9] WANG S，YANG X Q.Power penalty method for linear complementarity problems[J].Operations Research Letters，2008，36(2):211－214.

[10] WANG S，HUANG C S.A power penalty method for solving a nonlinear parabolic complementarity problem[J].Nonlinear Analysis，2008，69(4): 1125－1137.

[11] LI Y，HAN H S，LI Y M，et al.Convergence analysis of power penalty method for three dimensional linear complementarity problems[J].Intelligent Information Management Systems and Technologies，2009，5(3):191－198.

[12] 李園，楊丹丹，韓海山.線性互補(bǔ)問(wèn)題罰函數(shù)方法的收斂性分析[J].運(yùn)籌與管理，2012，21(5):129－134.

[13] 張賢達(dá).矩陣分析與應(yīng)用[M].北京:清華大學(xué)出版社，2004.

責(zé)任編輯:時(shí) 凌

Apenalized Method for Solving H－Matrix Absolute－value Linear Complementarity Problems

LI Yuan
(College of Mathematics，Inner Mongolia University for Nationalities，Tongliao 028043，China)

This paper considers a new class of linear complementarity problems，namely，the absolutevalue of the linear complementarity problems.We give a penalized method for solving such absolute－value inear complementarity problems by constructing a penalty equation which is equivalent to absolute－value inear complementarity problems and prove the global convergence when the matrix in absolute－value linear complementarity problems is a H－matrix.The numerical experiments show the effectiveness of this proposed algorithm.

operations research；absolute value linear complementarity problem；H－matrix；penalized method；convergence

O221.2

A

1008－8423(2017)01－0046－07

10.13501/j.cnki.42－1569/n.2017.03.011

2016－10－09.

內(nèi)蒙古自然科學(xué)基金項(xiàng)目(2011MSO114)；內(nèi)蒙古民族大學(xué)科學(xué)研究基金項(xiàng)目(NMDY15017).

李園(1985－)，男，碩士，主要從事變分不等式與互補(bǔ)問(wèn)題的研究.