Abstract
The mixed complementarity problem can be reformulated as a nonsmooth equation by using the median operator. In this paper, we first study some useful properties of this reformulation and then derive the Chen-Harker-Kanzow-Smale smoothing function for the mixed complementarity problem. On the basis of this smoothing function, we present a smoothing Newton method for solving the mixed complementarity problem. Under suitable conditions, the method exhibits global and quadratic convergence properties. We also present a smoothing Broyden-like method based on the same smoothing function. Under appropriate conditions, the method converges globally and superlinearly.
Article PDF
Similar content being viewed by others
References
B. Chen and X. Chen, “A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints,” Computational Optimizational and Applications, vol. 17, pp. 131-158, 2000.
B. Chen, X. Chen, and C. Kanzow, “A penalized Fischer-Burmeister NCP-function: Theoretical investigation and numerical results,” Mathematical Programming, vol. 88, pp. 211-216, 2000.
B. Chen and P.T. Harker, “A non-interior-point continuation method for linear complementarity problems,” SIAM Journal on Matrix Analysis and Applications, vol. 14, pp. 1168-1190, 1993.
B. Chen and P.T. Harker, “Smooth approximations to nonlinear complementarity problems,” SIAM Journal on Optimization, vol. 7, pp. 403-420, 1997.
C. Chen and O.L. Mangasarian, “A class of smoothing functions for nonlinear and mixed complementarity problems,” Computational Optimization and Applications, vol. 5, pp. 97-138, 1996.
X. Chen, “Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations,” Journal of Computational and Applied Mathematics, vol. 80, pp. 105-126, 1997.
X. Chen, Z. Nashed, and L. Qi, “Convergence of Newton's method for singular smooth and nonsmooth equations using adaptive outer inverses,” SIAM Journal on Optimization, vol. 7, pp. 445-462, 1997.
X. Chen, L. Qi, and D. Sun, “Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities,” Mathematics of Computation, vol. 67, pp. 519-540, 1998.
F.H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons: New York, 1983.
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.
T. De Luca, F. Facchinei, and C. Kanzow, “A theoretical and numerical comparison of some semismooth algorithms for complementarity problems,” Computational Optimization and Applications, vol. 16, pp. 173-205, 2000.
J.E. Dennis, Jr. and J.J. Moré, “A characterization of superlinear convergence and its applications to quasi-Newton methods,” Mathematics of Computation, vol. 28, pp. 549-560, 1974.
F. Facchinei, A. Fischer, and C. Kanzow, “A semismooth Newton method for variational inequalities: The case of box constraints,” in Complementarity and Variational Problems: State of the Art, M.C. Ferris and J.S. Pang (Eds.), SIAM: Philadelphia, 1997, pp. 76-90.
A. Fischer, “Solution of monotone complementarity problems with locally Lipschitzian functions,” Mathematical Programming, vol. 76, pp. 513-532, 1997.
M. Fukushima and L. Qi (Eds.), Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers: Boston, 1999.
S.A. Gabriel and J.J. More, “Smoothing of mixed complementarity problems,” in Complementarity and Variational Problems: State of the Art, M.C. Ferris and J.S. Pang (Eds.), SIAM: Philadelphia, 1997, pp. 105-116.
S.A. Gabriel and J.S. Pang, “An inexact NE/SQP method for solving the nonlinear complementarity problem,” Computational Optimization and Applications, vol. 1, pp. 67-91, 1992.
H. Jiang, L. Qi, X. Chen, and D. Sun, “Semismoothness and superlinear convergence in nonsmooth optimization and nonsmooth equations,” in Nonlinear Optimization and Applications, G. Di Pillo and F. Giannessi (Eds.), Plenum Press: New York, 1996, pp. 197-212.
C. Kanzow, “Some noninterior continuation methods for linear complementarity problems,” SIAM Journal on Matrix Analysis and Applications, vol. 17, pp. 851-868, 1996.
C. Kanzow and M. Fukushima, “Theoretical and Numerical investigate of the D-gap function for box constrained variational inequalities,” Mathematical Programming, vol. 83, pp. 55-87, 1998.
C. Kanzow and H. Jiang, “A continuation method for (strongly) monotone variational inequalities,” Mathematical Programming, vol. 81, pp. 103-125, 1998.
C. Kanzow, N. Yamashita, and M. Fukushima, “New NCP-functions and their properties,” Journal of Optimimization Theory and Applications, vol. 94, pp. 115-135, 1997.
D.H. Li and M. Fukushima, “Broyden-like methods for variational inequality and nonlinear complementarity problems with global and superlinear convergence,” Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Technical Report 98016, Sep. 1998.
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 A. Trangenstein, “On the global convergence of Broyden's method,” Mathematic of Computation, vol. 30, pp. 523-540, 1976.
J.S. Pang, “A B-differentiable equation based, globally, and locally quadratically convergent algorithm for nonlinear 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, “Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems,” Mathematics of Operations Research, vol. 24, pp. 440-471, 1999.
L. Qi and X. Chen, “A globally convergent successive approximation method for severely nonsmooth equations,” SIAM Journal on Control and Optimization, vol. 33, pp. 402-418, 1995.
L. Qi and J. Sun, “A nonsmooth version of Newton's method,” Mathematical Programming, vol. 58, pp. 353-367, 1993.
L. Qi and D. Sun, “Nonsmoth equations and smoothing methods”, in Progress in Optimization: Contributions from Australia, A. Eberhard, B. Glover, R. Hill and D. Ralph, (Eds.), Kluwer Academic Publishers, pp. 121-146, 1999.
L. Qi, D. Sun, and G. Zhou, “A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities,” Mathematical Programming, vol. 87, pp. 1-35, 2000.
S. Smale, “Algorithms for solving the equations,” in Proceedings of the International Congress of Mathematicians, Berkeley, California, 1986, pp. 172-195.
D. Sun and R.S. Womersley, “A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,” SIAM Journal on Optimization, vol. 9, pp. 388-413, 1999.
K. Yamada, N. Yamashita, and M. Fukushima, “A new derivative-free descent method for the nonlinear complementarity problem,” in Nonlinear Optimization and Applications 2, G. Di Pillo and F. Giannessi (Eds.), Kluwer Academic Publishers: Boston, 2000, pp. 463-487.
N. Yamashita and M. Fukushima, “Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems,” Mathematical Programming, vol. 76, pp. 469-491, 1997.
N. Yamashita and M. Fukushima, “Equivalent unconstrained minimization and global error bounds for variational inequality problems,” SIAM Journal on Control and Optimization, vol. 35, pp. 273-284, 1997.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Li, D., Fukushima, M. Smoothing Newton and Quasi-Newton Methods for Mixed Complementarity Problems. Computational Optimization and Applications 17, 203–230 (2000). https://doi.org/10.1023/A:1026502415830
Issue Date:
DOI: https://doi.org/10.1023/A:1026502415830