求解广义互补问题的 Levenberg-Marquardt 算法

摘要/Abstract

摘要：

该文提出求解广义互补问题的 Levenberg-Marquardt 型方法. 首先, 结合一类互补函数, 将广义互补问题等价重构为非线性方程组, 进而提出一类带有线搜索的自适应修正 Levenberg-Marquardt 算法对其进行求解. 其次, 在适当的条件下分析了算法的收敛性. 最后, 通过数值实验验证了所提出算法的可行性和有效性.

关键词: 广义互补问题, Levenberg-Marquardt 算法, 线搜索, 收敛性分析

Abstract:

In this paper, the Levenberg-Marquardt type method is proposed for solving the generalized complementarity problems. Firstly, by integrating a class of complementary functions, the generalized complementarity problem is equivalently reformulated as a system of nonlinear equations. An adaptive modified Levenberg-Marquardt algorithm with line search is then introduced to address this reformulated problem. Furthermore, the convergence of the proposed algorithm is analyzed under appropriate conditions. Finally, numerical experiments are conducted to verify the feasibility and effectiveness of the proposed algorithm.

Key words: generalized complementarity problem, Levenberg-Marquardt algorithm, line search, convergence analysis

中图分类号:

O224

于冬梅, 刘大熠. 求解广义互补问题的 Levenberg-Marquardt 算法[J]. 数学物理学报, 2025, 45(4): 1311-1326.

Yu Dongmei, Liu Dayi. The Levenberg-Marquardt Algorithm for Solving the Generalized Complementarity Problems[J]. Acta mathematica scientia,Series A, 2025, 45(4): 1311-1326.

图/表 10

表1

表2

表3

图1

图2

图3

图4

表4

表5

表6

参考文献 33

[1]	Kanzow C, Fukushima M. Equivalence of the generalized complementarity problem to differentiable unconstrained minimization. J Optim Theory Appl, 1996, 90: 581-603
[2]	Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer Linear Algebra Appl, 2010, 17(6): 917-933
[3]	Noor M A. On the nonlinear complementarity problem. J Math Anal Appl, 1987, 1.3(2): 455-460
[4]	Pang J S. On the convergence of a basic iterative method for the implicit complementarity problem. J Optim Theory Appl, 1982, 37: 149-162
[5]	Fischer A. A special Newton-type optimization method. Optimization, 1992, 24( 3/4): 269-284
[6]	迟晓妮, 曾荣, 刘三阳, 等. 对称锥权互补问题的正则化非单调非精确光滑牛顿法. 数学物理学报, 2021, 41A(2): 507-522
	Chi X N, Zeng R, Liu S Y, et al. A regularized nonmonotone inexact smoothing Newton algorithm for weighted symmetric cone complementarity problems. Acta Math Sci, 2021, 41A(2): 507-522
[7]	张运胜, 高雷阜. 对称锥互补问题的一种非精确光滑牛顿算法. 数学物理学报, 2015, 35A(4): 824-832
	Zhang Y S, Gao L F. A smoothing inexact Newton method for symmetric cone complementarity problems. Acta Math Sci, 2015, 35A(4): 824-832
[8]	Mittal G, Giri A K. Convergence rates for iteratively regularized Gauss-Newton method subject to stability constraints. J Comput Appl Math, 2022, 4.0: 113744
[9]	Tang J Y, Zhou J C. A modified damped Gauss-Newton method for non-monotone weighted linear complementarity problems. Optim Methods Softw, 2022, 37(3): 1145-1164
[10]	Facchinei F, Kanzow C. A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Math Program, 1997, 76: 493-512
[11]	刘志敏, 杜守强, 王瑞莹. 求解线性互补问题的 Levenberg-Marquardt 型算法. 应用数学学报, 2018, 41(3): 403-419 doi: 10.12387/C2018031
	Liu Z M, Du S Q, Wang R Y. Levenberg-Marquardt type method for solving linear complementarity problems. Acta Math Appl Sin, 2018, 41(3): 403-419 doi: 10.12387/C2018031
