一種求解絕對值方程的非精確Levenberg-Marquardt算法

摘 要：本文首先運(yùn)用一個光滑逼近函數(shù)對絕對值方程進(jìn)行光滑化處理.其次提出了一種非精確光滑化Levenberg-Marquardt算法，并證明了算法具有全局收斂性. 最后給出了數(shù)值實驗證明算法有效性．

關(guān)鍵詞：絕對值方程；非精確Levenberg-Marquardt算法；全局收斂性

中圖分類號：O221.2       文獻(xiàn)標(biāo)識碼：A

絕對值方程AVE（Absolute Value Equation）形式如下：

（1）

這里常數(shù)矩陣，向量，表示對的各個分量取絕對值. 絕對值方程是一個NP-hard問題[1].AVE方程在許多實際應(yīng)用中具有重要的作用，如：半監(jiān)督和無監(jiān)督分類問題、背包可行性問題和選址問題等.在經(jīng)濟(jì)學(xué)中，AVE方程可用于分析市場均衡和最優(yōu)決策等問題.在求解線性規(guī)劃，雙矩陣對策，二次規(guī)劃等問題時需要轉(zhuǎn)化成線性互補(bǔ)問題進(jìn)行處理，而線性互補(bǔ)問題又可以轉(zhuǎn)化為絕對值方程.因此，絕對值方程的研究為許多數(shù)學(xué)規(guī)劃問題提供了一種新的求解途徑，從而對絕對值方程理論及算法的研究具有重要的意義，已成為優(yōu)化領(lǐng)域中的研究熱點(diǎn).

在優(yōu)化算法設(shè)計中，Levenberg-Marquardt算法由Levenberg[2]和Marquardt[3]提出，是求解優(yōu)化問題的一類重要方法，并且此算法在迭代時融合了牛頓法和梯度下降法的優(yōu)點(diǎn)，具有良好的數(shù)值穩(wěn)定性與數(shù)值效果.本文所提出的非精確光滑化Levenberg-Marquardt算法，此算法具有全局收斂性質(zhì)且一般條件下算法有效.

1  光滑函數(shù)和相關(guān)性質(zhì)

定義1 （光滑逼近函數(shù)[4]）給定函數(shù)，我們稱光滑函數(shù)是的光滑逼近函數(shù)，如果對任意的，存在，使得：

這里不依賴于，則稱是的一致光滑逼近函數(shù).

受文獻(xiàn)[5-7]啟發(fā)，下面我們來構(gòu)造的一個新的光滑逼近函數(shù).

記，對每一個，我們采用一種光滑函數(shù)，如下：

進(jìn)行光滑化處理，且

即

這樣就得到絕對值函數(shù)的光滑函數(shù)：

于是有：

即當(dāng)時，一致逼近（從上方逼近）絕對值函數(shù).

引理1  對，是連續(xù)可微的，且

證明 對，可通過對式（2）關(guān)于求導(dǎo)數(shù)直接得到式（5）.

令于是求解絕對值方程（1）等價于求解如下方程：

那么對利用（3）式進(jìn)行光滑化處理，則可得：

定理1  ，一致光滑逼近.

證明  由（4）式知，對，有

由定理可知，一致光滑逼近.

定理2  當(dāng)時，式（7）的解即為式（6）的解.

證明  由定理易知：，得證.

綜上可知，可通過求解光滑方程組得到非光滑方程組的近似解，下面來研究光滑函數(shù)的一些性質(zhì).

定理3  映射是連續(xù)可微的，記的Jacobian矩陣為，則有：

其中

2  非精確光滑化Levenberg-Marquardt算法

為了求解問題（7），我們現(xiàn)在給出一個非精確光滑化Levenberg-Marquardt算法. 通過函數(shù)可以定義一個效益函數(shù)如下：

且其梯度如下：

算法

步驟0  選取參數(shù)；.選取初始點(diǎn)，令.

步驟1  如果，則終止.否則，令，計算

步驟2  若下式成立

則，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟3.

步驟3  計算步長滿足：

令，轉(zhuǎn)步驟1.

步驟4  令，，轉(zhuǎn)到步驟1.

3  算法的收斂性分析

定理4  由算法生成的序列，的任一聚點(diǎn)是的穩(wěn)定點(diǎn).

證明  因為，，有

所以由（9）式、（10）式可知：單調(diào)遞減，且也單調(diào)遞減.

當(dāng)時，有：.因此，的任一聚點(diǎn)都是的解.

當(dāng)時，有：，所以.由文獻(xiàn)[8]知，對充分大的有下式成立

因此

所以，且.那么是的穩(wěn)定點(diǎn).

4  數(shù)值實驗

為了測試算法的性能，本節(jié)進(jìn)行數(shù)值實驗.算法中的參數(shù)取值如下：

算例1[9]  考慮絕對值方程

最優(yōu)解：.

試驗結(jié)果見表1

本文首先將求解非光滑的絕對值方程問題轉(zhuǎn)化為求解光滑方程組問題，給 出一個非精確光滑的Levenberg-Marquardt算法并對其進(jìn)行收斂性分析.最后結(jié)合相關(guān)的數(shù)值實驗證明算法的有效性．

參考文獻(xiàn)：

[1] O. L. Mangasarian. Absolute value programming[J]. Computaional Optimization and Applications， 2007， 36（1）： 43-53.

[2] K. Levenberg. A method for the solution of certain nonlinear problems in least squares[J]. Quarterly Applied Mathematics， 1944， 2（2）： 164-166.

[3] D. W. Marquardt. An algorithm for least-squares estimation of nonlinear inequalities[J]. SIAM Journal on Applied Mathematics， 1963， 11（2）： 431-441.

[4] 韓繼業(yè)， 修乃華， 戚厚鐸. 非線性互補(bǔ)理論與算法[M]. 上海：上海科學(xué)技術(shù)出版社， 2006.

[5] 雍龍泉. 神經(jīng)網(wǎng)絡(luò)方法求解絕對值方程及線性互補(bǔ)[J]. 陜西理工大學(xué)學(xué)報（自然科學(xué)版）， 2020， 36（05）： 72-81.

[6] 雍龍泉， 賈偉， 黎延海. 基于光滑逼近函數(shù)的高階牛頓法求解凸二次規(guī)劃[J]. 科學(xué)技術(shù)與工程， 2021， 21（06）： 2151-2156.

[7] 雍龍泉. 一致光滑逼近函數(shù)及其性質(zhì)[J]. 陜西理工大學(xué)學(xué)報（自然科學(xué)版）， 2018， 34（1）： 74-79．

[8] 梁娜， 杜守強(qiáng). 非精確線搜索條件下求解絕對值方程問題的Levenberg-Marquardt方法[J].江蘇師范大學(xué)學(xué)報（自然科學(xué)版）， 2017， 35（04）： 46-48.

[9] 雍龍泉. 神經(jīng)網(wǎng)絡(luò)方法求解絕對值方程及線性互補(bǔ)[J]. 陜西理工大學(xué)學(xué)報（自然科學(xué)版）， 2020， 36（05）： 72-81.

基金項目：安徽省高等學(xué)?？茖W(xué)研究項目（自然科學(xué)）重點(diǎn)項目“絕對值方程的算法及其應(yīng)用研究”（課題編號：2023AH052042）

*通訊作者：趙琪（1991-），女，漢族，安徽淮北人，碩士，淮北理工學(xué)院 教育學(xué)院，助教，研究方向：優(yōu)化理論與計算、金融優(yōu)化。（剩余730字）