×

A smoothing inexact Newton method for nonlinear complementarity problems. (English) Zbl 1351.90158

Summary: A smoothing inexact Newton method is presented for solving nonlinear complementarity problems. Different from the existing exact methods, the associated subproblems are not necessary to be exactly solved to obtain the search directions. Under suitable assumptions, global convergence and superlinear convergence are established for the developed inexact algorithm, which are extensions of the exact case. On the one hand, results of numerical experiments indicate that our algorithm is effective for the benchmark test problems available in the literature. On the other hand, suitable choice of inexact parameters can improve the numerical performance of the developed algorithm.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gabriel, S. A.; Conejo, A. J.; Fuller, J. D.; Hobbs, B. F.; Ruiz, C., Complementarity Modeling in Energy Markets. Complementarity Modeling in Energy Markets, International Series in Operations Research and Management Science, 180 (2013), New York, NY, USA: Springer, New York, NY, USA · Zbl 1296.90002 · doi:10.1007/978-1-4419-6123-5
[2] Harker, P. T.; Pang, J.-S., Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Mathematical Programming, 48, 1-3, 161-220 (1990) · Zbl 0734.90098 · doi:10.1007/bf01582255
[3] Ferris, M. C.; Pang, J. S., Engineering and economic applications of complementarity problems, SIAM Review, 39, 4, 669-713 (1997) · Zbl 0891.90158 · doi:10.1137/s0036144595285963
[4] Zhang, J.; Zhang, K.-C., A variant smoothing Newton method for \(P_0- NCP\) based on a new smoothing function, Journal of Computational and Applied Mathematics, 225, 1, 1-8 (2009) · Zbl 1163.65043 · doi:10.1016/j.cam.2008.06.012
[5] Chen, X., Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations, Journal of Computational and Applied Mathematics, 80, 1, 105-126 (1997) · Zbl 0881.65042 · doi:10.1016/s0377-0427(97)80133-1
[6] Chen, J. S.; Pan, S. H., A family of NCP functions and a descent method for the nonlinear complementarity problem, Computational Optimization and Applications, 40, 3, 389-404 (2008) · Zbl 1153.90542 · doi:10.1007/s10589-007-9086-0
[7] Chen, B.; Harker, P. T., Smooth approximations to nonlinear complementarity problems, SIAM Journal on Optimization, 7, 2, 403-420 (1997) · Zbl 0879.90177 · doi:10.1137/s1052623495280615
[8] Chen, X. H.; Ma, C. F., A regularization smoothing Newton method for solving nonlinear complementarity problem, Nonlinear Analysis: Real World Applications, 10, 3, 1702-1711 (2009) · Zbl 1159.90518 · doi:10.1016/j.nonrwa.2008.02.010
[9] Chen, X., Smoothing methods for complementarity problems and their applications: a survey, Journal of the Operations Research Society of Japan, 43, 1, 32-47 (2000) · Zbl 0998.90078 · doi:10.1016/s0453-4514(00)88750-5
[10] Chen, X.; Qi, L.; Sun, D., Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Mathematics of Computation, 67, 222, 519-540 (1998) · Zbl 0894.90143 · doi:10.1090/s0025-5718-98-00932-6
[11] Liu, X.-H.; Wu, W., Coerciveness of some merit functions over symmetric cones, Journal of Industrial and Management Optimization, 5, 3, 603-613 (2009) · Zbl 1187.90294 · doi:10.3934/jimo.2009.5.603
[12] Huang, Z. H.; Han, J. Y.; Chen, Z. W., Predictor-corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a \(P_0\) function, Journal of Optimization Theory and Applications, 117, 1, 39-68 (2003) · Zbl 1044.90081 · doi:10.1023/a:1023648305969
[13] Huang, Z.; Han, J.; Xu, D.; Zhang, L., The non-interior continuation methods for solving the \(P_0\) function nonlinear complementarity problem, Science in China Series A: Mathematics, 44, 9, 1107-1114 (2001) · Zbl 1002.90072 · doi:10.1007/bf02877427
[14] Zhu, J. G.; Liu, H. W.; Liu, C. H., A family of new smoothing functions and a nonmonotone smoothing Newton method for the nonlinear complementarity problems, Journal of Applied Mathematics and Computing, 37, 1-2, 647-662 (2011) · Zbl 1297.90162 · doi:10.1007/s12190-010-0457-9
[15] Zhu, J.; Hao, B., A new class of smoothing functions and a smoothing Newton method for complementarity problems, Optimization Letters, 7, 3, 481-497 (2013) · Zbl 1287.90079 · doi:10.1007/s11590-011-0432-x
[16] Tang, J.; Dong, L.; Zhou, J.; Fang, L., A smoothing Newton method for nonlinear complementarity problems, Computational and Applied Mathematics, 32, 1, 107-118 (2013) · Zbl 1275.90109 · doi:10.1007/s40314-013-0015-9
[17] Li, Q.; Li, D. H., A smoothing Newton method for nonlinear complementarity problems, Advanced Modeling and Optimization, 13, 2, 141-152 (2011) · Zbl 1332.90306
[18] Zhang, L. P.; Han, J. Y.; Huang, Z. H., Superlinear/quadratic one-step smoothing Newton method for \(P_0\)-NCP, Acta Mathematica Sinica, 21, 1, 117-128 (2005) · Zbl 1124.90037 · doi:10.1007/s10114-004-0412-5
[19] Miff, R., Semi-smooth and semi-convex function in constrained optimization, Mathematical Programming, 15, 957-972 (1997)
[20] Qi, L. Q.; Sun, J., A nonsmooth version of Newton’s method, Mathematical Programming, 58, 3, 353-367 (1993) · Zbl 0780.90090 · doi:10.1007/bf01581275
[21] Clarke, F. H., Optimization and Nonsmooth Analysis (1983), New York, NY, USA: Wiley, New York, NY, USA · Zbl 0582.49001
[22] Fang, L., A new one-step smoothing Newton method for nonlinear complementarity problem with \(P_0\)-function, Applied Mathematics and Computation, 216, 4, 1087-1095 (2010) · Zbl 1239.65034 · doi:10.1016/j.amc.2010.02.001
[23] Huang, Z.-H.; Qi, L.; Sun, D., Sub-quadratic convergence of a smoothing Newton algorithm for the \(P_{\text{0}} \)- and monotone LCP, Mathematical Programming, 99, 423-441 (2004) · Zbl 1168.90646 · doi:10.1007/s10107-003-0457-8
[24] Liu, S.; Tang, J.; Ma, C., A new modified one-step smoothing Newton method for solving the general mixed complementarity problem, Applied Mathematics and Computation, 216, 4, 1140-1149 (2010) · Zbl 1192.65079 · doi:10.1016/j.amc.2010.02.006
[25] Qi, L., Convergence analyis of some algorithms for solving nonsmooth equations, SIAM Journal on Control and Optimization, 18, 227-244 (1993) · Zbl 0776.65037
[26] Rui, S.-P.; Xu, C.-X., A smoothing inexact Newton method for nonlinear complementarity problems, Journal of Computational and Applied Mathematics, 233, 9, 2332-2338 (2010) · Zbl 1204.65069 · doi:10.1016/j.cam.2009.10.018
[27] Tang, J.; Liu, S.; Ma, C., One-step smoothing Newton method for solving the mixed complementarity problem with a \(P_0\) function, Applied Mathematics and Computation, 215, 2326-2336 (2009) · Zbl 1179.65073
[28] Qi, L.; Sun, D., Smoothing functions and smoothing Newton method for complementarity and variational inequality problems, Journal of Optimization Theory and Applications, 113, 1, 121-147 (2002) · Zbl 1032.49017 · doi:10.1023/a:1014861331301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.