×

zbMATH — the first resource for mathematics

A smoothing Levenberg-Marquardt method for NCP. (English) Zbl 1104.65061
Nonlinear complementarity problems (NCPs) are converted to an equivalent system of smooth nonlinear equations by using a smoothing technique. Then a Levenberg-Marquardt type method is used to solve the system of nonlinear equations. The method has the following merits: (i) any cluster point of the iteration sequence is a solution of the \(P_{0}\)-NCP; (ii) it generates a bounded sequence if the \(P_{0}\)-NCP has a nonempty and bounded solution set; (iii) if the generalized Jacobian is nonsingular at a solution point, then the whole sequence converges to the (unique) solution of the \(P_{0}\)-NCP superlinearly; (iv) for the \(P_{0}\)-NCP, if an accumulation point of the iteration sequence satisfies strict complementary condition, then the whole sequence converges to this accumulation point superlinearly.

MSC:
65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahn, B.H., Iterative methods for linear complementarity problem with upperbounds and lowerbounds, Math. prog., 26, 265-315, (1983)
[2] Burke, J.; Xu, S., A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem, Math. prog., 87, 113-130, (2000) · Zbl 1081.90603
[3] Chen, B.; Chen, X., A global and local superlinear continuation-smoothing method for P0+R0 and monotone NCP, SIAM J. optim., 9, 624-645, (1999)
[4] Chen, B.; Harker, P.T., A non-interior-point continuation method for linear complementarity problems, SIAM J. matrix anal. appl., 14, 1168-1190, (1993) · Zbl 0788.65073
[5] Chen, B., Error bound for R0-type and monotone nonlinear complementarity problems, J. optim. theory appl., 108, 2, 297-316, (2001) · Zbl 1041.90055
[6] Chen, B.; Xiu, N., A superlinear noninterior one-step continuation method for monotone LCP in the absence of strict complementarity, J. optim. theory appl., 108, 2, 317-332, (2001) · Zbl 1041.90056
[7] Chen, X.; Ye, Y., On smoothing methods for the P0 matrix linear complementarity problem, SIAM J. optim., 11, 341-363, (2000) · Zbl 0994.65077
[8] Cottle, R.W.; Pang, J.-S.; Stone, R.W., The linear complementarity problem, (1992), Academic New York, NY · Zbl 0757.90078
[9] H. Dan, N. Yamashita, M. Fukushima, Convergence Properties of the inexact Levenberg-Marquardt method under local error bound conditions, Technical Report 2001-003, Department of Applied Mathematics and Physics, Kyoto University, January 2001. · Zbl 1030.65049
[10] De Luca, T.; Fancchinei, F.; Kanzow, C., A semismooth equation approach to the solution of nonlinear complementarity problems, Math. prog., 75, 407-439, (1996) · Zbl 0874.90185
[11] S. Engelke, C. Konzow, Improved smoothing-type methods for the solution of linear programs, Preprint, Institute of Applied Mathematics, University of Hamburg, Hamburg, March, 2000.
[12] Facchinei, F.; Kanzow, C., A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems, Math. prog., 76, 493-512, (1997) · Zbl 0871.90096
[13] Ferris, M.C.; Pang, J.-S., Engineering and economic application of complementarity problems, SIAM rev., 39, 669-713, (1997) · Zbl 0891.90158
[14] Geiger, C.; Kanzow, K., On the resolution of monotone complementarity problems, Comput. optim. appl., 5, 155-173, (1996) · Zbl 0859.90113
[15] Gowda, M.S.; Sznajder, J.J., Weak univalence and connectedness of inverse images of continuous functions, Math. oper. res., 24, 255-261, (1999) · Zbl 0977.90060
[16] Huang, Z.H., Sufficient condition on nonemptiness and boundness of the solution set of the P0 function nonlinear complementarity problem, Oper. res. lett., 30, 202-210, (2002)
[17] Huang, Z.H.; Qi, L.; Sun, D., Sub-quadratic convergence of a smoothing Newton algorithm for the P0- and monotone LCP, Math. progr., ser. A, 99, 423-441, (2004) · Zbl 1168.90646
[18] Karamardian, S., Complementarity problem over cones with monotone and pseudomonotone maps, J. optim., theory appl., 18, 5-445, (1976) · Zbl 0304.49026
[19] Luo, Z.Q.; Pang, J.S., Error bounds for analysis systems and their applications, Math. progr., 67, 1-28, (1994)
[20] Mclinden, L., Stable monotone variational inequalities, Math. progr., 48, 303-338, (1990) · Zbl 0726.90093
[21] Mangsarian, O.L.; Ren, J., New error bounds for the nonlinear complementarity problem, Commun. appl. nonlinear anal., 1, 49-56, (1994) · Zbl 0860.90117
[22] Murty, K.G., Linear complementarity, linear and nonlinear programming, (1988), Helderman-Verlag Berlin · Zbl 0634.90037
[23] Pang, J.S., A posterior error bound for the linearly-constrained variational inequality problem, Math. oper. res., 12, 474-484, (1987)
[24] Pang, J.S., Error bounds in mathematical programming, Math. progr., 79, 299-332, (1997) · Zbl 0887.90165
[25] Pang, J.S.; Gabriel, S.A., NE/SQP: A robust algorithm for the nonlinear complementarity problem, Math. progr., 60, 295-337, (1993) · Zbl 0808.90123
[26] L. Qi, D. Sun, Smoothing functions and smoothing Newton method for complemenarity and variational inequality problems, Report, University of New South Wales, Sydney, Australia, 1998.
[27] Qi, L.; Sun, D.; Zhou, G., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. prog., 87, 1-35, (2000) · Zbl 0989.90124
[28] Tseng, P., Growth behaviour of aclass of merit functions for the nonlinear complementarity problem, J. optim. theory appl., 89, 17-37, (1996) · Zbl 0866.90127
[29] Yamashita, N.; Fukushima, M., On the rate of convergence of the levenberg – marquardt method, Computing, 15, 239-249, (2001) · Zbl 1001.65047
[30] N. Yamashita, H. Dan, M. Fukushima, On the identification of degenerate indices in the nonlinear complementarity problem with proxmal point algorithm, Technical Report 2001-003, Department of Applied Mathematics and Physics, Kyoto University, February 2001.
[31] Yamashita, N.; Fukushima, M., Modified Newton methods for solving a semismooth reformulation of monotone complementarity, Math. prog., 76, 469-491, (1997) · Zbl 0872.90102
[32] Y. Zhao, D. Li, A global and locally superlinearly convergent non-interior-point algorithm for P0 LCPs, Tech. Report, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, 2001.
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.