Inexact Newton methods for the nonlinear complementarity problem.

*(English)*Zbl 0613.90097An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application.

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C30 | Nonlinear programming |

65K05 | Numerical mathematical programming methods |

##### Keywords:

error measure; exact Newton method; nonlinear complementarity; sequence of linear complementarity subproblems
Full Text:
DOI

##### References:

[1] | H.Z. Aashtiani, ”The multi-modal traffic assignment problem,” Ph.D. dissertation, Alfred P. Sloan School of Management, Massachusetts Institute of Technology (1979). |

[2] | R.W. Cottle, S.G. Duval and K. Zikan, ”A Lagrangean relaxation algorithm for the constrained matrix problem,”Naval Research Logistics Quarterly 33 (1986) 55–76 · Zbl 0598.90070 |

[3] | R.S. Dembo, S.G. Eisenstat and T. Steihaug, ”Inexact Newton methods,”SIAM Journal on Numerical Analysis 19 (1982) 400–408. · Zbl 0478.65030 |

[4] | R.S. Dembo and U. Tulowitzki, ”Sequential truncated quadratic programming methods,” in Paul T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numericla Optimization 1984 (SIAM, Philadelphia, 1985) pp. 83–101. · Zbl 0583.65042 |

[5] | R.S. Dembo and U. Tulowitzki ”Local convergence analysis for successive inexact quadratic programming methods,” SOM Working Paper, Series B #78, School of Organization and Management, Yale University (Revised October 1984). · Zbl 0883.90115 |

[6] | J.E. Dennis and J. MorĂ©, ”Quasi-Newton methods: Motivation and theory,”SIAM Review 19 (1977) 46–89. · Zbl 0356.65041 |

[7] | B.C. Eaves, ”Where solving for stationary points by LCPs is mixing Newton iterates,” in B.C. Eaves, F.J. Gould, H.O. Peitgen and M.J. Todd, eds.Homotopy Methods and Global Convergence (Plenum Press, New York, 1983) pp. 63–78. · Zbl 0508.65026 |

[8] | P.C. Jones, R. Saigal and M. Schneider, ”Computing nonlinear network equilibria,”Mathematical Programming 31 (1985) 57–66. · Zbl 0571.90091 |

[9] | N.H. Josephy, ”Newton’s method for generalized equations,” Technical Summary Report No. 1965, Mathematics Research Center, University of Wisconsin (Madison, Wisconsin, 1979). |

[10] | N.H. Josephy, ”Quasi-Newton methods for generalized equations,” Technical Summary Report No. 1966, Mathematics Research Center, University of Wisconsin (Madison, Wisconsin, 1979). |

[11] | N.H. Josephy, ”A Newton method for the PIES energy model,” Technical Summary Report No. 1977, Mathematics Research Center, University of Wisconsin (Madison, Wisconsin, 1979). |

[12] | L. Mathiesen, ”Computational experience in solving equilibrium models by a sequence of linear complementarity problems,”Operations Research 33 (1985) 1225–1250. · Zbl 0583.90097 |

[13] | J. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046 |

[14] | J.S. Pang, ”Solution of the general multicommodity spatial equilibrium problems by variational and complementarity methods,”Journal of Regional Science 24 (1984) 403–414. |

[15] | J.S. Pang, ”More results on the convergence of iterative methods for the symmetric linear complementarity problem,” to appear inJournal of Optimization Theory and Applications. · Zbl 0568.90096 |

[16] | J.S. Pang and D. Chan, ”Iterative methods for variational and complementarity problems,”Mathematical Programming 24 (1982) 284–313. · Zbl 0499.90074 |

[17] | J.S. Pang and C.S. Yu, ”Linearized simplicial decomposition methods for computing traffic equilibria on networks,”Networks 14 (1984) 427–438. · Zbl 0545.90037 |

[18] | P.V. Preckel, ”Alternative algorithms for computing economic equilibria,” manuscript, Department of Agricultural Economics, Purdue University (West Lafayette, Indiana, 1984). |

[19] | S.M. Robinson, ”Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming algorithms,”Mathematical Programming 7 (1974) 1–16. · Zbl 0294.90078 |

[20] | S.M. Robinson, ”An implicit-function theorem for generalized variational inequalities,” Technical Summary Report No. 1672, Mathematics Research Center, University of Wisconsin (Madison, Wisconsin, 1976). |

[21] | S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094 |

[22] | S.M. Robinson, ”Generalized equations,” in A. Bachem, M. Grotschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, 1983) pp. 346–367. |

[23] | R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053 |

[24] | U. Tulowitzki, ”Inexact successive linearization methods for variational inequality problems,” SOM Working Paper, School of Organization and Management, Yale University (New Haven, Connecticut, October 1984). |

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.