基于线性互补理论求解绝对值方程

邓永坤，张萍，曹苏玉

（中国矿业大学理学院，江苏徐州 221000）

基于线性互补理论求解绝对值方程

邓永坤，张萍，曹苏玉

（中国矿业大学理学院，江苏徐州 221000）

针对绝对值方程Ax-|x|=b的求解问题.在假设1不是矩阵A的特征值时，绝对值方程可转化为线性互补问题，然后将线性互补问题转换为非光滑方程组的形式进行求解，进而求得原绝对值方程的解.

绝对值方程；线性互补问题；非光滑方程组

1 引言

考虑以下形式的绝对值方程

其中A∈Rn×n，b∈Rn，绝对值依分量而取.

绝对值方程首次由Rohn于1989年在文献[1]中研究区间线性方程组问题时提出，此后许多学者对其理论及数值求解进行了广泛的研究.Mangasarian等人在文献[2]中对绝对值方程（1）进行了详细的理论研究，证明了当1不是矩阵A的特征值时，绝对值方程（1）可以转换为线性互补问题，给出了方程有解、无解、唯一解、非负解及2n个解的充分条件等.文献[3]中，Mangasarian用广义牛顿法对绝对值方程（1）进行求解，并且证明了在适当条件下该算法具有线性收敛速度.文献[4]用一个光滑函数代替绝对值函数后给出了求解该绝对值方程的一个光滑牛顿法，并证明了该算法具有二次收敛性.文献[5-6]结合区间算法相关知识，给出了求解绝对值方程（1）的区间算法.文献[7-8]基于极大熵函数光滑化处理，给出了求解绝对值方程（1）的极大熵自适应微粒群混合算法及和声搜索算法.

当绝对值方程（1）中矩阵A是对称矩阵时，文献[9]结合优化技术给出了求该绝对值方程的一种迭代算法，紧接着文献[10]利用一种改进的Gauss-Seidel算法对其进行了求解，并且文章最后理论分析与数值实验均证明了此算法计算速度要明显快于文献[9]中的迭代算法.

目前绝对值方程的现有算法多是基于半光滑或光滑化处理技术下的有效算法，在计算过程中分别利用了绝对值方程的广义梯度及近似逼近.然而很少有文章通过将绝对值方程等价转化为其他相关问题进行求解，本文正是基于这一点同文献[11]的基本思想一致，首先将绝对值方程（1）等价转化为线性互补问题，然后利用互补理论的相关知识来求解.现阶段线性互补理论与算法已经十分成熟，由此可见此方法对于求解绝对值方程问题是十分有效的.

2 等价性转化

定义2.1[12]设M∈Rn×n是一n×n实矩阵，q∈Rn是一n维矢量，F:Rn→Rn为连续可微的向量值函数，且F=Mx+q，则线性互补问题（linear complementarity problems）记为LCP（F），是指：求x∈Rn满足

即xi≥0，Fi(x)≥0，xiFi(x)=0，i=1,2,…n.

定义2.2[12]函数ψ:R2→R1被称为“NCP函数”，如果对任意(a,b)T∈R2，ψ(a,b)=0当且仅当a≥0，b≥0，ab=0.

从事优化理论与算法研究的学者提出了许多不同的NCP函数，其中较为常用的有以下两个NCP函数：

1.Fischer-Burmeister函数：

2.min函数：

由定义2.1[12]及定义2.2[12]可知，对于任意的NCP函数ψ，LCP（F）可等价地转化为方程组：

引理[2]假设1不是矩阵A的特征值，则绝对值方程Ax-|| x=b可等价转化为以下线性互补问题

其中：M=(A+I)(A-I)-1，z=(A-I)x-b，q=((A+I)(A-I)-1-I)b，I为n×n的单位矩阵.

由式（5）、（6），绝对值方程（1）可以等价转化为以下方程组：

其中：F(z)=Mz+q，M、z、q、I如引理[2]所示.

（7）式中NCP函数ψ假如取Fischer-Burmeister函数（或min函数），则绝对值方程（1）可等价转化为以下非光滑方程组：

