基于熵函數的梯度型算法求解絕對值方程

祝文娟，嚴　濤

(南京理工大學 理學院， 江蘇 南京 210094)

?

基于熵函數的梯度型算法求解絕對值方程

祝文娟，嚴濤

(南京理工大學 理學院， 江蘇 南京 210094)

[摘要]本文中，在假設矩陣A的奇異值大于1的條件下，給出了求解絕對值方程的一個新的光滑化梯度型算法. 通過引入極大熵函數對絕對值方程進行光滑化處理，得到一個非線性光滑方程組，再引入適當的目標函數，把絕對值方程轉化為無約束優化問題，進而利用共軛梯度算法對其求解，從而獲得原問題的解. 數值實驗表明了新方法的有效性.

[關鍵詞]絕對值方程；極大熵函數；共軛梯度法；無約束最優化

1引言

絕對值方程(Absolute Value Equation，簡記AVE)定義如下：

(1)

絕對值方程的研究來源于兩個方面，一個是區間線性方程[2]，另一個是線性互補問題. 目前對于問題(1)的研究主要集中在理論和算法兩個方面，其中理論方面的研究主要集中在解的存在性和唯一性條件、替代定理以及各種等價轉化形式[2-3]. 而算法方面的研究則主要是以各等價問題為基礎構造有效算法從而求解原問題，并進行相應的收斂性分析. 我們把已有算法歸結為以下幾類，一是利用絕對值方程與線性互補問題的等價性，在一定條件下，將絕對值方程轉化為線性互補問題，然后通過求解轉化后的線性互補問題求得原問題的解[4]. 二是利用迭代算法來求解絕對值方程，即將絕對值方程轉化為一個可微函數f(x)，則問題(1)的求解等價于求解無約束優化問題[5-6]. 三是先將絕對值方程光滑化，轉化為一個非線性方程組，再引入適當的目標函數，從而把絕對值方程轉化為等價的無約束優化問題，然后利用牛頓法、擬牛頓法等來求解無約束優化問題[7-8]. 但它在求解過程中要存儲一個n×n矩陣，這對大規模無約束問題會因為計算機內存的限制而無法使用. 另外，它在迭代的每一步構造搜索方向要解一個線代數方程組，這使得算法的效率受到影響.

本文中為方便求解大規模的絕對值方程問題，我們以文獻[8]中的等價無約束優化形式為基礎，給出了一種梯度型求解算法. 論文安排如下：我們在第1節引言中將給出一些相關基礎知識；在第2節中，先通過引入極大熵函數對絕對值方程進行光滑化處理，得到一個非線性方程組，再引入適當的目標函數，把絕對值方程的求解轉化為無約束優化問題的求解，在此基礎上，我們用PRP共軛梯度法對最優化問題進行求解從而得出原方程的解，并給出收斂性分析；第3節，我們給出數值實驗結果. 最后對本文進行總結.

本文用‖·‖表示2范數，I表示單位矩陣，exp表示指數函數ex，則我們給出如下定義：

定義1.1[9](光滑逼近函數)給定函數H:=Rn→Rn,我們稱光滑函數Hμ:=Rn→Rn(μ>0)為H的光滑逼近函數，如果對任意x∈Rn,存在κ>0,使得

這里κ不依賴于x,則稱Hμ為H的一致光滑逼近函數.

下面我們以引理的形式給出極大熵函數的性質：

引理1.1[11]對于任意的x∈Rn，

其中：m代表分量函數的個數.

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

定理1.2[12](一致凸函數的判別定理)設D?Rn是非空開凸集，f:D?Rn→R1，且f(x)在D上一階連續可微，則f(x)在D上是一致凸函數的充要條件是存在常數β>0，使

成立.

2算法及收斂性分析

絕對值方程(1)等價于非線性方程組

(2)

則有下式成立

于是我們就將絕對值方程(1)轉化為如下非線性光滑方程組

(3)

則我們可以得到以下定理：

又因為對于任意的μ>0，有

為了方便求解，下面我們對任意的μ>0給出目標函數

(4)

則有下面定理成立.

以上述理論為基礎，為了適應大規模絕對值方程求解問題，我們將給出求解無約束優化問題(4)的梯度型算法. 在本文中，我們的算法采取精確線性搜索，具體描述如下：

算法2.1

g1=，令d1=-g1,k:=0;

步驟2如果‖gk‖≤ε,則停；否則，利用精確線性搜索求αk，即

xk+1=xk+αkdk.

下面我們給出算法2.1的收斂性分析.

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

即

(5)

(6)

