一个求解绝对值线性互补问题的罚函数方法

李 园

( 内蒙古民族大学 数学学院，内蒙古 通辽028043)

线性互补问题(简记作LCP(A，b))定义为，求x=(x1，x2，…，xn)∈Rn，使得:

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

线性互补问题是运筹学与计算数学的一个交叉研究领域，已经广泛应用于力学、交通、经济、金融、控制等领域中出现的许多数学模型，例如障碍和自由边界问题、供应链问题、交通分配问题、经济均衡问题、非均衡博弈论等，这使得线性互补问题成为数学规划中的一个十分热门的研究课题．许多学者对线性互补问题的求解进行了深入的研究，提出了许多算法［1-2］，例如:投影法、牛顿法、松弛法、内点法、非光滑方程法、预条件迭代法等．随着对线性互补问题这一领域研究的不断深入，线性互补问题的推广形式也非常之多．

2012 年，Noor 等［3］定义了LCP(A，b)的一种推广形式，即绝对值线性互补问题(简记作ALCP(A，b))，其定义如下:

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

求x∈K，使得∀y∈K，满足:

其中式(3)称为绝对值变分不等式问题，该不等式由Noor［4］于1975 年引入．

当K=Rn时，绝对值变分不等式问题(3)等价于如下绝对值方程组:

关于方程组(4)，近年已经提出了许多求解的方法［5-9］．Mangasarian［5-6］证明了方程组(4)等价于LCP(A，b)，并且用互补性理论对方程组(4)进行了求解．

本文主要研究求解ALCP(A，b)的罚函数方法，构造如下关于ALCP(A，b)的罚函数方法．求xλ∈Rn，使得:

其中λ＞1 是惩罚因子，k＞0 是参数，［u］+=max{u，0}，并且，有

在LCP(A，b)的罚函数方法研究方面，Glowinski［10］讨论了Hilbert 空间中椭圆型变分不等式罚函数法，在适当的假设条件下证明了罚函数方法的收敛性，以及作为Hilbert 空间的特例，Rn(n有限)空间中变分不等式在矩阵对称正定的情况下罚函数法的收敛性问题．Yang［11-13］在LCP(A，b)中的矩阵A正定，A的主对角线元素大于零，其余元素均小于等于零的假设条件下，证明了随着惩罚因子趋于无穷大时罚函数方法的解收敛到LCP(A，b)的解，且收敛速率为指数次．Li［14］将LCP(A，b)中矩阵A的正定条件放宽，证明了当A是P-矩阵时的罚函数方法的收敛性，且收敛速率也是指数次．本文将求解LCP(A，b)的罚函数方法应用到ALCP(A，b)的求解，并且在适当的条件下证明罚函数方法的收敛性．

1 预备知识

为方便起见，本文给出如下记号．设Rn表示n维欧式空间为n×n实矩阵． x表示向量x的绝对值，即表示Rn中的lp-范数，即当p=2时，lp-范数变成l2-范数，也称为欧式范数，即

定义1 设A=(aij)∈Rn×n是一个矩阵，则称:

i)A为正定的，如果存在常数γ＞0，使得∀x∈Rn，都有xTAx≥γ‖x‖2成立;

ii)A为有界的，如果存在常数β＞0，使得∀y∈Rn，都有‖Ay‖2≤β‖y‖2成立．

关于矩阵的F-范数‖·‖F与向量的欧式范数‖·‖2的相容性，有如下结论:

引理1 设A∈Rm×n，x∈Rn，则有:‖Ax‖2≤‖A‖F‖x‖2，其中

引理2(Hölder 不等式)［5］设x，y∈Rn，则

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

引理3［6］设K是Rn中的闭凸集，则存在常数ρ＞0，x∈K是ALCP(A，b)的解当且仅当x∈K是如下不动点问题，的解，其中PK是Rn到闭凸集K的投影．

引理4［6］设矩阵A为正定矩阵且有界．如果则存在唯一的解x∈K，使得:

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

2 主要结论

本文对矩阵A作如下假设:A1:A∈Rn×n是正定矩阵且有界:矩阵A的元素满足aii＞0，aij≤0，i，j=1，2，…，n，i≠j．

根据假设A1、A2 以及引理3～4，可知ALCP(A，b)有唯一解．根据上述假设，可以得到如下结论．

定理1 设xλ是罚方程(5)的解，则存在一个与n，xλ和λ 均无关的正数C，使得:

其中λ 和k是罚方程(5)中定义的参数代表lp-范数．

证明 用［xλ］+分别左乘罚方程(5)两端，得:

当m=0 时，［xλ］+=0，式(6)和式(7)显然成立．下面考虑当m≥1 的情形，设xλ=(uT1，uT2)T，其中u2∈，将矩阵A分解成，其中则

式(8)成为:

因为A为正定矩阵，u1≥0，u2≤0，γ＞1 以及，所以有:

即:

于是:

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

因此式(6)得证．

下面证明式(7)．根据有限维空间Rn中任意两种范数的等价性，则存在常数a0＞0，使得:

所以式(9)左端:

所以:

当惩罚因子λ 充分大时，有:

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

定理2 设x*∈Rn和xλ∈Rn分别是ALCP(A，b)和罚方程(5)的解，则存在一个与n，x，xλ和λ 均无关的常数C＞0，使得其中λ 和k是罚方程(5)中定义的参数．

于是:

其中:

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

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

又由式(12)知:

所以:

而:

所以:

再根据矩阵A的正定性，

所以:

对式(17)应用Cauchy-schwarz 不等式和引理1，得:

再结合式(16)，得:

证毕．

进一步，还可以得到如下定理:

定理3 设x*∈Rn和xλ∈Rn分别是ALCP(A，b)和罚方程(5)的解，则存在一个与n，x，xλ和λ 均无关的常数C＞0，使得:

其中λ 和k是罚方程(5)中定义的参数．

证明 由定理2 和有限维空间中任何两种不同范数之间的等价性即可证明．

3 数值举例

4 总结

本文通过构造罚方程的思想提出一个求解绝对值线性互补问题的罚函数方法，证明了当惩罚因子趋于正无穷时，所提出了罚函数方法的解收敛于绝对值线性互补问题的解，并且收敛速率是指数次，并且通过数值算例证明了该方法的有效性．

［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］ 山晓东，吴梅花，杨丹丹．绝对值互补问题的一种收敛算法［J］．湖北民族学院学报:自然科学版，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．