一個(gè)求解絕對(duì)值線性互補(bǔ)問題的罰函數(shù)方法

李 園

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

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

其中A∈Rn×n，b∈Rn．

線性互補(bǔ)問題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)的一個(gè)交叉研究領(lǐng)域，已經(jīng)廣泛應(yīng)用于力學(xué)、交通、經(jīng)濟(jì)、金融、控制等領(lǐng)域中出現(xiàn)的許多數(shù)學(xué)模型，例如障礙和自由邊界問題、供應(yīng)鏈問題、交通分配問題、經(jīng)濟(jì)均衡問題、非均衡博弈論等，這使得線性互補(bǔ)問題成為數(shù)學(xué)規(guī)劃中的一個(gè)十分熱門的研究課題．許多學(xué)者對(duì)線性互補(bǔ)問題的求解進(jìn)行了深入的研究，提出了許多算法［1-2］，例如:投影法、牛頓法、松弛法、內(nèi)點(diǎn)法、非光滑方程法、預(yù)條件迭代法等．隨著對(duì)線性互補(bǔ)問題這一領(lǐng)域研究的不斷深入，線性互補(bǔ)問題的推廣形式也非常之多．

2012 年，Noor 等［3］定義了LCP(A，b)的一種推廣形式，即絕對(duì)值線性互補(bǔ)問題(簡(jiǎn)記作ALCP(A，b))，其定義如下:

求x=(x1，x2，…，xn)∈Rn，使得:

求x∈K，使得?y∈K，滿足:

其中式(3)稱為絕對(duì)值變分不等式問題，該不等式由Noor［4］于1975 年引入．

當(dāng)K=Rn時(shí)，絕對(duì)值變分不等式問題(3)等價(jià)于如下絕對(duì)值方程組:

關(guān)于方程組(4)，近年已經(jīng)提出了許多求解的方法［5-9］．Mangasarian［5-6］證明了方程組(4)等價(jià)于LCP(A，b)，并且用互補(bǔ)性理論對(duì)方程組(4)進(jìn)行了求解．

本文主要研究求解ALCP(A，b)的罰函數(shù)方法，構(gòu)造如下關(guān)于ALCP(A，b)的罰函數(shù)方法．求xλ∈Rn，使得:

其中λ＞1 是懲罰因子，k＞0 是參數(shù)，［u］+=max{u，0}，并且，有

在LCP(A，b)的罰函數(shù)方法研究方面，Glowinski［10］討論了Hilbert 空間中橢圓型變分不等式罰函數(shù)法，在適當(dāng)?shù)募僭O(shè)條件下證明了罰函數(shù)方法的收斂性，以及作為Hilbert 空間的特例，Rn(n有限)空間中變分不等式在矩陣對(duì)稱正定的情況下罰函數(shù)法的收斂性問題．Yang［11-13］在LCP(A，b)中的矩陣A正定，A的主對(duì)角線元素大于零，其余元素均小于等于零的假設(shè)條件下，證明了隨著懲罰因子趨于無窮大時(shí)罰函數(shù)方法的解收斂到LCP(A，b)的解，且收斂速率為指數(shù)次．Li［14］將LCP(A，b)中矩陣A的正定條件放寬，證明了當(dāng)A是P-矩陣時(shí)的罰函數(shù)方法的收斂性，且收斂速率也是指數(shù)次．本文將求解LCP(A，b)的罰函數(shù)方法應(yīng)用到ALCP(A，b)的求解，并且在適當(dāng)?shù)臈l件下證明罰函數(shù)方法的收斂性．

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

為方便起見，本文給出如下記號(hào)．設(shè)Rn表示n維歐式空間為n×n實(shí)矩陣． x表示向量x的絕對(duì)值，即表示Rn中的lp-范數(shù)，即當(dāng)p=2時(shí)，lp-范數(shù)變成l2-范數(shù)，也稱為歐式范數(shù)，即

定義1 設(shè)A=(aij)∈Rn×n是一個(gè)矩陣，則稱:

i)A為正定的，如果存在常數(shù)γ＞0，使得?x∈Rn，都有xTAx≥γ‖x‖2成立;

ii)A為有界的，如果存在常數(shù)β＞0，使得?y∈Rn，都有‖Ay‖2≤β‖y‖2成立．

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

引理1 設(shè)A∈Rm×n，x∈Rn，則有:‖Ax‖2≤‖A‖F(xiàn)‖x‖2，其中

引理2(H?lder 不等式)［5］設(shè)x，y∈Rn，則

其中p和q均大于1 且滿足

引理3［6］設(shè)K是Rn中的閉凸集，則存在常數(shù)ρ＞0，x∈K是ALCP(A，b)的解當(dāng)且僅當(dāng)x∈K是如下不動(dòng)點(diǎn)問題，的解，其中PK是Rn到閉凸集K的投影．

引理4［6］設(shè)矩陣A為正定矩陣且有界．如果則存在唯一的解x∈K，使得:

