Global and superlinear convergence of the

smoothing Newton method and its application

to general box constrained variational inequalities

Authors:
X. Chen, L. Qi and D. Sun

Journal:
Math. Comp. **67** (1998), 519-540

MSC (1991):
Primary 90C33, 90C30, 65H10

DOI:
https://doi.org/10.1090/S0025-5718-98-00932-6

MathSciNet review:
1458218

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The smoothing Newton method for solving a system of nonsmooth equations , which may arise from the nonlinear complementarity problem, the variational inequality problem or other problems, can be regarded as a variant of the smoothing method. At the th step, the nonsmooth function is approximated by a smooth function , and the derivative of at is used as the Newton iterative matrix. The merits of smoothing methods and smoothing Newton methods are global convergence and convenience in handling. In this paper, we show that the smoothing Newton method is also superlinearly convergent if is semismooth at the solution and satisfies a Jacobian consistency property. We show that most common smooth functions, such as the Gabriel-Moré function, have this property. As an application, we show that for box constrained variational inequalities if the involved function is -uniform, the iteration sequence generated by the smoothing Newton method will converge to the unique solution of the problem globally and superlinearly (quadratically).

**1.**O. Axelsson and I.E. Kaporin,*On the solution of nonlinear equations for nondifferentiable mappings*, Technical Report, Department of Mathematics, University of Nijmegen, The Netherlands, 1994.**2.**S.C. Billups, S.P. Dirkse and M.C. Ferris,*A comparison of algorithms for large-scale mixed complementarity problems*, Comp. Optim. Appl., 7 (1997), pp. 3-25. CMP**97:09****3.**B. Chen and P. Harker,*Smooth approximations to nonlinear complementarity problems*, SIAM J. Optim., 7 (1997), pp. 403-420. CMP**97:11****4.**C. Chen and O.L. Mangasarian,*A class of smoothing functions for nonlinear and mixed complementarity problems,*Comp. Optim. Appl., 5 (1996), pp. 97-138. MR**96m:90102****5.**X. Chen and L. Qi,*A parameterized Newton method and a quasi-Newton method for solving nonsmooth equations*, Comp. Optim. Appl., 3 (1994), pp. 157-179. MR**95e:90090****6.**X. Chen and T. Yamamoto,*Convergence domains of certain iterative methods for solving nonlinear equations,*Numer. Funct. Anal. Optim., 10 (1989), pp. 37-48. MR**90a:65137****7.**F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983. MR**85m:49002****8.**T. De Luca, F. Facchinei and C. Kanzow,*A semismooth equation approach to the solution of nonlinear complementarity problems,*Math. Programming, 75 (1996), pp. 407-439. CMP**97:05****9.**S.P. Dirkse and M.C. Ferris,*The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems*, Optim. Method. Softw., 5 (1995), pp. 123-156.**10.**B.C. Eaves,*On the basic theorem of complementarity,*Math. Programming, 1 (1971), pp. 68-75. MR**44:5103****11.**F. Facchinei, A. Fischer and C. Kanzow,*Inexact Newton methods for semismooth equations with applications to variational inequality problems,*in: G. Di Pillo and F. Giannessi, eds., ``Nonlinear Optimization and Applications'', Plenum Press, New York, 1996, pp. 155-170.**12.**F. Facchinei, A. Fischer and C. Kanzow,*A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience,*Preprint 102, Institute of Applied Mathematics, University of Hamburg, Hamburg, December 1995.**13.**F. Facchinei, A. Fischer and C. Kanzow,*A semismooth Newton method for variational inequalities: The case of box constraints*, in: M.C. Ferris and J.S. Pang, eds., ``Complementarity and Variational Problems: State of the Art,'' SIAM, Philadelphia, Pennsylvania, 1997, pp. 76-90. CMP**97:11****14.**F. Facchinei and C. Kanzow,*A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems,*Math. Programming, 76 (1997), pp. 493-512. CMP**97:08****15.**A. Fischer,*A special Newton-type optimization method,*Optim., 24 (1992), pp. 269-284. MR**94g:90109****16.**A. Fischer,*An NCP-function and its use for the solution of complementarity problems,*in: D. Du, L. Qi and R. Womersley, eds., ``Recent Advances in Nonsmooth Optimization'', World Scientific Publishers, New Jersey, 1995, pp. 88-105.**17.**M. Fukushima,*Merit functions for variational inequality and complementarity problems,*in: G. Di Pillo and F. Giannessi eds., ``Nonlinear Optimization and Applications'', Plenum Publishing Corporation, New York, 1996, pp. 155-170.**18.**S.A. Gabriel and J.J. Moré,*Smoothing of mixed complementarity problems*, in: M.C. Ferris and J.S. Pang, eds., ``Complementarity and Variational Problems: State of the Art,'' SIAM, Philadelphia, Pennsylvania, 1997, pp. 105-116. CMP**97:11****19.**M.S. Gowda and R. Sznajder,*The generalized order linear complementarity problem*, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 779-795. MR**95e:90108****20.**P.T. Harker and J.S. Pang,*Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications,*Math. Programming, 48 (1990), pp. 161-220. MR**91g:90166****21.**P.T. Harker and B. Xiao,*Newton's method for the nonlinear complementarity problem: A B-differentiable equation approach,*Math. Programming, 48 (1990), pp. 339-357. MR**91m:90176****22.**M. Heinkenschloß, C.T. Kelley and H.T. Tran,*Fast algorithms for nonsmooth compact fixed point problems*, SIAM J. Numer. Anal., 29 (1992), pp. 1769-1792. MR**94c:65073****23.**C.M. Ip and J. Kyparisis,*Local convergence of quasi-Newton methods for B-differentiable equations,*Math. Programming, 56 (1992), pp. 71-89. MR**93c:65072****24.**G. Isac and M. M. Kostreva,*The generalized order complementarity problem, models and iterative methods*, Ann. Oper. Res., 44 (1993), pp. 63-92.**25.**H. Jiang and L. Qi,*A new nonsmooth equations approach to nonlinear complementarity problems,*SIAM J. Control Optim., 35 (1997), pp. 178-193. CMP**97:07****26.**H. Jiang, L. Qi, X. Chen and D. Sun,*Semismoothness and superlinear convergence in nonsmooth optimization and nonsmooth equations,*in: G. Di Pillo and F. Giannessi eds., ``Nonlinear Optimization and Applications'', Plenum Press, New York, 1996, pp. 197-212.**27.**C. Kanzow and M. Fukushima,*Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities,*Math. Programming, to appear.**28.**C. Kanzow and H. Jiang,*A continuation method for (strongly) monotone variational inequalities,*Math. Programming, to appear.**29.**B. Kummer,*Newton's method for non-differentiable functions,*in: J. Guddat, B. Bank, H. Hollatz, P. Kall, D. Klatte, B. Kummer, K. Lommatzsch, L. Tammer, M. Vlach and K. Zimmerman, eds., ``Advances in Mathematical Optimization'', Akademi-Verlag, Berlin, 1988, pp. 114-125. MR**89h:90201****30.**Z.Q. Luo and P. Tseng,*A new class of merit functions for the nonlinear complementarity problem*, in: M.C. Ferris and J.S. Pang, eds., ``Complementarity and Variational Problems: State of the Art,'' SIAM, Philadelphia, Pennsylvania, 1997, pp. 204-225. CMP**97:11****31.**J.M. Martínez, and L. Qi,*Inexact Newton methods for solving nonsmooth equations,*J. Comp. Appl. Math., 60 (1995), pp. 127-145. MR**96h:65076****32.**J.M. Ortega and W.C. Rheinboldt, Iterative Solutions of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR**42:8686****33.**J.V. Outrata,*On optimization problems with variational inequality constraints,*SIAM J. Optim., 4 (1994), pp. 340-357. MR**95g:90075****34.**J.V. Outrata and J. Zowe,*A Newton method for a class of quasi-variational inequalities,*Comp. Optim. Appl., 4 (1995), pp. 5-21. MR**95k:49023****35.**J.S. Pang,*Newton's method for B-differentiable equations,*Math. Oper. Res., 15 (1990), pp. 311-341. MR**91m:49029****36.**J.S. Pang,*A B-differentiable equation based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,*Math. Programming, 51 (1991), pp. 101-131. MR**92f:90062****37.**J.S. Pang,*Complementarity problems,*in: R. Horst and P. Pardalos, eds., ``Handbook of Global Optimization'', Kluwer Academic Publishers, Boston, pp. 271-338, 1995. MR**97a:90095****38.**J.S. Pang and L. Qi,*Nonsmooth equations: Motivation and algorithms,*SIAM J. Optim., 3 (1993), pp. 443-465. MR**94g:90145****39.**J.S. Pang and J.C. Yao,*On a generalization of a normal map and equation*, SIAM J. Control Optim., 33 (1995), pp. 168-184. MR**95m:90131****40.**L. Qi,*Convergence analysis of some algorithms for solving nonsmooth equations*, Math. Oper. Res., 18 (1993), pp. 227-244. MR**95f:65109****41.**L. Qi,*C-differentiability, C-Differential operators and generalized Newton methods*, AMR 96/5, Applied Mathematics Report, University of New South Wales, Sydney, 1996.**42.**L. Qi and X. Chen,*A globally convergent successive approximation method for severely nonsmooth equations*, SIAM J. Control Optim., 33 (1995), pp. 402-418. MR**96a:90035****43.**L. Qi and J. Sun,*A nonsmooth version of Newton's method*, Math. Programming, 58 (1993), pp. 353-367. MR**94b:90077****44.**D. Ralph,*Global convergence of damped Newton's method for nonsmooth equations via the path search,*Math. Oper. Res., 19 (1994), pp. 352-389. MR**95e:49012****45.**D. Ralph and S. Wright,*Superlinear convergence of an interior-point method for monotone variational inequalities*, Technical Report MCS-P556-0196, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, 1996.**46.**W.C. Rheinboldt,*A unified convergence theory for a class of iterative processes*, SIAM J. Numer. Anal., 5 (1968), pp. 42-63. MR**37:1061****47.**S. M. Robinson,*Newton's method for a class of nonsmooth functions,*Set-Valued Anal., 2 (1994), pp. 291-305. MR**95c:65093****48.**D. Sun, M. Fukushima and L. Qi,*A computable generalized Hessian of the D-gap function and Newton-type methods for variational inequality problem*, in: M.C. Ferris and J.S. Pang, eds., ``Complementarity and Variational Problems: State of the Art,'' SIAM, Philadelphia, Pennsylvania, 1997, pp. 452-473. CMP**97:11****49.**D. Sun and J. Han,*Newton and quasi-Newton methods for a class of nonsmooth equations and related problems*, SIAM J. Optim., 7 (1997), pp. 463-480. CMP**97:11****50.**T. Yamamoto,*Split nonsmooth equations and verification of solution*, in: ``Numerical Analysis, Scientific Computing, Computer Science'', the Zeitschrift fuer Angewandte Mathematik und Mechanik (ZAMM) with the Akademie Verlag, Berlin, 1996, pp. 199-202. CMP**97:11****51.**N. Yamashita and M. Fukushima,*Modified Newton methods for solving semismooth reformulations of monotone complementarity problems,*Math. Programming, 76 (1997), pp. 469-491. CMP**97:08****52.**I. Zang,*A smoothing-out technique for min-max optimization*, Math. Programming, 19 (1980), pp. 61-77. MR**82c:90085**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
90C33,
90C30,
65H10

Retrieve articles in all journals with MSC (1991): 90C33, 90C30, 65H10

Additional Information

**X. Chen**

Affiliation:
School of Mathematics The University of New South Wales Sydney 2052, Australia

Email:
X.Chen@unsw.edu.au

**L. Qi**

Affiliation:
School of Mathematics The University of New South Wales Sydney 2052, Australia

Email:
L.Qi@unsw.edu.au

**D. Sun**

Affiliation:
School of Mathematics The University of New South Wales Sydney 2052, Australia

Email:
sun@alpha.maths.unsw.edu.au

DOI:
https://doi.org/10.1090/S0025-5718-98-00932-6

Keywords:
Variational inequalities,
nonsmooth equations,
smoothing approximation,
smoothing Newton method,
convergence

Received by editor(s):
June 17, 1996

Received by editor(s) in revised form:
January 9, 1997

Additional Notes:
This work is supported by the Australian Research Council.

Article copyright:
© Copyright 1998
American Mathematical Society