一种求解绝对值方程的非精确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-），男，汉族，安徽淮北人，硕士，淮北理工学院 教育学院，助教，研究方向：优化理论与计算、金融优化。