成立，其中K是Rn中的閉凸集．

2 主要結(jié)論

本文對(duì)矩陣A作如下假設(shè):A1:A∈Rn×n是正定矩陣且有界:矩陣A的元素滿足aii＞0，aij≤0，i，j=1，2，…，n，i≠j．

根據(jù)假設(shè)A1、A2 以及引理3～4，可知ALCP(A，b)有唯一解．根據(jù)上述假設(shè)，可以得到如下結(jié)論．

定理1 設(shè)xλ是罰方程(5)的解，則存在一個(gè)與n，xλ和λ 均無關(guān)的正數(shù)C，使得:

其中λ 和k是罰方程(5)中定義的參數(shù)代表lp-范數(shù)．

證明 用［xλ］+分別左乘罰方程(5)兩端，得:

當(dāng)m=0 時(shí)，［xλ］+=0，式(6)和式(7)顯然成立．下面考慮當(dāng)m≥1 的情形，設(shè)xλ=(uT1，uT2)T，其中u2∈，將矩陣A分解成，其中則

式(8)成為:

因?yàn)锳為正定矩陣，u1≥0，u2≤0，γ＞1 以及，所以有:

即:

于是:

其中q=k+1，滿足，因此，于是:

因此式(6)得證．

下面證明式(7)．根據(jù)有限維空間Rn中任意兩種范數(shù)的等價(jià)性，則存在常數(shù)a0＞0，使得:

所以式(9)左端:

所以:

當(dāng)懲罰因子λ 充分大時(shí)，有:

由定理1，可以得到下面的收斂性定理:

定理2 設(shè)x*∈Rn和xλ∈Rn分別是ALCP(A，b)和罰方程(5)的解，則存在一個(gè)與n，x，xλ和λ 均無關(guān)的常數(shù)C＞0，使得其中λ 和k是罰方程(5)中定義的參數(shù)．

于是:

其中:

因此ω∈K，在式(3)中令y=ω 后有:

將式(13)和式(14)相加后得:

又由式(12)知:

所以:

而:

所以:

再根據(jù)矩陣A的正定性，

所以:

對(duì)式(17)應(yīng)用Cauchy-schwarz 不等式和引理1，得:

再結(jié)合式(16)，得:

證畢．

進(jìn)一步，還可以得到如下定理:

定理3 設(shè)x*∈Rn和xλ∈Rn分別是ALCP(A，b)和罰方程(5)的解，則存在一個(gè)與n，x，xλ和λ 均無關(guān)的常數(shù)C＞0，使得:

其中λ 和k是罰方程(5)中定義的參數(shù)．

證明 由定理2 和有限維空間中任何兩種不同范數(shù)之間的等價(jià)性即可證明．

3 數(shù)值舉例

4 總結(jié)

本文通過構(gòu)造罰方程的思想提出一個(gè)求解絕對(duì)值線性互補(bǔ)問題的罰函數(shù)方法，證明了當(dāng)懲罰因子趨于正無窮時(shí)，所提出了罰函數(shù)方法的解收斂于絕對(duì)值線性互補(bǔ)問題的解，并且收斂速率是指數(shù)次，并且通過數(shù)值算例證明了該方法的有效性．

［1］ Cottle R W，Pang J S，Stone R E．The linear complementarity problems［M］．New York:Academic Press，1992．

［2］ Facchinei F，Pang J S．Finite－dimensional variational inequalities and complementarity problems［M］．Vol．I ＆ II．New York:Springer，2003．

［3］ Noor M A，Iqbal J，Noor K I，et al．Genaralied AOR method for solving absolute complementarity problem［J］．Journal of Applied Mathematics，2012，2012:1－14．

［4］ Noor M A．On variational inequalities［D］．London:Brunel University，1975．

［5］ Mangasarian O L．Absolute value programming［J］．Computational Optimization and Applications，2007，36(1):43－53．

［6］ Mangasarian O L．Absolute value equations［J］．Linear Algebra and Its Applications，2006，419(2/3):359－367．

［7］ Mangasarian O L．Absolute value equation solution via concave minimization［J］．Optimization Letters，2007，1(1):3－8．

［8］ Mangasarian O L．A generalized Newton method for absolute value equation［J］．Optimization Letters，2009，3(1):101－108．

［9］ 山曉東，吳梅花，楊丹丹．絕對(duì)值互補(bǔ)問題的一種收斂算法［J］．湖北民族學(xué)院學(xué)報(bào):自然科學(xué)版，2014，32(3):300－301．

［10］ Glowinski R．Numerical methods for nonlinear variational problems［M］．New York:Springer－Verlag，1984．

［11］ 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:227－254．

［12］ Wang S，Yang X Q．Power penalty method for linear complementarity problems［J］．Operations Research Letters，2008，36(2):211－214．

［13］ Wang S，Huang C S．A power penalty method for solving a nonlinear parabolic complementarity problem［J］．Nonlinear Analysis，2008，69(4):1125－1137．

［14］ 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．