鄧永坤，張萍，曹蘇玉

（中國礦業(yè)大學(xué)理學(xué)院，江蘇徐州 221000）

基于線性互補理論求解絕對值方程

鄧永坤，張萍，曹蘇玉

（中國礦業(yè)大學(xué)理學(xué)院，江蘇徐州 221000）

針對絕對值方程Ax-|x|=b的求解問題.在假設(shè)1不是矩陣A的特征值時，絕對值方程可轉(zhuǎn)化為線性互補問題，然后將線性互補問題轉(zhuǎn)換為非光滑方程組的形式進行求解，進而求得原絕對值方程的解.

絕對值方程；線性互補問題；非光滑方程組

1 引言

考慮以下形式的絕對值方程

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

絕對值方程首次由Rohn于1989年在文獻[1]中研究區(qū)間線性方程組問題時提出，此后許多學(xué)者對其理論及數(shù)值求解進行了廣泛的研究.Mangasarian等人在文獻[2]中對絕對值方程（1）進行了詳細(xì)的理論研究，證明了當(dāng)1不是矩陣A的特征值時，絕對值方程（1）可以轉(zhuǎn)換為線性互補問題，給出了方程有解、無解、唯一解、非負(fù)解及2n個解的充分條件等.文獻[3]中，Mangasarian用廣義牛頓法對絕對值方程（1）進行求解，并且證明了在適當(dāng)條件下該算法具有線性收斂速度.文獻[4]用一個光滑函數(shù)代替絕對值函數(shù)后給出了求解該絕對值方程的一個光滑牛頓法，并證明了該算法具有二次收斂性.文獻[5-6]結(jié)合區(qū)間算法相關(guān)知識，給出了求解絕對值方程（1）的區(qū)間算法.文獻[7-8]基于極大熵函數(shù)光滑化處理，給出了求解絕對值方程（1）的極大熵自適應(yīng)微粒群混合算法及和聲搜索算法.

當(dāng)絕對值方程（1）中矩陣A是對稱矩陣時，文獻[9]結(jié)合優(yōu)化技術(shù)給出了求該絕對值方程的一種迭代算法，緊接著文獻[10]利用一種改進的Gauss-Seidel算法對其進行了求解，并且文章最后理論分析與數(shù)值實驗均證明了此算法計算速度要明顯快于文獻[9]中的迭代算法.

目前絕對值方程的現(xiàn)有算法多是基于半光滑或光滑化處理技術(shù)下的有效算法，在計算過程中分別利用了絕對值方程的廣義梯度及近似逼近.然而很少有文章通過將絕對值方程等價轉(zhuǎn)化為其他相關(guān)問題進行求解，本文正是基于這一點同文獻[11]的基本思想一致，首先將絕對值方程（1）等價轉(zhuǎn)化為線性互補問題，然后利用互補理論的相關(guān)知識來求解.現(xiàn)階段線性互補理論與算法已經(jīng)十分成熟，由此可見此方法對于求解絕對值方程問題是十分有效的.

2 等價性轉(zhuǎn)化

定義2.1[12]設(shè)M∈Rn×n是一n×n實矩陣，q∈Rn是一n維矢量，F(xiàn):Rn→Rn為連續(xù)可微的向量值函數(shù)，且F=Mx+q，則線性互補問題（linear complementarity problems）記為LCP（F），是指：求x∈Rn滿足

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

定義2.2[12]函數(shù)ψ:R2→R1被稱為“NCP函數(shù)”，如果對任意(a,b)T∈R2，ψ(a,b)=0當(dāng)且僅當(dāng)a≥0，b≥0，ab=0.

從事優(yōu)化理論與算法研究的學(xué)者提出了許多不同的NCP函數(shù)，其中較為常用的有以下兩個NCP函數(shù)：

1.Fischer-Burmeister函數(shù)：

2.min函數(shù)：

由定義2.1[12]及定義2.2[12]可知，對于任意的NCP函數(shù)ψ，LCP（F）可等價地轉(zhuǎn)化為方程組：

引理[2]假設(shè)1不是矩陣A的特征值，則絕對值方程Ax-|| x=b可等價轉(zhuǎn)化為以下線性互補問題

其中：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）可以等價轉(zhuǎn)化為以下方程組：

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

（7）式中NCP函數(shù)ψ假如取Fischer-Burmeister函數(shù)（或min函數(shù)），則絕對值方程（1）可等價轉(zhuǎn)化為以下非光滑方程組：

至此，絕對值方程（1）的求解問題轉(zhuǎn)化為了非光滑方程組（8）的求解問題.通過求解，非光滑方程組（8）求得解z*，再求解線性方程組z*=(A-I)x-b，求得x*即原問題絕對值方程（1）的解.

接下來構(gòu)造非光滑化方法、光滑化方法及優(yōu)化方法三類較為有效且常用的方法對非光滑方程組（8）進行求解.

3 算法構(gòu)造

3.1 非光滑化方法

非光滑化方法的基本思想是利用基于Clarke[13]意義下的廣義Jacobian矩陣進行求解非光滑方程組（8），從而得到原互補問題及絕對值方程（1）的解.該方法始于20世紀(jì)90年代早期，隨著眾多學(xué)者對非光滑研究的不斷深入，非光滑化方法得到了迅速的發(fā)展，并成為當(dāng)時最優(yōu)化研究中極為活躍的領(lǐng)域之一.

