多解絕對(duì)值方程的對(duì)分搜索法

王愛(ài)祥

(常州工學(xué)院機(jī)械與車(chē)輛工程學(xué)院,江蘇常州213032)

多解絕對(duì)值方程的對(duì)分搜索法

王愛(ài)祥

(常州工學(xué)院機(jī)械與車(chē)輛工程學(xué)院,江蘇常州213032)

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

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

0 引言

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

(1)

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

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

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

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

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

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

定義區(qū)間運(yùn)算：

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

以及

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

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

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

則稱(chēng)F為f的區(qū)間擴(kuò)展。有關(guān)區(qū)間數(shù)學(xué)的其他概念和詳細(xì)內(nèi)容，參閱文獻(xiàn)[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 設(shè)x*為絕對(duì)值方程(1)的解，且x*∈[x]，則對(duì)于任意y∈[x]，x*∈K(y,[x])。

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

對(duì)于任意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，若絕對(duì)值方程(1)的解x*∈[x]，則[x]∩K(y,[x])≠?。我們可得定理2。

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

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

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

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

(3)

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

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

wid(K(y,[x]))

對(duì)于任意x0∈[x]為初值，通過(guò)點(diǎn)迭代

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

(4)

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

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

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

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

事實(shí)上，對(duì)于k=0，上式成立。假設(shè)上式對(duì)k=m(m>0)成立。

[x](m)?[x]，就有A-G([x](m))?A-G([x])。于是，對(duì)于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])。這就證明了對(duì)于k=m+1，原式也成立。

從而，當(dāng)k→+∞時(shí)，wid([x](k))→ 0。

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

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

事實(shí)上，當(dāng)k=0，上式成立。假設(shè)對(duì)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)。

于是，當(dāng)時(shí)k→+∞，xk→x*。證畢。

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

3 對(duì)分搜索法

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

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

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]))

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

算法如下：

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

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

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

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

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

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

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

步7 (對(duì)分)令[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為空，則輸出無(wú)解，轉(zhuǎn)步10，否則打印表T的所有子域。

步10 停止。

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

4 數(shù)值算例

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

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

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

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

5 結(jié)語(yǔ)

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

[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]雍龍泉，馬守富.絕對(duì)值等式問(wèn)題解的存在性研究[J].新鄉(xiāng)學(xué)院學(xué)報(bào)，2010,27(5):19-21.

[7]王愛(ài)祥，王海軍，龔成.絕對(duì)值方程的唯一可解性[J].科學(xué)技術(shù)與工程，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ìn)化—單純性混合算法求解絕對(duì)值方程[J].計(jì)算機(jī)應(yīng)用研究，2011,28(9):3327-3329.

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

責(zé)任編輯：周澤民

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

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

O242

A

1671- 0436(2016)06- 0051- 06