求解絕對(duì)值方程的光滑化同倫方法

劉子立，　王秀玉

(長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長(zhǎng)春　130012)

?

求解絕對(duì)值方程的光滑化同倫方法

劉子立，王秀玉*

(長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長(zhǎng)春130012)

摘要：先構(gòu)造絕對(duì)值函數(shù)光滑化函數(shù),利用此光滑化函數(shù)對(duì)絕對(duì)值方程Ax-|x|=b建立同倫方程，用逆像定理證明同倫路徑的存在性，用一維流形分類定理證明了同倫路徑的收斂性,得到該光滑同倫路徑的極限點(diǎn)就是絕對(duì)值方程的解。

關(guān)鍵詞：絕對(duì)值方程; 同倫方法; 同倫路徑

0引言

絕對(duì)值方程Ax-|x|=b,其中,A∈Rn×n,x∈Rn,b∈Rn是非線性方程組的一種推廣,其來(lái)源于線性互補(bǔ)問(wèn)題。首先由Rohn J[1]提出絕對(duì)值方程，隨后，由學(xué)者M(jìn)angasarian O L[2]指出求解絕對(duì)值方程是NP-hard的。Caccetta L[3]利用磨光技術(shù)將|x|磨光，把絕對(duì)值方程轉(zhuǎn)化為光滑化問(wèn)題來(lái)解決。

在實(shí)際計(jì)算中，轉(zhuǎn)化絕對(duì)值方程、改進(jìn)算法、弱化條件是一類重要問(wèn)題。文獻(xiàn)[4-6]詳細(xì)地介紹用同倫方法求解互補(bǔ)問(wèn)題，但是，用組合同倫方法直接求解絕對(duì)值方程的文獻(xiàn)未見(jiàn)發(fā)表。文中基于這一點(diǎn)，構(gòu)造絕對(duì)值函數(shù)光滑化函數(shù)，利用光滑化函數(shù)建立同倫方程，證明同倫路徑的一些性質(zhì)，最后得到絕對(duì)值方程的準(zhǔn)確解。

1預(yù)備知識(shí)

引理1[7]同倫算法的基本原理。

1)求方程組F(x)=0的解，其中F(x)滿足條件：

2)選擇很容易求解的方程組:

G(x)=0

其中G(x)滿足條件：

3)構(gòu)造同倫方程組:

觀察3)中所構(gòu)造的同倫方程組，同倫參數(shù)t的取值范圍是[0,1]，當(dāng)t=0時(shí)，同倫方程組所得到的解就是2)中方程組的解，當(dāng)t=1時(shí)，同倫方程組所得到的解就是要求得的1)中方程組的解。

引理2[8](逆像定理)設(shè)φ是U?Rn→Rp的一個(gè)Cα(α>max{0,m-k})映射，如果0是φ的一個(gè)正則值，那么φ-1(0)由一些n-p維Cα流形組成。

引理3[8](一維流形分類定理)一維帶邊光滑流形的每個(gè)連通分支，或者微分同胚于單位圓周，或者微分同胚于區(qū)間(0,1]或(0,1)或[0,1]。

定義1[9]設(shè)f:D?Rm→Rn是光滑映射，且n≤m，則對(duì)任意y∈Rn，記f-1(y)為在映射下的逆象，即f-1(y)={x∈D|f(x)=y}。對(duì)D中的某一點(diǎn)x0，如果f在x0處的Jacobi矩陣行滿秩，則稱是映射f的正則值(注:不符合正則值點(diǎn)定義的點(diǎn)稱為臨界點(diǎn))。

2主要結(jié)果

條件1:

A-(1-t)D可逆。

證:必要性:

若[A-E,A+E]正則，由于A-(1-t)D∈[A-E,A+E]，因此A-(1-t)D可逆。

充分性:

記

i≠j

當(dāng)bii∈[aii-1,aii]時(shí)，?t∈[0,1],使得

di=1

當(dāng)bii∈[aii,aii+1]時(shí)，

di=-1

因此，總有bii=aii-(1-t)di，從而有B=A-(1-t)D可逆。

即條件1成立，證畢。

構(gòu)造同倫方程如下:

(1)

當(dāng)t=1時(shí)，同倫方程(1)有唯一解

當(dāng)t=0時(shí)，同倫方程(1)即為絕對(duì)值方程。

對(duì)給定的x(0)，同倫方程(1)也記為Hx(0)(x,t)，并記

