王愛祥

(常州工學院機械與車輛工程學院,江蘇常州213032)

多解絕對值方程的對分搜索法

王愛祥

(常州工學院機械與車輛工程學院,江蘇常州213032)

絕對值方程可以作為研究線性規(guī)劃、二次規(guī)劃等優(yōu)化問題的統(tǒng)一框架。針對絕對值方程具有多解的情形，提出一個基于區(qū)間數(shù)學的求解算法。在一個較大的范圍內(nèi)，不斷將區(qū)間對分和刪除，搜索到絕對值方程的每一個解。最后，數(shù)值算例也驗證了算法的有效性。

絕對值方程；多解；區(qū)間算法；Krawczyk算子

0 引言

考慮如下形式的絕對值方程：

(1)

絕對值方程(1)形式簡單，為研究線性規(guī)劃、二次規(guī)劃等眾多優(yōu)化問題提供了一個統(tǒng)一框架，引起了不少學者的研究興趣。目前研究重點主要集中在絕對值方程(1)的性質(zhì)、求解算法兩方面。

在性質(zhì)研究方面，Jiri Rohn在文獻[1—2]中研究了絕對值方程(1)和區(qū)間線性方程組的關系，給出了絕對值方程的分類定理，證明了其等價于線性互補問題。Mangasarian在文獻[3]中指出絕對值方程等價于雙線性規(guī)劃、廣義線性互補問題，在一定條件下，絕對值方程可以轉(zhuǎn)化為線性互補問題，從而得出了絕對值方程有解、無解、唯一解、非負解及多解的充分條件。文獻[4]進一步研究了絕對值方程和線性互補問題的轉(zhuǎn)化方法，研究了絕對值方程和混合整數(shù)規(guī)劃之間的關系。文獻[5—7]也研究了絕對值方程解的存在性條件。

在求解算法方面，Mangasarian在文獻[3]中，證明了絕對值方程(1)是NP-hard問題，通過用有限步的逐次線性化方法求解絕對值方程(1)等價的凹極小化形式。文獻[8]提出了求解絕對值方程(1)的廣義牛頓法。文獻[9]給出了求解絕對值方程(1)的二次收斂的牛頓法。王海軍、王愛祥等在文獻[10—11]中給出了求解絕對值方程(1)的區(qū)間算法和區(qū)間膨脹算法。雍龍泉等利用智能算法的優(yōu)點，在文獻[12—14]中分別給出了求解絕對值方程(1)的粒子群算法、和聲搜索算法、差分進化算法等，取得較好的數(shù)值效果。

然而，絕對值方程(1)還存在多解或無解的情形。此時，上述文獻中的牛頓型算法將無法實現(xiàn)，而智能算法，有時收斂性又無法保證?；诖?，本文利用區(qū)間數(shù)學的工具，提出了絕對值方程(1)具有多解時的求解算法，無解時也可以判斷。該算法具有很好的數(shù)值穩(wěn)定性。理論分析和數(shù)值算例都驗證了算法的有效性。

1 區(qū)間數(shù)學

對于[x]，[y]∈I(Rn)，我們依分量也可定義中點、寬度、絕對值等概念。

定義區(qū)間運算：

[x]∩[y]=([x]i,∩[y]i)

以及

[x]?[y]?[x]i?[y]i，i=1,2,…,n

設區(qū)間函數(shù)F:I(Rn)→I(R)和函數(shù)f:Rn→R，對任意的xi∈[x]i，i=1,2,…,n，

F([x1,x1],[x2,x2]，…,[xn,xn])=f(x1,x2,…,xn)成立,

則稱F為f的區(qū)間擴展。有關區(qū)間數(shù)學的其他概念和詳細內(nèi)容，參閱文獻[15]。

2 Krawczyk算子

F([x])=(A-G([x]))[x]-b，

(2)

式中：G([x])=diag(G([x])1；G([x])2,…,G([x])n)；

于是F′([x])=A-G([x])。

定義Krawczyk算子為K(y,[x])=y-f(y)+(E-YF′([x]))([x]-y)，?y∈[x]，其中E為單位矩陣。

定理1 設x*為絕對值方程(1)的解，且x*∈[x]，則對于任意y∈[x]，x*∈K(y,[x])。

證明 由x*為絕對值方程(1)的解知，f(x*)=0，x*=g(x*)。

對于任意y∈[x]，i∈(1,2,…,n)，

故，g(x*)∈g(y)+(E-Y(A-G([x])))([x-y])成立，即x*=g(x*)∈K(y,[x])。證畢。

根據(jù)定理1，若絕對值方程(1)的解x*∈[x]，則[x]∩K(y,[x])≠?。我們可得定理2。

