求解絕對(duì)值方程的PRP型梯度算法

祝文娟，嚴(yán)　濤

（南京理工大學(xué)理學(xué)院，江蘇南京210094）

求解絕對(duì)值方程的PRP型梯度算法

祝文娟，嚴(yán)濤

（南京理工大學(xué)理學(xué)院，江蘇南京210094）

摘要：給出了一種求解絕對(duì)值方程Ax -|x | = b的新方法.在矩陣A為對(duì)稱正定的假設(shè)條件下，絕對(duì)值方程可轉(zhuǎn)化為一個(gè)無約束優(yōu)化問題，進(jìn)而用PRP共軛梯度型方法對(duì)轉(zhuǎn)化的無約束優(yōu)化問題進(jìn)行求解，從而獲得原問題的解.證明了新算法在適當(dāng)條件下可收斂到原問題的解.數(shù)值實(shí)驗(yàn)也表明了新方法的有效性.

關(guān)鍵詞：絕對(duì)值方程；PRP共軛梯度法；收斂性；無約束最優(yōu)化

1　相關(guān)基礎(chǔ)知識(shí)

絕對(duì)值方程（Absolute Value Equation，簡(jiǎn)記為AVE）定義如下：

其中對(duì)稱正定矩陣A∈Rn×n,b∈Rn，|x|表示對(duì)x的各個(gè)分量取絕對(duì)值.它是一類不可微的NP-hard優(yōu)化問題.從形式上，問題（1）是絕對(duì)值方程Ax + B|x | = b的重要子類［1］.

絕對(duì)值方程的研究來源于兩個(gè)方面，一個(gè)是區(qū)間線性方程［2］，另一個(gè)是線性互補(bǔ)問題.在理論方面，目前對(duì)于問題（1）的研究主要集中在解的存在性條件、唯一性條件、替代定理以及各種等價(jià)轉(zhuǎn)化形式［2-3］.算法研究主要是以各等價(jià)問題為基礎(chǔ)構(gòu)造算法進(jìn)而求解原問題，并進(jìn)行相應(yīng)的收斂性分析.現(xiàn)有算法可以歸結(jié)為以下幾類，一是利用絕對(duì)值方程與線性互補(bǔ)問題的等價(jià)性，將絕對(duì)值方程轉(zhuǎn)化為線性互補(bǔ)問題，然后通過求解轉(zhuǎn)化后的線性互補(bǔ)問題求得原問題的解［4］.二是將絕對(duì)值方程光滑化，等價(jià)轉(zhuǎn)化成求解一個(gè)非線性方程組［5-6］.三是利用迭代算法來求解絕對(duì)值方程，即將絕對(duì)值方程轉(zhuǎn)化為一個(gè)可微函數(shù)f（x），則問題（1）求解等價(jià)于求解無約束優(yōu)化問題［7-9］.文獻(xiàn)［9］中利用Armijo步長(zhǎng)搜索規(guī)則，運(yùn)用最速下降法來求解轉(zhuǎn)化的無約束優(yōu)化問題.但最速下降法產(chǎn)生的迭代點(diǎn)列移向極小點(diǎn)的路徑呈“鋸齒狀”.隨迭代點(diǎn)越來越接近極小點(diǎn)，目標(biāo)函數(shù)下降得越來越緩慢，因而迭代點(diǎn)列收斂速度較慢.

定義1.3設(shè)f：D?Rn→R1,D是非空凸集，如果存在一個(gè)常數(shù)β＞0,對(duì)任意的x,y∈D和任意的α∈（0,1）有αf（x）+（1 -α）f（y）- f（αx +（1 -α）y）≥（1 -α）αβ‖x- y‖2,則稱f（x）在凸集D上是一致凸函數(shù).

定理1.1［3］若矩陣A的奇異值大于1，則對(duì)任意的b∈Rn，絕對(duì)值方程存在唯一解.

引理1.1若矩陣A為對(duì)稱正定的，則存在向量P≠0及實(shí)數(shù)s＞0使得PTAP≥s‖P‖2.

證明設(shè)n維矩陣A的特征值為λ1,...,λn,令s= min（λ1,...,λn）,則s＞0.故A - sE的特征值為λ1- s,λ2- s,...,λn- s均非負(fù).又因?yàn)锳 - sE均為實(shí)對(duì)稱矩陣，則PT（A - sE）P≥0,P≠0,則PTAP≥sPTP.即PTAP≥s‖P‖2.

2　算法及收斂性分析

對(duì)于問題（1）中的對(duì)稱矩陣A∈Rn×n,b∈Rn可構(gòu)造如下模型［8］：