至此，绝对值方程（1）的求解问题转化为了非光滑方程组（8）的求解问题.通过求解，非光滑方程组（8）求得解z*，再求解线性方程组z*=(A-I)x-b，求得x*即原问题绝对值方程（1）的解.

接下来构造非光滑化方法、光滑化方法及优化方法三类较为有效且常用的方法对非光滑方程组（8）进行求解.

3 算法构造

3.1 非光滑化方法

非光滑化方法的基本思想是利用基于Clarke[13]意义下的广义Jacobian矩阵进行求解非光滑方程组（8），从而得到原互补问题及绝对值方程（1）的解.该方法始于20世纪90年代早期，随着众多学者对非光滑研究的不断深入，非光滑化方法得到了迅速的发展，并成为当时最优化研究中极为活跃的领域之一.

定义3.1[14]向量值函数H:Rn→Rn在点x∈Rn局部Lipschitz连续，即存在ε＞0，L＞0使

定义3.2[14]H为局部Lipschitz函数，称矩阵集

为H在x的B-次微分.称B-次微分的凸包为H在x的Clarke[13]意义下的广义Jacobian矩阵集，记为

基于Clarke[13]意义下的广义Jacobian矩阵集（11），非光滑方程组（8）可以利用文献[12]中De Luca，Fac⁃chinei和Kanzow[15]给出的半光滑牛顿法求解，并且该算法具有大范围和局部收敛性质；也可以利用文献[12]中给出的Yamashita-Fukushima算法进行求解，该算法搜索方向仅需求解一次扰动Newton方程即可，进一步减小了计算量.

在绝对值方程问题的求解中，文献[3]基于广义的Jacobian矩阵给出了求解绝对值方程（1）的广义牛顿法；文献[16]利用广义的Jacobian矩阵及广义牛顿法求解了绝对值方程（1）的一种广义形式Ax+B|x|=b，并且证明了该方程与二阶锥互补问题的等价性，进而延伸到求解二阶锥互补问题.可见非光滑化方法对于求解绝对值方程是十分有效的方法之一.

3.2 光滑化方法

光滑化方法的基本思想是对非光滑方程引进光滑逼近方程，然后利用光滑化方法求解光滑逼近方程，进而求得原非光滑方程的解.

