A regularized projection method for complementarity problems with non-Lipschitzian functions

Alefeld, Goetz; Chen, Xiaojun

doi:10.1090/S0025-5718-07-02025-X

A regularized projection method for complementarity problems with non-Lipschitzian functions
HTML articles powered by AMS MathViewer

by Goetz Alefeld and Xiaojun Chen PDF

Math. Comp. 77 (2008), 379-395 Request permission

Abstract:

We consider complementarity problems involving functions which are not Lipschitz continuous at the origin. Such problems arise from the numerical solution for differential equations with non-Lipschitzian continuity, e.g. reaction and diffusion problems. We propose a regularized projection method to find an approximate solution with an estimation of the error for the non-Lipschitzian complementarity problems. We prove that the projection method globally and linearly converges to a solution of a regularized problem with any regularization parameter. Moreover, we give error bounds for a computed solution of the non-Lipschitzian problem. Numerical examples are presented to demonstrate the efficiency of the method and error bounds.

References

G. E. Alefeld, X. Chen, and F. A. Potra, Numerical validation of solutions of complementarity problems: the nonlinear case, Numer. Math. 92 (2002), no. 1, 1–16. MR 1917363, DOI 10.1007/s002110100351
John W. Barrett and Robert M. Shanahan, Finite element approximation of a model reaction-diffusion problem with a non-Lipschitz nonlinearity, Numer. Math. 59 (1991), no. 3, 217–242. MR 1106381, DOI 10.1007/BF01385777
Xiaojun Chen and Shuhuang Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program. 106 (2006), no. 3, Ser. A, 513–525. MR 2216793, DOI 10.1007/s10107-005-0645-9
Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone, The linear complementarity problem, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1992. MR 1150683
John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems I, II, Springer-Verlag, New York, 2003.
Steven A. Gabriel and Jorge J. Moré, Smoothing of mixed complementarity problems, Complementarity and variational problems (Baltimore, MD, 1995) SIAM, Philadelphia, PA, 1997, pp. 105–116. MR 1445075
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
Jong-Shi Pang, Error bounds in mathematical programming, Math. Programming 79 (1997), no. 1-3, Ser. B, 299–332. Lectures on mathematical programming (ismp97) (Lausanne, 1997). MR 1464772, DOI 10.1016/S0025-5610(97)00042-7
Uwe Schäfer, An enclosure method for free boundary problems based on a linear complementarity problem with interval data, Numer. Funct. Anal. Optim. 22 (2001), no. 7-8, 991–1011. MR 1871871, DOI 10.1081/NFA-100108319
Paul Tseng, An infeasible path-following method for monotone complementarity problems, SIAM J. Optim. 7 (1997), no. 2, 386–402. MR 1443625, DOI 10.1137/S105262349427409X
Richard S. Varga, Matrix iterative analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713, DOI 10.1007/978-3-642-05156-2