絕對值方程的一種嚴(yán)格可行內(nèi)點算法

雍龍泉, 劉三陽, 張建科, 陳 濤, 鄧方安

(1. 西安電子科技大學(xué) 應(yīng)用數(shù)學(xué)系, 西安 710071; 2. 陜西理工學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院, 陜西 漢中 723001;3. 西安郵電學(xué)院 理學(xué)院, 西安 710121)

1 絕對值方程

考慮如下問題：

u=Au-b,

(1)

本文在假設(shè)矩陣A的奇異值大于1(這里矩陣A的奇異值定義為矩陣ATA特征值的非負(fù)平方根)時, 提出一種絕對值方程的新算法----可行內(nèi)點算法, 并證明了該算法經(jīng)過多次迭代后收斂到原問題的最優(yōu)解, 數(shù)值實驗表明該方法是有效的.

2 算 法

定義1如果對?x∈Rn,x≠0, 都有xTMx≥0, 則矩陣M∈Rn×n稱為半正定矩陣. 如果對?x∈Rn,x≠0, 都有xTMx>0, 則M稱為正定矩陣. 這里定義的(半)正定矩陣不要求對稱性, 因此, 這樣定義的(半)正定矩陣也稱為廣義(半)正定矩陣[14]. 顯然, 廣義(半)正定矩陣包含對稱(半)正定矩陣. 若無特殊說明, 本文所涉及的正定矩陣均為廣義(半)正定矩陣.

線性互補問題: 即求一個向量x∈Rn, 滿足x≥0,Mx+q≥0,xT(Mx+q)=0, 線性互補問題簡記為LCP(M,q). 當(dāng)矩陣M是半正定矩陣時, 稱LCP(M,q)為單調(diào)線性互補問題.

引理1[15]若矩陣A的特征值不為1, 則AVE可以轉(zhuǎn)化為LCP(M,q), 其中:

M=(A+I)(A-I)-1;q=((A+I)(A-I)-1-I)b;x=(A-I)u-b.

引理2[15]若矩陣A的奇異值大于1, 則矩陣M=(A+I)(A-I)-1是一個正定矩陣.

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

下面通過求解線性互補問題獲得問題(1)的解. 求解線性互補問題的算法有很多, 如投影法、 內(nèi)點法、 非光滑牛頓法和光滑牛頓法等[16-19]. 本文借鑒文獻(xiàn)[19]中求解線性互補問題的思想, 將牛頓方向和中心路徑方向相結(jié)合, 通過求解一個線性方程組得到搜索方向; 在每次迭代中, 尋找新的迭代點, 使得新的迭代點仍滿足可行性, 同時使得優(yōu)化目標(biāo)值減少, 這樣通過有限次迭代即可獲得原問題的一個近似解.

為了求解LCP(M,q), 構(gòu)造如下優(yōu)化問題：

(NP) minxTy; s.t.y=Mx+q,x≥0,y≥0.

顯然, 當(dāng)且僅當(dāng)問題(NP)達(dá)到最優(yōu)目標(biāo)值0時, 對應(yīng)的(x,y)是LCP(M,q)的一個解.

下面將建立一種算法, 使得該算法產(chǎn)生的點列在中心路徑鄰域內(nèi), 即{(xk,yk)}?N(a), 且使得(xk+1)Tyk+1≤ρ(xk)Tyk(k=0,1,…), 其中ρ∈(0,1)是一個與k無關(guān)的常數(shù). 這樣, 通過有限步迭代即有(xN)TyN≤ε, 且(xN,yN)∈N(a).

算法1

取命題1中的參數(shù)a,β,ρ,θ,ε>0為容許誤差, (x0,y0)∈N(a)為給定的初始點,k∶=0;

1) 若(xk)Tyk≤ε, 則停, 得到近似最優(yōu)解(xk,yk), 否則轉(zhuǎn)2);

2) 尋找轉(zhuǎn)移方向(Δx(β),Δy(β)), 其中(Δx(β),Δy(β))由下列方程組確定：

3) 令xk+1∶=xk+θΔx(β),yk+1∶=yk+θΔy(β),k∶=k+1, 轉(zhuǎn)1).

3 收斂性分析

證明參見文獻(xiàn)[20].

由引理3知, 在算法1步驟2)中, 轉(zhuǎn)移方向(Δx(β),Δy(β))存在且唯一.

記方程組(2)的解為(Δxa,Δya), 方程組(3)的解為(Δxc,Δyc). 顯然在算法1中, 轉(zhuǎn)移方向

Δx(β)=βΔxc+(1-β)Δxa, Δy(β)=βΔyc+(1-β)Δya;

因此, 在算法1中, 轉(zhuǎn)移方向(Δx(β),Δy(β))是牛頓方向(Δxa,Δya)和中心路徑方向(Δxc,Δyc)的嚴(yán)格凸組合.

