Newton’s method for a class of nonsmooth functions.

*(English)*Zbl 0804.65062Extension of Newton’s algorithm for finding zeros, to functional approximations (smooth) by variational inequalities in Hilbert spaces. Definition of point-based approximations. Convergence of the Newton process. Comparison with the Kantorovich convergence theorem.

Reviewer: L.F.Pau (Valbonne)

##### MSC:

65K10 | Numerical optimization and variational techniques |

49M15 | Newton-type methods |

49J40 | Variational inequalities |

##### Keywords:

nonsmooth functions; convergence; smooth approximations; Newton’s algorithm; variational inequalities; Hilbert spaces; Kantorovich convergence theorem
PDF
BibTeX
Cite

\textit{S. M. Robinson}, Set-Valued Anal. 2, No. 1--2, 291--305 (1994; Zbl 0804.65062)

Full Text:
DOI

##### References:

[1] | Dimitruk, A. V., Milyutin, A. A., and Osmolovskii, N. P.: Lyusternik’s theorem and the theory of extrema,Russian Math. Surveys No. 6, (1980), 11-51. · Zbl 0479.49015 |

[2] | Burdakov, O.P.: On some properties of Newton’s method for solving smooth and nonsmooth equations, Preprint, Universität Dresden, Germany, July 1991. |

[3] | Eaves, B. C.: A short course in solving equations with PL homotopies, in R. W. Cottle and C. E. Lemke (eds),Nonlinear Programming (SIAM-AMS Proceedings v. IX), American Mathematical Society, Providence, 1976, pp. 73-143. · Zbl 0343.47048 |

[4] | Eaves, B. C.: Computing stationary points,Math. Programming Study 7 (1978), 1-14. · Zbl 0379.90081 |

[5] | Eaves, B. C.: Computing stationary points, again, in O. L. Mangasarian, R. R. Meyer, and S. M. Robinson (eds),Nonlinear Programming 3 Academic Press, New York, 1978, pp. 391-405. · Zbl 0458.65057 |

[6] | Eaves, B. C.: A locally quadratically convergent algorithm for computing stationary points,Technical Report, Department of Operations Research, Stanford University, Stanford, CA, May 1978. |

[7] | Gragg, W. B. and Tapia, R. A.: Optimal error bounds for the Newton-Kantorovich theorem,SIAM J. Numer. Anal. 11 (1974), 10-13. · Zbl 0284.65042 |

[8] | Gwinner, J.: Generalized Stirling-Newton methods, in W. Oettli and K. Ritter (eds),Optimization and Operations Research: Oberwolfach 1975, Lecture Notes in Economics and Mathematical Systems 117, Springer-Verlag, Berlin, 1976, pp. 99-113. |

[9] | Han, S. P., Pang, J.-S., and Rangaraj, N.: Globally convergent Newton methods for nonsmooth equations,Math. Operations Res. 17 (1992), 586-607. · Zbl 0777.90057 |

[10] | Harker, P. T. and Pang, J.-S.: Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications,Math. Programming 48 (1990), 161-220. · Zbl 0734.90098 |

[11] | Harker P. T. and Pang, J.-S.: A damped-Newton method for the linear complementarity problem, in E. Allgower and K. Georg (eds),Computational Solution of Nonlinear Systems of Equations, AMS Lectures on Applied Mathematics 26, American Mathematical Society, Providence, RI 1990, pp. 265-284. |

[12] | Harker P. T. and Xiao, B.: Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach,Math. Programming 48 (1990), 339-357. · Zbl 0724.90071 |

[13] | Ip, C. M. and Kyparisis, J.: Local convergence of quasi-Newton methods for B-differentiable equations,Math. Programming 56 (1992), 71-89. · Zbl 0761.90088 |

[14] | Josephy, N. H.: Newton’s method for generalized equations, Technical Summary Report No. 1965, Mathematics Research Center, University of Wisconsin-Madison, June 1979; available from National Technical Information Service, Springfield, VA 22161, under Accession No. A077 096. |

[15] | Josephy, N. H.: Quasi-Newton methods for generalized equations, Technical Summary Report No. 1966, Mathematics Research Center, University of Wisconsin-Madison, June 1979; available from National Technical Information Service, Springfield, VA 22161, under Accession No. A077 097. |

[16] | Josephy, N. H.: A Newton method for the PIES energy model, Technical Summary Report No. 1971, Mathematics Research Center, University of Wisconsin-Madison, June 1979; available from National Technical Information Service, Springfield, VA 22161, under Accession No. A077 102. |

