×

zbMATH — the first resource for mathematics

Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. (English) Zbl 0894.90143
Summary: The smoothing Newton method for solving a system of nonsmooth equations \(F(x)=0\), 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 \(k\)th step, the nonsmooth function \(F\) is approximated by a smooth function \( f(\cdot, \varepsilon_k)\), and the derivative of \( f(\cdot, \varepsilon_k)\) at \(x^k\) 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 \(F\) is semismooth at the solution and \(f\) 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 \(P\)-uniform, the iteration sequence generated by the smoothing Newton method will converge to the unique solution of the problem globally and superlinearly (quadratically).

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65H10 Numerical computation of solutions to systems of equations
90C30 Nonlinear programming
49J40 Variational inequalities
Software:
PATH Solver
PDF BibTeX XML Cite
Full Text: DOI
References:
[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. · Zbl 0880.76052
[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 · Zbl 0883.90116
[3] B. Chen and P. Harker, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim., 7 (1997), pp. 403-420. CMP 97:11
[4] Chunhui Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl. 5 (1996), no. 2, 97 – 138. · Zbl 0859.90112 · doi:10.1007/BF00249052 · doi.org
[5] Xiao Jun Chen and Li Qun Qi, A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Comput. Optim. Appl. 3 (1994), no. 2, 157 – 179. · Zbl 0821.65029 · doi:10.1007/BF01300972 · doi.org
[6] Xiao Jun Chen and Tetsuro Yamamoto, Convergence domains of certain iterative methods for solving nonlinear equations, Numer. Funct. Anal. Optim. 10 (1989), no. 1-2, 37 – 48. · Zbl 0645.65028 · doi:10.1080/01630568908816289 · doi.org
[7] Frank H. Clarke, Optimization and nonsmooth analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication. · Zbl 0582.49001
[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 · Zbl 0874.90185
[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), no. 1, 68 – 75. · Zbl 0227.90044 · doi:10.1007/BF01584073 · doi.org
[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. · Zbl 0980.90101
[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 · Zbl 0871.90096
[15] A. Fischer, A special Newton-type optimization method, Optimization 24 (1992), no. 3-4, 269 – 284. · Zbl 0814.65063 · doi:10.1080/02331939208843795 · doi.org
[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. · Zbl 0948.90133
[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. · Zbl 0996.90082
[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. Seetharama Gowda and Roman Sznajder, The generalized order linear complementarity problem, SIAM J. Matrix Anal. Appl. 15 (1994), no. 3, 779 – 795. · Zbl 0831.90112 · doi:10.1137/S0895479892237859 · doi.org
[20] Patrick T. Harker and Jong-Shi Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Programming 48 (1990), no. 2, (Ser. B), 161 – 220. · Zbl 0734.90098 · doi:10.1007/BF01582255 · doi.org
[21] Patrick T. Harker and Baichun Xiao, Newton’s method for the nonlinear complementarity problem: a \?-differentiable equation approach, Math. Programming 48 (1990), no. 3, (Ser. B), 339 – 357. · Zbl 0724.90071 · doi:10.1007/BF01582262 · doi.org
[22] M. Heinkenschloss, C. T. Kelley, and H. T. Tran, Fast algorithms for nonsmooth compact fixed-point problems, SIAM J. Numer. Anal. 29 (1992), no. 6, 1769 – 1792. · Zbl 0763.65040 · doi:10.1137/0729099 · doi.org
[23] Chi Ming Ip and Jerzy Kyparisis, Local convergence of quasi-Newton methods for \?-differentiable equations, Math. Programming 56 (1992), no. 1, Ser. A, 71 – 89. · Zbl 0761.90088 · doi:10.1007/BF01580895 · doi.org
[24] G. Isac and M. M. Kostreva, The generalized order complementarity problem, models and iterative methods, Ann. Oper. Res., 44 (1993), pp. 63-92. · Zbl 0816.46013
[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. · Zbl 0991.90123
[27] C. Kanzow and M. Fukushima, Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities, Math. Programming, to appear. · Zbl 0920.90134
[28] C. Kanzow and H. Jiang, A continuation method for (strongly) monotone variational inequalities, Math. Programming, to appear. · Zbl 0920.90131
[29] Bernd Kummer, Newton’s method for nondifferentiable functions, Advances in mathematical optimization, Math. Res., vol. 45, Akademie-Verlag, Berlin, 1988, pp. 114 – 125. · Zbl 0662.65050
[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] José Mario Martínez and Li Qun Qi, Inexact Newton methods for solving nonsmooth equations, J. Comput. Appl. Math. 60 (1995), no. 1-2, 127 – 145. Linear/nonlinear iterative methods and verification of solution (Matsuyama, 1993). · Zbl 0833.65045 · doi:10.1016/0377-0427(94)00088-I · doi.org
[32] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. · Zbl 0241.65046
[33] JiříV. Outrata, On optimization problems with variational inequality constraints, SIAM J. Optim. 4 (1994), no. 2, 340 – 357. · Zbl 0826.90114 · doi:10.1137/0804019 · doi.org
[34] JiříV. Outrata and Jochem Zowe, A Newton method for a class of quasi-variational inequalities, Comput. Optim. Appl. 4 (1995), no. 1, 5 – 21. · Zbl 0827.49007 · doi:10.1007/BF01299156 · doi.org
[35] Jong-Shi Pang, Newton’s method for \?-differentiable equations, Math. Oper. Res. 15 (1990), no. 2, 311 – 341. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311 · doi.org
[36] Jong-Shi Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Math. Programming 51 (1991), no. 1, (Ser. A), 101 – 131. · Zbl 0733.90063 · doi:10.1007/BF01586928 · doi.org
[37] Jong-Shi Pang, Complementarity problems, Handbook of global optimization, Nonconvex Optim. Appl., vol. 2, Kluwer Acad. Publ., Dordrecht, 1995, pp. 271 – 338. · Zbl 0833.90114 · doi:10.1007/978-1-4615-2025-2_6 · doi.org
[38] Jong-Shi Pang and Li Qun Qi, Nonsmooth equations: motivation and algorithms, SIAM J. Optim. 3 (1993), no. 3, 443 – 465. · Zbl 0784.90082 · doi:10.1137/0803021 · doi.org
[39] Jong-Shi Pang and Jen Chih Yao, On a generalization of a normal map and equation, SIAM J. Control Optim. 33 (1995), no. 1, 168 – 184. · Zbl 0827.90131 · doi:10.1137/S0363012992241673 · doi.org
[40] Li Qun Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res. 18 (1993), no. 1, 227 – 244. · Zbl 0776.65037 · doi:10.1287/moor.18.1.227 · doi.org
[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] Li Qun Qi and Xiao Jun Chen, A globally convergent successive approximation method for severely nonsmooth equations, SIAM J. Control Optim. 33 (1995), no. 2, 402 – 418. · Zbl 0833.90109 · doi:10.1137/S036301299223619X · doi.org
[43] Li Qun Qi and Jie Sun, A nonsmooth version of Newton’s method, Math. Programming 58 (1993), no. 3, Ser. A, 353 – 367. · Zbl 0780.90090 · doi:10.1007/BF01581275 · doi.org
[44] Daniel Ralph, Global convergence of damped Newton’s method for nonsmooth equations via the path search, Math. Oper. Res. 19 (1994), no. 2, 352 – 389. · Zbl 0819.90102 · doi:10.1287/moor.19.2.352 · doi.org
[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. · Zbl 0886.90162
[46] Werner C. Rheinboldt, A unified convergence theory for a class of iterative processes, SIAM J. Numer. Anal. 5 (1968), 42 – 63. · Zbl 0155.46701 · doi:10.1137/0705003 · doi.org
[47] Stephen M. Robinson, Newton’s method for a class of nonsmooth functions, Set-Valued Anal. 2 (1994), no. 1-2, 291 – 305. Set convergence in nonlinear analysis and optimization. · Zbl 0804.65062 · doi:10.1007/BF01027107 · doi.org
[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] Israel Zang, A smoothing-out technique for min-max optimization, Math. Programming 19 (1980), no. 1, 61 – 77. · Zbl 0468.90064 · doi:10.1007/BF01581628 · doi.org
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.