2)

根據(jù)引理4, 有:

定理2取命題1中的參數(shù)a,β,ρ,θ, (x0,y0)∈N(a)為初始點, 則算法1產(chǎn)生的點列滿足： 1) (xk,yk)>0; 2) (xk,yk)∈N(a); 3) (xk+1)Tyk+1≤ρ(xk)Tyk. 其中k=0,1,2,…

證明: 由定理2可知(xk+1)Tyk+1≤ρ(xk)Tyk(k=0,1,2,…), 因此有

4 數(shù)值實驗

圖1 目標(biāo)函數(shù)值xTy的下降過程Fig.1 Descent of xTy

由于矩陣A的奇異值為(22.070 5,2.271 2,1.316 7)>1, 因此矩陣M為正定矩陣, 相應(yīng)的LCP(M,q)具有唯一解. 用本文算法進(jìn)行求解, 經(jīng)過247次迭代后, 得到線性互補問題的解為x=(0.000 2,0.000 5,0)T, 優(yōu)化問題(NP)的目標(biāo)函數(shù)值xTy下降過程如圖1所示. 從而AVE問題的唯一解為

進(jìn)一步, 用算法1求解隨機產(chǎn)生的AVE問題, 這里矩陣A和向量b由下述Matlab代碼產(chǎn)生:

rand(“state”,0);

R=rand(n,n);

b=rand(n,1);

A=R′*R+n*eye(n);

M=(A+eye(n))*(inv(A-eye(n)));

q=((A+eye(n))*(inv(A-eye(n)))-eye(n))*b;

輸入矩陣A的階數(shù)n, 給定初始點后, 可以快速得到AVE問題的解. 表1列出了不同維數(shù)的計算結(jié)果, 其中k表示(計算機)執(zhí)行算法1獲得近似解所需的迭代次數(shù).

表1 不同維數(shù)的計算結(jié)果

數(shù)值實驗表明, 本文算法對求解此類絕對值方程十分有效, 鑒于該算法具有多項式復(fù)雜性, 因此該算法可以作為求解此類問題的一種有效方法.

[1] Mangasarian O L, Meyer R R. Absolute Value Equations [J]. Linear Algebra and Its Applications, 2006, 419(2): 359-367.

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

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

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

[5] Mangasarian O L. Knapsack Feasibility as an Absolute Value Equation Solvable by Successive Linear Programming [J]. Optim Lett, 2009, 3(2): 161-170.

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

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

[8] Zhang C, Wei Q J. 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.

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

[10] 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.

[11] 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.

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

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

[14] TONG Wen-ting. Generalized Positive Definite Matrix [J]. Acta Mathematica Sinica: English Series, 1984, 27(6): 801-810. (佟文廷. 廣義正定矩陣 [J]. 數(shù)學(xué)學(xué)報, 1984, 27(6): 801-810.)

[15] 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.)

[16] KOU Shu-shun. Existence of Solutions for Linear Complementarity Problem [J]. Applied Mathematics and Mechanics, 1995, 16(7): 641-643. (寇述舜. 關(guān)于線性互補問題解的存在性 [J]. 應(yīng)用數(shù)學(xué)和力學(xué), 1995, 16(7): 641-643.)

[17] Kojima M, Megiddo N, Yoshise A. A Unified Approach to Interior Point Algorithms for Linear Complementary Problem [M]. Lecture Notes in Computer Science, Vol.538. Berlin: Springer-Verlag, 1991.

[18] 韓繼業(yè), 修乃華, 戚厚鐸. 非線性互補理論與算法 [M]. 上海: 上海科學(xué)技術(shù)出版社, 2006.

[19] YONG Long-quan, DENG Fang-an, CHEN Tao. An Interior Point Method for Solving Monotone Linear Complementarity Problems [J]. Journal of Math, 2009, 29(5): 681-686. (雍龍泉, 鄧方安, 陳濤. 單調(diào)線性互補的一種內(nèi)點算法 [J]. 數(shù)學(xué)雜志, 2009, 29(5): 681-686.)

[20] YONG Long-quan, LIU San-yang. The Proof and Application of a Series of Nonsingular Matrixes in Interior Point Algorithm [J]. Mathematics in Practice and Theory, 2006, 36(2): 258-261. (雍龍泉, 劉三陽. 內(nèi)點算法中一類非奇異矩陣的證明及其應(yīng)用 [J]. 數(shù)學(xué)的實踐與認(rèn)識, 2006, 36(2): 258-261.)

[21] YONG Long-quan. The Study of Algorithms for Quadratic Programming [D]: [Master’s Degree Thesis]. Xi’an: Xidian University, 2005. (雍龍泉. 二次規(guī)劃的算法研究 [D]: [碩士學(xué)位論文]. 西安: 西安電子科技大學(xué), 2005.)