具有2n個解的絕對值方程問題

雍龍泉,劉三陽,拓守恒,熊文濤,史加榮

(1. 西安電子科技大學(xué) 應(yīng)用數(shù)學(xué)系,西安 710071;2. 陜西理工學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,陜西 漢中 723001;3. 湖北工程學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,湖北 孝感 432000;4. 西安建筑科技大學(xué) 理學(xué)院,西安 710055)

0 引言與預(yù)備知識

考慮問題:

Ax-|x|=b,

(1)

其中:A∈Rn×n;x,b∈Rn;|x|表示對x的各分量取絕對值. 問題(1)稱為絕對值方程(absolute value equations,AVE),它是文獻(xiàn)[1]提出的絕對值矩陣方程Ax+B|x|=b的重要子類.

關(guān)于AVE的研究主要源于兩方面：一是區(qū)間線性方程[1-2];二是線性互補(bǔ)問題. 目前對于AVE的研究主要集中于理論[3-12]和算法[13-35]兩方面,前者主要研究解的存在性和唯一性;后者主要建立有效的算法并分析算法的收斂性. 本文給出了AVE問題解存在的條件,構(gòu)造了一些具有2n個解的AVE問題,并指出了求解多解絕對值方程應(yīng)注意的問題.

考慮Ax-|x|=b,若令A(yù)=I,b=0,則任意的x≥0都是AVE問題的解,此時AVE問題具有無窮多個解.

定理1[3]對AVE問題,若存在r∈Rn滿足r≥ATr≥-r,bTr>0,則AVE無解.

定理2[3]若0≠b≥0,且‖A‖<1,則AVE無解.

定理3[3]如果A的特征值不為1,并且A的奇異值大于或等于1,則當(dāng)集合

{x|(A+I)x-b≥0,(A-I)x-b≥0}≠?

時,AVE問題的解存在.

定理4[3]若矩陣A的奇異值大于1,則對任意的b∈Rn,AVE存在唯一解.

推論1[3]對任意的b,如果‖A-1‖<1,則AVE存在唯一解.

定理5[3]如果A≥0,‖A‖<1,b≤0,則AVE存在非負(fù)解.

如果區(qū)間矩陣[A-I,A+I]正則,則對于任意的b∈Rn,AVE有唯一解[9-10]. 該條件弱于矩陣A的奇異值大于1. 事實上,該條件恰好是文獻(xiàn)[7]的特例.

1 2n個解存在的條件

證明: 分兩步.

1) 證明在滿足上述條件下,方程Ax-x=b有唯一的正解x*.

構(gòu)造迭代過程xk+1=Axk-b,由于‖A‖∞<γ/2≤0.5<1,從而對于任意給定的初始點(diǎn)x0,迭代產(chǎn)生的序列{xk}都收斂,假設(shè)收斂點(diǎn)為x*,則x*唯一.

不妨取x0=-b,由于xk+1=Axk-b,則

從而

于是

‖xk+1-xk‖∞<(γ/2)k+1‖b‖∞,k=0,1,2,…

又由于

結(jié)合x0=-b,則有

2) 證明滿足條件的AVE問題有2n個解.

先證明矩陣(AD-I)是可逆的. 反之,則齊次線性方程組(AD-I)x=0存在非零解a≠0,使得(AD-I)a=0,從而‖AD‖∞‖a‖∞≥‖ADa‖∞=‖a‖∞,因此‖A‖∞=‖AD‖∞≥1,這與‖A‖∞<γ/2≤0.5<1矛盾. 用|D|表示對矩陣D的每個元素取絕對值,則有|D|=I,令x=Dy,則有|x|=|Dy|=|y|.

考慮方程ADy-y=b,由于‖AD‖∞=‖A‖∞<1,則利用上述結(jié)果知ADy-y=b有唯一的正解y*,且y*=(AD-I)-1b. 而ADy-y=b有唯一的正解y*?ADy-|y|=b有唯一的正解y*?Ax-|x|=b有唯一的(帶D模式的)解x*=Dy*.

由于D=diag(d1,d2,…,dn),di=±1,i=1,2,…,n,因此D的模式共有2n個,從而方程Ax-|x|=b共有2n個解,且2n個解可由式x*=D(AD-I)-1b分別計算.

由上述證明易見,該2n個解互不相同.

2 2n個解的算例分析

例1考慮AVE問題:

(2)

經(jīng)簡單計算可得:

例2考慮AVE問題:

(3)

經(jīng)簡單計算可得:

例3考慮AVE問題:

(4)

下面考慮例3中2n個解的分布.

定理7記例3的解為x*(共有2n個互不相同的解),則x*滿足

證明: 由于Ax*-|x*|=b,b=(-1,-1,…,-1)T,則有

‖(|x*|-1)‖∞=‖Ax*‖∞≤‖A‖∞‖x*‖∞=0.4‖x*‖∞.

(5)

不妨設(shè)