由于f（x）是連續(xù)可微的，則有?f（x）= 2（Ax -|x | - b）,?2f（x）= 2（A - D）= 2C ,其中D = diag（sign（x）,xi∈［- 1,1］, i= 1,2,...,n .

定理2.1［8］當(dāng)矩陣C = A - D是正定時(shí)，x∈Rn是（1）的解當(dāng)且僅當(dāng)x為f（x）的最小值點(diǎn).

定理2.2［5］若矩陣A的奇異值大于1，則區(qū)間矩陣［］A - I,A + I是正則的，故矩陣C為非奇異矩陣.

由上可知，絕對(duì)值方程（1）的求解可以轉(zhuǎn)化為以下無約束優(yōu)化問題：

則，進(jìn)一步有：

引理2.1［9］x是絕對(duì)值方程（1）的解當(dāng)且僅當(dāng)?f（x）= 0 .

以上述理論為基礎(chǔ)，為了適應(yīng)大規(guī)模絕對(duì)值方程求解問題，我們將給出求解無約束優(yōu)化問題（3）的PRP型梯度算法，為區(qū)別于文獻(xiàn)［9］及方便收斂性分析.本文的算法采取精確線性搜索，具體描述如下：

算法2.1

步驟1初始化：選取初始點(diǎn)x1，參數(shù)ε∈（0,1），計(jì)算g1=?f（x1），令d1= -g1,k：= 0；

步驟2如果‖gk‖≤ε,則停；否則，利用精確線性搜索求αk，即f（xk+αkdk）= mα＞in0f（xk+αdk）, xk + 1= xk+αkdk.

步驟3計(jì)算?f（xk + 1）,令gk + 1=?f（xk + 1）.

步驟4利用下列公式來計(jì)算參數(shù)βk：

步驟5令dk + 1= -gk + 1+βkPRPdk,k：= k + 1.返回步驟2.

下面我們給出算法2.1的收斂性分析，首先給兩個(gè)引理.

引理2.2［10］設(shè)?f（x）在水平集L（x（0））=｛x|f（x）≤f（x（0））｝上存在且一致連續(xù)，下降算法的搜索方向d（k）與-?f（x（k））之間的夾角θk滿足θk≤π2-μˉ,μˉ＞0,?k.步長(zhǎng)αk由精確線性搜索確定.則或者對(duì)某個(gè)k,有?f（x（k））= 0,或者有f（x（k））→-∞（k→∞）,或者有?f（x（k））→0（k→∞）.

引理2.3矩陣C = A - D正定，則目標(biāo)函數(shù)f（x）是Rn上的一致凸函數(shù).

證明設(shè)u∈Rn,α∈R,考慮函數(shù)f（x +αu）在x處的二階泰勒展開式，有

當(dāng)‖g（k + 1）‖＞0時(shí)，由（15）式可得cos θk + 1≥ρ.由此可知存在μˉ＞0,使θk + 1≤-μˉ.由引理2.2知g（k + 1）→0,故g（x?）= 0 .而由引理2.3知，x?是唯一的極小點(diǎn)，所以x（k + 1）→x?且x?是極小點(diǎn).

維數(shù)n算例1的結(jié)果本文算法　文獻(xiàn)［9］中算法10 20 50 100 500 1000 777791 1 671 2 ------算例2的結(jié)果本文算法13 14 16 17 18 18文獻(xiàn)［9］中算法19 19 --------

表2　算例3與算例4的實(shí)驗(yàn)結(jié)果

3　數(shù)值實(shí)驗(yàn)

在本節(jié)中，我們將給出數(shù)值實(shí)例來驗(yàn)證算法的有效性.我們選取文獻(xiàn)［8］和文獻(xiàn)［6］中的算例進(jìn)行求解.停止準(zhǔn)則為‖g（k）‖= 10-6，表中“--”表示在規(guī)定的最大迭代次數(shù)內(nèi)沒有得到問題的解.在本文中，我們?cè)O(shè)定最大迭代次數(shù)為2 000.算法程序用MATLAB R2 012b在4 GB RAM，CPU@1.70 GHz 2.40 GHz上運(yùn)行.同時(shí)，為方便進(jìn)行數(shù)值實(shí)驗(yàn)比較，我們將文獻(xiàn)［9］中的算法完成程序后在同樣的環(huán)境下運(yùn)行.

算例1［8］矩陣A的元素定義為AT= A, aii= 500, aij= 1 + rand, i≠j,其中rand表示［0，1］中的隨機(jī)數(shù)，令b =（A - I）e,其中I為n維單位矩陣，e =（1,1,...,1）T,該問題存在唯一解x =（1,1,...,1）T.

