×

zbMATH — the first resource for mathematics

The locally Chen-Harker-Kanzow-Smale smoothing functions for mixed complementarity problems. (English) Zbl 1423.90260
Summary: According to the structure of the projection function onto the box set \(\varPi_X\) and the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, a new class of smoothing projection functions onto the box set are proposed in this paper. The new smoothing projection functions only smooth \(\varPi_X\) in neighborhoods of nonsmooth points of \(\varPi_X\), and keep unchanged with \(\varPi_X\) at other points, hence they are referred as the locally Chen-Harker-Kanzow-Smale (LCHKS) smoothing functions. Based on the Robinson’s normal equation and the LCHKS smoothing functions, a smoothing Newton method with its convergence results is proposed for solving mixed complementarity problems. Compared with smoothing Newton methods based on various smoothing projection functions, the computations of the LCHKS smoothing function, the function value and its Jacobian matrix of the Newton equation become cheaper, and the Newton direction can be found by solving a low dimensional linear equation, hence the smoothing Newton method based on the LCHKS smoothing functions shows more efficient for large-scale mixed complementarity problems. The LCHKS smoothing functions are proved to be feasible, continuously differentiable, uniform approximations of \(\varPi_X\), globally Lipschitz continuous and strongly semismooth, which are important to establish the superlinear and quadratic convergence of the smoothing Newton method. The proposed smoothing Newton method is implemented in MATLAB and numerical tests are done on the MCPLIB test collection. Numerical results show that the smoothing Newton method based on the LCHKS smoothing functions is promising for mixed complementarity problems.
MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C30 Nonlinear programming
Software:
MCPLIB; Matlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Billups, SC; Dirkse, SP; Ferris, MC, A comparison of algorithms for large-scale mixed complementarity problems, Comput. Optim. Appl., 7, 3-25, (1997) · Zbl 0883.90116
[2] Chen, BT; Harker, PT, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim., 7, 403-420, (1997) · Zbl 0879.90177
[3] Chen, BT; Harker, PT; Pınar, MÇ, Continuation methods for nonlinear complementarity problems via normal maps, Eur. J. Oper. Res., 116, 591-606, (1999) · Zbl 1009.90118
[4] Chen, CH; Mangasarian, OL, Smoothing methods for convex inequalities and linear complementarity problems, Math. Program., 71, 51-69, (1995) · Zbl 0855.90124
[5] Chen, CH; Mangasarian, OL, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl., 5, 97-138, (1996) · Zbl 0859.90112
[6] Chen, XJ; Qi, LQ; Sun, DF, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Math. Comput., 67, 519-540, (1998) · Zbl 0894.90143
[7] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[8] Luca, T.; Facchinei, F.; Kanzow, C., A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program., 75, 407-439, (1996) · Zbl 0874.90185
[9] Dirkse, SP; Ferris, MC, MCPLIB: a collection of nonlinear mixed complementarity problem, Optim. Methods Softw., 5, 319-345, (1995)
[10] Eaves, BC, On the basic theorem of complementarity, Math. Program., 1, 68-75, (1971) · Zbl 0227.90044
[11] Facchinei, F.; Kanzow, C., A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems, Math. Program., 76, 493-512, (1997) · Zbl 0871.90096
[12] Facchinei, F., Pang, J.S.: Finite-dimensional variational inequality and complementarity problems I. In: Springer Series in Operations Research. Springer, New York (2003) · Zbl 1062.90001
[13] Facchinei, F., Pang, J.S.: Finite-dimensional variational inequality and complementarity problems II. In: Springer Series in Operations Research. Springer, New York (2003) · Zbl 1062.90001
[14] Ferris, MC; Pang, JS, Engineering and economic applications of complementarity problem, SIAM Rev., 39, 669-713, (1997) · Zbl 0891.90158
[15] Fischer, A., Solution of monotone complementarity problems with locally Lipschitzian functions, Math. Program., 76, 513-532, (1997) · Zbl 0871.90097
[16] Gabriel, SA; Moré, JJ; Ferris, MC (ed.); Pang, JS (ed.), Smoothing of mixed complementarity problems in complementarity and variational problems, 105-116, (1997), Philadelphia, Pennsylvania
[17] Harker, PT; Pang, JS, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Program., 48, 161-220, (1990) · Zbl 0734.90098
[18] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 959-972, (1977) · Zbl 0376.90081
[19] Qi, LQ, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244, (1993) · Zbl 0776.65037
[20] Qi, LQ; Sun, DF, Smoothing functions and smoothing Newton method for complementarity and variational inequality problems, J. Optim. Theory Appl., 113, 121-147, (2002) · Zbl 1032.49017
[21] Qi, LQ; Sun, DF; Zhou, GL, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87, 1-35, (2000) · Zbl 0989.90124
[22] Qi, LQ; Sun, J., A nonsmooth version of Newton’s method, Math. Program., 58, 353-367, (1993) · Zbl 0780.90090
[23] Robinson, SM, Normal maps induced by linear transformations, Math. Oper. Res., 17, 691-714, (1992) · Zbl 0777.90063
[24] Zhou, ZY; Yu, B., A smoothing homopy method based on Robinson’s normal equations for mixed complementarity problems, J. Ind. Manag. Optim., 7, 977-989, (2011) · Zbl 1231.90360
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.