求解張量絕對(duì)值方程的兩步非精確Levenberg-Marquardt算法

馬昌鳳，謝亞君

（福州外語(yǔ)外貿(mào)學(xué)院 大數(shù)據(jù)學(xué)院 數(shù)字技術(shù)與智能計(jì)算重點(diǎn)實(shí)驗(yàn)室，福建 福州 350202）

0 引言

考慮如下的張量絕對(duì)方程（TAVE）：尋找向量x∈Rn滿足

其中A∈T(m，n)且m為偶數(shù)，b∈Rn為已知向量。這里T(m，n)表示m階n維實(shí)張量的集合，向量|x|[m-1]定義為

當(dāng)m=2 時(shí)，方程（1）退化為下面的（向量）絕對(duì)值方程（AVE）：

絕對(duì)值方程在物理和經(jīng)濟(jì)均衡問題等應(yīng)用科學(xué)技術(shù)中有著廣泛的應(yīng)用［1］。關(guān)于方程（2）的數(shù)值算法，已經(jīng)存在大量研究工作，可參見文獻(xiàn)［2-8］。

本文將證明張量絕對(duì)值方程（1）等價(jià)于廣義張量互補(bǔ)問題，然后通過引入互補(bǔ)函數(shù)將張量互補(bǔ)問題轉(zhuǎn)化為等價(jià)的非線性方程組。我們將在有關(guān)研究工作的基礎(chǔ)上提出兩步非精確Levenberg-Marquardt 算法（簡(jiǎn)記為L(zhǎng)M 算法）來(lái)求解該非線性方程組。在適當(dāng)?shù)募僭O(shè)條件下證明該方法的全局收斂性，并討論它的收斂率，利用數(shù)值實(shí)驗(yàn)驗(yàn)證所做的理論分析。

1 兩步非精確LM算法

本節(jié)，我們首先證明TAVE（1）等價(jià)于廣義張量互補(bǔ)問題。首先介紹如下定義。

定義1一個(gè)m階n維張量A稱為對(duì)稱張量，若成立

式中Πm表示m個(gè)指標(biāo)i1i2…im的置換群。

定義2設(shè)A是m階n維實(shí)張量，x，b∈Rn。定義

這里，I是m階n維單位張量，廣義張量互補(bǔ)問題就是尋找向量x∈Rn滿足

定理1設(shè)A∈T(m，n)，b∈Rn，其中m為偶數(shù)，那么TAVE（1）等價(jià)于廣義張量互補(bǔ)問題（3）。

證明事實(shí)上，由于

因此，由（1）可得：

這就意味著x是（3）的可行解。因?yàn)?/p>

這就完成了定理證明。

利用Fischer-Burmeister 函數(shù)φFB，可以將（3）再生為如下方程：

這里，x是（3）的解當(dāng)且僅當(dāng)H(x)=0。進(jìn)一步，由于H(x)各個(gè)分量函數(shù)是強(qiáng)半光滑的，所以H(x)是強(qiáng)半光滑的（參見文獻(xiàn)［9］）。

定理2設(shè)A是m階n維對(duì)稱張量，則函數(shù)H(x) 是強(qiáng)半光滑的。進(jìn)一步對(duì)任意的x∈Rn，有

其中Da(x)=diag(ai(x))，Db(x)=diag(bi(x))是n×n對(duì)角矩陣，對(duì)應(yīng)元素

這里?φFB(Fi(x)，Gi(x))是?φFB(a，b)中的(a，b)由(Fi(x)，Gi(x))替換，并且JF(x)和JG(x)由下式給出：

為了給出求解H(x)=0 的算法，定義如下的價(jià)值函數(shù)：

接下來(lái)給出價(jià)值函數(shù)的一個(gè)性質(zhì)：

性質(zhì)1設(shè)A是m階n維對(duì)稱張量，則價(jià)值函數(shù)Ψ(x) 是連續(xù)可微的并且對(duì)任意的Q∈?H(x)，有

最近，許多專家學(xué)者在LM 算法的試探步和LM 參數(shù)的選擇上進(jìn)行研究。例如文獻(xiàn)［10］中提出了一種修正LM 方法，使用了如下的LM近似步：

其中Fk=F(xk)，。在局部誤差界條件下，可證明其具有三次收斂性。

Argyros 和Chen 提出了Chebyshev 方法（文獻(xiàn)［11］），在每步迭代計(jì)算：

其中p∈(0，1]是一個(gè)常數(shù)，那么可得到

