鄧永坤，張萍，曹蘇玉

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

基于線(xiàn)性互補(bǔ)理論求解絕對(duì)值方程

鄧永坤，張萍，曹蘇玉

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

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

絕對(duì)值方程；線(xiàn)性互補(bǔ)問(wèn)題；非光滑方程組

1 引言

考慮以下形式的絕對(duì)值方程

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

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

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

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

2 等價(jià)性轉(zhuǎn)化

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

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

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

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

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

2.min函數(shù)：

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

引理[2]假設(shè)1不是矩陣A的特征值，則絕對(duì)值方程Ax-|| x=b可等價(jià)轉(zhuǎn)化為以下線(xiàn)性互補(bǔ)問(wè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），絕對(duì)值方程（1）可以等價(jià)轉(zhuǎn)化為以下方程組：

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

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

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

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

3 算法構(gòu)造

3.1 非光滑化方法

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

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

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

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

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

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

3.2 光滑化方法

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

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

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

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

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

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

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

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

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

3.3 優(yōu)化方法

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

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

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

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

4 結(jié)束語(yǔ)

本文基于線(xiàn)性互補(bǔ)理論利用兩種不同的NCP函數(shù)（Fischer-Burmeister函數(shù)或m in函數(shù)）將絕對(duì)值方程（1）等價(jià)轉(zhuǎn)化為非光滑方程組，然后構(gòu)造了求解該非光滑方程組的非光滑化方法、光滑化方法及優(yōu)化方法，該三類(lèi)方法也是大家較為熟知且常用的方法，不僅算法復(fù)雜度相當(dāng)而且均可以間接求得絕對(duì)值方程（1）的解，可否利用其他更好的等價(jià)性理論對(duì)絕對(duì)值方程進(jìn)行等價(jià)性轉(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]王愛(ài)祥，王海軍.絕對(duì)值方程的區(qū)間算法[J].貴州大學(xué)學(xué)報(bào)，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)微粒子群混合算法求解絕對(duì)值方程[J].計(jì)算機(jī)應(yīng)用研究，2011，28（7）：2479-2481.

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

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

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

[14]白梅花，翟麗麗，章樹(shù)玲，等.非線(xiàn)性互補(bǔ)問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題的方法[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]鄧永坤，張萍.絕對(duì)值方程的光滑牛頓算法[J].黑龍江科技學(xué)院學(xué)報(bào)，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—），男，山東青州人，中國(guó)礦業(yè)大學(xué)理學(xué)院2010級(jí)碩士研究生，研究方向：計(jì)算數(shù)學(xué).