求解張量方程的Levenberg-Marquardt-型方法

王 麗，劉奇龍，段雪峰

(1.山東管理學(xué)院 信息工程學(xué)院，濟(jì)南 250357;2.貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，貴陽 550025；3.桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004)

記所有的m階n維實(shí)張量構(gòu)成的集合為R[m,n]?？紤]如下張量方程：

(1)

張量方程(1)本質(zhì)上是一種特殊的非線性方程F(x)=0，有多種不同的求解方法[8-10]。通?？赊D(zhuǎn)化為非線性最小二乘問題

其中‖·‖為2-范數(shù)。求解非線性最小二乘問題常用的算法有Newton法、LM方法以及信賴域等方法、LM方法是Newton法的改進(jìn)，于1944年Levenberg在文獻(xiàn)[11]中首次提出，隨后Marquardt[12]于1963年重新發(fā)現(xiàn)。LM方法通過引進(jìn)迭代參數(shù)，克服了Jacobi矩陣接近奇異或者壞條件時(shí)Newton法所帶來的困難。將應(yīng)用LM-型方法求解系數(shù)為一般張量的張量方程。數(shù)值算例表明，在某些情況下所給算法優(yōu)于文獻(xiàn)[6]中的LM法。

1 LM-型方法

應(yīng)用LM-型方法求解張量方程(1)。為方便討論，首先給出如下定義和符號(hào)。

(2)

因此，張量方程(1)的解等價(jià)于下面優(yōu)化問題的全局最優(yōu)解，

ai1i2…im=aπ(1)π(2)…π(m), ?π∈Πm,

ai0i1…im-1=ai0iπ(1)…iπ(m-1),?π∈Πm-1，

通過計(jì)算可得F(x)與f(x)的Jacobi矩陣分別為：

(3)

g(x)=f(x)=J(x)TF(x)。

(4)

下面給出求解張量方程(1)的LM-型方法，見算法1。

算法1LM-型方法求解一般張量方程。

1)若k>N，則停止；否則通過式(2)、(3)和(4)計(jì)算

2)若‖gk‖<ε，則停止；否則，轉(zhuǎn)步驟3。

4)若dk滿足‖F(xiàn)(xk+dk)‖<σ‖F(xiàn)k‖，則取αk=1；否則尋找αk滿足如下Armijo條件：

2 收斂性證明

為了方便證明算法1的收斂性，引入局部誤差界的定義及一些引理。

定義1設(shè)X*為F(x)的解集，N?Rn且滿足N∩X*≠?,若存在常數(shù)c>0，使得

‖F(xiàn)(x)‖≥c·dist(x,X*)， ?x∈N，

則稱F(x)在N內(nèi)有局部誤差界，其中dist(xk,X*)=infyk∈X*‖xk-yk‖。

引理1[6]設(shè)F(x)與J(x)如式(2)與式(3)所示，則F(x)連續(xù)可微，且F(x)與J(x)在

N(x*,r1)={x|‖x-x*‖

內(nèi)Lipschilz連續(xù)，即存在常L1、L2>0,r1<1，使得對(duì)?x,y∈N(x*,r1)，均有

‖F(xiàn)(y)-F(x)‖≤L1‖y-x‖,

‖J(y)-J(x)‖≤L2‖y-x‖。

由引理1和文獻(xiàn)[13]可得如下引理。

引理2若xk∈N(x*,r1)，則算法1產(chǎn)生的迭代點(diǎn)列{xk}收斂于張量方程(1)的解x*。

引理3[13]設(shè){dk}為算法1得到的序列。若xk∈N(x*,r1),則存在常數(shù)c1>0，使得

‖dk‖≤c1dist(xk,X*)。

引理4[14]設(shè){Jk}為算法1得到的序列。若迭代點(diǎn)列{xk}收斂于張量方程(1)的解x*，則Jk有如下形式的奇異值分解

(5)

其中rank(Σ1)=rank(J(x*)),且rank(Σ2)≥0,Σ3=0。

定理1若初始向量x0在誤差界內(nèi)收斂于張量方程(1)的解x*，則算法1產(chǎn)生的迭代點(diǎn)列{xk}二階收斂于x*。

證明利用式(5)與引理5的奇異值分解，得到當(dāng)前迭代步，

其中，

(6)

(7)

又因?yàn)?/p>

根據(jù)引理1、引理5與式(7)可知，

cL2‖xk-x*‖2=

c1dist(xk+1,X*)≤‖F(xiàn)k+Jkdk‖+O(‖dk‖2)≤

對(duì)所有充分大的k，都有

根據(jù)引理4，可得

‖dk+1‖=O(‖dk‖2)。

因此

‖xk+1-x*‖=O(‖xk-x*‖2)。

即{xk}二次收斂于x*。證畢。

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

選取幾個(gè)例子運(yùn)用算法1進(jìn)行數(shù)值實(shí)驗(yàn)。所有的數(shù)值實(shí)驗(yàn)都在配置為Intel(R) Core(TM) i5-6200U CPU @ 2.40 GHz的計(jì)算機(jī)中使用Matlab 2015b運(yùn)行。選取容許誤差界ε=10-5，最大迭代次數(shù)N=20。

b=(x*)m-1，

表1 比較算法1和文獻(xiàn)[6]中LM算法的數(shù)值結(jié)果

用算法1求解一個(gè)4階20維的一般張量方程。在局部誤差界的條件下，繪制絕對(duì)誤差與迭代次數(shù)的關(guān)系如圖1所示。從圖1可看出，算法1是二次收斂的。

圖1 LM-型二次收斂可視化

算法1也可求解形如

其中x*=5ones(n,1)，選取初始向量x0=2ones(n,1)，用算法1求解廣義的張量方程

數(shù)值實(shí)驗(yàn)結(jié)果見表2。該實(shí)驗(yàn)表明，算法1對(duì)解決一類廣義三階的張量方程是有效的。

表2 選取不同維數(shù)的廣義張量方程的數(shù)值結(jié)果

4 結(jié)束語