×

zbMATH — the first resource for mathematics

On the resolution of monotone complementarity problems. (English) Zbl 0859.90113
Summary: A reformulation of the nonlinear complementarity problem (NCP) as an unconstrained minimization problem is considered. It is shown that any stationary point of the unconstrained objective function is a solution of NCP if the mapping \(F\) involved in NCP is continuously differentiable and monotone, and that the level sets are bounded if \(F\) is continuous and strongly monotone. A descent algorithm is described which uses only function values of \(F\). Some numerical results are given.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Software:
L-BFGS; MCPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R.W. Cottle, J.-S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic Press: Boston-San Diego-New York-London-Sydney-Tokyo-Toronto, 1992. · Zbl 0757.90078
[2] S.P. Dirkse and M.C. Ferris, ”MCPLIB: A collection of nonlinear mixed complementarity problems,” Technical Report 1215, Computer Sciences Department, University of Wisconsin, Madison, WI, February 1994.
[3] F. Facchinei, Private communications, November 1994.
[4] A. Fischer, ”A special Newton-type optimization method” Optimization, vol. 24, pp. 269–284, 1992. · Zbl 0814.65063
[5] A. Fischer, ”A Newton-type method for positive semidefinite linear complementarity problems,” to appear in Journal of Optimization Theory and Applications. · Zbl 0839.90121
[6] R. Fletcher, Practical Methods of Optimization, John Wiley and Sons: Chichester-New York-Brisbane-Toronto-Singapore, second edition 1987. · Zbl 0905.65002
[7] A. Friedlander, J.M. Martínez, and S.A. Santos ”Resolution of linear complementarity problems using minimization with simple bounds” Technical Report, Department of Applied Mathematics, University of Campinas, Campinas, Brazil, November 1993.
[8] M. Fukushima, ”Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,” Mathematical Programming, vol. 53, pp. 99–110, 1992. · Zbl 0756.90081
[9] J.C. Gilbert and C. Lemaréchal, ”Some numerical experiments with variable-storage quasi-Newton algorithms,” Mathematical Programming, vol. 45, pp. 407–435, 1989. · Zbl 0694.90086
[10] P.T. Harker, Lectures on Computation of Equilibria with Equation-Based Methods, CORE Lecture Series, CORE–Center for Operations Research and Econometrics, Université Catholique de Louvain, Louvain, Belgium, 1993.
[11] P.T. Harker and J.-S. Pang, ”Finite dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications” Mathematical Programming, vol. 48, pp. 161–220, 1990. · Zbl 0734.90098
[12] P.T. Harker and B. Xiao, ”Newton’s method for the nonlinear complementarity problem: a B-differentiable equation approach,” Mathematical Programming, vol. 48, pp. 339–357, 1990. · Zbl 0724.90071
[13] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems 187, Springer-Verlag: Berlin, Germany, 1981. · Zbl 0452.90038
[14] G. Isac, Complementarity Problems, Lecture Notes in Mathematics 1528, Springer-Verlag: Berlin-Heidelberg-New York-London-Paris-Tokyo-Hongkong-Barcelona-Budapest, 1992.
[15] C. Kanzow, ”Global convergence properties of some iterative methods forlinear complementarity problems” to appear in SIAM Journal on Optimization. · Zbl 0847.90132
[16] C. Kanzow, ”Nonlinear complementarity as unconstrained optimization,” to appear in Journal of Optimization Theory and Applications. · Zbl 0845.90120
[17] C. Kanzow, ”Some equation-based methods for the nonlinear complementarity problem” Optimization Methods and Software, vol. 3, pp. 327–340, 1994.
[18] C. Kanzow, ”An unconstrained optimization technique for large-scale linearly constrained convex minimization problems,” Computing, vol. 53, pp. 101–117, 1994. · Zbl 0820.90099
[19] D.C. Liu and J. Nocedal, ”On the limited memory BFGS method for large scale optimization,” Mathematical Programming, vol. 45, pp. 503–528, 1989. · Zbl 0696.90048
[20] Z.-Q. Luo, O.L. Mangasarian, J. Ren, and M.V. Solodov, ”New error bounds for the linear complementarity problem,” to appear in Mathematics of Operations Research. · Zbl 0833.90113
[21] H.-J. Lüthi, Komplementaritöts- und Fixpunktalgorithmen in der mathematischen Programmierung, Spieltheorie und Ökonomie, Lecture Notes in Economics and Mathematics System 129, Springer-Verlag: Berlin-Heidelberg-New York, 1976.
[22] O.L. Mangasarian, ”Equivalence of the complementarity problem to a system of nonlinear equations” SIAM Journal on Applied Mathematics, vol. 31, pp. 89–92, 1976. · Zbl 0339.90051
[23] O.L. Mangasarian and M.V. Solodov, ”Nonlinear complementarity as unconstrained and constrained minimization” Mathematical Programming, vol. 62, pp. 277–297, 1993. · Zbl 0813.90117
[24] K.G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Sigma Series in Applied Mathematics, 3, Heldermann Verlag: Berlin, 1988. · Zbl 0634.90037
[25] S.G. Nash and J. Nocedal, ”A numerical study of the limited memory BFGS method and the truncated–Newton method for large scale optimization,” SIAM Journal on Optimization, vol. 1, pp. 358–372, 1991. · Zbl 0756.65091
[26] J. Nocedal, ”Updating quasi-Newton matrices with limited storage,” Mathematics of Computation, vol. 35, pp. 773–782, 1980. · Zbl 0464.65037
[27] J. Nocedal, ”The performance of several algorithms for large scale unconstrained optimization,” in: Large-Scale Numerical Optimization, T.F. Coleman and Y. Li (Eds.), SIAM, Philadelphia, pp. 138–151, 1990.
[28] J.-S. Pang, ”Newton’s method for B-differentiable equations,” Mathematics of Operations Research, vol. 15: 311–341, 1990. · Zbl 0716.90090
[29] J.-S. Pang, ”A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,” Mathematical Programming, vol. 51, pp. 101–131, 1991. · Zbl 0733.90063
[30] J.-S. Pang and S.A. Gabriel, ”NE/SQP: A robust algorithms for the nonlinear complementarity problem,” Mathematical Programming, vol. 60, pp. 295–337, 1993. · Zbl 0808.90123
[31] K. Taji, M. Fukushima, and T. Ibaraki, ”A globally convergent Newton method for solving strongly monotone variational inequalities,” Mathematical Programming, vol. 58, pp. 369–383, 1993. · Zbl 0792.49007
[32] P. Tseng, ”Growth behaviour of a class of merit functions for the nonlinear complementarity problem,” Technical Report, Department of Mathematics, University of Washington, Seattle, WA, May 1994.
[33] P. Tseng, N. Yamashita, and M. Fukushima, ”Equivalence of complementarity problems to differentiable minimization: a unified approach,” to appear in SIAM Journal on Optimization. · Zbl 0853.65067
[34] W. Warth and J. Werner, ”Effiziente Schrittweitenfunktionen bei unrestringierten Optimierungsaufgaben,” Computing, vol. 19, pp. 59–72, 1977. · Zbl 0367.90101
[35] J. Werner, ”Über die globale Konvergenz von Variable-Metrik-Verfahren mit nicht-exakter Schrittweitenbestimmung,” Numerische Mathematik, vol. 31, pp. 321–334, 1978. · Zbl 0427.65047
[36] N. Yamashita and M. Fukushima, ”On stationary points of the implicit Lagrangian for nonlinear complementarity problems,” to appear in Journal of Optimization Theory and Applications. · Zbl 0824.90131
[37] X. Zou, I.M. Navon, M. Berger, K.H. Phua, T. Schlick, and F.X.Le Dimet, ”Numerical experience with limited-memory quasi-Newton and truncated Newton methods,” SIAM Journal on Optimization, vol. 3, pp. 582–608, 1993. · Zbl 0784.90086
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.