結(jié)合（4）可導(dǎo)出如下修正Chebyshev 方法：

注意到，當(dāng)Jacobi 矩陣是奇異或接近奇異，（4）、（6）中的dk和k不能很好地定義。為了克服這個(gè)困難，Levenberg-Marquardt 算法計(jì)算如下的步長(zhǎng)：

其中LM 參數(shù)λk是非負(fù)的，且當(dāng)接近奇異時(shí)能阻止步長(zhǎng)過大。目前已經(jīng)有很多學(xué)者研究參數(shù)λk，并分析算法的收斂性。例如，Yamashita和Fukushima 選擇λk=||Fk||2，在局部誤差有界的條件下證明了其二次收斂性［13］。Fan 和Yuan選擇λk=||Fk||δ，δ∈[1，2]，證明了算法仍保留二次收斂性，并且在λk=||Fk|| 時(shí)實(shí)驗(yàn)效果最好［14］。但是，當(dāng)?shù)蛄芯嚯x方程的解較遠(yuǎn)時(shí)，該算法的迭代結(jié)果并不令人滿意。為避免該缺陷，文獻(xiàn)［15］進(jìn)一步提出λk=μk||Fk||，μk＞0，利用信賴域技術(shù)證明了它的收斂性，數(shù)值結(jié)果表明其具有較好的收斂性質(zhì)。但當(dāng)?shù)蛄羞h(yuǎn)離方程的解集時(shí)，λk=μk||Fk||的值可能會(huì)比較大，這會(huì)導(dǎo)致LM 嘗試步長(zhǎng)dk非常小，以致算法的效率可能很低。基于上述考慮，文獻(xiàn)［16］考慮了新的參數(shù)：

這種選擇方式避免了上面提到的不足。目前，LM 方法及其變形修正在求解非線性方程、非線性互補(bǔ)問題及無(wú)約束優(yōu)化和約束優(yōu)化問題等方面均有廣泛應(yīng)用。

受Chebyshev 方法的啟發(fā)，本文提出兩步LM 方法用于求解張量絕對(duì)值方程，在每步計(jì)算

來(lái)獲得步長(zhǎng)dk，μk＞0 隨著步長(zhǎng)的更新而更新。不難發(fā)現(xiàn)，步長(zhǎng)dk也是如下凸極小化問題的極小解：

則易證明dk是如下信賴域子問題的解

考慮如下兩步迭代

其中yk=xk+dk。為了提高數(shù)值性能，用Qk代替Q(yk)來(lái)避免計(jì)算新的Jacobi 矩陣Q(yk)，并提出Hk和H(zk)的凸組合代替H(yk)，即

其中θ=1/α且α≥1。因此可得到

預(yù)估下降量要求非負(fù)，根據(jù)文獻(xiàn)［17］可得

結(jié)合（10）和（11），定義如下兩步預(yù)下降

基于以上分析，提出以下兩步非精確LM算法。

算法1（兩步非精確LM 算法）

步0 給定初始點(diǎn)x0，令μ0＞m＞0，0 ＜γ0≤γ1＜γ2＜1，α＞1，ε＞0，置k?0。

步1 若||H(xk)||≤ε，停算。否則，計(jì)算Qk∈?H(xk)。

步2 計(jì)算LM 參數(shù)

步3 非精確求解方程組

得到dk，其中k為非精確求解的控制閾值。置zk=xk+αdk。

步4 計(jì)算

步5 非精確求解方程組

步6 計(jì)算下降比

其中Aredk和Predk分別如（9）和（12）所定義。

步7 選擇μk+1為

步8 置k?k+1，轉(zhuǎn)步1。

下面分析算法1 的全局收斂性，假設(shè)算法1生成無(wú)限序列｛xk｝。類似于文獻(xiàn)［18］定理2.1和定理2.2 的證明，可以得到如下的兩個(gè)定理。

定理3設(shè){xk}是由算法1 生成的序列，如果殘差向量k，k滿足如下條件：

其中η∈(0，1)，νk=o(dist(xk，X*))，其中X*是信賴域問題的解集，δ∈[ 1，2 )，那么對(duì)任意{xk}的聚點(diǎn)是價(jià)值函數(shù)Ψ 的穩(wěn)定點(diǎn)。進(jìn)一步，如果{xk}的聚點(diǎn)x*是H(x)=0 的 解，則{dist(xk，X*)}超線性收斂到0。