故由定理1.2可知，φμ(x)為Rn上的一致凸函數.

3數值實驗

在本節中，我們將給出數值實例來驗證算法的有效性. 我們選取文獻[8]中的兩個算例進行求解. 算法程序用MatlabR2012b在4GB RAM, CPU@1.70GHz 2.40GHz上運行.

算例1[8]我們考慮矩陣A和向量b按如下給出的絕對值方程問題

我們知道矩陣A的奇異值大于1，因此該絕對值方程問題存在唯一解.若我們取μ=0.01，e=10-6，設定初始點為x=(0.5,0.5,0.5,0.5)T，則經26次迭代，平均用時0.0126秒，便可得到該絕對值方程的唯一解x=(1,1,1,1)T.

算例2[8]矩陣A的元素定義為

令b=(A-I)e,其中I為n維單位矩陣，e=(1,1,…,1)T,該問題存在唯一解x=(1,1,…,1)T.

我們設定不同的初始點和參數μ,停止準則e=1.0e-6，利用本文算法對算例2進行計算. 結果表明，我們的算法能在有限步數內獲得問題的唯一解. 其具體結果將在表1和表2中給出.

我們選取文獻[8]中的初始點x0=(10,10,…,10)T，令參數μ=0.1，停止準則e=10-6，運用我們的算法來求解算例2，我們將在表3中給出其具體計算結果.

我們從表1～3的數值結果可以看出，本文的算法具有一定的有效性，且能夠快速的求得高維絕對值方程問題的解. 且與文獻[8]中算例4的數值結果相比，本文算法在解決相同維數的絕對值方程問題時所耗時間較少.

4結束語

本文先采用極大熵函數對絕對值方程進行光滑化處理，構造一個與絕對值方程等價的無約束優化問題，然后采用共軛梯度法求解無約束優化問題從而獲得原問題的解. 數值實驗表明，本文的算法是可行的，并且適合求解高維的絕對值方程問題. 因此，本文的算法可作為求解絕對值方程問題的一個有效算法.

[參考文獻]

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

[2]Jiri Rohn. 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]Oleg Prokopyev. On equivalent reformulations for absolute value equations [J]. Computational Optimization and Applications,2009, 44(3) :363-372.

[5]Noor M A, Iqbal J, Khattri S, Al-Said E. A new iterative method for Solving absolute value Equations [J]. International Journal of the Physical Science, 2011, 6(7): 1793-1797.

[6]Noor M A, Iqbal J, Noor K I , Al-Said E. On an iterative method for solving absolute value Equations [J]. Optimization Letters. 2012，6(5):1027-1033.

[7]C Zhang, Q J Wei. 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.[8]雍龍泉，拓守恒. 基于凝聚函數的擬牛頓算法求解絕對值方程[J]. 系統科學與數學，2012,32(11)，1427-1436.

[9]韓繼業，修乃華，戚厚鐸. 非線性互補理論與算法[M]. 上海：上?？茖W技術出版社，2006:248-250.

[10]陳玥琪. 絕對值方程的算法及收斂性分析[D]. 西安電子科技大學，2014,17-21.

[11]李興斯. 一類不可微優化問題的有效解法[J]. 中國科學(A 輯)，1994,24(4):371-377.

[12]徐成賢，陳志平，李乃成. 近代優化方法[M]. 科學出版社，2002,185-186.

The Conjugate Gradient Algorithm for Solving the Absolute Value Equations Based on Maximum Entropy Function

ZHU Wenjuan, YAN Tao

(DepartmentofInformationandComputationalScience,SchoolofScience,NanjingUniversityofScienceandTechnology,Nanjing210094,China)

Abstract：In this paper, a new smoothing conjugate gradient algorithm for solving absolute value equations is proposed under the condition that all singular values of matric A exceed one. By using the maximum entropy function, absolute value equation problems are transformed into a smooth nonlinear equations, and then into an unconstrained optimization problem by introducing appropriate objective function. We apply the conjugate gradient algorithm for solving the absolute value equation. Numerical results are presented to show efficiency of the new method.

Key words：absolute value equations; maximum entropy function; conjugate gradient method; unconstrained optimization

[收稿日期]2016-03-05

[基金項目]國家自然科學基金項目(11101214)

[作者簡介]祝文娟(1990-)，女，安徽安慶人，碩士生，研究方向：互補問題及均衡約束規劃問題；通訊作者：嚴濤(1977-)，男，副教授，博士，研究方向：最優化方法。

[中圖分類號]O24

[文獻標識碼]A

[文章編號]1674-2273(2016)03-0001-04