祝文娟，嚴(yán)　濤

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

?

基于熵函數(shù)的梯度型算法求解絕對(duì)值方程

祝文娟，嚴(yán)濤

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

[摘要]本文中，在假設(shè)矩陣A的奇異值大于1的條件下，給出了求解絕對(duì)值方程的一個(gè)新的光滑化梯度型算法. 通過(guò)引入極大熵函數(shù)對(duì)絕對(duì)值方程進(jìn)行光滑化處理，得到一個(gè)非線性光滑方程組，再引入適當(dāng)?shù)哪繕?biāo)函數(shù)，把絕對(duì)值方程轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，進(jìn)而利用共軛梯度算法對(duì)其求解，從而獲得原問(wèn)題的解. 數(shù)值實(shí)驗(yàn)表明了新方法的有效性.

[關(guān)鍵詞]絕對(duì)值方程；極大熵函數(shù)；共軛梯度法；無(wú)約束最優(yōu)化

1引言

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

(1)

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

本文中為方便求解大規(guī)模的絕對(duì)值方程問(wèn)題，我們以文獻(xiàn)[8]中的等價(jià)無(wú)約束優(yōu)化形式為基礎(chǔ)，給出了一種梯度型求解算法. 論文安排如下：我們?cè)诘?節(jié)引言中將給出一些相關(guān)基礎(chǔ)知識(shí)；在第2節(jié)中，先通過(guò)引入極大熵函數(shù)對(duì)絕對(duì)值方程進(jìn)行光滑化處理，得到一個(gè)非線性方程組，再引入適當(dāng)?shù)哪繕?biāo)函數(shù)，把絕對(duì)值方程的求解轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題的求解，在此基礎(chǔ)上，我們用PRP共軛梯度法對(duì)最優(yōu)化問(wèn)題進(jìn)行求解從而得出原方程的解，并給出收斂性分析；第3節(jié)，我們給出數(shù)值實(shí)驗(yàn)結(jié)果. 最后對(duì)本文進(jìn)行總結(jié).

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

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

這里κ不依賴(lài)于x,則稱(chēng)Hμ為H的一致光滑逼近函數(shù).

下面我們以引理的形式給出極大熵函數(shù)的性質(zhì)：

引理1.1[11]對(duì)于任意的x∈Rn，

其中：m代表分量函數(shù)的個(gè)數(shù).

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

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

成立.

2算法及收斂性分析

絕對(duì)值方程(1)等價(jià)于非線性方程組

(2)

則有下式成立

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

(3)

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

又因?yàn)閷?duì)于任意的μ>0，有

為了方便求解，下面我們對(duì)任意的μ>0給出目標(biāo)函數(shù)

(4)

則有下面定理成立.

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

算法2.1

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

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

xk+1=xk+αkdk.

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

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

即

(5)

(6)

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

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

在本節(jié)中，我們將給出數(shù)值實(shí)例來(lái)驗(yàn)證算法的有效性. 我們選取文獻(xiàn)[8]中的兩個(gè)算例進(jìn)行求解. 算法程序用MatlabR2012b在4GB RAM, CPU@1.70GHz 2.40GHz上運(yùn)行.

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

我們知道矩陣A的奇異值大于1，因此該絕對(duì)值方程問(wèn)題存在唯一解.若我們?nèi)ˇ?0.01，e=10-6，設(shè)定初始點(diǎn)為x=(0.5,0.5,0.5,0.5)T，則經(jīng)26次迭代，平均用時(shí)0.0126秒，便可得到該絕對(duì)值方程的唯一解x=(1,1,1,1)T.

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

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

我們?cè)O(shè)定不同的初始點(diǎn)和參數(shù)μ,停止準(zhǔn)則e=1.0e-6，利用本文算法對(duì)算例2進(jìn)行計(jì)算. 結(jié)果表明，我們的算法能在有限步數(shù)內(nèi)獲得問(wèn)題的唯一解. 其具體結(jié)果將在表1和表2中給出.

我們選取文獻(xiàn)[8]中的初始點(diǎn)x0=(10,10,…,10)T，令參數(shù)μ=0.1，停止準(zhǔn)則e=10-6，運(yùn)用我們的算法來(lái)求解算例2，我們將在表3中給出其具體計(jì)算結(jié)果.

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

4結(jié)束語(yǔ)

本文先采用極大熵函數(shù)對(duì)絕對(duì)值方程進(jìn)行光滑化處理，構(gòu)造一個(gè)與絕對(duì)值方程等價(jià)的無(wú)約束優(yōu)化問(wèn)題，然后采用共軛梯度法求解無(wú)約束優(yōu)化問(wèn)題從而獲得原問(wèn)題的解. 數(shù)值實(shí)驗(yàn)表明，本文的算法是可行的，并且適合求解高維的絕對(duì)值方程問(wèn)題. 因此，本文的算法可作為求解絕對(duì)值方程問(wèn)題的一個(gè)有效算法.

[參考文獻(xiàn)]

[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]雍龍泉，拓守恒. 基于凝聚函數(shù)的擬牛頓算法求解絕對(duì)值方程[J]. 系統(tǒng)科學(xué)與數(shù)學(xué)，2012,32(11)，1427-1436.

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

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

[11]李興斯. 一類(lèi)不可微優(yōu)化問(wèn)題的有效解法[J]. 中國(guó)科學(xué)(A 輯)，1994,24(4):371-377.

[12]徐成賢，陳志平，李乃成. 近代優(yōu)化方法[M]. 科學(xué)出版社，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

[基金項(xiàng)目]國(guó)家自然科學(xué)基金項(xiàng)目(11101214)

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

[中圖分類(lèi)號(hào)]O24

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

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