×

zbMATH — the first resource for mathematics

Smoothing functions and smoothing Newton method for complementarity and variational inequality problems. (English) Zbl 1032.49017
Summary: This paper provides for the first time some computable smoothing functions for variational inequality problems with general constraints. This paper proposes also a new version of the smoothing Newton method and establishes its global and superlinear (quadratic) convergence under conditions weaker than those previously used in the literature. These are achieved by introducing a general definition for smoothing functions, which include almost all the existing smoothing functions as special cases.

MSC:
49J40 Variational inequalities
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C53 Methods of quasi-Newton type
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] CLARKE, F. H., Optimization and Nonsmooth Analysis, Wiley, New York, NY, 1983. · Zbl 0582.49001
[2] PANG, J. S., and QI, L., Nonsmooth Equations: Motivation and Algorithms, SIAM Journal on Optimization, Vol. 3, pp. 443-465, 1993. · Zbl 0784.90082
[3] DONTCHEV, A. L., QI, H. D., and QI, L., Convergence of Newton’s Method for Best Convex Interpolation, Numerische Mathematik, Vol. 87, pp. 435-456, 2001. · Zbl 0970.65009
[4] QI, L., and SUN, D., A Survey of Some Nonsmooth Equations and Smoothing Newton Methods, Progress in Optimization: Contributions from Australasia, Edited by A. Eberhard, B. Glover, R. Hill, and D. Ralph, Kluwer Academic Publishers, Boston, Massachusetts, pp. 121-146, 1999. · Zbl 0957.65042
[5] SUN, D., and QI, L., Solving Variational Inequality Problems via Smoothing-Nonsmooth Reformulations, Journal of Computational and Applied Mathematics, Vol. 129, pp. 37-62, 2001. · Zbl 0987.65059
[6] CHEN, X., QI, L., and SUN, D., 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. · Zbl 0894.90143
[7] CHEN, X., and YE, Y., On Homotopy-Smoothing Methods for Variational Inequalities, SIAM Journal on Control and Optimization, Vol. 37, pp. 589-616, 1999. · Zbl 0973.65051
[8] EAVES, B. C., On the Basic Theorem of Complementarity, Mathematical Programming, Vol. 1, pp. 68-75, 1971. · Zbl 0227.90044
[9] HARKER, P. T., and PANG, J. S., Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithms, and Applications, Mathematical Programming, Vol. 48, pp. 161-220, 1990. · Zbl 0734.90098
[10] FISCHER, A., A Special Newton-Type Optimization Method, Optimization, Vol. 24, pp. 269-284, 1992. · Zbl 0814.65063
[11] ROBINSON, S. M., Normal Maps Induced by Linear Transformations, Mathematics of Operations Research, Vol. 17, pp. 691-714, 1992. · Zbl 0777.90063
[12] MIFFLIN, R., Semismooth and Semiconvex Functions in Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 15, pp. 957-972, 1977. · Zbl 0376.90081
[13] POLAK, E., Optimization: Algorithms and Consistent Approximations, Springer, New York, NY, 1997. · Zbl 0899.90148
[14] QI, L., and SUN, J., A Nonsmooth Version of Newton’s Method, Mathematical Programming, Vol. 58, pp. 353-367, 1993. · Zbl 0780.90090
[15] GOWDA, M. S., and SZNAJDER, R., Weak Univalence and Connectedness of Inverse Images of Continuous Functions, Mathematics of Operations Research, Vol. 24, pp. 255-261, 1999. · Zbl 0977.90060
[16] RAVINDRAN, G., and GOWDA, M. S., Regularization of P 0-Functions in Box-Constrained Variational Inequality Problems, SIAM Journal on Optimization, Vol. 11, pp. 748-760, 2000. · Zbl 1010.90083
[17] QI, L., and CHEN, X., A Globally Convergent Successive Approximation Method for Severely Nonsmooth Equations, SIAM Journal on Control and Optimization, Vol. 33, pp. 402-418, 1995. · Zbl 0833.90109
[18] CHEN, C., and MANGASARIAN, O. L., A Class of Smoothing Functions for Nonlinear and Mixed Complementarity Problems, Computational Optimization and Applications, Vol. 5, pp. 97-138, 1996. · Zbl 0859.90112
[19] QI, L., SUN, D., and ZHOU, G., A New Look at Smoothing Newton Methods for Nonlinear Complementarity Problems and Box-Constrained Variational Inequalities, Mathematical Programming, Vol. 87, pp. 1-35, 2000. · Zbl 0989.90124
[20] CHEN, B., and HARKER, P. T., A Noninterior-Point Continuation Method for Linear Complementarity Problems, SIAM Journal on Matrix Analysis and Applications, Vol. 14, pp. 1168-1190, 1993. · Zbl 0788.65073
[21] KANZOW, C., Some Noninterior Continuation Methods for Linear Complementarity Problems, SIAM Journal on Matrix Analysis and Applications, Vol. 17, pp. 851-868, 1996. · Zbl 0868.90123
[22] SMALE, S., Algorithms for Solving Equations, Proceedings of the International Congress of Mathematicians, Berkeley, California, pp. 172-195, 1986.
[23] ZANG, I., A Smoothing-Out Technique for Min-Max Optimization, Mathematical Programming, Vol. 19, pp. 61-71, 1980. · Zbl 0468.90064
[24] GABRIEL, S. A., and MORÉ, J. J., Smoothing of Mixed Complementarity Problems, Complementarity and Variational Problems: State of the Art, Edited by M. C. Ferris and J. S. Pang, SIAM, Philadelphia, Pennsylvania, pp. 105-116, 1997. · Zbl 0886.90154
[25] ORTEGA, J. M., and RHEINBOLDT, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, NY, 1970. · Zbl 0241.65046
[26] FERRIS, M. C., and PANG, J. S., Engineering and Economic Applications of Complementarity Problems, SIAM Review, Vol. 39, pp. 669-713, 1997. · Zbl 0891.90158
[27] KANZOW, C., and JIANG, H., A Continuation Method for (Strongly) Monotone Variational Inequalities, Mathematical Programming, Vol. 81, pp. 140-157, 1998. · Zbl 0920.90131
[28] KUNTZ, L., and SCHOLTES, S., Structural Analysis of Nonsmooth Mappings, Inverse Functions, and Metric Projections, Journal of Mathematical Analysis and Applications, Vol. 188, pp. 346-386, 1994. · Zbl 0809.49014
[29] LLOYD, N. G., Degree Theory, Cambridge University Press, Cambridge, England, 1978.
[30] FACCHINEI, F., and PANG, J. S., Total Stability of Variational Inequalities, Preprint, Department of Mathematical Sciences, Johns Hopkins University, Baltimore, Maryland, 1998.
[31] BURKE, J., and XU, S., The Global Linear Convergence of a Noninterior Path-Following Algorithm for Linear Complementarity Problem,Mathematics of Operations Research, Vol. 23, pp. 719-734, 1998. · Zbl 0977.90056
[32] CHEN, B., and CHEN, X., A Global and Local Superlinear Continuation-Smoothing Method for P0CR0 and Monotone NCP, SIAM Journal on Optimization, Vol. 9, pp. 624-645, 1999. · Zbl 0955.90132
[33] CHEN, B., and HARKER, P. T., Smooth Approximations to Nonlinear Complementarity Problems, SIAM Journal on Optimization, Vol. 7, pp. 403-420, 1997. · Zbl 0879.90177
[34] CHEN, B., and XIU, N., A Global Linear and Local Quadratic Noninterior Continuation Method for Nonlinear Complementarity Problems Based on the Chen-Mangasarian Smoothing Function, SIAM Journal on Optimization, Vol. 9, pp. 605-623, 1999. · Zbl 1037.90052
[35] QI, L., Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations, Mathematics of Operations Research, Vol. 18, pp. 227-244, 1993. · Zbl 0776.65037
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.