從而式(5)可簡化為

(6)

因此

即

3 求解多解AVE問題的注意事項

1) AVE問題是一個不可微問題,不能直接使用傳統(tǒng)的梯度類算法(最速下降算法、 各類擬牛頓算法和光滑牛頓法等),即使如文獻(xiàn)[16,23]中進(jìn)行光滑處理后再使用梯度類(或擬牛頓)算法,在給定初始點(diǎn)后,也只能收斂到原問題的一個最優(yōu)解[24-25]；如何求得上述問題的所有2n個互不相同的解,傳統(tǒng)算法則無法實現(xiàn).

2) 而群體智能算法(如粒子群算法[26]、 差分進(jìn)化算法[27]和聲搜索算法[28]等)是一類隨機(jī)搜索算法,對目標(biāo)函數(shù)的可微性沒有要求,且算法是多點(diǎn)開始的,因此經(jīng)過多次執(zhí)行算法就有可能找到AVE問題盡可能多的解.

3) 算法初始可行域的選取一定要包含AVE問題的所有解(防止漏解),只有這樣,通過多次執(zhí)行算法,才有可能找到AVE問題盡可能多的解.

如例3中,由于

?[-2,2],i=1,2,…,n,

因此可以選取初始可行域為[-2,2],既能防止漏解,又明確了搜索范圍；避免了為求得所有解而選取搜索空間過大,即減少了搜索的盲目性.

4) 2n個解的分布僅與向量b和矩陣A的無窮范數(shù)有關(guān),與矩陣A的元素?zé)o關(guān).

如例3中,向量b不變,三對角矩陣A的元素變更為

此時,這2n個解的分布仍不變,即對任意一個解,定理7仍成立.

5) 對高維的且有多個解的AVE問題,為了防止計算過程溢出,建議采用稀疏存儲方法. 考慮例3,在MatlabR2009a系統(tǒng)中,若不采用稀疏存儲,則當(dāng)維數(shù)n=1×104時溢出；若采用稀疏存儲,即使維數(shù)n=1×107也不會發(fā)生溢出現(xiàn)象. 例3中矩陣A的稀疏存儲可用如下語句在Matlab系統(tǒng)中生成：

A1=sparse(1∶n,1∶n,0.2,n,n);

A2=sparse(1∶n-1,2∶n,0.1,n,n);

A3=sparse(2∶n,1∶n-1,0.1,n,n);

A=A1+A2+A3.

[1] Rohn J. Systems of Linear Interval Equations [J]. Linear Algebra and Its Applications,1989,126: 39-78.

[2] Rohn J. A Theorem of the Alternatives for the EquationAx+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(2/3): 359-367.

[4] Oleg P. On Equivalent Reformulations for Absolute Value Equations [J]. Computational Optimization and Applications,2009,44(3): 363-372.

[5] HU Sheng-long,HUANG Zheng-hai. A Note on Absolute Value Equations [J]. Optim Lett,2010,4(3): 417-424.

[6] Rohn J. On Unique Solvability of the Absolute Value Equation [J]. Optim Lett,2009,3(4): 603-606.

[7] Rohn J. An Algorithm for Solving the Absolute Value Equation [J]. Electronic Journal of Linear Algebra,2009,18: 589-599.

[8] Rohn J. A Residual Existence Theorem for Linear Equations [J]. Optim Lett,2010,4(2): 287-292.

[9] WEI Qing-ju. A Generalized Newton Method and Its Convergence for Absolute Value Equation [D]. Beijing: Beijing Jiaotong University,2009. (魏慶舉. 絕對值方程的廣義牛頓算法及其收斂性 [D]. 北京: 北京交通大學(xué),2009.)

[10] ZHANG Chao,WEI Qing-ju. Global and Finite Convergence of a Generalized Newton Method for Absolute Value Equations [J]. Journal of Optimization Theory and Applications,2009,143(2): 391-403.

[11] YONG Long-quan,MA Shou-fu. Existent Conditions of Solution to Absolute Value Equations Problem [J]. Journal of Xinxiang University: Natural Science Edition,2010,27(5): 19-21. (雍龍泉,馬守富. 絕對值等式問題解的存在性研究 [J]. 新鄉(xiāng)學(xué)院學(xué)報: 自然科學(xué)版,2010,27(5): 19-21.)

[12] WANG Ai-xiang,WANG Hai-jun,GONG Cheng. Unique Solvability of Absolute Value Equations [J]. Science Technology and Engineering,2010,10(34): 8501-8502. (王愛祥,王海軍,龔成. 絕對值方程的唯一可解性 [J]. 科學(xué)技術(shù)與工程,2010,10(34): 8501-8502.)

[13] Mangasarian O L. Absolute Value Programming [J]. Computational Optimization and Aplications,2007,36(1): 43-53.

[14] Mangasarian O L. Absolute Value Equation Solution via Concave Minimization [J]. Optim Lett,2007,1(1): 3-8.

