×

A new class of smoothing functions and a smoothing Newton method for complementarity problems. (English) Zbl 1287.90079

Summary: We introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a \( P_0\) function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

MCPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Harker P.T., Pang J.S.: Finite dimensional variational inequality and nonlinear complementarity problem: a survey of theory, algorithms and applications. Math. Program. 48, 161–220 (1990) · Zbl 0734.90098 · doi:10.1007/BF01582255
[2] Ferris M.C., Pang J.S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669–713 (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[3] Chinchuluun A., Pardalos P.M., Migdalas A., Pitsoulis L.: Pareto Optimality, Game Theory and Equilibria. Springer, Berlin (2008) · Zbl 1143.91004
[4] Isac G.: Nonlinear analysis and complementarity theory. J. Glob. Optim. 40, 129–146 (2008) · Zbl 1145.90093 · doi:10.1007/s10898-007-9233-2
[5] Pardalos P.M., Ye Y.Y., Han C.G., Kaliski J.A.: Solution of P 0 matrix linear complementarity problems using reduction algorithm. SIAM J. Matrix Anal. Appl. 14, 1048–1060 (1993) · Zbl 0788.65072 · doi:10.1137/0614069
[6] Ma C.F., Chen X.H.: The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function. J. Comput. Appl. Math. 216, 1–13 (2008) · Zbl 1140.65046 · doi:10.1016/j.cam.2007.03.031
[7] Chen J.S.: The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem. J. Glob. Optim. 36, 565–580 (2006) · Zbl 1144.90493 · doi:10.1007/s10898-006-9027-y
[8] Huang Z.H., Han J., Xu D., Zhang L.: The non-linear continuation methods for solving the P 0-functions non-linear complementarity problem. Sci. China 44(2), 1107–1114 (2001) · Zbl 1002.90072 · doi:10.1007/BF02877427
[9] Huang Z.H., Han J., Chen Z.: Predictor-corrector smoothing newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function. J. Optim. Theory Appl. 117(1), 39–68 (2003) · Zbl 1044.90081 · doi:10.1023/A:1023648305969
[10] Qi L., Sun D., Zhou G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87(1), 1–35 (2000) · Zbl 0989.90124
[11] Yu H.D., Pu D.G.: Smoothing Newton method for NCP with the identification of degenerate indices. J. Comput. Appl. Math. 234, 3424–3435 (2010) · Zbl 1210.65121 · doi:10.1016/j.cam.2010.05.004
[12] Chen J.S., Huang Z.H., She C.Y.: A new class of penalized NCP-functions and its properties. Comput. Optim. Appl. 50, 49–73 (2011) · Zbl 1254.90253 · doi:10.1007/s10589-009-9315-9
[13] Hu S.L., Huang Z.H., Chen J.S.: Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems. J. Comput. Appl. Math. 230, 69–82 (2009) · Zbl 1172.65029 · doi:10.1016/j.cam.2008.10.056
[14] Kojima M., Megiddo N., Noma T.: Homotopy continuation methods for nonlinear complementarity problems. Math. Oper. Res. 16, 754–774 (1991) · Zbl 0744.90087 · doi:10.1287/moor.16.4.754
[15] Kanzow C., Pieper H.: Jacobian smoothing methods for nonlinear complementarity problems. SIAM J. Optim. 9, 342–373 (1999) · Zbl 0986.90065 · doi:10.1137/S1052623497328781
[16] Zhang L.P., Wu S.Y., Gao T.R.: Improved smoothing Newton methods for P0 nonlinear complementarity problems. Appl. Math. Comput. 215, 324–332 (2009) · Zbl 1176.65076 · doi:10.1016/j.amc.2009.04.088
[17] Kanzow C.: Some equation-based methods for the nonlinear complementarity problem. Optim. Methods Softw. 3, 327–340 (1994) · doi:10.1080/10556789408805573
[18] Jiang H., Qi L.: A new nonsmooth equations approach to nonlinear complementarity problems. SIAM J. Control Optim. 35, 178–193 (1997) · Zbl 0872.90097 · doi:10.1137/S0363012994276494
[19] Liu X., Wu W.: Coerciveness of some merit functions over symmetric cones. J. Ind. Manag. Optim. 5, 603–613 (2009) · Zbl 1187.90294 · doi:10.3934/jimo.2009.5.603
[20] Mifflin R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977) · Zbl 0376.90081
[21] Qi L., Sun J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275
[22] Clarke F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[23] Gowa M.S., Tawhid M.A.: Existence and limiting behavior of trajectories associated with P 0-equations. Comput. Optim. Appl. 12, 229–251 (1999) · Zbl 1040.90563 · doi:10.1023/A:1008688302346
[24] Kojima M., Megiddo N., Noma T., Yoshise A.: A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science. Springer, Berlin (1991) · Zbl 0745.90069
[25] Chen X., Qi L.Q., Sun D.F.: 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 · doi:10.1090/S0025-5718-98-00932-6
[26] Facchinei F., Kanzow C.: Beyond monotonicity in regularization methods for non-linear complementarity problems. SIAM J. Control Optim. 37, 1150–1161 (1999) · Zbl 0997.90085 · doi:10.1137/S0363012997322935
[27] Fang L.: A new one-step smoothing Newton method for nonlinear complementarity problem with P0-function. Appl. Math. Comput. 216, 1087–1095 (2010) · Zbl 1239.65034 · doi:10.1016/j.amc.2010.02.001
[28] Pang J.S., Gabriel S.A.: NE/SQP: a robust algorithm for the nonlinear complementarity problem. Math. Program. 60, 295–337 (1993) · Zbl 0808.90123 · doi:10.1007/BF01580617
[29] Mangasarian O.L., Solodov M.V.: Nonlinear complementarity as unconstrained and constrained minimization. Math. Program. 62, 277–297 (1993) · Zbl 0813.90117 · doi:10.1007/BF01585171
[30] Dirkse S.P., Ferris M.C.: MCPLIB: a collection of nonlinear mixed complementarity problems. Optim. Methods Softw. 5, 319–345 (1995) · doi:10.1080/10556789508805619
[31] Oberlin C., Wright S.J.: An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems. Math. Program. 117, 355–386 (2009) · Zbl 1166.65341 · doi:10.1007/s10107-007-0173-x
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.