A smooth Levenberg-Marquardt method without nonsingularity condition for wLCP

Xiaorui He; Jingyong Tang; Xiaorui He; Jingyong Tang

doi:10.3934/math.2022497

AIMS Mathematics

2022, Volume 7, Issue 5: 8914-8932. doi: 10.3934/math.2022497

Previous Article Next Article

Research article

A smooth Levenberg-Marquardt method without nonsingularity condition for wLCP

Xiaorui He ,
Jingyong Tang ^,

College of Mathematics and Statistics, Xinyang Normal University, Xinyang 464000, China

Received: 12 September 2021 Revised: 16 February 2022 Accepted: 22 February 2022 Published: 07 March 2022
MSC : 65K05, 90C33

In this paper we consider the weighted Linear Complementarity Problem (wLCP). By using a smooth weighted complementarity function, we reformulate the wLCP as a smooth nonlinear equation and propose a Levenberg-Marquardt method to solve it. The proposed method differentiates itself from the current Levenberg-Marquardt type methods by adopting a simple derivative-free line search technique. It is shown that the proposed method is well-defined and it is globally convergent without requiring wLCP to be monotone. Moreover, the method has local sub-quadratic convergence rate under the local error bound condition which is weaker than the nonsingularity condition. Some numerical results are reported.
- weighted linear complementarity problem,
- Levenberg-Marquardt method,
- local error bound condition,
- sub-quadratic convergence
Citation: Xiaorui He, Jingyong Tang. A smooth Levenberg-Marquardt method without nonsingularity condition for wLCP[J]. AIMS Mathematics, 2022, 7(5): 8914-8932. doi: 10.3934/math.2022497

Related Papers:

Abstract

In this paper we consider the weighted Linear Complementarity Problem (wLCP). By using a smooth weighted complementarity function, we reformulate the wLCP as a smooth nonlinear equation and propose a Levenberg-Marquardt method to solve it. The proposed method differentiates itself from the current Levenberg-Marquardt type methods by adopting a simple derivative-free line search technique. It is shown that the proposed method is well-defined and it is globally convergent without requiring wLCP to be monotone. Moreover, the method has local sub-quadratic convergence rate under the local error bound condition which is weaker than the nonsingularity condition. Some numerical results are reported.

References