算例2［8］矩陣A的元素定義為aii= 4n,ai,i+ 1= ai+ 1,i= n,aij= 0.5,i,j= 1,2,...,n. 令b =（A - I）e,其中I為n維單位矩陣，e =（1,1,...,1）T,該問題存在唯一解x =（1,1,...,1）T.

我們?cè)O(shè)定算例1的初始點(diǎn)為x0=（0,0,...,0）T，算例2的初始點(diǎn)為x0=（x1,x2,...,xn）T,xi= 0.001?i .在規(guī)定的最大迭代次數(shù)內(nèi)，我們的算法能有限中止，獲得問題的唯一解.而文獻(xiàn)［9］中的算法只有在維數(shù)較小時(shí)才能在規(guī)定的最大迭代次數(shù)內(nèi)獲得問題的唯一解.我們?cè)诒?給出了算例1和2的具體迭代步數(shù).

算例3和算例4中的矩陣A由文獻(xiàn)［6］中的MATLAB程序生成.問題具有唯一解x =（1,1,...,1）T.我們?cè)O(shè)定算例3和4的初始點(diǎn)為x0=（10,10,...,10）T.我們的算法能在有限步數(shù)內(nèi)獲得問題的唯一解.而文獻(xiàn)［9］中的算法對(duì)于算例3只有在維數(shù)較小時(shí)才能在有限步數(shù)內(nèi)獲得問題的唯一解，但對(duì)于算例4在規(guī)定的最大迭代次數(shù)內(nèi)不能得到問題的解.我們?cè)诒?給出了算例3和4的具體迭代步數(shù).

從上述數(shù)值結(jié)果可以看出，本文的算法具有一定的有效性，與文獻(xiàn)［9］中給出的下降算法相比，本文的算法在求解維數(shù)較大的問題上有一定優(yōu)勢(shì)，除算例4（n=1 000）外，其他測(cè)試問題均能在滿足停機(jī)準(zhǔn)則下有限中止，得到問題的唯一解，且迭代次數(shù)較少.

4　結(jié)束語

本文先直接將絕對(duì)值方程等價(jià)轉(zhuǎn)化為一個(gè)可微的無約束優(yōu)化問題，然后采用共軛梯度法對(duì)該無約束優(yōu)化問題進(jìn)行迭代求解從而獲得原問題的解.理論證明和數(shù)值實(shí)驗(yàn)表明，本文的算法是可行的，并且適合求解維數(shù)比較高的絕對(duì)值方程.因此本文的算法可作為求解絕對(duì)值方程問題的一個(gè)有效算法.

參考文獻(xiàn)：

［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 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 Multiplication, 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］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.

［6］雍龍泉，拓守恒.基于凝聚函數(shù)的擬牛頓算法求解絕對(duì)值方程［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2012，32（11）：1427-1436.

［7］NOOR M A, IQBAL J, KHATTRI S, et al. A new iterative method for Solving absolute value Equations［J］. International Journal of the Physical Science, 2011, 6（7）：1793-1797.

［8］NOOR M A, IQBAL J, NOOR K I , et al. On an iterative method for solving absolute value Equations［J］. Optimization Letters, 2012, 16（5）：1027-1033. DOI：10.1007/s11590-011-0332-0.

［9］王炳囡.絕對(duì)值方程的算法及其收斂性分析［D］.曲阜：曲阜師范大學(xué)，2012：32-36.

［10］徐成賢，陳志平，李乃成.近代優(yōu)化方法［M］.北京：科學(xué)出版社，2002：98-98.

The PRP Conjugate Gradient Algorithm for Solving the Absolute Value Equations

ZHU Wenjuan, YAN Tao
（School of Science, Nanjing University of Science and Technology, Nanjing 210094, China）

Abstract：In this paper, the authors propose a new algorithm for solving the absolute value equation（AVE）：Ax -| | x = b. Under the condition of coefficient matric A , which is symmetric and positive definite, absolute value equation is equivalent to an unconstrained optimization problem. The authors apply the PRP conjugate gradient algorithm for solving the absolute value equation based on the unconstrained optimization problem. The convergence of the proposed method is discussed under suitable conditions. Besides, numerical results are presented to show the efficiency of the new method.

Key words：absolute value equations；PRP conjugate gradient method；convergence；unconstrained optimization

中圖分類號(hào)：O24

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1008-2794（2016）02-0086-05

收稿日期：2015-12-01

基金項(xiàng)目：國(guó)家自然科學(xué)基金“對(duì)稱錐均衡約束規(guī)劃的算法研究”（11101214）

通信作者：嚴(yán)濤，副教授，博士，研究方向：最優(yōu)化方法，E-mail：tyan@njust.edu.cn.