×

zbMATH — the first resource for mathematics

Stationary points of bound constrained minimization reformulations of complementarity problems. (English) Zbl 0893.90161
Summary: We consider two merit functions which can be used for solving the nonlinear complementarity problem via nonnegatively constrained minimization. One of the functions is the restricted implicit Lagrangian [M. Fukushima, Mathematical Programming 53, 99-110 (1993; Zbl 0756.90081), O. L. Mangasarian and M. V. Solodov, Mathematical Programming 62, 277-297 (1993; Zbl 0813.90117), K. Taji and M. Fukushima, J. Oper. Res. Soc. Jap. 37, 310-331 (1994; Zbl 0829.90125)], and the other appears to be new. We study the conditions under which a stationary point of the minimization problem is guaranteed to be a solution of the underlying complementarity problem. It appears that, for both formulations, the same regularity condition is needed. This condition is closely related to the one used by F. Facchinei and C. Kanzow [Technical Report A-97, Inst. Appl. Math., Univ. Hamburg, Germany (1995)] for unrestricted implicit Lagrangian. Some new sufficient conditions are also given.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] FUKUSHIMA, M., Equivalent Differentiable Optimization Problems and Descent Methods for Asymmetric Variational Inequality Problems, Mathematical Programming, Vol. 53, pp. 99–110, 1992. · Zbl 0756.90081 · doi:10.1007/BF01585696
[2] MANGASARIAN, O. L., and SOLODOV, M. V., Nonlinear Complementarity as Unconstrained and Constrained Minimization, Mathematical Programming, Vol. 62, pp. 277–297, 1993. · Zbl 0813.90117 · doi:10.1007/BF01585171
[3] TAJI, K., and FUKUSHIMA, M., Optimization Based Globally Convergent Methods for the Nonlinear Complementarity Problem, Journal of the Operations Research Society of Japan, Vol. 37, pp. 310–331, 1994. · Zbl 0829.90125
[4] FACCHINEI, F., and KANZOW, C., On Unconstrained and Constrained Stationary Points of the Implicit Lagrangian, Technical Report A-97, Institute of Applied Mathematics, University of Hamburg, Hamburg, Germany, 1995. · Zbl 0914.90249
[5] COTTLE, R., GIANNESSI, F., and LIONS, J. L., Variational Inequalities and Complementarity Problems: Theory and Applications, Wiley, New York, New York, 1980.
[6] PANG, J. S., Complementarity Problems, Handbook of Global Optimization, Edited by R. Horst and P. Pardalos, Kluwer Academic Publishers, Boston, Massachusetts, pp. 271–338, 1995.
[7] COTTLE, R., PANG, J. S., and STONE, R., The Linear Complementarity Problem, Academic Press, New York, New York, 1992. · Zbl 0757.90078
[8] KANZOW, C., Nonlinear Complementarity as Unconstrained Optimization, Journal of Optimization Theory and Applications, Vol. 88, pp. 139–155, 1996. · Zbl 0845.90120 · doi:10.1007/BF02192026
[9] GEIGER, C., and KANZOW, C., On the Resolution of Monotone Complementarity Problems, Computational Optimization and Applications, Vol. 5, pp. 155–173, 1996. · Zbl 0859.90113 · doi:10.1007/BF00249054
[10] LUO, Z. Q., and TSENG, P., A New Class of Merit Functions for the Nonlinear Complementarity Problem, SIAM Journal on Optimization (to appear). · Zbl 0886.90158
[11] LI, W., A Merit Function and a Newton-Type Method for Symmetric Linear Complementarity Problems, SIAM Journal on Optimization (to appear). · Zbl 0886.90156
[12] MORÉ, J., Global Methods for Nonlinear Complementarity Problems, Technical Report MCS-P429–0494, Mathematics and Computer Sciences Division, Argonne National Laboratory, 1994.
[13] TSENG, P., YAMASHITA, N., and FUKUSHIMA, M., Equivalence of Complementarity Problems to Differentiable Minimization: A Unified Approach, SIAM Journal on Optimization, Vol. 6, pp. 446–460, 1996. · Zbl 0853.65067 · doi:10.1137/0806024
[14] FERRIS, M., and RALPH, D., Projected Gradient Methods for Nonlinear Complementarity Problems via Normal Maps, Recent Advances in Nonsmooth Optimization, Edited by D. Z. Du, L. Qi, and R. Womersley, World Scientific Publishers, Singapore, pp. 1–29, 1994.
[15] FISCHER, A., An NCP Function and Its Use for the Solution of Complementarity Problems, Recent Advances in Nonsmooth Optimization, Edited by D. Z. Du, L. Qi, and R. Womersley, World Scientific Publishers, Singapore, pp. 88–105, 1995. · Zbl 0948.90133
[16] LUCA, T. D., FACCHINEI, F., and KANZOW, C., A Semismooth Equation Approach to the Solution of Nonlinear Complementarity Problems, Technical Report, Dipartimento di Informatica e Sistemistica, Università di Roma ”La Sapienza”, Rome, Italy, 1995. · Zbl 0874.90185
[17] FACCHINEL, F., FISCHER, A., and KANZOW, C., Inexact Newton Methods for Semismooth Equations with Applications to Variational Inequality Problems, Technical Report, Institute of Numerical Mathematics, Dresden University of Technology, Dresden, Germany, 1995.
[18] PANG, J. S., and GABRIEL, S., NE/SQP: A Robust Algorithm for the Nonlinear Complementarity Problem, Mathematical Programming, Vol. 60, pp. 295–337, 1993. · Zbl 0808.90123 · doi:10.1007/BF01580617
[19] JIANG, H., and QI, L., A New Nonsmooth Equations Approach to Nonlinear Complementarities, Technical Report AMR94/31, School of Mathematics, University of New South Wales, Sydney, NSW, Australia, 1994.
[20] FUKUSHIMA, M., Merit Functions for Variational Inequality and Complementarity Problems, Nonlinear Optimization and Applications, Edited by G. D. Pillo and F. Giannessi, Plenum Publishing Corporation, New York, New York, 1996. · Zbl 0996.90082
[21] MANGASARIAN, O. L., Nonlinear Programming, McGraw-Hill, New York, New York, 1969.
[22] LUO, Z. Q., MANGASARIAN, O. L., REN, J., and SOLODOV, M. V., New Error Bounds for the Linear Complementarity Problem, Mathematics of Operations Research, Vol. 19, pp. 880–892, 1994. · Zbl 0833.90113 · doi:10.1287/moor.19.4.880
[23] YAMASHITA, N., and FUKUSHIMA, M., On Stationary Points of the Implicit Lagrangian for Nonlinear Complementarity Problems, Journal of Optimization Theory and Applications, Vol. 84, pp. 653–663, 1995. · Zbl 0824.90131 · doi:10.1007/BF02191990
[24] JIANG, H., Unconstrained Minimization Approaches to Nonlinear Complementarities, Technical Report AMR94/33, School of Mathematics, University of New South Wales, Sydney, NSW, Australia, 1994.
[25] PENG, J. M., The Convexity of the Implicit Lagrangian, Technical Report, State Key Laboratory of Scientific and Engineering Computing, Academia Sinica, Beijing, China, 1995.
[26] YAMASHITA, N., TAJI, K., and FUKUSHIMA, M., Unconstrained Optimization Reformulations of Variational Inequality Problems, Technical Report, Graduate School of Information Science, Nara Institute of Science and Technology, Nara, Japan, 1995. · Zbl 0879.90180
[27] KANZOW, C., YAMASHITA, N., and FUKUSHIMA, M., New NCP Functions and Their Properties, Technical Report TR-IS-96010, Nara Institute of Science and Technology, Nara, Japan, 1996. · Zbl 0886.90146
[28] FISCHER, A., A New Constrained Optimization Reformulation for Complementarity Problems, Technical Report MATH-NM–10–1995, Institute for Numerical Mathematics, Technical University of Dresden, Dresden, Germany, 1995.
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.