定義3.1[14]向量值函數(shù)H:Rn→Rn在點x∈Rn局部Lipschitz連續(xù)，即存在ε＞0，L＞0使

定義3.2[14]H為局部Lipschitz函數(shù)，稱矩陣集

為H在x的B-次微分.稱B-次微分的凸包為H在x的Clarke[13]意義下的廣義Jacobian矩陣集，記為

基于Clarke[13]意義下的廣義Jacobian矩陣集（11），非光滑方程組（8）可以利用文獻[12]中De Luca，F(xiàn)ac?chinei和Kanzow[15]給出的半光滑牛頓法求解，并且該算法具有大范圍和局部收斂性質(zhì)；也可以利用文獻[12]中給出的Yamashita-Fukushima算法進行求解，該算法搜索方向僅需求解一次擾動Newton方程即可，進一步減小了計算量.

在絕對值方程問題的求解中，文獻[3]基于廣義的Jacobian矩陣給出了求解絕對值方程（1）的廣義牛頓法；文獻[16]利用廣義的Jacobian矩陣及廣義牛頓法求解了絕對值方程（1）的一種廣義形式Ax+B|x|=b，并且證明了該方程與二階錐互補問題的等價性，進而延伸到求解二階錐互補問題.可見非光滑化方法對于求解絕對值方程是十分有效的方法之一.

3.2 光滑化方法

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

定義3.3[12（光滑逼近函數(shù)）給定函數(shù)H:Rn→Rn，稱光滑函數(shù)Hμ(·):Rn→Rn（μ＞0）為H的光滑逼近函數(shù)，如果對任意的x∈Rn，存在κ＞0，使得

如果κ不依賴于x，則稱Hμ(·)為H的一致光滑逼近函數(shù).

為求解非光滑方程組（8），文獻[12]引進以下光滑函數(shù)：

1.Fischer-Burmeister函數(shù)的光滑函數(shù)：

2.min函數(shù)的光滑函數(shù)：

由光滑函數(shù)（13）、（14）、（15）可以得到非光滑方程組（8）的光滑逼近方程組：

至此，我們通過引進光滑函數(shù)構(gòu)造光滑逼近方程將非光滑方程組（8）進行了光滑化處理，得到對應(yīng)的光滑逼近方程組（16）、（17）、（18），然后就可以利用光滑函數(shù)的相關(guān)算法來求解（16）、（17）、（18），進而求得非光滑方程組（8）即絕對值方程（1）的解.

在絕對值方程問題的求解中，文獻[11]利用了ψCHKS(μ,a,b)光滑化函數(shù)進行光滑逼近，然后利用非內(nèi)部連續(xù)化算法進行求解取得了較好的研究成果，可見該光滑化方法對于求解絕對值方程問題也是十分有效的.此外還有許多學(xué)者的研究文獻[4-5，7-8，17]直接對非光滑的絕對值|| x進行了光滑化處理，然后進行相關(guān)求解，也取得了非常好的成果.

3.3 優(yōu)化方法

優(yōu)化方法的基本思想是基于第一部分中絕對值方程（1）等價轉(zhuǎn)化為非光滑方程組（8），然后將非光滑方程組（8）進一步轉(zhuǎn)化為無約束優(yōu)化問題，接著用無約束優(yōu)化類方法對其進行求解，進而求得絕對值方程（1）的解.

非光滑方程組（8）可轉(zhuǎn)化為求解以下無約束優(yōu)化問題的全局最優(yōu)解：

且此無約束優(yōu)化問題的最優(yōu)值為零.

現(xiàn)階段對無約束優(yōu)化理論及其算法的研究工作已經(jīng)十分成熟，基于這一點，將絕對值方程（1）通過一系列轉(zhuǎn)化為無約束優(yōu)化問題（19）進行求解不失為一種十分有效的計算方法.

4 結(jié)束語

本文基于線性互補理論利用兩種不同的NCP函數(shù)（Fischer-Burmeister函數(shù)或m in函數(shù)）將絕對值方程（1）等價轉(zhuǎn)化為非光滑方程組，然后構(gòu)造了求解該非光滑方程組的非光滑化方法、光滑化方法及優(yōu)化方法，該三類方法也是大家較為熟知且常用的方法，不僅算法復(fù)雜度相當(dāng)而且均可以間接求得絕對值方程（1）的解，可否利用其他更好的等價性理論對絕對值方程進行等價性轉(zhuǎn)化及求解將是我們下一步要做的主要工作.

[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]王愛祥，王海軍.絕對值方程的區(qū)間算法[J].貴州大學(xué)學(xué)報，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]雍龍泉，孫培民，高凱.極大熵自適應(yīng)微粒子群混合算法求解絕對值方程[J].計算機應(yīng)用研究，2011，28（7）：2479-2481.

[8]雍龍泉.基于凝聚函數(shù)的和聲搜索算法求解絕對值方程[J].計算機應(yīng)用研究，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]封京梅.求解一類絕對值方程組的非內(nèi)部連續(xù)化算法[J].陜西科技大學(xué)學(xué)報，2011，29（2）：165-169.

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

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

[14]白梅花，翟麗麗，章樹玲，等.非線性互補問題轉(zhuǎn)化為無約束優(yōu)化問題的方法[J].陰山學(xué)刊，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].黑龍江科技學(xué)院學(xué)報，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—），男，山東青州人，中國礦業(yè)大學(xué)理學(xué)院2010級碩士研究生，研究方向：計算數(shù)學(xué).