Abstract
The linear complementarity problem (LCP) is to find \({(x,s)\in\mathfrak{R}^n\times\mathfrak{R}^n}\) such that (x, s) ≥ 0, s = Mx + q, x T s = 0 with \({M\in\mathfrak{R}^{n\times n}}\) and \({q\in\mathfrak{R}^n}\) . The smoothing Newton algorithm is one of the most efficient methods for solving the LCP. To the best of our knowledge, the best local convergence results of the smoothing Newton algorithm for the LCP up to now were obtained by Huang et al. (Math Program 99:423–441, 2004). In this note, by using a revised Chen–Harker–Kanzow–Smale smoothing function, we propose a variation of Huang–Qi–Sun’s algorithm and show that the algorithm possesses better local convergence properties than those given in Huang et al. (Math Program 99:423–441, 2004).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Clarke F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
Hu S.L., Huang Z.H., Wang P.: A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. Optim. Methods Softw. 24(3), 447–460 (2009)
Huang Z.H.: Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms. Math. Methods Oper. Res. 61, 41–55 (2005)
Huang Z.H., Qi L., Sun D.: Sub-quadratic convergence of a smoothing Newton algorithm for the P 0- and monotone LCP. Math. Program. 99, 423–441 (2004)
Huang Z.H., Sun J.: A non-interior continuation algorithm for the P 0 or P * LCP with strong global and local convergence properties. Appl. Math. Optim. 52, 237–262 (2005)
Huang Z.H., Xu S.W.: Convergence properties of a non-interior-point smoothing algorithm for the P* NCP. J. Ind. Manag. Optim. 3, 569–584 (2007)
Pardalos P.M., Rosen J.B.: Global optimization approach to the linear complementarity problem. SIAM J. Sci. Stat. Comput. 9, 341–353 (1988)
Pardalos P.M., Ye Y.: Class of linear complementarity problems solvable in polynomial time. Linear Algebra Appl. 152, 3–17 (1991)
Pardalos P.M., Ye Y., Han C.-G., Kalinski J.: Solution of P-matrix linear complementarity problems using a potential reduction algorithm. SIAM J. Matrix Anal. Appl. 14, 1048–1060 (1993)
Qi L., Sun J.: A nonsmooth version of Newtons method. Math. Program. 58, 353–367 (1993)
Qi L., Sun D.: Improving the convergence of non-interior point algorithm for nonlinear complementarity problems. Math. Comput. 69, 283–304 (2000)
Qi L., Sun D., Zhou G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87, 1–35 (2000)
Sun D.: A regularization Newton method for solving nonlinear complementarity problems. Appl. Math. Optim. 36, 315–339 (1999)
Zhao Y.B., Li D.: A globally and locally superlinearly convergent non-interior-point algorithm for P 0 LCPs. SIAM J. Optim. 13, 1196–1221 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ni, T., Hu, SL. A note on quadratic convergence of a smoothing Newton algorithm for the LCP. Optim Lett 7, 519–531 (2013). https://doi.org/10.1007/s11590-011-0436-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0436-6