A double step size method for linear complementarity problem
Resumo
Solving a linear complementarity problem remains an NP-hard research topic. In this paper, we present a two-step size algorithm with an accelerated property for solving linear complementarity problems LCP(q,M) with M a positive matrix, in which we reformulate our problem as a system of nonlinear equations F_{p}(x)=0 where p is large. We use the inexact linear search technique, as well as the approximation of the Jacobian by the acceleration parameter, an efficient accelerated Newton and gradient descent method is developed. It is shown that the proposed method is convergent under some specific conditions. This method is derivative-free, which is advantageous for solving large-scale problems.
Downloads
Referências
R.W. Cottle, J.S. Pang, R.E. Stone,The Linear Complementarity Problem, Academic Press, New York, 1992.
K. Murty,Linear Complementarity, Linear and Nonlinear Programming, Heldermann-Verlag, 1988.
Y. El foutayeni, M. Khaladi,Using vector divisions in solving the linear complementarity problem, Journal of Computational
and Applied Mathematics, 236 (2012) 1919-1925.
Y. El foutayeni, H. El bouanani, M. Khaladi,An (m+1)-step iterative method of convergence order (m+2) for linear
complementarity problems, Journal of Applied Mathematics and Computing, 54 (2017) 229-242.
A. Halilu , M. Waziri, Y. Musa, Inexact Double Step Length Method for Solving Systems of Nonlinear Equations,
Statistics, Optimization and Information Computing, Vol. 8, March 2020, pp 165-174.
A. Halilu, M. Waziri,Solving System of Nonlinear Equations using Improved Double Direction Method, Journal of the
Vol. 39, Issue 2, pp. 287-301, 2020.
P.S. Stanimirovie, M.B. Miladinovie, Accelerated gradient descent methods with line search, Springer Science + Business
Media, LLC 2009, DOI 10.1007/s11075-009-9350-8, Numer Algor (2010) 54:503-520.
J. E. Dennis, J. More,A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods, Mathematics of Computation, Vol. 28, No. 126 (Apr., 1974), pp. 549-560.
G. Yuan , X. Lu,A new backtracking inexact BFGS method for symmetric nonlinear equations, Computers and Mathematics with Applications 55 (2008) 116-129.
M. J. Petrovic,An Accelerated Double Step Size model in unconstrained optimization, Applied Mathematics and Computation 250 (2015) 309-319.
E. Polak, G. Riere,Note sur la convergence de methodes de directions conjuguees, Revue fran¸caise d’informatique et de recherche operationnelle. Serie rouge, tome 3, n R1 (1969), p. 35-43.
A. Naseem, M. A. Rehman, T. Abdeljawad,Numerical Algorithms for Finding Zeros of Nonlinear Equations and Their Dynamical Aspects, Journal of Mathematics vol 2020.
J. E Dennis, R. B Schnabel,Numerical method for unconstrained optimization and non-linear equations, practice Hall, Englewood cliffs, NJ, USA, 1983.
M. Y Waziri, A. S. Halilu,An improved derivative-free method via double direction approach for solving systems of nonlinear equations, Journal of the Ramanujan Mathematical Society, vol. 33, no. 1, pp. 75-89, 2018.
P. N. Brown, Y. Saad,Convergence theory of nonlinear Newton-Krylov algorithms search, SIAM Journal on Optimization, vol.4, no.2, pp.297-330, 1994.
A. S Halilu, M. Y Waziri,A transformed double step length method for solving large-scale systems of nonlinear equations, Journal of Numerical Mathematics and Stochastics, vol.9, no. 1, pp. 20–23, 2017.
D. Li, M. Fukushima,A global and superlinear convergent Gauss-Newton based BFGS method for symmetric nonlinear equations, SIAM Journal on numerical Analysis, vol.37, pp. 152–172, 1999.
A. S Halilu, M. Y Waziri,Enhanced matrix-free method via double step length approach for solving systems of nonlinear equations, International Journal of Applied Mathematical Research, vol.6, no. 4, pp. 147-156, 2017.
Z. Shi, J. Shen,Convergence of nonmonotone line search method, Journal of Computational and Applied Mathematics, vol.193, pp. 397-412, 2006.
I. A. Osinuga, S.O. Yusuff,Quadrature based Broyden-like method for systems of nonlinear equations, Statistics, Optimization and Information Computing, vol.6, pp. 130-138, 2018.
W. Cheng, Q. Hu,A Nonmonotone Spectral Gradient Method for l -regularized Least Squares, Statistics, Optimization and Information Computing, vol.4, pp.265-277, 2016.
M. Y Waziri, J. Sabiu,A derivative-free conjugate gradient method and its global convergence for symmetric nonlinear equation, Journal of Mathematics and Mathematical Sciences, vol. 2015, pp. 8, 2015.
A. S Halilu, M. Y Waziri,A transformed double step length method for solving large-scale systems of nonlinear equations, Journal of Numerical Mathematics and Stochastics, vol.9, no. 1, pp. 20–23, 2017.
N. I. Dbaruranovic-milicic, M. Gardasevic-Filipovic,A multistep curve search algorithm in nonlinear convex case, Facta universitatis series: Mathematics and informatics 25/ 11-24, 2010.
N. I. Dbaruranovic-milicic,A multi step curve search algorithm in nonlinear optimization, Yugoslav Journal of operation research 18/ 47-52, 2008.
M. J. petrovic, P. S. Stanimirovic, Accelerated double direction method for solving unconstrained optimization problems, Mathematical problem Eng., 2014.
N. I Dbaruranovic-milicic, A multi step curve search algorithm in nonlinear opti-mization, Yugoslav Journal of operation research 18 47-52, 2008.
G. Yuan , X. Lu, A new backtracking inexact BFGS method for symmetric nonlinear equations, Journal of Computers and Mathematics with Applications, vol.55, pp. 116-129, 2008.
Copyright (c) 2025 Boletim da Sociedade Paranaense de Matemática
This work is licensed under a Creative Commons Attribution 4.0 International License.
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
