Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-04T20:11:06.316Z Has data issue: false hasContentIssue false
  • English
  • Français

A Regularization Semismooth Newton Method for P0-NCPs with a Non-monotone Line Search

Published online by Cambridge University Press:  28 May 2015

Li-Yong Lu ,
Wei-Zhe Gu  and
Wei Wang
Li-Yong Lu
Affiliation:
Department of Mathematics, School of Science, Tianjin University of Technology, Tianjin 300384, China
Wei-Zhe Gu*
Affiliation:
Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, China
Wei Wang
Affiliation:
School of Public Administration, Tianjin University of Commerce, Tianjin 300134, China
*
Corresponding author.Email address:[email protected]
Get access

Abstract

In this paper, we propose a regularized version of the generalized NCP-function proposed by Hu, Huang and Chen [J. Comput. Appl. Math., 230 (2009), pp. 69-82]. Based on this regularized function, we propose a semismooth Newton method for solving nonlinear complementarity problems, where a non-monotone line search scheme is used. In particular, we show that the proposed non-monotone method is globally and locally superlinearly convergent under suitable assumptions. We test the proposed method by solving the test problems from MCPLIB. Numerical experiments indicate that this algorithm has better numerical performance in the case of p = 5 and Θ ∈ [0.25,075] than other cases.

Keywords