定理2 若[x]∩K(y,[x])=?，?y∈[x]，則絕對值方程(1)在[x]中無解。

定理3 若存在K(y,[x])?[x]，?y∈[x]，則絕對值方程(1)在[x]中有解。

證明 對于任意x∈[x]，成立g(x)∈K(y,[x])?[x]。即連續(xù)映射g將[x]映射到自身。由于[x]為有界閉凸集，則由Browuer不動點原理得，連續(xù)映射g在[x]中有不動點存在，即絕對值方程(1)在[x]中有解。證畢。

由此，我們構(gòu)造Krawczyk區(qū)間迭代法

(3)

式中：k=0,1,2,…；yk∈[x]；E為單位矩陣。

定理4 區(qū)間迭代(3)中，若對某個y∈[x]，K(y,[x])?[x]成立，且

wid(K(y,[x]))

對于任意x0∈[x]為初值，通過點迭代

xk+1=xk-Yf(xk)，k=0,1,2,…,

(4)

得到收斂到x*的序列{xk}。

證明 對于某個給定的y和[x]，記K=K(y,[x])和R=E-Y(A-G([x]))，顯然存在0≤β<1，滿足wid(K)≤β·wid([x])。

記絕對值方程(1)在[x]中的解集為Z。由定理3知，Z非空。構(gòu)造區(qū)間迭代算法

下面用歸納法證明Z?[x]k， wid([x](k))≤βkwid([x])，k=0,1,2,…。

事實上，對于k=0，上式成立。假設上式對k=m(m>0)成立。

[x](m)?[x]，就有A-G([x](m))?A-G([x])。于是，對于ym∈[x](m)，K(ym,[x](m))?V(m)。由Z?[x](m)，有Z?K(ym,[x](m))?V(m)，故Z?[x](m+1)。

βmwid(Ki)≤βm+1wid([x]i)

即，wid([x](m+1))≤βm+1wid([x])。這就證明了對于k=m+1，原式也成立。

從而，當k→+∞時，wid([x](k))→ 0。

由Z非空知，序列{[x](k)}收斂到一個點x*。即，絕對值方程(1)有唯一解x*。

下面考慮由式(4)定義的迭代序列{[x](k)}，當任意點xo∈[x]，有xk∈[x]k，k=0,1,2，…。

事實上，當k=0，上式成立。假設對k=m(m>0)，上式成立，即xm∈[x]m。從而，

xm+1=xm-YF(xm)∈K(ym,[x]m)?Vm。

由xm∈[x]，有xm+1=xm-Yf(xm)∈K(y,[x])?[x]。

因此，xm+1∈Vm∩[x]=[x](m+1)。

于是，當時k→+∞，xk→x*。證畢。

從定理證明中可見，條件一旦滿足，運用點迭代(4)代替區(qū)間迭代(3)，減少了計算量，提高了計算效率。通過點迭代(4)，不但可以計算絕對值方程(1)的近似解，也可以估算出近似解和準確解之間的差距。

3 對分搜索法

下面，在一個大范圍上求解絕對值方程(1)。此時，不必限定絕對值方程(1)有唯一解。對于某個子域，由上面的討論知，可能有如下情形：

1)若K(y,[x])∩[x]=?時，方程無解；

2)若wid(K(y,[x])∩[x])≤αwid([x])，其中0≤α<1，那么更新[x]=K(y,[x])∩[x]，在更小的區(qū)間上去考慮；

3)若K(y,[x])?[x]且wid(K(y,[x]))

下面，我們給出對分搜索的算法。記待對分的子域表為S，不可分子域表為T，不可分長度為h，計算精度為ε，并取正數(shù)α，選取Y為非奇異矩陣。

算法如下：

步0 (初始化)清表S和T，把D送入S。

步1 (無解判別)計算式(2)區(qū)間函數(shù)F([x])，若0?F([x])，轉(zhuǎn)步8，否則轉(zhuǎn)步2。

步2 (計算)計算K(y,[x])及Z=K(y,[x])∩[x]。

步3 (無解判別)若Z=?，轉(zhuǎn)步8，否則，轉(zhuǎn)步4。

步4 (存在唯一性判別)計算wid(K(y,[x]))和wid([x])，若K([x])?[x]與wid(K([x]))

步5 (點迭代)取x0=mid([x])，由迭代(4)計算{kk}，直到‖xk-xk-1‖≤ε，輸出近似解xk，轉(zhuǎn)步8。

步6 (縮小區(qū)間)計算wid(Z)，若wid(Z)≤αwid([x])，則令[x]=Z，轉(zhuǎn)步1，否則轉(zhuǎn)步7。

