Abstract
In last decades, there has been much effort on the solution and the analysis of the nonlinear complementarity problem (NCP) by reformulating NCP as an unconstrained minimization involving an NCP function. In this paper, we propose a family of new NCP functions, which include the Fischer-Burmeister function as a special case, based on a p-norm with p being any fixed real number in the interval (1,+∞), and show several favorable properties of the proposed functions. In addition, we also propose a descent algorithm that is indeed derivative-free for solving the unconstrained minimization based on the merit functions from the proposed NCP functions. Numerical results for the test problems from MCPLIB indicate that the descent algorithm has better performance when the parameter p decreases in (1,+∞). This implies that the merit functions associated with p∈(1,2), for example p=1.5, are more effective in numerical computations than the Fischer-Burmeister merit function, which exactly corresponds to p=2.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Billups, S.C., Dirkse, S.P., Soares, M.C.: A comparison of algorithms for large scale mixed complementarity problems. Comput. Optim. Appl. 7, 3–25 (1997)
Chen, J.-S.: On some NCP-functions based on the generalized Fischer-Burmeister function. Asia-Pac. J. Oper. Res. 24, 401–420 (2007)
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)
Cottle, R.W., Pang, J.-S., Stone, R.-E.: The Linear Complementarity Problem. Academic Press, New York (1992)
Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997)
Ferris, M.C., Mangasarian, O.L., Pang, J.-S. (eds.): Complementarity: Applications, Algorithms and Extensions. Kluwer Academic, Dordrecht (2001)
Fischer, A.: A special Newton-type optimization methods. Optimization 24, 269–284 (1992)
Fischer, A.: Solution of the monotone complementarity problem with locally Lipschitzian functions. Math. Program. 76, 513–532 (1997)
Fukushima, M.: Merit functions for variational inequality and complementarity problems. In: Di Pillo, G., Giannessi, F. (eds.) Nonlinear Optimization ans Applications, pp. 155–170. Plenum Press, New York (1996)
Geiger, C., Kanzow, C.: On the resolution of monotone complementarity problems. Comput. Optim. Appl. 5, 155–173 (1996)
Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)
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)
Higham, N.J.: Estimating the matrix p-norm. Num. Math. 62, 539–555 (1992)
Jiang, H.: Unconstrained minimization approaches to nonlinear complementarity problems. J. Glob. Optim. 9, 169–181 (1996)
Kanzow, C.: Nonlinear complementarity as unconstrained optimization. J. Optim. Theory Appl. 88, 139–155 (1996)
Mangasarian, O.L., Solodov, M.V.: Nonlinear complementarity as unconstrained and constrained minimization. Math. Program. 62, 277–297 (1993)
Mangasarian, O.L.: Equivalence of the complementarity problem to a system of nonlinear equations. SIAM J. Appl. Math. 31, 89–92 (1976)
Pang, J.-S.: Complementarity problems. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization, pp. 271–338. Kluwer Academic, Boston (1994)
Qi, H.-D., Liao, L.-Z.: A smoothing Newton method for gneral nonlinear complementarity problems. Comput. Optim. Appl. 17, 231–253 (2000)
Sun, D., Qi, L.-Q.: On NCP-functions. Comput. Optim. Appl. 13, 201–220 (1999)
Tseng, P.: Global behaviour of a class of merit functions for the nonlinear complementarity problem. J. Optim. Theory Appl. 89, 17–37 (1996)
Yamada, K., Yamashita, N., Fukushima, M.: A new derivative-free descent method for the nonlinear complementarity problems. In: Pillo, G.D., Giannessi, F. (eds.) Nonlinear Optimization and Related Topics, pp. 463–489. Kluwer Academic, Dordrecht (2000)
Yamashita, N., Fukushima, M.: On stationary points of the implicit Lagrangian for the nonlinear complementarity problems. J. Optim. Theory Appl. 84, 653–663 (1995)
Yamashita, N., Fukushima, M.: Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems. Math. Program. 76, 469–491 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
J.-S. Chen is a member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. J.-S. Chen’s work is partially supported by National Science Council of Taiwan.
Rights and permissions
About this article
Cite this article
Chen, JS., Pan, S. A family of NCP functions and a descent method for the nonlinear complementarity problem. Comput Optim Appl 40, 389–404 (2008). https://doi.org/10.1007/s10589-007-9086-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9086-0