Abstract
In this paper we introduce a general line search scheme which easily allows us to define and analyze known and new semismooth algorithms for the solution of nonlinear complementarity problems. We enucleate the basic assumptions that a search direction to be used in the general scheme has to enjoy in order to guarantee global convergence, local superlinear/quadratic convergence or finite convergence. We examine in detail several different semismooth algorithms and compare their theoretical features and their practical behavior on a set of large-scale problems.
Similar content being viewed by others
References
D.P. Bertsekas, Nonlinear Programming, Athena Scientific: Belmont, MA, 1995.
B. Chen, X. Chen, and C. Kanzow, “A penalized Fischer-Burmeister function: Theoretical investigation and numerical results,” Preprint 126, Institute of Applied Mathematics, University of Hamburg, Hamburg, Germany, September 1997. (Revised May 1998).
B. Chen and P.T. Harker, “A noninterior continuation method for quadratic and linear programming,” SIAM Journal on Optimization, vol. 3, pp. 503–515, 1993.
F.H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons: New York, 1983. (Reprinted by SIAM, Philadelphia, PA, 1990.)
R.W. Cottle, J.-S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic Press: Boston, 1992.
T. De Luca, F. Facchinei, and C. Kanzow, “A semismooth equation approach to the solution of nonlinear complementarity problems,” Mathematical Programming, vol. 75, pp. 407–439, 1996.
J.E. Dennis, Jr. and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall: Englewood Cliffs, NJ, 1983. (Reprinted by SIAM, Philadelphia, PA, 1996).
S.P. Dirkse and M.C. Ferris, “Crash techniques for large-scale complementairty problems,” in Complementarity and Variational Problems: State of the Art, M.C. Ferris and J.-S. Pang (Eds.), SIAM: Philadelphia, PA, 1997, pp. 40–53.
F. Facchinei, A. Fischer, and C. Kanzow, “Inexact Newton methods for semismooth equations with applications to variational inequality problems,” in Nonlinear Optimization and Applications, G. Di Pillo and F. Giannessi (Eds.), Plenum Press: New York, NY, 1996, pp. 125–139.
F. Facchinei and C. Kanzow, “A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems,” Mathematical Programming, vol. 76, pp. 493–512, 1997.
F. Facchinei and J. Soares, “A new merit function for nonlinear complementarity problems and a related algorithm,” SIAM Journal on Optimization, vol. 7, pp. 225–247, 1997.
M.C. Ferris and J.-S. Pang, “Engineering and economic applications of complementarity problems,” SIAM Review, vol. 39, pp. 669–713, 1997.
A. Fischer, “A special Newton-type optimization method,” Optimization, vol. 24, pp. 269–284, 1992.
A. Fischer, “Solution of monotone complementarity problems with locally Lipschitzian functions,” Mathematical Programming, vol. 76, pp. 513–532, 1997.
A. Fischer and C. Kanzow: “On finite termination of an iterative method for linear complementarity problems,” Mathematical Programming, vol. 74, pp. 279–292, 1996.
C. Geiger and C. Kanzow, “On the resolution of monotone complementarity problems,” Computational Optimization and Applications, vol. 5, pp. 155–173, 1996.
M.A. Gomes-Ruggiero, J.M. Martínez, and S.A. Santos, “Solving nonsmooth equations by means of quasi-Newton methods with globalization,” in Recent Advances in Nonsmooth Optimization, D.-Z. Du, L. Qi, and R. Womersley (Eds.), World Scientific Publisher: Singapore, 1995, pp. 121–140.
P.T. Harker and J.-S. Pang, “Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,” Mathematical Programming, vol. 48, pp. 161–220, 1990.
H. Jiang and L. Qi, “A new nonsmooth equations approach to nonlinear complementarity problems,” SIAM Journal on Control and Optimization, vol. 35, pp. 178–193, 1997.
C. Kanzow, “Semismooth Newton-type methods for the solution of nonlinear complementarity problems,” Habilitation Thesis, Institute of Applied Mathematics, University of Hamburg, Hamburg, Germany, April 1997.
C. Kanzow and M. Fukushima, “Solving box constrained variational inequality problems by using the natural residual with D-gap function globalization,” Operations Research Letters, vol. 23, pp. 45–51, 1998.
C. Kanzow and H. Kleinmichel, “A new class of semismooth Newton-type methods for nonlinear complementarity problems,” Computational Optimization and Applications, vol. 11, pp. 227–251, 1998.
C. Kanzow, N. Yamashita, and M. Fukushima, “New NCP-functions and their properties,” Journal of Optimization Theory and Applications, vol. 94, pp. 115–135, 1997.
L. Lukšan, “Inexact trust region method for large sparse systems of nonlinear equations,” Journal of Optimization Theory and Applications, vol. 81, pp. 569–590, 1994.
Z.-Q. Luo and P. Tseng, “A new class of merit functions for the nonlinear complementarity problem,” in Complementarity and Variational Problems: State of the Art, M.C. Ferris and J.-S. Pang (Eds.), SIAM: Philadelphia, PA, 1997, pp. 204–225.
O.L. Mangasarian, “Equivalence of the complementarity problem to a system of nonlinear equations”, SIAM Journal on Applied Mathematics, vol. 31, pp. 89–92, 1976.
J.M. Martínez and L. Qi, “Inexact Newton methods for solving nonsmooth equations,” Journal of Computational and Applied Mathematics, vol. 60, pp. 127–145, 1995.
R. Mifflin, “Semismooth and semiconvex functions in constrained optimization,” SIAM Journal on Control and Optimization, vol. 15, pp. 957–972, 1977.
J.J. Moré and W.C. Rheinboldt, “On P-and S-functions and related classes of n-dimensional nonlinear mappings,” Linear Algebra and its Applications, vol. 6, pp. 45–68, 1973.
J.-S. Pang, “Newton's method for B-differentiable equations,” Mathematics of Operations Research, vol. 15, pp. 311–341, 1990.
J.-S. Pang, “A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,” Mathematical Programming, vol. 51, pp. 101–131, 1991.
J.-S. Pang and L. Qi, “Nonsmooth equations: Motivation and algorithms,” SIAM Journal on Optimization, vol. 3, pp. 443–465, 1993.
L. Qi, “Convergence analysis of some algorithms for solving nonsmooth equations,” Mathematics of Operations Research, vol. 18, pp. 227–244, 1993.
L. Qi and J. Sun, “A nonsmooth version of Newton's method,” Mathematical Programming, vol. 58, pp. 353–368, 1993.
D. Ralph, Private communications, March 1998.
D. Sun and L. Qi, “On NCP-functions,” Computational Optimization and Applications, vol. 13, pp. 201–220, 1999.
P. Tseng, “Growth behavior of a class of merit functions for the nonlinear complementarity problem,” Journal of Optimization Theory and Applications, vol. 89, pp. 69–94, 1996.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
De Luca, T., Facchinei, F. & Kanzow, C. A Theoretical and Numerical Comparison of Some Semismooth Algorithms for Complementarity Problems. Computational Optimization and Applications 16, 173–205 (2000). https://doi.org/10.1023/A:1008705425484
Issue Date:
DOI: https://doi.org/10.1023/A:1008705425484