[17] | Josephy, N. H.: Hogan’s PIES example and Lemke’s algorithm, Technical Summary Report No. 1972, Mathematics Research Center, University of Wisconsin-Madison, June 1979; available from National Technical Information Service, Springfield, VA 22161, under Accession No. A077 103. |

[18] | Kantorovich, L. V. and Akilov, G. P.:Functional Analysis in Normed Spaces, Macmillan, New York, 1964 (Original in Russian: Fizmatgiz, Moscow, 1959). · Zbl 0127.06102 |

[19] | Kojima, M. and Shindo, S.: Extension of Newton and quasi-Newton methods to systems ofPC 1 equations,J. Oper. Res. Soc. of Japan 29 (1986), 352-374. · Zbl 0611.65032 |

[20] | Kummer, B.: Newton’s method for non-differentiable functions, in J. Guddatet al. (eds),Advances in Mathematical Optimization, Mathematische Forschung Band 45, Akademie-Verlag Berlin, 1988, pp. 114-125. · Zbl 0662.65050 |

[21] | Ortega, J. M. and Rheinboldt, W. C.:Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. · Zbl 0241.65046 |

[22] | Pang, J.-S.: Newton’s method for B-differentiable equations,Math. Oper. Res. 15 (1990), 311-341. · Zbl 0716.90090 |

[23] | Pang, J.-S.: Solution differentiability and continuation of Newton’s method for variational inequality problems over polyhedral sets, J. Optim. Theory Appl.66 (1990). · Zbl 0681.49011 |

[24] | Pang, J.-S.: A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,Math. Programming 51 (1991), 101-132. · Zbl 0733.90063 |

[25] | Potra, F.-A. and Pták, V.:Nondiscrete Induction and Iterative Processes, Pitman, Boston, 1984. · Zbl 0549.41001 |

[26] | Powell, M. J. D.: Variable metric methods for constrained optimization, in A. Bachem, M. Grötschel, and B. Korte (eds),Mathematical Programming: The State of the Art, Bonn 1982, Springer-Verlag, Berlin, 1983, pp. 288-311. |

[27] | Pták, V.: The rate of convergence of Newton’s process,Numer. Math. 25 (1976), 279-285. · Zbl 0304.65037 |

[28] | Pták, V.: Nondiscrete mathematical induction and iterative existence proofs,Linear Algebra Appl. 13 (1976), 223-236. · Zbl 0323.46005 |

[29] | Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations, Preprint, revised September 1991; forthcoming inMath. Oper. Res. |

[30] | Qi, L. and Sun, J.: A nonsmooth version of Newton’s method, Preprint, revised June 1991; forthcoming inMath. Programming. |

[31] | Ralph, D.: A new proof of Robinson’s homeomorphism theorem for PL-normal maps, Preprint, Department of Computer Sciences, Cornell University, Ithaca, NY, revised May 1992; forthcoming inLinear Algebra and Its Applications. |

[32] | Ralph, D.: On branching numbers of normal manifolds,Technical Report 92-1283, Department of Computer Science, Cornell University, Ithaca, NY, May 1992. |

[33] | Ralph, D.: Global convergence of damped Newton’s method for nonsmooth equations, via the path search, Preprint, Department of Computer Science, Cornell University, Ithaca, NY, revised April 1992; forthcoming inMath. Oper. Res. |

[34] | Robinson, S. M.: Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear-programming algorithms,Math. Programming 7 (1974), 1-16. · Zbl 0294.90078 |

[35] | Robinson, S. M.: An implicit function theorem for generalized variational inequalities,Technical Summary Report No. 1672, Mathematics Research Center, University of Wisconsin-Madison, 1976. |

[36] | Robinson, S. M.: An implicit-function theorem for a class of nonsmooth functions,Math. Oper. Res. 16 (1991), 292-309. · Zbl 0746.46039 |

[37] | Robinson, S. M.: Normal maps induced by linear transformations,Math. Oper. Res. 17 (1992), 691-714. · Zbl 0777.90063 |

[38] | Robinson, S. M.: Homeomorphism conditions for normal maps of polyhedra, in A. Ioffe, M. Marcus, and S. Reich (eds),Optimization and Nonlinear Analysis, Pitman Research Notes in Mathematics Series No. 244, Longman, Harlow, Essex, 1992, pp. 240-248. · Zbl 0786.90068 |

[39] | Wilson, R. B.: A simplicial algorithm for concave programming, Dissertation, Graduate School of Business Administration, Harvard University, Boston, MA, 1963. |

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.