步7 (對分)令[x]=Z，按[x]的最大寬度方向?qū)Ψ諿x]，將其一半記入表S的末部，另一半記為[x]。若wid([x])≤h且‖f(mid([x]))‖≤ε，則把[x]記入表T后轉(zhuǎn)步8，否則轉(zhuǎn)步1。

步8 (檢查表S)若表S為空，轉(zhuǎn)步9；若S非空，從表末取出最小子域送入[x]，并在表中將取出的部分抹去，轉(zhuǎn)步1。

步9 (檢查表T)如表T為空，則輸出無解，轉(zhuǎn)步10，否則打印表T的所有子域。

步10 停止。

算法在較大的范圍上，通過不斷區(qū)間迭代和對分的手段，在新的較小區(qū)間上考慮絕對值方程(1)解的情況，從而大量刪除無解區(qū)間。算法的收斂性簡單自明。

4 數(shù)值算例

我們利用Intlab軟件編程，計算下列算例。設計上述算法中的計算精度ε=1e-4，α=0.8。Y=[mid(F′([x]))]-1，若不可能，取Y為單位矩陣。

在[-10,10]上，利用算法求解，得到4個解

利用算法， 在[-10，10]上搜索到下列8個解：

上述算例的數(shù)值結(jié)果，驗證了算法是有效的。

5 結(jié)語

區(qū)間對分搜索法用于求解絕對值方程(1)，簡單易行。算法具有較好的數(shù)值穩(wěn)定性，但隨著問題維度的增大，對分的子域數(shù)量急劇增多，設計必要的無效區(qū)間刪除法則是十分有意義的。這是我們接下來要思考的問題。

[1]ROHN J.Systems of linear interval equations[J].Linear Algebra and Its Applications,1989，126(6):39-78.

[2]ROHN J.A theorem of the alternatives for the equation Ax+B|x|=b[J].Linear and Multilinear Algebra,2004,52(6):421-426.

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

[4]PROKOPYEV O.On equivalent reformulations for absolute value equations[J].Computational Optimization and Applications,2009,44(3):363-372.

[5]ROHN J.On unique solvability of the absolute value equation[J].Optimization Letter,2009,3(4):603-606.

[6]雍龍泉，馬守富.絕對值等式問題解的存在性研究[J].新鄉(xiāng)學院學報，2010,27(5):19-21.

[7]王愛祥，王海軍，龔成.絕對值方程的唯一可解性[J].科學技術與工程，2010,10(34):8501-8502.

[8]MANGASARIAN O L.A generalized Newton method for absolute value equations[J].Optimization Letter,2009(3):101-108.

[9]CACCETTA L,QU B,ZHOU G L.A globally and quadratically convergent method for absolute value equations[J].Computational Optimization and Applications,2011,48(1):45-58.

[10]WANG H J,LIU H,CAO S Y.A verification method for enclosing solutions of absolute value equations[J].Collectanea Mathematica,2013,64(1):17-38.

[11]WANG A X,WANG H J,DENG Y K.Interval algorithm for absolute value equations[J].Central European Journal of Mathematics,2011,9(5):1171-1184.

[12]YONG L Q.Particle swarm optimization for absolute value equations[J].Journal of Computational Information Systems,2010,6(7):2359-2366.

[13]YONG L Q,LIU S Y,ZHANG S M,et al.A new method for absolute value equations based on harmony search algorithm[J].ICIC Express Letters,Part B:Applications,2011,2(6):1231-1236.

[14]雍龍泉.基于差分進化—單純性混合算法求解絕對值方程[J].計算機應用研究，2011,28(9):3327-3329.

[15]李慶揚，莫孜中，祁力群.非線性方程組的數(shù)值解法[M].北京：科學出版社，1987:215-216.

責任編輯：周澤民

Dividing Search Algorithms for Absolute Value Equation with Multiple Solutions

WANG Aixiang

(School of Mechanical and Vehicule Engineering,Changzhou Institute of Technology,Changzhou 213032)

Absolute value equation can be used as a unified framework for study of many optimization problems such as linear programming and quadratic linear programming.Considering that absolute value equations have multiple solutions,an algorithm based on interval mathematics was proposed.Intervals were divided or deleted to obtain each solution of the absolute value equation within a large range.The numerical results verify the validity of the algorithm.

absolute value equation;multiple solution;interval algorithm;Krawczyk operator

10．3969/j．issn．1671?0436．2016．06．012

2016-11- 06

王愛祥(1984— )，男，碩士，講師。

O242

A

1671- 0436(2016)06- 0051- 06