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

趙琪 葛康康

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

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

中圖分類號：O221.2? ? ? ?文獻標識碼：A

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

（1）

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

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

1? 光滑函數和相關性質

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

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

受文獻[5-7]啟發，下面我們來構造的一個新的光滑逼近函數.

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

進行光滑化處理，且

即

這樣就得到絕對值函數的光滑函數：

于是有：

即當時，一致逼近（從上方逼近）絕對值函數.

引理1? 對，是連續可微的，且

證明 對，可通過對式（2）關于求導數直接得到式（5）.

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

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

定理1? ，一致光滑逼近.

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

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

定理2? 當時，式（7）的解即為式（6）的解.

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

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

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

其中

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

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

且其梯度如下：

算法

步驟0? 選取參數；.選取初始點，令.

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

步驟2? 若下式成立

則，轉步驟4；否則，轉步驟3.

步驟3? 計算步長滿足：

令，轉步驟1.

步驟4? 令，，轉到步驟1.

3? 算法的收斂性分析

定理4? 由算法生成的序列，的任一聚點是的穩定點.

證明? 因為，，有

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

當時，有：.因此，的任一聚點都是的解.

當時，有：，所以.由文獻[8]知，對充分大的有下式成立

因此

所以，且.那么是的穩定點.

4? 數值實驗

為了測試算法的性能，本節進行數值實驗.算法中的參數取值如下：

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

最優解：.

試驗結果見表1

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

參考文獻：

[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] 韓繼業， 修乃華， 戚厚鐸. 非線性互補理論與算法[M]. 上海：上海科學技術出版社， 2006.

[5] 雍龍泉. 神經網絡方法求解絕對值方程及線性互補[J]. 陜西理工大學學報（自然科學版）， 2020， 36（05）： 72-81.

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

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

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

[9] 雍龍泉. 神經網絡方法求解絕對值方程及線性互補[J]. 陜西理工大學學報（自然科學版）， 2020， 36（05）： 72-81.

基金項目：安徽省高等學校科學研究項目（自然科學）重點項目“絕對值方程的算法及其應用研究”（課題編號：2023AH052042）

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

作者簡介：葛康康（1990-），男，漢族，安徽淮北人，碩士，淮北理工學院 教育學院，助教，研究方向：優化理論與計算、金融優化。