求解絕對值方程的PRP型梯度算法

祝文娟，嚴　濤

（南京理工大學理學院，江蘇南京210094）

求解絕對值方程的PRP型梯度算法

祝文娟，嚴濤

（南京理工大學理學院，江蘇南京210094）

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

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

1　相關基礎知識

絕對值方程（Absolute Value Equation，簡記為AVE）定義如下：

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

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

定義1.3設f：D?Rn→R1,D是非空凸集，如果存在一個常數(shù)β＞0,對任意的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，則對任意的b∈Rn，絕對值方程存在唯一解.

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

證明設n維矩陣A的特征值為λ1,...,λn,令s= min（λ1,...,λn）,則s＞0.故A - sE的特征值為λ1- s,λ2- s,...,λn- s均非負.又因為A - sE均為實對稱矩陣，則PT（A - sE）P≥0,P≠0,則PTAP≥sPTP.即PTAP≥s‖P‖2.

2　算法及收斂性分析

對于問題（1）中的對稱矩陣A∈Rn×n,b∈Rn可構造如下模型［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］當矩陣C = A - D是正定時，x∈Rn是（1）的解當且僅當x為f（x）的最小值點.

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

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

則，進一步有：

引理2.1［9］x是絕對值方程（1）的解當且僅當?f（x）= 0 .

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

算法2.1

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

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

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

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

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

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

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

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

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

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

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

表2　算例3與算例4的實驗結果

3　數(shù)值實驗

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

算例1［8］矩陣A的元素定義為AT= A, aii= 500, aij= 1 + rand, i≠j,其中rand表示［0，1］中的隨機數(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.

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

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

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

4　結束語

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

參考文獻：

［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ù)的擬牛頓算法求解絕對值方程［J］.系統(tǒng)科學與數(shù)學，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］王炳囡.絕對值方程的算法及其收斂性分析［D］.曲阜：曲阜師范大學，2012：32-36.

［10］徐成賢，陳志平，李乃成.近代優(yōu)化方法［M］.北京：科學出版社，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

中圖分類號：O24

文獻標識碼：A

文章編號：1008-2794（2016）02-0086-05

收稿日期：2015-12-01

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

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