定理4設(shè){xk}是由算法1 生成的序列，δ=2。若殘差向量k，滿足如下條件：

其中η∈(0，1)，νk=O(dist(xk，X*)2)，則{xk}的任意聚點(diǎn)都是價(jià)值函數(shù)Ψ 的穩(wěn)定點(diǎn)。進(jìn)一步，如果{xk} 的聚點(diǎn)x*是H(x)=0 的解，則{dist(xk，X*)}二次收斂到0。

下面再對(duì)算法1 做一些說(shuō)明。在算法1 的執(zhí)行過程中，主要計(jì)算（13）、（14）當(dāng)k=k=0 時(shí)的近似值。注意到方程總是可解的。事實(shí)上，由于λk＞0，那么矩陣是對(duì)稱正定矩陣，因此（13）和（14）一定可解?，F(xiàn)在考慮如何計(jì)算Qk∈?H(xk)，我們選擇在第k步迭代，通過定理2，矩陣Qk∈?H(xk)的元素可以通過如下公式計(jì)算。令

是一個(gè)退化指數(shù)集合，定義z∈Rn是一個(gè)向量，若i∈Λ，其分量zi=1；否則zi=0，那么矩陣Qk可以如下定義

其中A(xk)和B(xk)是n×n對(duì)角矩陣，其第i個(gè)對(duì)角元素可分別如下給出

后面實(shí)驗(yàn)部分計(jì)算Qk用這個(gè)公式。

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

本節(jié)，將用一個(gè)數(shù)值算例來(lái)說(shuō)明用算法1求解張量絕對(duì)值方程（TAVE）的可行性及有效性。數(shù)值實(shí)驗(yàn)在MATLAB R2018b 軟件上運(yùn)行，PC 機(jī)的運(yùn)行環(huán)境為2.40 GHz 中央處理器，8.0 GB 內(nèi)存以及Windows 10 操作系統(tǒng)。

在整個(gè)計(jì)算實(shí)驗(yàn)中，算法1 使用的參數(shù)，取ε=10-4，γ0=10-5，γ1=0.25，γ2=0.75，m=10-5，μ0=10.0。終止條件為||H(xk)||≤ε。

例1首先隨機(jī)生成一個(gè)四階四維的張量，其元素屬于[0，1]，然后將其對(duì)稱化得到非負(fù)張量B。令

其 中e=(1，1，1，1)T，a∈(0，+∞)。因 為，這樣c的選擇確保c＞ρ(B)+1，那么令A(yù)=cI-B滿足A-I是強(qiáng)M 張量。張量B和張量A見表1 和表2。

表1 隨機(jī)對(duì)稱非負(fù)張量B=(bi1 i2 i3 i4)∈S(4，4)Table 1 Random symmetric non-negative tensors B=(bi1 i2 i3 i4)∈S(4,4)

表2 基于張量B的對(duì)稱張量A=(ai1 i2 i3 i4)∈S(4，4)Table 2 Symmetric tensors A=(ai1 i2 i3 i4)∈S(4，4) based on tensor B

這個(gè)例子主要用于觀察算法1 的迭代過程。隨機(jī)生成對(duì)稱張量B∈S[4，4] 和隨機(jī)向量x*∈R4且張量B和向量x*元素取值均在[0，1]。為了確保方程只有唯一的解，計(jì)算b=A(x*)3-|x*|[3]，這里取a=3，從而計(jì)算出c=4.899 8。算法1 的迭代過程參見表3。從表3 可以看到||H(xk)||隨著迭代次數(shù)k的增加會(huì)快速趨于0。此外，||?Ψ(xk)||隨著迭代次數(shù)k的增加亦會(huì)快速趨于0，這說(shuō)明了算法具有良好的收斂性。

表3 算法1的迭代過程Table 3 The iterative process of Algorithm 1

此外，選擇不同的b值來(lái)測(cè)試算法的收斂結(jié)果。實(shí)驗(yàn)中式（15）中的參數(shù)a取為15，數(shù)值結(jié)果見表4，其中xs表示方程的解，Iter 表示迭代次數(shù)。

表4 不同b值下算法1收斂效果Table 4 Convergence effect of Algorithm 1 under different b values

3 結(jié)論

本文提出了求解張量絕對(duì)值方程的一個(gè)兩步非精確LM 算法。在適當(dāng)?shù)臈l件下得到了該算法的收斂性定理。數(shù)值實(shí)驗(yàn)結(jié)果表明，所提出的算法是行之有效的。