引理6若條件1成立且H由式(1)定義，則Γx(0)是一條有界曲線。

證明:Γx(0)的存在性已由引理6獲得。反證，假設(shè)Γx(0)無(wú)界，則必存在點(diǎn)列

使得

因tk∈[0,1]，{tk}必存在收斂子列，仍記為{tk}，記

由式(1)可得:

(2)

(3)

記

式(3)兩邊取極限得:

(4)

由式(4)及A可逆，‖(x(*)‖=1，知t*≠1。

記

D=diag(di)

由式(4)得

(5)

由條件1及式(5)得x(*)=0，此與‖x(*)‖=1相矛盾，所以Γx(0)有界。

證明:由引理5、6知Γx(0)是有界曲線,由一維流形分類定理知Γx(0),或者微分同胚于單位圓周、或者微分同胚于單位區(qū)間。

由

其中

可逆。知Γx(0)微分同胚于單位區(qū)間,記(x(*),t*)為Γx(0)的極限點(diǎn)，只能下列3種情況出現(xiàn):

1)t*=1,x(*)∈Rn。

2)t*∈(0,1),x(*)∈?Rn。

3)t*=0,x(*)∈Rn。

H(x(0),x(0),1)=0有唯一解，情況1)不可能出現(xiàn)，由引理6知2)不可能出現(xiàn)，因此只能是3)成立。由此證明了Γx(0)的收斂性，由同倫方程組(1)知Γx(0)極限點(diǎn)為絕對(duì)值方程的解。

參考文獻(xiàn)：

[1]Rohn J. Atheorem of the alternatives for the equatinAx+B|x|=b[J]. Linear Mnltilinear Algetra,2004,52:421-426.

[2]MangasarianOL,MeyerRR.Absolutevalueequation[J].LinearAlgetraAppl.,2006,419:359-367.

[3]CaccettaL,QuB,ZhouGL.Agloballyandquadraticallyconvergentmethodforabslutevalueequations[J].ComputeOptimAppl.,2009,48:45-58.

[4]王秀玉，姜興武，劉慶懷.求解互補(bǔ)問(wèn)題的新同倫算法[J].吉林大學(xué)學(xué)報(bào):理學(xué)版，2012，50(3)：494-499.

[5]姜興武，王秀玉.P0線性互補(bǔ)問(wèn)題的新同倫方法[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版，2013,51(5)：807-810.

[6]楊泰山，姜興武，王秀玉.線性互補(bǔ)問(wèn)題解的存在性[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版，2013,51(6)：1063-1067.

[7]田金燕.兩種改進(jìn)的同倫分析方法[D].哈爾濱：哈爾濱理工大學(xué)應(yīng)用科學(xué)學(xué)院，2014.

[8]李海洋.基于改進(jìn)的同倫法求解非線性方程[D].鞍山：遼寧科技大學(xué)理學(xué)院，2013.

[9]趙雅玲，申海明，王秀玉.法錐條件下非凸非線性優(yōu)化問(wèn)題的同倫算法[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，31(6)：613-616.

A smoothing homotopy method for the absolute value equation

LIU Zili,WANG Xiuyu*

(School of Basic Sciences, Changchun University of Technology, Changchun 130012， China)

Abstract：First we construct a smoothing function for absolute function. With the smoothing function, we propose a homotopy formula for the absolute equation Ax-|x|=b. The inverse theorem is used to prove the existence of the homotopy path and one-dimensional manifold theorem the convergence. We can come to the conclusion that the limit point of the smooth homotopy path is the solution of the absolute equation.

Key words：absolute value equation; homotopy algorithm; homotopy path.

中圖分類號(hào)：O 221

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-1374(2016)01-0095-03

DOI:10.15923/j.cnki.cn22-1382/t.2016.1.19

作者簡(jiǎn)介：劉子立(1989-)，男，漢族，內(nèi)蒙古興安盟阿爾山人，長(zhǎng)春工業(yè)大學(xué)碩士研究生，主要從事最優(yōu)化理論與算法方向研究,E-mail:1271372108@qq.com. *通訊作者：王秀玉(1965-)，女，漢族，吉林長(zhǎng)春人，長(zhǎng)春工業(yè)大學(xué)教授，碩士，主要從事最優(yōu)化理論與算法方向研究,E-mail:1062775175@qq.com.

基金項(xiàng)目：吉林省自然科學(xué)基金資助項(xiàng)目(201215128)

收稿日期：2015-10-08