求解加权水平线性互补问题的非单调光滑非精确牛顿法

数学物理学报 ›› 2025, Vol. 45 ›› Issue (1): 165-179.

求解加权水平线性互补问题的非单调光滑非精确牛顿法

范甜甜¹, 汤京永^1,*, 周金川²

¹信阳师范大学数学与统计学院河南信阳 464000;
²山东理工大学数学与统计学院山东淄博 255000

收稿日期:2023-07-14 修回日期:2024-03-01 出版日期:2025-02-26 发布日期:2025-01-08
通讯作者: *汤京永,E-mail:tangjy@xynu.edu.cn
基金资助:
国家自然科学基金 (12371305)、山东省自然科学基金 (ZR2023MA020)、河南省自然科学基金 (222300420520) 和河南省高等学校重点科研项目 (22A110020)

Nonmonotone Smoothing Inexact Newton Algorithm for Solving Weighted Horizontal Linear Complementarity Problems

Fan Tiantian¹, Tang Jingyong¹, Zhou Jinchuan²

¹School of Mathematics and Statistics, Xinyang Normal University, Henan Xinyang 464000;
²College of Mathematics and Statistics, Shandong University of Technology, Shandong Zibo 255000

Received:2023-07-14 Revised:2024-03-01 Online:2025-02-26 Published:2025-01-08
Supported by:
National Natural Science Foundation of China (12371305), the Natural Science Foundation of Shandong Province (ZR2023MA020), the Natural Science Foundation of Henan Province (222300420520) and the Key Scientific Research Projects of Higher Education of Henan Province (22A110020)

摘要/Abstract

摘要： 该文研究一个求解加权水平线性互补问题的非单调光滑非精确牛顿法. 该算法利用一个光滑函数将加权水平线性互补问题等价转化成一个非线性方程组, 然后利用非精确牛顿法求解此方程组. 由于非精确方向一般不是下降方向, 算法采用一个新的非单调线搜索技术来确保其全局收敛性. 特别地, 在 $ {P} $ 对条件下, 证明了算法生成的迭代序列有界. 进一步, 分析了算法在 Hölderian 局部误差界条件下的收敛速率, 而该条件比局部误差界条件更广泛. 算法在每次迭代时只需求解方程组的近似解, 从而可以节省大量的计算时间, 数值实验结果验证了这一优点.

关键词: 加权水平线性互补问题, 光滑算法, 非精确牛顿法, 非单调技术, Hölderian 局部误差界

Abstract: In this paper, we study a nonmonotone smoothing inexact Newton algorithm for solving the weighted horizontal linear complementarity problem (wHLCP). The algorithm uses a smoothing function to reformulate the wHLCP as a nonlinear system of equations and then solve it by inexact Newton's method. Since inexact directions are not necessarily descent, the algorithm adopts a new nonmonotone line search technique to ensure its globalization. Especially, we prove that the generated iteration sequence is bounded under the $ {P} $-pair condition. Moreover, we analyze the local convergence rate of the algorithm under the Hölderian local error bound condition which is more general than the local error bound condition. The algorithm solves the nonlinear equations only approximately so that a lot of computation time can be saved. Numerical experiment results confirm the advantage of the algorithm.

Key words: weighted horizontal linear complementarity problem, smoothing algorithm, inexact Newton algorithm, nonmonotone technique, Hölderian local error bound

中图分类号:

O221.1

范甜甜, 汤京永, 周金川. 求解加权水平线性互补问题的非单调光滑非精确牛顿法[J]. 数学物理学报, 2025, 45(1): 165-179.

Fan Tiantian, Tang Jingyong, Zhou Jinchuan. Nonmonotone Smoothing Inexact Newton Algorithm for Solving Weighted Horizontal Linear Complementarity Problems[J]. Acta mathematica scientia,Series A, 2025, 45(1): 165-179.

参考文献

[1] Potra F A.Weighted complementarity problems-a new paradigm for computing equilibria. SIAM Journal on Optimization, 2012, 22(4): 1634-1654
[2] Asadi S, Darvay Z, Lesaja G, et al.A full-Newton step interior-point method for monotone weighted linear complementarity problems. Journal of Optimization Theory and Applications, 2020, 186: 864-878
[3] Tang J Y, Zhou J C.A modified damped Gauss-Newton method for non-monotone weighted linear complementarity problems. Optimization Methods and Software, 2022, 37(3): 1145-1164
[4] Tang J Y, Zhou J C, Sun Z F.A derivative-free line search technique for Broyden-like method with applications to NCP, wLCP and SI. Annals of Operations Research, 2023, 321(1): 541-564
[5] Tang J Y, Zhou J C.Quadratic convergence analysis of a nonmonotone Levenberg-Marquardt type method for the weighted nonlinear complementarity problem. Computational Optimization and Applications, 2021, 80: 213-244
[6] Tang J Y.A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs. Computational and Applied Mathematics, 2018, 37: 3927-3936
[7] Tang J Y, Zhou J C, Zhang H C.An accelerated smoothing Newton method with cubic convergence for weighted complementarity problems. Journal of Optimization Theory and Applications, 2023, 196(2): 641-665
[8] Zhang J.A smoothing Newton algorithm for weighted linear complementarity problem. Optimization Letters, 2016, 10: 499-509
[9] Potra F A.Sufficient weighted complementarity problems. Computational Optimization and Applications, 2016, 64(2): 467-488
[10] Achache M, Tabchouche N.A full-Newton step feasible interior-point algorithm for monotone horizontal linear complementarity problems. Optimization Letters, 2019, 13: 1039-1057
[11] Monteiro R D C, Tsuchiya T. Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem. Mathematics of Operations Research, 1996, 21(4): 793-814
[12] Zhang Y.On the convergence of a class of infeasible interior-point algorithms for the horizontal linear complementarity problem. SIAM Journal on Optimization, 1994, 4: 208-227
[13] Tang J Y, Zhang H C.A nonmonotone smoothing Newton algorithm for weighted complementarity problems. Journal of Optimization Theory and Applications, 2021, 189: 679-715
[14] Sznajder R, Gowda M S.Generalizations of $ P_0 $-and $ P $-properties; extended vertical and horizontal linear complementarity problems. Linear Algebra and its Applications, 1995, 223: 695-715
[15] Chi X N, Gowda M S, Tao J.The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra. Journal of Global Optimization, 2019, 73(1): 153-169
[16] Wang H Y, Fan J Y.Convergence rate of the Levenberg-Marquardt method under Hölderian local error bound. Optimization Methods and Software, 2020, 35(4): 767-786
[17] Wang H Y, Fan J Y.Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial and Management Optimization, 2021, 17(4): 2265-2275
[18] Burke J, Xu S.A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Mathematical Programming, 2000, 87: 113-130
[19] Zhang J L, Chen J.A smoothing Levenberg-Marquardt type method for LCP. Journal of Computational Mathematics, 2004, 22: 735-752