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

馬昌鳳，謝亞君

（福州外語外貿學院 大數據學院 數字技術與智能計算重點實驗室，福建 福州 350202）

0 引言

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

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

當m=2 時，方程（1）退化為下面的（向量）絕對值方程（AVE）：

絕對值方程在物理和經濟均衡問題等應用科學技術中有著廣泛的應用［1］。關于方程（2）的數值算法，已經存在大量研究工作，可參見文獻［2-8］。

本文將證明張量絕對值方程（1）等價于廣義張量互補問題，然后通過引入互補函數將張量互補問題轉化為等價的非線性方程組。我們將在有關研究工作的基礎上提出兩步非精確Levenberg-Marquardt 算法（簡記為LM 算法）來求解該非線性方程組。在適當的假設條件下證明該方法的全局收斂性，并討論它的收斂率，利用數值實驗驗證所做的理論分析。

1 兩步非精確LM算法

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

定義1一個m階n維張量A稱為對稱張量，若成立

式中Πm表示m個指標i1i2…im的置換群。

定義2設A是m階n維實張量，x，b∈Rn。定義

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

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

證明事實上，由于

因此，由（1）可得：

這就意味著x是（3）的可行解。因為

這就完成了定理證明。

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

這里，x是（3）的解當且僅當H(x)=0。進一步，由于H(x)各個分量函數是強半光滑的，所以H(x)是強半光滑的（參見文獻［9］）。

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

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

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

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

接下來給出價值函數的一個性質：

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

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

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

Argyros 和Chen 提出了Chebyshev 方法（文獻［11］），在每步迭代計算：

其中p∈(0，1]是一個常數，那么可得到

結合（4）可導出如下修正Chebyshev 方法：

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

其中LM 參數λk是非負的，且當接近奇異時能阻止步長過大。目前已經有很多學者研究參數λk，并分析算法的收斂性。例如，Yamashita和Fukushima 選擇λk=||Fk||2，在局部誤差有界的條件下證明了其二次收斂性［13］。Fan 和Yuan選擇λk=||Fk||δ，δ∈[1，2]，證明了算法仍保留二次收斂性，并且在λk=||Fk|| 時實驗效果最好［14］。但是，當迭代序列距離方程的解較遠時，該算法的迭代結果并不令人滿意。為避免該缺陷，文獻［15］進一步提出λk=μk||Fk||，μk＞0，利用信賴域技術證明了它的收斂性，數值結果表明其具有較好的收斂性質。但當迭代序列遠離方程的解集時，λk=μk||Fk||的值可能會比較大，這會導致LM 嘗試步長dk非常小，以致算法的效率可能很低?；谏鲜隹紤]，文獻［16］考慮了新的參數：

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

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

來獲得步長dk，μk＞0 隨著步長的更新而更新。不難發現，步長dk也是如下凸極小化問題的極小解：

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

考慮如下兩步迭代

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

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

預估下降量要求非負，根據文獻［17］可得

結合（10）和（11），定義如下兩步預下降

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

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

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

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

步2 計算LM 參數

步3 非精確求解方程組

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

步4 計算

步5 非精確求解方程組

步6 計算下降比

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

步7 選擇μk+1為

步8 置k?k+1，轉步1。

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

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

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

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

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

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

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

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

后面實驗部分計算Qk用這個公式。

2 數值實驗

本節，將用一個數值算例來說明用算法1求解張量絕對值方程（TAVE）的可行性及有效性。數值實驗在MATLAB R2018b 軟件上運行，PC 機的運行環境為2.40 GHz 中央處理器，8.0 GB 內存以及Windows 10 操作系統。

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

例1首先隨機生成一個四階四維的張量，其元素屬于[0，1]，然后將其對稱化得到非負張量B。令

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

表1 隨機對稱非負張量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的對稱張量A=(ai1 i2 i3 i4)∈S(4，4)Table 2 Symmetric tensors A=(ai1 i2 i3 i4)∈S(4，4) based on tensor B

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

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

此外，選擇不同的b值來測試算法的收斂結果。實驗中式（15）中的參數a取為15，數值結果見表4，其中xs表示方程的解，Iter 表示迭代次數。

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

3 結論

本文提出了求解張量絕對值方程的一個兩步非精確LM 算法。在適當的條件下得到了該算法的收斂性定理。數值實驗結果表明，所提出的算法是行之有效的。