盛 洲，袁功林，冀祥麟

(廣西大學數(shù)學與信息科學學院， 廣西南寧530004)

解絕對值方程的廣義信賴域算法

盛 洲，袁功林，冀祥麟

(廣西大學數(shù)學與信息科學學院， 廣西南寧530004)

絕對值方程；信賴域算法；廣義Jacobian矩陣；全局收斂性

0 引 言

考慮具有如下形式的一類絕對值方程(absolute value equations, AVE)：

(1)

其中

且A,b為給定的已知常量矩陣或向量。

一般地，式(1)按照矩陣的計算原則化簡，可得到:

其中，n為分量的個數(shù)，fi(x1,x2,…,xn)為化簡后矩陣的分量，i=1,2,…,n。即絕對值方程等價于下列形式的非線性方程組:

(2)

g(x)=diag(sign(x)),

絕對值方程是由Rohn在文獻[3]中首次提出的，并且討論了式(1)的解的存在性和唯一性[4]，隨后有許多學者對該問題進行了研究。Mangasarian在文獻[5]中證明了AVE的求解是一個不可微的NP-hard的優(yōu)化問題。在文獻[6]中，Mangasarian證明了式(1)與線性互補問題等價，線性互補問題是應用科學和工程中一類重要的問題。陳玥琪[7]提出的用光滑牛頓算法求解絕對值方程；Wang等[8]提出的求解絕對值方程的區(qū)間算法；雍龍泉等[9]的擬牛頓算法求解絕對值方程；Mangasarian在文獻[10]和文獻[11]分別提出廣義牛頓法和通過凹極小化優(yōu)化求解絕對值方程；Yong[12]提出了一個迭代算法，通過有限次迭代得到絕對值方程的近似解；Zhang等[13]證明了求解絕對值方程的廣義牛頓法的全局收斂性；在文獻[14]中，Caccetta等提出了一個具有全局收斂性和二次收斂速率的光滑牛頓法求解絕對值方程。更多求解絕對值方程的方法參見文獻[15]～文獻[19]。

信賴域方法最早由Powell[20]提出，由于其具有強收斂性和穩(wěn)定性等優(yōu)點，在求解非線性優(yōu)化問題中已經(jīng)被證明是十分有效的方法之一。對于求解非線性方程組問題，Yuan[21]證明了信賴域算法具有全局收斂性，信賴域算法在非線性方程組問題中應用分析見文獻[22]～文獻[25]。貫穿全文，‖·‖表示歐幾里得范數(shù)。

1 信賴域算法

首先，根據(jù)文獻[6]中性質(zhì)3和性質(zhì)4，給出一些絕對值方程的基本結(jié)論。

引理1 ①若A∈Rn×Rn,且A的所有奇異值都大于1，則對任意的b∈Rn,絕對值方程存在唯一解；

②若A∈Rn×Rn,且‖A-1‖<1,則對任意的b∈Rn,絕對值方程存在唯一解。

引理2 若A∈Rn×Rn,且A的所有奇異值都大于1，那么對于任意的對角元素是1或-1或0的g,A-g都是可逆的。

對于非線性方程組問題(2)，將其轉(zhuǎn)化為一個與之等價的無約束優(yōu)化問題來求解，即:

(3)

對于信賴域方法，在每個迭代點xk,通過求解下列信賴域子問題得到試探步dk:

(4)

其中Fk=F(xk),Jk=J(xk),Δk是信賴域半徑。

若dk由信賴域子問題(4)確定，定義實際下降量和預測下降量分別為:

aredk:=φ(xk)-φ(xk+dk),

(5)

predk:=mk(0)-mk(dk),

(6)

其比值為:

(7)

現(xiàn)在，給出求解非線性方程組問題(2)的廣義信賴域算法:

Step 1: 設定初始值，x0∈Rn,0

Step 3: 求解信賴域子問題(4)得到dk；

Step 4: 通過式(5)～式(7)分別求出aredk,predk,rk,通過下列準則更新信賴域半徑:

Step 5: 若rk≥c1,則xk+1:=xk+dk,返回到step 2，令k:=k+1；否則，令xk+1:=xk,返回至step 3，令k:=k+1。

廣義信賴域算法的適定性證明類似于文獻[26]的定理29及推論3，此處省略不證。

引理3 設{xk}是廣義信賴域算法產(chǎn)生的迭代序列，dk是信賴域子問題(4)的解，則{φk}是單調(diào)非增的且算法是適定的。

2 廣義信賴域算法收斂性

本文做如下假設分析廣義信賴域算法的收斂性。

假設1F(x)的所有廣義Jacobian矩陣是一致有界的，即?M>0滿足:

‖Jk‖≤M, ?k∈N+.

假設2 若x*是廣義信賴域算法產(chǎn)生點列{xk}的聚點，J(x*)是非退化的。

引理4 若假設1成立，則:

定理1 若假設1和假設2成立，點列{xk}是算法1產(chǎn)生的。那么，算法1經(jīng)過有限次迭代終止或:

(8)

成立。

證明 注意到引理2，假設1和假設2，若:

(9)

為了證明式(9)成立，本文采用反證法。假設廣義信賴域算法不能有限終止且式(9)不成立，則存在ε>0和無窮多個k滿足:

(10)

(11)

因此:

(12)式(12)表明，當k充分大時，有Δk+1≥Δk。這與式(11)矛盾，由此說明式(10)不成立，定理的結(jié)論成立。

3 數(shù)值實驗

本文在引理1的前提下，隨機生成絕對值方程問題，測試本文廣義Jacobian信賴域方法對求解絕對值方程的有效性。本節(jié)實驗的所有代碼都在CPU為Intel Pentium(R) Dual-Core E5800 3.20 GHz, SDRAM為2.00G bytes的Windows7的操作系統(tǒng)下，使用Matlab R2010b運行測試。實驗中，算法1中的參數(shù)選擇為c1=0.1,c2=0.9,α1=0.25,α2=3,ε=10-10和Δ0=1,初始迭代點x0=rand(n,1),其中n為問題維數(shù)。

實驗中，采用文獻[27]隨機生成絕對值方程的代碼生成n維的隨機算例。實驗的終止條件為‖F(xiàn)(x)‖≤ε或k≥20(n+1),其中k為算法1的迭代次數(shù)。對于信賴域子問題，本文使用Steihaug-Toint方法[28]獲得廣義信賴域每次迭代信賴域子問題的試探步dk。在實驗中，隨機生成并測試了維數(shù)分別n=100,300,500,800,1 000,1 500,2 000的絕對值方程。實驗結(jié)果見表1，表1中n表示問題維數(shù)；k表示廣義信賴域算法求解問題所需的迭代次數(shù)；cput表示求解問題所需時間；tfinal表示求解問題的最優(yōu)值。

從表1中可以看出，廣義信賴域算法可以成功地求解絕對值方程維數(shù)n≤2 000的問題，所需的迭代次數(shù)都比較小，得到的最優(yōu)值也十分接近于0。但同時，也不難發(fā)現(xiàn)，對于維數(shù)n≥500的絕對值方程問題，廣義信賴域算法成功求解問題所耗費的時間是比較大的，這是由于在求解信賴域子問題(4)時，需要用到廣義Jacobian矩陣的信息，然而廣義Jacobian矩陣是n×n維，因此會耗費更多的CPU時間。圖1給出了對于表1中不同維數(shù)的7個絕對值方程問題的φ(x)的值隨迭代次數(shù)變化的折線圖。總之，由表1和圖1可知，對于求解絕對值方程問題，廣義信賴域算法是合適的。

表1 數(shù)值結(jié)果
Tab.1 Numerical results

nkcputtfinal1001088921e-0135698e-133001135303e+0132477e-125001119912e+0277233e-128001199799e+0275561e-1110001127542e+0322458e-1115001214441e+0485761e-1120001458004e+0494748e-11

圖1φ(x)的值隨迭代次數(shù)k的變化圖
Fig.1 Values ofφ(x) with the number of iterations

4 結(jié) 語

(責任編輯 梁碧芬)

A generalized trust region algorithm for absolute value equations

SHENG Zhou，YUAN Gong-lin，JI Xiang-lin

(College of Mathematics and Information Science, Guangxi University, Nanning 530004, China)

Absolute value equations is a non-differentiable NP-hard problem. In this paper, a trust region algorithm with generalized Jacobian matrix of |x| based on a subgradient is proposed. Under mild conditions, the well-definedness and global convergence of the presented algorithm are proved. The numerical results indicate that the proposed algorithm is very effective for solving absolute value equations (with a maximum dimension of 2 000).

absolute value equations; trust region algorithm; generalized Jacobian matrix; global convergence

2016-05-20；

2016-07-22

國家自然科學基金資助項目(11261006)；廣西杰出青年科學基金資助項目(2015GXNSFGA139001)

袁功林(1976—), 男，河南商丘人，廣西大學教授，博士生導師；E-mail:yuangl0417@126.com。

盛洲，袁功林，冀祥麟.解絕對值方程的廣義信賴域算法[J].廣西大學學報(自然科學版)，2016，41(6)：2078-2083.

10.13624/j.cnki.issn.1001-7445.2016.2078

O224

A

1001-7445(2016)06-2078-06