90C3365K10Nonlinear complementarity problemnon-monotone line searchsemismooth Newton methodglobal convergencelocal superlinear convergence
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 5 , Issue 2 , May 2012 , pp. 186 - 204
Copyright
Copyright © Global Science Press Limited 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ferris, M.C., Pang, J.S., Engineering and economic applications of complementarity problems, SIAM Rev., vol. 39 (1997), pp. 669–713.CrossRefGoogle Scholar
[2]Harker, P.T., Pang, J.S., Finite dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications, Math. Program., vol. 48 (1990), pp. 161–220.CrossRefGoogle Scholar
[3]Facchinei, F., Pang, J.S., Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Verlag, New York, 2003.Google Scholar
[4]Han, J.Y., Xiu, N.H., Qi, H.D., Theory and methods for nonlinear complementarity problems, Shanghai Science and Technology Press. 2006 (in Chinese).Google Scholar
[5]Chen, B., Chen, X., Kanzow, C., A penalized Fischer-Burmeister NCP-function, Math. Program., vol. 88 (2000), pp. 211–216.CrossRefGoogle Scholar
[6]Facchinei, F., Kanzow, C., On unconstrained and constrained stationary points of the implicit Lagrangian, J. Optim. Theory Appl., vol. 92 (1997), pp. 99–115.CrossRefGoogle Scholar
[7]Facchinei, F., Soares, J., A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., vol. 7 (1997), pp. 225–247.CrossRefGoogle Scholar
[8]Chen, B., Xiu, N.H., A global linear and local quadratic non-interior continuation method for NCP based on Chen-Mangasarian smoothing functions, SIAM J. Optim., vol. 9 (1999), pp. 605–623.CrossRefGoogle Scholar
[9]Chen, B., Xiu, N.H., A superlinear noninterior one-step continuation method for monotone LCP in the absence of strict complementarity, J. Optim. Theory Appl., vol. 108 (2001), pp. 317–332.CrossRefGoogle Scholar
[10]Fischer, A., A special Newton-type optimization method, Optim., vol. 24 (1992), pp. 269–284.CrossRefGoogle Scholar
[11]Zhang, L.P., Wu, S.Y., Gao, T.R., Improved smoothing Newton methods for P0 nonlinear complementarity problems, Appl. Math. Comput., vol. 215 (2009), pp. 324–332.Google Scholar
[12]Geiger, C., Kanzow, C., On the resolution of monotone complementarity problems, Comput. Optim. Appl., vol. 5 (1996), pp. 155–173.CrossRefGoogle Scholar
[13]Huang, Z.H., Qi, L.Q., Sun, D.F., Sub-quadratric convergence of a smoothing Newton algorithm for the P0-and monotone LCP, Math. Program., vol. 99 (2004), pp. 423–441.CrossRefGoogle Scholar
[14]Hu, S.L., Huang, Z.H., Wang, P., A non-monotone smoothing Newton algorithm for solving nonlinear complementarity problems, Optim. Methods Softw., vol.24 (2009), pp. 447–460.CrossRefGoogle Scholar
[15]Kanzow, C., Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., vol. 17 (1996), pp. 851–868.CrossRefGoogle Scholar
[16]Kanzow, C., Kleinmichel, H., A new class of semismooth Newton method for nonlinear complementarity problems, Comput. Optim. Appl., vol.11 (1998), pp. 227–251.CrossRefGoogle Scholar
[17]Kanzow, C., Yamashita, N., Fukushima, M., New NCP-functions and their properties, J. Optim. Theory Appl., vol.94 (1997), pp. 115–135.CrossRefGoogle Scholar
[18]Qi, L.Q., Sun, D.F., Zhou, G.L., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., vol. 87 (2000), pp. 1–35.CrossRefGoogle Scholar
[19]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., vol. 230 (2009), pp. 69–82.CrossRefGoogle Scholar
[20] J.-Chen, S., The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J. Global Optim., vol. 36 (2006), pp. 565–580.CrossRefGoogle Scholar
[21]Chen, J.-S., Pan, S., A family of NCP-functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., vol. 40 (2008), pp. 389–404.CrossRefGoogle Scholar
[22]Huang, Z.H., Han, J., Xu, D.C., Zhang, L.P., The non-interior continuation methods for solving the P0 function nonlinear complementarity problem, Science in China, vol.44 (2001), pp. 1107–1114.CrossRefGoogle Scholar
[23]Huang, Z.H., Han, J., Chen, Z., A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function, J. Optim. Theory Appl., vol. 117 (2003), pp. 39–68.CrossRefGoogle Scholar
[24] J.-Chen, S., Pan, S., A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for P0-NCPs, J. Comput. Appl. Math., vol. 220 (2008), pp. 464–479.CrossRefGoogle Scholar
[25]Sun, D.F., A. Regularization Newton Method For Solving Nonlinear Complementarity Problems, Appl. Math. Optim., vol. 40 (1999), pp. 315–339.CrossRefGoogle Scholar
[26]Huang, Z.H., Sufficient conditions on nonemptiness and boundedness of the solution set of the P0 function nonlinear complementarity problem, Oper. Res. Lett., vol. 30 (2002), pp. 202–210.CrossRefGoogle Scholar
[27]Zhang, Y., Huang, Z.H., A nonmonotone smoothing-type algorithm for solving a system of equalities and inequalities, J. Comput. Appl. Math., vol. 233 (2010), pp. 2312–2321.CrossRefGoogle Scholar
[28]Billups, S.C., Dirkse, S.P., Ferris, M.C., A comparison of algorithms for large scale mixed complementarity problems, Comput. Optim. Appl., vol. 7 (1997), pp. 3–25.CrossRefGoogle Scholar
[29]Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., vol. 15 (1977), pp. 957–972.CrossRefGoogle Scholar
[30]Qi, L.Q., Sun, J., A nonsmooth version of Newton’s method, Math. Program., vol. 58 (1993), pp. 353–367.CrossRefGoogle Scholar
[31]Clarke, F.H., Optimization and Nonsmooth Analysis, Wiley, New York, 1983.Google Scholar
[32]Hu, S.L., Huang, Z.H., Lu, N., A non-monotone line search algorithm for unconstrained optimization, J. Sci. Comput., vol.42 (2010), pp. 38–53.CrossRefGoogle Scholar
[33]Facchinei, F., Kanzow, C., Beyond monotonicity in regularization methods for the nonlinear complementarity problems, SIAM J. Optim., vol. 37 (1999), pp. 1150–1161.Google Scholar
[34]Dolan, E.D., Moré, J.J., Benchmarking optimization software with performance profiles, Math. Program., vol. 91 (2002), pp. 201–213.CrossRefGoogle Scholar