×

zbMATH — the first resource for mathematics

A parameterized Newton method and a quasi-Newton method for nonsmooth equations. (English) Zbl 0821.65029
Two methods are discussed for solving nonsmooth equations. The first method, a parametrized Newton method, uses a damping parameter for the Newton step and a regularization parameter for the chosen member of the generalized Jacobian, and, therefore, is well-defined even when the generalized Jacobian is singular. The second method is a Broyden-like method based on a so-called point-based smooth approximation function, which generalizes the technique of splitting the nonsmooth function into a smooth and a nonsmooth part.
For both methods local linear and superlinear convergence results are proven. Numerical examples are given for four nonlinear complementarity problems from literature. The numerical results are compared with other methods for solving nonsmooth equations.
Reviewer: W.Zulehner (Linz)

MSC:
65H10 Numerical computation of solutions to systems of equations
65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] X. Chen, On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms, Ann. Inst. Statist. Math. 42(1990) 387-401. · Zbl 0718.65039
[2] X. Chen, M.Z. Nashed and L. Qi, Convergence of Newton’s method for singular smooth and nonsmooth equations using adaptive outer inverses, Applied Mathematics Preprint AM93/4, School of Mathematics, The University of New South Wales (Sydney, Australia 1993). · Zbl 0871.65047
[3] X. Chen and T. Yamamoto, On the convergence of some quasi-Newton methods for nonlinear equations with nondifferentiable operators, Computing 48(1992) 87-94. · Zbl 0801.65048
[4] X. Chen and T. Yamamoto, Newton-like methods for solving underdetermined nonlinear equations, to appear in: J. of Comp. App. Math.
[5] F.H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983. · Zbl 0582.49001
[6] J.E. Dennis, Jr and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Inc., 1983.
[7] M. Ferris and S. Lucidi, Globally convergence methods for nonlinear equations, Computer Sciences Technical Report #1030, Computer Sciences Department, University of Wisconsin, (Madison, USA 1991). · Zbl 0803.65070
[8] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Programming 53(1992) 99-110. · Zbl 0756.90081
[9] S.A. Gabriel and J.S. Pang, A trust region method for constrained nonsmooth equations, W.W. Hager, D.W. Hearn and P.M. Pardalos, ed., Large Scale Optimization: State of the Art, Kluwer Academic Publishers B.V. (1994) 159-186. · Zbl 0813.65091
[10] S.P. Han, J.S. Pang and N. Rangaraj Globally convergent Newton methods for nonsmooth equations, Math. Oper. Res. 17(1992) 586-607. · Zbl 0777.90057
[11] T. Hansen and T.C. Koopmans, On the definition and computation of capital stock invariant under optimization, J. Economic Theory 5(1972) 487-523. · Zbl 0266.90018
[12] P.T. Harker, Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities, Math. Programming 41(1988) 25-59. · Zbl 0825.49019
[13] M. Heinkenschloss, C.T. Kelley and H.T. Tran, Fast algorithms for nonsmooth compact fixed point problems, SIAM J. Numer. Anal. 29(1992) 1769-1792. · Zbl 0763.65040
[14] C.M. Ip and J. Kyparisis, Local convergence of quasi-Newton methods for B-differentiable equations. Math. Programming 56(1992) 71-89. · Zbl 0761.90088
[15] M. Kojima and S. Shindo, Extensions of Newton and quasi-Newton methods to systems ofPC 1 equations, J. Oper. Res. Soc. of Japan, 29(1986) 352-374. · Zbl 0611.65032
[16] 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) 114-125. · Zbl 0662.65050
[17] J.M. MartĂ­nez and M.C. Zambaldi, Least change update methods for nonlinear systems with nondifferentiable terms. Numer. Funct. Anal. and Optimiz. 14(1993) 405-415. · Zbl 0801.65049
[18] M.Z. Nashed and X. Chen, Convergence of Newton-like methods for singular operator equations using outer inverses, Numer. Math. 66(1993) 235-257. · Zbl 0797.65047
[19] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several, Variables, Academic Press, New York, 1970. · Zbl 0241.65046
[20] J.S. Pang, Newton’s method for B-differentiable equations, Math. of Oper. Res. 15(1990) 311-341. · Zbl 0716.90090
[21] 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) 101-131. · Zbl 0733.90063
[22] J.S. Pang and S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem, Math. Programming 60(1993) 295-337. · Zbl 0808.90123
[23] J.S. Pang and L. Qi, Nonsmooth equations: motivation and algorithms, SIAM J. Optimization 3(1993) 443-465. · Zbl 0784.90082
[24] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res. 18(1993) 227-244. · Zbl 0776.65037
[25] L. Qi, Trust region algorithms for solving nonsmooth equations, to appear in SIAM J Optimization. · Zbl 0832.90108
[26] L. Qi and X. Chen, A globally convergent successive approximation method for nonsmooth equations, to appear in SIAM J. Control & Optimization. · Zbl 0833.90109
[27] L. Qi and J. Sun, A nonsmooth version of Newton’s method, Math. Programming 58(1993) 353-367. · Zbl 0780.90090
[28] D. Ralph, Global convergence of damped Newton’s method for nonsmooth equations via the path search, to appear in: Math. Oper. Res.
[29] S.M. Robinson, Newton’s method for a class of nonsmooth functions, Industrial Engineering Working Paper, University of Wisconsin, (Madison, USA 1988).
[30] H. Scarf, The Computation of Economic Equilibria, Yale University Press(1973). · Zbl 0311.90009
[31] A. Shapiro, On concepts of directional differentiability. J. Optimiz. Theory. Appl. 66(1990) 477-487. · Zbl 0682.49015
[32] T. Yamamoto, A note on a posteriori error bound of Zabrejko and Nguen for Zincenko’s iteration, Numer. Funct. Anal. and Optimiz. 9(1987) 987-994. · Zbl 0625.65053
[33] T. Yamamoto and X. Chen. Ball-convergence theorems and error estimates for certain iterative methods for nonlinear equations, Japan J. Appl. Math. 7(1990) 131-143. · Zbl 0699.65042
[34] A.I. Zincenko, Some approximate methods of solving equations with nondifferentiable operators (Ukrainian), Dopovidi Akad. Nauk. Ukrain. RSR (1963) 156-161.
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.