定义3.3[12（光滑逼近函数）给定函数H:Rn→Rn，称光滑函数Hμ(·):Rn→Rn（μ＞0）为H的光滑逼近函数，如果对任意的x∈Rn，存在κ＞0，使得

如果κ不依赖于x，则称Hμ(·)为H的一致光滑逼近函数.

为求解非光滑方程组（8），文献[12]引进以下光滑函数：

1.Fischer-Burmeister函数的光滑函数：

2.min函数的光滑函数：

由光滑函数（13）、（14）、（15）可以得到非光滑方程组（8）的光滑逼近方程组：

至此，我们通过引进光滑函数构造光滑逼近方程将非光滑方程组（8）进行了光滑化处理，得到对应的光滑逼近方程组（16）、（17）、（18），然后就可以利用光滑函数的相关算法来求解（16）、（17）、（18），进而求得非光滑方程组（8）即绝对值方程（1）的解.

在绝对值方程问题的求解中，文献[11]利用了ψCHKS(μ,a,b)光滑化函数进行光滑逼近，然后利用非内部连续化算法进行求解取得了较好的研究成果，可见该光滑化方法对于求解绝对值方程问题也是十分有效的.此外还有许多学者的研究文献[4-5，7-8，17]直接对非光滑的绝对值|| x进行了光滑化处理，然后进行相关求解，也取得了非常好的成果.

3.3 优化方法

优化方法的基本思想是基于第一部分中绝对值方程（1）等价转化为非光滑方程组（8），然后将非光滑方程组（8）进一步转化为无约束优化问题，接着用无约束优化类方法对其进行求解，进而求得绝对值方程（1）的解.

非光滑方程组（8）可转化为求解以下无约束优化问题的全局最优解：

且此无约束优化问题的最优值为零.

现阶段对无约束优化理论及其算法的研究工作已经十分成熟，基于这一点，将绝对值方程（1）通过一系列转化为无约束优化问题（19）进行求解不失为一种十分有效的计算方法.

4 结束语

本文基于线性互补理论利用两种不同的NCP函数（Fischer-Burmeister函数或m in函数）将绝对值方程（1）等价转化为非光滑方程组，然后构造了求解该非光滑方程组的非光滑化方法、光滑化方法及优化方法，该三类方法也是大家较为熟知且常用的方法，不仅算法复杂度相当而且均可以间接求得绝对值方程（1）的解，可否利用其他更好的等价性理论对绝对值方程进行等价性转化及求解将是我们下一步要做的主要工作.

[1]Rohn J.Systems of linear intervalequations[J].Linear A lgebra and Its Application,1989,126(11):39-78.

[2]Mangasarian O L,Meyer R R.Absolute value equations[J].Linear Algebra and Its Application,2006,419(5):359-367.

[3]Mangasarian O L.A generalized Newtonmethod for absolute value equations[J].Optimization Letters,2009,3(1):101-108.

[4]Caccetta L,Qu B,Zhou G L.A globally and quadratically convergentmethod for absolute value equations[J].Computation Optim iza⁃tion Application,2011,48(1):45-58.

[5]王爱祥，王海军.绝对值方程的区间算法[J].贵州大学学报，2010，27（2）：7-10.

[6]Wang A X,Wang H J,Deng Y K.Interval algorithm for absolute value equations[J].Central European JournalMathematics,2011,9 (5):1171-1184.

[7]雍龙泉，孙培民，高凯.极大熵自适应微粒子群混合算法求解绝对值方程[J].计算机应用研究，2011，28（7）：2479-2481.

[8]雍龙泉.基于凝聚函数的和声搜索算法求解绝对值方程[J].计算机应用研究，2011，28（8）：2922-2926.

[9]Noor M A,Iqbal J,Al-Said E.On an iterative method for solving absolute value equations[J].Optimization Letters,2012,6(5): 1027-1033.

[10]NoorM A,Iqbal J,KhattriS,etal.A new iterativemethod for solving absolute value equations[J].International Journalof the Phys⁃ical Sciences,2011,6(7):1793-1797.

[11]封京梅.求解一类绝对值方程组的非内部连续化算法[J].陕西科技大学学报，2011，29（2）：165-169.

[12]韩继业，修乃华，戚厚铎.非线性互补理论与算法[M].上海：上海科学技术出版社，2006.

[13]Clarke FH.Optimization and Nonsmooth Analysis[M].Philadelphia:SIAM,1990.

[14]白梅花，翟丽丽，章树玲，等.非线性互补问题转化为无约束优化问题的方法[J].阴山学刊，2008，22（2）：5-7.

[15]De Luca T,Facchinei F,Kanzow C.A semismooth equation approach to the solution of nonlinear complementarity problems[J].Math Programming,1996,75:407.

[16]Hu S L,Huang Z H,Zhang Q.A generalized Newton method for absolute value equations associated with second order cones[J]. ComputationalOptimization and Applications,2011,235:1490-1501.

[17]邓永坤，张萍.绝对值方程的光滑牛顿算法[J].黑龙江科技学院学报，2011，26（6）：499-502.

Solving Absolute Value Equations Based on Linear Complementarity Theory

DENG Yong-kun,ZHANG Ping,CAO Su-yu
(School of Sciences,China University of Mining and Technology,Xuzhou 221000,China)

Aimed at the solution to the absolute value equations,the absolute value equations can be transformed into linear complementarity problems under the condition that one is not an eigenvalue of,and then the linear complementarity problems can be reformulated as a nonsmooth system of equations.The authors of this paper find the solution to absolute value equations by solving the nonsmooth system of equations.

absolute value equation;linear complementarity problems;nonsmooth system of equations

O24

A

1008-2794（2012）08-0008-05

2012-07-07

邓永坤（1988—），男，山东青州人，中国矿业大学理学院2010级硕士研究生，研究方向：计算数学.