Abstract
In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.
Similar content being viewed by others
References
R.W. Cottle, J.S. Pang, and R. E. Stone, The Linear Complementarity Problem, Academic Press: Boston, MA, 1992.
R.S. Dembo, S.C. Eisenstat, and T. Steihaug, “Inexact Newton methods”, SIAM J. Numer. Anal., vol. 19, pp. 400–408, 1982.
A.R. de Pierro and A.N. Iusem, “Convergence properties of iterative methods for symmetric positive semidefinite linear complementarity problems,” Math. of Op. Res., forthcoming, 1992.
T.L. Friesz, R.L. Tobin, T.E. Smith, and P.T. Harker, “A nonlinear complementarity formulation and solution procedure for the general derived demand network equilibrium problem,” J. of Reg. Sci., vol. 23, pp. 337–359, 1983.
R.H.W. Hoppe and H.D. Mittlemann, “A multi-grid continuation method for parameter-dependent variational inequalities,” J. of Comp. and App., Math., vol. 26, pp. 35–46, 1989.
R.A. Horn and C.R. Johnson, Matrix analysis Cambridge University Press: Cambridge, UK, 1985.
A.N. Iusem, “On the convergence of iterative methods for symmetric linear complementarity problems,” Math. Prog., forthcoming, 1992.
N.H. Josephy, “Newton's method for generalized equations”, Mathematics Research Center, University of Wisconsin, Madison, WI, technical report 1965, 1979.
W. Li, “Remarks on convergence of matrix splitting algorithm,” Department of Mathematics and Statistics, Old Dominion University, Norfolk, VA, technical report TR91–8, 1991.
Y.Y. Lin and J.S. Pang, “Iterative methods for large convex quadratic programs: A survey,” SIAM J. Con. and Opt., vol. 25, pp. 383–411, 1987.
Z.Q. Luo and P. Tseng, “On the convergence of a matrix splitting algorithm for the symmetric linear complementarity problem,” SIAM J. Con. and Opt., vol. 29, pp. 1037–1060, 1991.
O.L. Mangasarian, “Convergence of iterates of a inexact matrix splitting algorithm for the symmetric monotone linear complementarity problem” SIAM J. Opt.,vol. 1, pp. 114–122, 1991.
E. Miersemann and H.D. Mittelmann, “Continuation for parametrized variational inequalities,” J. of Comp. and App. Math., vol. 26, pp. 23–24, 1989.
J.S. Pang, “Inexact Newton methods for the nonlinear complementarity problem,” Math. Prog., vol. 36, pp. 54–71, 1986.
J.S. Pang, “Newton's method for B-differentiable equations,” Math. of Op. Res., vol. 15, pp. 311–341. 1990.
J.S. Pang, “Convergence of splitting and Newton methods for complementarity problems: An application of some sensitivity results,” Math. Prog., forthcoming, 1992.
J.S. Pang and S.A. Gabriel, “NE/SQP: A robust algorithm for the nonlinear complementarity problem,” Math. Prog., forthcoming, 1992.
J.S. Pang and J.M. Yang, “Two-stage parallel iterative methods for the symmetric linear complementarity problem,” Annals of Op. Res., vol. 14, pp. 61–75, 1988.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gabriel, S.A., Pang, JS. An inexact NE/SQP method for solving the nonlinear complementarity problem. Comput Optim Applic 1, 67–91 (1992). https://doi.org/10.1007/BF00247654
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00247654