[1]	K. M. Anstreicher, Interior-point algorithms for a generalization of linear programming and weighted centering, Optim. Method. Softw., 27 (2012), 605–612. https://doi.org/10.1080/10556788.2011.644791 doi: 10.1080/10556788.2011.644791
[2]	S. Asadi, Z. Darvay, G. Lesaja, N. Mahdavi-Amiri, F. Potra, A full-Newton step interior-point method for monotone weighted linear complementarity problems, J. Optim. Theory Appl., 186 (2020), 864–878. https://doi.org/10.1007/s10957-020-01728-4 doi: 10.1007/s10957-020-01728-4
[3]	X. N. Chi, M. S. Gowda, J. Tao, The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, J. Global Optim., 73 (2019), 153–169. https://doi.org/10.1007/s10898-018-0689-z doi: 10.1007/s10898-018-0689-z
[4]	X. N. Chi, Z. P. Wan, Z. J. Hao, A full-modified-Newton step $O(n)$ infeasible interior-point method for the special weighted linear complementarity problem, J. Ind. Manag. Optim., 2021. https://doi.org/10.3934/jimo.2021082
[5]	J. S. Chen, The semismooth-related properties of a merit function and adescent method for the nonlinear complementarity problem, J. Glob. Optim., 36 (2006), 565–580. https://doi.org/10.1007/s10898-006-9027-y doi: 10.1007/s10898-006-9027-y
[6]	F. Facchinei, J. S. Pang, Finite-dimensional variational inequalities and complementarity problems, New York: Springer, 2003.
[7]	J. Y. Fan, J. Y. Pan, Convergence properties of a self-adaptive Levenberg-Marquardt algorithm under local error bound condition, Comput. Optim. Appl., 34 (2006), 47–62. https://doi.org/10.1007/s10589-005-3074-z doi: 10.1007/s10589-005-3074-z
[8]	J. Y. Fan, Accelerating the modified Levenberg-Marquardt method for nonlinear equations, Math. Comput., 83 (2014), 1173–1187. https://doi.org/10.1090/S0025-5718-2013-02752-4 doi: 10.1090/S0025-5718-2013-02752-4
[9]	J.Y. Fan, Y. X. Yuan, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74 (2005), 23–39. https://doi.org/10.1007/s00607-004-0083-1 doi: 10.1007/s00607-004-0083-1
[10]	M. S. Gowda, Weighted LCPs and interior point systems for copositive linear transformations on Euclidean Jordan algebras, J. Glob. Optim., 74 (2019), 285–295. https://doi.org/10.1007/s10898-019-00760-7 doi: 10.1007/s10898-019-00760-7
[11]	Z. H. Huang, J. Sun, A non-interior continuation algorithm for the $P_0$ or $P_$ LCP with strong global and local convergence properties, Appl. Math. Optim.*, 52 (2005), 237–262. https://doi.org/10.1007/s00245-005-0827-0 doi: 10.1007/s00245-005-0827-0
[12]	Z. H. Huang, L. P. Zhang, J. Y. Han, A hybrid smoothing-nonsmooth Newton-type algorithm yielding an exact solution of the $P_0$-LCP, J. Comput. Math., 22 (2004), 797–806.
[13]	W. L. Liu, C. Y. Wang, A smoothing Levenberg-Marquardt method for generalized semi-infinite programming, Comput. Appl. Math., 32 (2013), 89–105. https://doi.org/10.1007/s40314-013-0013-y doi: 10.1007/s40314-013-0013-y
[14]	F. A. Potra, Weighted complementarity problems-A new paradigm for computing equilibria, SIAM J. Optim., 22 (2012), 1634–1654. https://doi.org/10.1137/110837310 doi: 10.1137/110837310
[15]	F. A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl., 64 (2016), 467–488. https://doi.org/10.1007/s10589-015-9811-z doi: 10.1007/s10589-015-9811-z
[16]	J. Y. Tang, A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Comput. Appl. Math., 37 (2018), 3927–3936. https://doi.org/10.1007/s40314-017-0554-6 doi: 10.1007/s40314-017-0554-6
[17]	J. Y. Tang, H. C. Zhang, A nonmonotone smoothing Newton algorithm for weighted complementarity problems, J. Optim. Theory Appl., 189 (2021), 679–715. https://doi.org/10.1007/s10957-021-01839-6 doi: 10.1007/s10957-021-01839-6
[18]	J. Y. Tang, J. C. Zhou, Quadratic convergence analysis of a nonmonotone Levenberg-Marquardt type method for the weighted nonlinear complementarity problem, Comput. Optim. Appl., 80 (2021), 213–244. https://doi.org/10.1007/s10589-021-00300-8 doi: 10.1007/s10589-021-00300-8
[19]	J. Y. Tang, J. C. Zhou, A modified damped Gauss-Newton method for non-monotone weighted linear complementarity problems, Optim. Method. Softw., 2021. https://doi.org/10.1080/10556788.2021.1903007
[20]	H. Y. Wang, J. Y. Fan, Convergence rate of the Levenberg-Marquardt method under Hölderian local error bound, Optim. Method. Softw., 35 (2020), 767–786. https://doi.org/10.1080/10556788.2019.1694927 doi: 10.1080/10556788.2019.1694927
[21]	Y. Y. Ye, A fully polynomial-time approximation algorithm for computing a stationary point of the general linear complementarity problem, Math. Oper. Res., 18 (1993), 334–345. https://doi.org/10.1287/moor.18.2.334 doi: 10.1287/moor.18.2.334
[22]	J. Zhang, A smoothing Newton algorithm for weighted linear complementarity problem, Optim. Lett., 10 (2016), 499–509. https://doi.org/10.1007/s11590-015-0877-4 doi: 10.1007/s11590-015-0877-4
[23]	J. L. Zhang, J. Chen, A smoothing Levenberg-Marquardt type method for LCP, J. Comput. Math., 22 (2004), 735–752.
[24]	Y. B. Zhao, D. Li, A globally and locally superlinearly convergent non-interior-point algorithm for $P_0$ LCPs, SIAM J. Optim., 13 (2003), 1195–1221. https://doi.org/10.1137/S1052623401384151 doi: 10.1137/S1052623401384151
[25]	J. L. Zhang, J. Chen, A new noninterior predictor-corrector method for the $P_0$ LCP, Appl. Math. Optim., 53 (2006), 79–100. https://doi.org/10.1007/s00245-005-0836-z doi: 10.1007/s00245-005-0836-z
[26]	L. P. Zhang, X. S. Zhang, Global linear and quadratic one-step smoothing Newton method for $P_0$-LCP, J. Glob. Optim., 25 (2003), 363–376. https://doi.org/10.1023/A:1022528320719 doi: 10.1023/A:1022528320719

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)