[15] Mangasarian O L. A Generlaized Newton Method for Absolute Value Equations [J]. Optim Lett,2009,3(1): 101-108.

[16] Caccetta L,QU Biao,ZHOU Guang-lu. A Globally and Quadratically Convergent Method for Absolute Value Equations [J]. Computational Optimization and Applications,2011,48(1): 45-58.

[17] WANG Ai-xiang,WANG Hai-jun. An Interval Method for Absolution Value Equations [J]. Journal of Guizhou University: Natural Science Edition,2010,27(2): 7-10. (王愛祥,王海軍. 絕對值方程的區(qū)間算法 [J]. 貴州大學(xué)學(xué)報: 自然科學(xué)版,2010,27(2): 7-10.)

[18] WANG Ai-xiang,WANG Hai-jun,DENG Yong-kun. Interval Algorithm for Absolute Value Equations [J]. Central European Journal of Mathematics,2011,9(5): 1171-1184.

[19] Noor M A,Iqbal J,Khattri S,et al. A New Iterative Method for Solving Absolute Value Equations [J]. International Journal of the Physical Sciences,2011,6(7): 1793-1797.

[20] Noor M A,Iqbal J,Noor K I,et al. On an Iterative Method for Solving Absolute Value Equations [J]. Optim Lett,2012,6(5): 1027-1033.

[21] Mangasarian O L. Absolute Value Equation Solution via Dual Complementarity [J]. Optim Lett,2013,7(4): 625-630.

[22] YONG Long-quan. A New Solution Method for Absolute Value Equations [J]. Science and Technology Review,2010,28(5): 60-62. (雍龍泉. 絕對值等式問題的一個求解方法 [J]. 科技導(dǎo)報,2010,28(5): 60-62.)

[23] YONG Long-quan,LIU San-yang,ZHANG She-min,et al. Smoothing Newton Method for Absolute Value Equations Based on Aggregate Function [J]. International Journal of the Physical Sciences,2011,6(23): 5399-5405.

[24] YONG Long-quan,LIU San-yang,ZHANG Jian-ke,et al. A New Feasible Interior Point Method to Absolute Value Equations [J]. Journal of Jilin University: Science Edition,2012,50(5): 887-891. (雍龍泉,劉三陽,張建科,等. 絕對值方程的一種嚴(yán)格可行內(nèi)點(diǎn)算法 [J]. 吉林大學(xué)學(xué)報: 理學(xué)版,2012,50(5): 887-891.)

[25] YONG Long-quan. An Iterative Method for Absolute Value Equations Associated with Real Symmetric Matrices [J]. Journal of Southwest University: Natural Science Edition,2012,34(5): 32-37. (雍龍泉. 迭代法求解實對稱矩陣絕對值方程 [J]. 西南大學(xué)學(xué)報: 自然科學(xué)版,2012,34(5): 32-37.)

[26] YONG Long-quan. Particle Swarm Optimization for Absolute Value Equations [J]. Journal of Computational Information Systems,2010,6(7): 2359-2366.

[27] YONG Long-quan. Differential Evolution-Simplex Hybrid Algorithm for Absolute Value Equations [J]. Application Research of Computers,2011,28(9): 3327-3329. (雍龍泉. 基于差分進(jìn)化-單純形混合算法求解絕對值方程 [J]. 計算機(jī)應(yīng)用研究,2011,28(9): 3327-3329.)

[28] YONG Long-quan,LIU San-yang,ZHANG She-min,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.

[29] Noor M A,Iqbal J,Al-Said E. Residual Iterative Method for Solving Absolute Value Equations [J/OL]. Abstract and Applied Analysis,2012:doi: 10.1155/2012/406232.

[30] Hooshyarbakhsh V,Lotfi T,Farhadsefat R,et al. An Iterative Method for Solving Absolute Value Equations [R/OL]. 2012. http://www3.cs.cas.cz/ics/reports/v1145-12.pdf.

[31] Rohn J. An Algorithm for Computing All Solutions of an Absolute Value Equation [J]. Optimization Letters,2012,6(5): 851-856.

[32] WANG Hai-jun,LIU Hao,CAO Su-yu. A Verification Method for Enclosing Solutions of Absolute Value Equations [J]. Collect Math,2013,64(1): 17-38.

[33] Ketabchi S,Moosaei H. Minimum Norm Solution to the Absolute Value Equation in the Convex Case [J]. Journal of Optimization Theory and Applications,2012,154(3): 1080-1087.

[34] Ketabchi S,Moosaei H,Fallahi S. Optimal Error Correction of the Absolute Value Equation Using a Genetic Algorithm [J]. Mathematical and Computer Modelling,2013,57(9/10): 2339-2342.

[35] Ketabchi S,Moosaei H. An Efficient Method for Optimal Correcting of Absolute Value Equations by Minimal Changes in the Right Hand Side [J]. Computers and Mathematics with Applications,2012,64(6): 1882-1885.