×

zbMATH — the first resource for mathematics

Modified Jacobian smoothing method for nonsmooth complementarity problems. (English) Zbl 1432.90149
Summary: This paper is devoted to solving a nonsmooth complementarity problem where the mapping is locally Lipschitz continuous but not continuously differentiable everywhere. We reformulate this nonsmooth complementarity problem as a system of nonsmooth equations with the max function and then propose an approximation to the reformulation by simultaneously smoothing the mapping and the max function. Based on the approximation, we present a modified Jacobian smoothing method for the nonsmooth complementarity problem. We show the Jacobian consistency of the function associated with the approximation, under which we establish the global and fast local convergence for the method under suitable assumptions. Finally, to show the effectiveness of the proposed method, we report our numerical experiments on some examples based on MCPLIB/GAMSLIB libraries or network Nash-Cournot game is proposed.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49J52 Nonsmooth analysis
49M15 Newton-type methods
65K10 Numerical optimization and variational techniques
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
91A43 Games involving graphs
Software:
MCPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chen, Ch; Mangasarian, Ol, A class of smoothing function for nonlinear and mixed complementarity problems, Comput. Optim. Appl., 5, 2, 97-138 (1996) · Zbl 0859.90112
[2] Chen, Ch; Mangasarian, Ol, Smoothing methods for convex inequalities and linear complementarity problems, Math. Program., 71, 1, 51-69 (1995) · Zbl 0855.90124
[3] Chen, X.; 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, 222, 519-540 (1998) · Zbl 0894.90143
[4] Chen, X.; Wets, Rj-B; Zhang, Yf, Stochastic variational inequalities: residual minimization smoothing sample average approximations, SIAM J. Optim., 22, 2, 649-673 (2012) · Zbl 1263.90098
[5] Chen, Yy; Gao, Y., Two new Levenberg-Marquardt methods for nonsmooth nonlinear complementarity problems, Scienceasia, 40, 1, 89-93 (2014)
[6] Chu, Aj; Du, Sq; Su, Yx, A new smoothing conjugate gradient method for solving nonlinear nonsmooth complementarity problems, Algorithms, 8, 4, 1195-1209 (2015) · Zbl 07042308
[7] Clarke, Fh, Optimization and Nonsmooth Analysis (1983), New York: Wiley, New York
[8] Dirkse, Sp; Ferris, Mc, MCPLIB: a collection of nonlinear mixed complementarity problems, Optim. Methods Softw., 5, 4, 319-345 (1995)
[9] Ermoliev, Ym; Norkin, Vi; Wets, Rj-B, The minimization of semicontinuous functions: mollifier subgradients, SIAM J. Control Optim., 33, 1, 149-167 (1995) · Zbl 0822.49016
[10] Facchinei, F.; Kanzow, C., Generalized Nash equilibrium problems, Ann. Oper. Res., 175, 1, 177-211 (2010) · Zbl 1185.91016
[11] Facchinei, F.; Pang, Js, Finite-Dimensional Variational Inequalities and Complementarity Problems (2003), New York: Springer, New York
[12] Ferris, Mc; Pang, Js, Engineering and economic applications of complementarity problems, SIAM Rev., 39, 4, 669-713 (1997) · Zbl 0891.90158
[13] Fischer, A., Solution of monotone complementarity problems with locally Lipschitzian functions, Math. Program., 76, 3, 513-532 (1997) · Zbl 0871.90097
[14] Fischer, A.; Jeyakumar, V.; Luc, Dt, Solution point characterizations and convergence analysis of a descent algorithm for nonsmooth continuous complementarity problems, J. Optim. Theory Appl., 110, 3, 493-513 (2001) · Zbl 1064.90048
[15] Gao, Y., A Newton method for a nonsmooth nonlinear complementarity problem, Oper. Res. Trans., 15, 2, 53-58 (2011) · Zbl 1249.90277
[16] Hobbs, Bf; Pang, Js, Nash-Cournot equilibrium in electric power markets with piecewise linear demand functions and joint constraints, Oper. Res., 55, 1, 113-127 (2007) · Zbl 1167.91356
[17] Izmailov, Af; Solodov, Mv, Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems, SIAM J. Optim., 13, 2, 386-405 (2002) · Zbl 1026.90085
[18] Jiang, H.Y.: Smoothed Fischer-Burmeister equation methods for the complementarity problem. Technical Report, Department of Mathematics, University of Melbourne, Parkville, Australia (1997)
[19] Jiang, Hy, Unconstrained minimization approaches to nonlinear complementarity problems, J. Glob. Optim., 9, 2, 169-181 (1996) · Zbl 0868.90122
[20] Kanzow, C.; Pieper, H., Jacobian smoothing methods for nonlinear complementarity problems, SIAM J. Optim., 9, 2, 342-373 (1999) · Zbl 0986.90065
[21] Kanzow, C.; Qi, Hd, A QP-free constrained Newton-type method for variational inequality problems, Math. Program., 85, 1, 81-106 (1999) · Zbl 0958.65078
[22] Li, Gy; Ng, Kf, Error bound of generalized D-gap functions for nonsmooth and nonmonotone variational inequality problems, SIAM J. Optim., 20, 2, 667-690 (2009) · Zbl 1194.65088
[23] Metzler, Cb; Hobbs, Bf; Pang, Js, Nash-Cournot equilibria in power markets on a linearized dc network with arbitrage: formulations and properties, Netw. Spat. Econ., 3, 2, 123-150 (2003)
[24] Ng, Kf; Tan, Ll, D-gap functions for nonsmooth variational inequality problems, J. Optim. Theory Appl., 133, 1, 77-97 (2007) · Zbl 1293.49022
[25] Ng, Kf; Tan, Ll, Error bounds for regularized gap function for nonsmooth variational inequality problem, Math. Program., 110, 2, 405-429 (2007) · Zbl 1129.49027
[26] Qi, Hd; Liao, Lz, A smoothing Newton method for general nonlinear complementarity problems, Comput. Optim. Appl., 17, 2-3, 231-253 (2000) · Zbl 0987.90078
[27] Qi, Lq; Sun, J., A nonsmooth version of Newton’s method, Math. Program., 58, 1-3, 353-367 (1993) · Zbl 0780.90090
[28] Ralph, D.; Xu, Hf, Implicit smoothing and its application to optimization with piecewise smooth equality constraints, J. Optim. Theory Appl., 124, 3, 673-699 (2005) · Zbl 1211.90278
[29] Rockafellar, Rt; Wets, Rj-B, Variational Analysis (1998), Berlin: Springer, Berlin
[30] Song, Ls; Gao, Y., On the local convergence of a Levenberg-Marquardt method for nonsmooth nonlinear complementarity problems, Scienceasia, 43, 6, 377-382 (2017)
[31] Sun, Df; Qi, Lq, Solving variational inequality problems via smoothing-nonsmooth reformulations, J. Comput. Appl. Math., 129, 1-2, 37-62 (2001) · Zbl 0987.65059
[32] Xu, Hf, Adaptive smoothing method, deterministically computable generalized Jacobians, and the Newton method, J. Optim. Theory Appl., 109, 1, 215-224 (2001) · Zbl 1001.90068
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.