×

zbMATH — the first resource for mathematics

Newton’s method for the nonlinear complementarity problem: a B- differentiable equation approach. (English) Zbl 0724.90071
The nonlinear complementarity problem \(F^ T(x)x=0\), \(F(x)\in R^ n_+\) can be equivalently formulated as a system of nonlinear equations \(H(x)=\min (x,F(x))=0\), where the ‘min’ operation is taken componentwise. The function H is not Fréchet differentiable in general, however, it is B-differentiable. S. Robinson was the first to study Newton’s method for equations with such functions. The present paper develops a previous work by the first author and J.-S. Pang [in: Computational solution of nonlinear systems of equations, Proc. SIAM-AMS Summer Semin., Ft. Collins/CO (USA) 1988, Lect. Appl. Math. 26, 265-284 (1990; Zbl 0699.65054)] converting the original problem into a system of equations through the use of a Minty map. At each step of the algorithm a linear system is solved and a line search for a given merit function is performed. Numerical results and a comparison with the traditional Josephy-Newton method are presented.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49J50 Fréchet and Gateaux differentiability in optimization
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D.P. Bertsekas and E.M. Gafni, ”Projection methods for variational inequalities with application to the traffic assignment problem,”Mathematical Programming Study 17 (1982) 139–159. · Zbl 0478.90071
[2] J.E. Dennis Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983).
[3] G.J. Habetler and M.M. Kostreva, ”On a direct algorithm for nonlinear complementarity problems,”SIAM Journal of Control and Optimization 16 (1978) 504–511. · Zbl 0392.90083
[4] P.T. Harker, ”Alternative models of spatial competition,”Operations Research 34 (1986) 410–425. · Zbl 0602.90018
[5] P.T. Harker, ”Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities,”Mathematical Programming 41 (1988) 29–59. · Zbl 0825.49019
[6] P.T. Harker and J.S. Pang, ”Finite dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,”Mathematical Programming B 48 (1990) 1–60. · Zbl 0738.90059
[7] P.T. Harker and J.S. Pang, ”A damped-Newton method for the linear complementarity problem,” in: G. Allgower and K. Gears, eds.,Computational Solutions of Nonlinear Systems of Equations, Lectures in Applied Mathematics, Vol. 26 (American Mathematical Society, Providence, RI, 1990) 265–284. · Zbl 0699.65054
[8] N.H. Josephy, ”Newton’s method for generalized equations,” Technical summary report No. 1965, Mathematics Research Center, University of Wisconsin (Madison, Wisconsin, 1979).
[9] N.H Josephy, ”Quasi-Newton method for generalized equations,” Technical Summary Report No. 1966, Mathematics Research Center, University of Wisconsin (Medison, WI, 1979).
[10] M. Kojima and S. Shindo, ”Extension of Newton and quasi-Newton methods to systems of PC equations,”Journal of the Operations Research Society of Japan 29 (1986) 352–374. · Zbl 0611.65032
[11] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087
[12] M. Kojima, S. Mizuno and T. Name, ”A new continuation method for complementarity problems with uniform P-functions,”Mathematical Programming 43 (1989) 107–113. · Zbl 0673.90084
[13] M. Kojima, S. Mizuno and T. Nome, ”Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems,” Report No. B-199, Department of Information Sciences, Tokyo Institute of Technology (Tokyo, Japan, 1988).
[14] M.M. Kostreva, ”Direct algorithms for complementarity problems,” unpublished Ph.D. Dissertation, Department of Mathematics, Rensselaer Polytechnic Institute (Troy, NY, 1976).
[15] M.M. Kostreva, ”Block pivot methods for solving the complementarity problem,”Linear Algebra and its Applications 21 (1978) 207–215. · Zbl 0395.65032
[16] O.L. Mangasarian, ”Equivalence of the complementarity problem to a system of nonlinear equations,”SIAM Journal on Applied Mathematics 31 (1976) 89–92. · Zbl 0339.90051
[17] L. Mathiesen, ”Computation of economic equilibria by a sequence of linear complementarity problems,”Mathematical Programming Study 23 (1985) 144–162. · Zbl 0579.90093
[18] L. Mathiesen, ”Computational experience in solving equilibrium models by a sequence of linear complementarity problems,”Operations Research 33 (1985) 1225–1250. · Zbl 0583.90097
[19] L. Mathiesen, ”An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: an example,”Mathematical Programming 37 (1987) 1–18. · Zbl 0613.90098
[20] K.G. Murty, ”Note on a Bard-type scheme for solving the complementarity problem,”Opsearch 11 (1974) 123–130.
[21] K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Helderman, Berlin, 1988). · Zbl 0634.90037
[22] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[23] J.S. Pang and D. Chan, ”Iterative methods for variational and complementarity problems,”Mathematical Programming 24 (1982) 284–313. · Zbl 0499.90074
[24] J.S. Pang, ”Inexact Newton methods for the nonlinear complementarity problem,”Mathematical Programming 36 (1986) 54–71. · Zbl 0613.90097
[25] J.S. Pang, ”Newton’s method for B-differentiable equations,”Mathematics of Operations Research, forthcoming. · Zbl 0716.90090
[26] M.J.D. Powell, ”A method for nonlinear constraints in minimization problems,” in: R. Fletcher, ed.,Optimization (Academic Press, New York, 1969). · Zbl 0194.47701
[27] P.V. Preckel, ”A modified Newton method for the nonlinear complementarity problem,” Paper presented at the ORSA/TIMS Joint National Meeting, Miami Beach, Florida, October 1986.
[28] S.M. Robinson, ”Implicit B-differentiability in generalized equations,” Technical Summary Report No. 2854, Mathematics Research Center, University of Wisconsin (Madison, WI, 1985).
[29] S.M. Robinson, ”Local structure of feasible sets in nonlinear programming, Part III: stability and sensitivity,”Mathematical Programming Study 30 (1987) 45–66. · Zbl 0629.90079
[30] S.M. Robinson, ”An implicit function theorem for B-differentiable functions,” Working Paper, Department of Industrial Engineering, University of Wisconsin (Madison, WI, 1988).
[31] S.M. Robinson, ”Newton’s method for a class of nonsmooth functions,” Working Paper, Department of Industrial Engineering, University of Wisconsin (Madison, WI, 1988).
[32] R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053
[33] H. Scarf,The Computation of Economic Equilibria, (Yale University Press, New Haven, CT, 1973). · Zbl 0311.90009
[34] A. Shapiro, ”On concepts of directional differentiability,” Research Report 73/88(18), Department of Mathematics and Applied Mathematics, University of South Africa (Pretoria, South Africa, 1988). · Zbl 0682.49015
[35] P.K. Subramanian, ”Gauss-Newton methods for the nonlinear complementarity problem,” Technical Summary Report No. 2845, Mathematics Research Center, University of Wisconsin (Madison, WI, 1985).
[36] P.K. Subramanian, ”A note on the least two norm solutions of monotone complementarity problems,”Applied Mathematics Letters 1 (1988) 395–397. · Zbl 0706.65061
[37] R.L. Tobin, ”A variable dimension solution approach for the general spatial price equilibrium problem,”Mathematical Programming 40 (1988) 33–51. · Zbl 0645.90095
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.