[12]	胡雅伶, 彭拯, 章旭, 等. 一种求解非线性互补问题的多步自适应 Levenberg-Marquardt 算法. 计算数学, 2021, 43(3): 322-336 doi: 10.12286/jssx.j2019-0615
	Hu Y L, Peng Z, Zhang X, et al. An adaptive multi-step Levenberg-Marquardt method for nonlinear complementarity problem. Math Numer Sin, 2021, 43(3): 322-336 doi: 10.12286/jssx.j2019-0615
[13]	Lera G, Pinzolas M. Neighborhood based Levenberg-Marquardt algorithm for neural network training. IEEE Trans Neural Netw, 2002, 13(5): 1200-1203
[14]	Chen L, Ma Y F. A modified Levenberg-Marquardt method for solving system of nonlinear equations. J Appl Math Comput, 2023, 69: 2019-2040
[15]	晋慧慧, 袁柳洋, 万仲平. 一种新的非单调修正 Levenberg-Marquardt 算法. 应用数学学报, 2024, 47(5): 799-810 doi: 10.20142/j.cnki.amas.202401016
	Jin H H, Yuan L Y, Wan Z P. A new nonmonotone modified Levenberg-Marquardt algorithm. Acta Math Appl Sin, 2024, 47(5): 799-810 doi: 10.20142/j.cnki.amas.202401016
[16]	Du S Q. Generalized Newton method for a kind of complementarity problem. Abstr Appl Anal, 2014, 20.4(1): 745981
[17]	Vivas H, Pérez R, Arias C A. A nonsmooth Newton method for solving the generalized complementarity problem. Numer Algorithms, 2024, 95: 551-574
[18]	Fan J Y, Yuan Y X. On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption. Computing, 2005, 74: 23-39
[19]	Ma C F, Jiang L H. Some research on Levenberg-Marquardt method for the nonlinear equations. Appl Math Comput, 2007, 1.4(2): 1032-1040
[20]	Fan J Y, Pan J Y. A note on the Levenberg-Marquardt parameter. Appl Math Comput, 2009, 2.7(2): 351-359
[21]	Amini K, Rostami F, Caristi G. An efficient Levenberg-Marquardt method with a new LM parameter for systems of nonlinear equations. Optimization, 2018, 67(5): 637-650
[22]	Huang B H, Ma C F. A Shamanskii-like self-adaptive Levenberg-Marquardt method for nonlinear equations. Comput Math Appl, 2019, 77(2): 357-373
[23]	Tang J Y, Zhou J C. Quadratic convergence analysis of a nonmonotone Levenberg-Marquardt type method for the weighted nonlinear complementarity problem. Comput Optim Appl, 2021, 80: 213-244
[24]	Liu X J, Liu S Y. A smoothing Levenberg-Marquardt method for the complementarity problem over symmetric cone. Appl Math, 2022, 67: 49-64
[25]	Lopes V L R, Martínez J M, Pérez R. On the local convergence of quasi-Newton methods for nonlinear complementarity problems. Appl Numer Math, 1999, 30(1): 3-22
[26]	Yang Y F, Qi L Q. Smoothing trust region methods for nonlinear complementarity problems with $P_{0}$-functions. Ann Oper Res, 2005, 1.3: 99-117
[27]	Jana R, Dutta A, Das A K. More on hidden $Z$-matrices and linear complementarity problem. Linear Multilinear Algebra, 2021, 69(6): 1151-1160
[28]	Facchinei F, Soares J. A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J Optim, 1997, 7(1): 225-247
[29]	Yamashita N, Fukushima M. On the rate of convergence of the Levenberg-Marquardt method. Computing, 2001, 15: 239-249
[30]	Behling R, Iusem A. The effect of calmness on the solution set of systems of nonlinear equations. Math Program, 2013, 1.7: 155-165
[31]	Stewart G W, Sun J G. Matrix Perturbation Theory. Boston: Academic Press, 1990
[32]	Outrata J V, Zowe J. A Newton method for a class of quasi-variational inequalities. Comput Optim Appl, 1995, 4: 5-21
[33]	Wu S L, Guo P. Modulus-based matrix splitting algorithms for the quasi-complementarity problems. Appl Numer Math, 2018, 1.2: 127-137