×

Newton’s method and its use in optimization. (English) Zbl 1123.90070

Summary: Newton’s method is a basic tool in numerical analysis and numerous applications, including operations research and data mining. We survey the history of the method, its main ideas, convergence results, modifications, its global behavior. We focus on applications of the method for various classes of optimization problems, such as unconstrained minimization, equality constrained problems, convex programming and interior point methods. Some extensions (non-smooth problems, continuous analog, Smale’s results, etc.) are discussed briefly, while some others (e.g., versions of the method to achieve global convergence) are addressed in more details.

MSC:

90C30 Nonlinear programming
90C53 Methods of quasi-Newton type
90C51 Interior-point methods
65K05 Numerical mathematical programming methods

Software:

NewtonLib; SNOPT
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arnold, V.I., Small denominators and problem of stability in classical and celestial mechanics, Uspekhi mathematicheskih nauk, 18, 6, 91-192, (1963)
[2] Barnsley, M., Fractals everywhere, (1993), Academic Press London · Zbl 0691.58001
[3] Bennet, A.A., Newton’s method in general analysis, Proceedings of national Academy of sciences, USA, 2, 10, 592-598, (1916)
[4] Ben-Tal, A.; Nemirovski, A., Lectures on modern convex optimization: analysis, algorithms and engineering applications, (2001), SIAM Philadelphia · Zbl 0986.90032
[5] Bertsekas, D.P., Constrained optimization and Lagrange multiplier method, (1982), Academic Press New York · Zbl 0453.65045
[6] Bertsekas, D.P., Nonlinear programming, (1999), Athena Scientific Belmont · Zbl 0935.90037
[7] L.T. Biegler, I.E. Grossmann, Part I: Retrospective on optimization, Part II: Future perspective on optimization, Preprints, Chemical Engineering Department, Carnegie-Mellon University, 2004.
[8] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press Cambridge · Zbl 1058.90049
[9] Chen, X.; Nashed, Z.; Qi, L., Smoothing methods and semismooth methods for nondifferentiable operator equations, SIAM journal on numerical analysis, 38, 1200-1216, (2000) · Zbl 0979.65046
[10] Collatz, L., Functional analysis and numerical mathematics, (1966), Academic Press New York · Zbl 0221.65088
[11] Conn, A.B.; Gould, N.I.M.; Toint, Ph.L., Trust region methods, (2000), SIAM Philadelphia · Zbl 0643.65031
[12] Curry, J.H.; Garnett, L.; Sullivan, D., On the iteration of a rational function: computer experiments with newton’s method, Communications on mathematical physics, 91, 267-277, (1983) · Zbl 0524.65032
[13] Deulfhard, P., Newton methods for nonlinear problems: affine invariant and adaptive algorithms, (2004), Springer Berlin
[14] R.M. Dickau, Newton’s method. Available from: <http://mathforum.org/advanced/robertd/newtons.html>.
[15] Electronic library ZIB. Available from: <http://www.zib.de/SciSoft/NewtonLib>.
[16] Facchinei, F.; Pang, J.S., Finite-dimensional variational inequalities and complementarity problems, (2003), Springer New York · Zbl 1062.90002
[17] Fine, H., On newton’s method of approximation, Proceedings of national Academy of sciences, USA, 2, 9, 546-552, (1916)
[18] Fukushima, M.; Qi, L., Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods, (1999), Kluwer Dordrecht
[19] Goldfeld, S.; Quandt, R.; Trotter, H., Maximization by quadratic Hill climbing, Econometrica, 34, 541-551, (1966) · Zbl 0145.40901
[20] Gill, P.E.; Murray, W.; Saunders, M.A., SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM journal on optimization, 12, 979-1006, (2002) · Zbl 1027.90111
[21] Graves, L.M., Some mapping theorems, Duke mathematical journal, 17, 111-114, (1950) · Zbl 0037.20401
[22] Ioffe, A.D., On the local surjection property, Nonlinear analysis: theory, methods and applications, 11, 5, 565-592, (1987) · Zbl 0642.49010
[23] D.E. Joyce, Newton basins. Available from: <http://aleph0.clarku.edu/djoyce/newton/newton.html>.
[24] Julia, G., Sur l’iteration des fonctions rationelles, Journal de mathematiques pure et applique, 8, 47-245, (1918) · JFM 46.0520.06
[25] Kantorovich, L.V., On newton’s method for functional equations, Doklady AN SSSR, 59, 7, 1237-1240, (1948)
[26] Kantorovich, L.V., Functional analysis and applied mathematics, Uspekhi mathematicheskih nauk, 3, 1, 89-185, (1948), Translated as N.B.S. Report 1509, Washington, DC, 1952 · Zbl 0034.21203
[27] Kantorovich, L.V., On newton’s method, Trudy mathematicheskogo instituta imeni V.A. steklova, 28, 104-144, (1949) · Zbl 0038.07401
[28] Kantorovich, L.V., Principle of majorants and newton’s method, Doklady AN SSSR, 76, 1, 17-20, (1951)
[29] Kantorovich, L.V., Some further applications of principle of majorants, Doklady AN SSSR, 80, 6, 849-852, (1951)
[30] Kantorovich, L.V., On approximate solution of functional equations, Uspekhi mathematicheskih nauk, 11, 6, 99-116, (1956) · Zbl 0073.10602
[31] Kantorovich, L.V., Some further applications of newton’s method, Vestnik LGU, seriya matematika mekhanika, 0, 7, 68-103, (1957) · Zbl 0091.11502
[32] Kantorovich, L.V.; Akilov, G.P., Functional analysis in normed spaces, (1959), Fizmatgiz Moscow · Zbl 0127.06102
[33] Kantorovich, L.V.; Akilov, G.P., Functional analysis, (1977), Nauka Moscow · Zbl 0555.46001
[34] Klatte, D.; Kummer, B., Nonsmooth equations in optimization: regularity, calculus, methods and applications, (2002), Kluwer Dordrecht · Zbl 1173.49300
[35] Krasnoselski, M.A.; Vainikko, G.M.; Zabreiko, P.P.; Rutitski, Ya.B.; Stetsenko, V.Ya., Approximate solution of operator equations, (1969), Nauka Moscow, English translation: Walter-Noordhoff, Groningen, 1972
[36] Levenberg, K., A method for the solution of certain nonlinear problems in least squares, Quarterly of applied mathematics, 2, 164-168, (1944) · Zbl 0063.03501
[37] Levitin, E.S.; Polyak, B.T., Constrained minimization methods, USSR computational mathematics and mathematical physics, 6, 5, 1-50, (1966) · Zbl 0184.38902
[38] Ljusternik, L.A., On conditional extrema of functionals, Mathematicheskij sbornik, 41, 3, 390-401, (1934)
[39] Mandelbrot, B., The fractal geometry of nature, (1983), W.H. Freeman New York
[40] Marquardt, D., An algorithm for least squares estimation of nonlinear parameters, SIAM journal of applied mathematics, 11, 431-441, (1963) · Zbl 0112.10505
[41] J.H. Mathews, Bibliography for Newton’s method. Available from: <http://math.fullerton.edu/mathews/newtonsmethod/Newton’sMethodBib/Links/Newton’sMethodBib_lnk_3.html>.
[42] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM journal on control and optimization, 15, 959-972, (1977) · Zbl 0376.90081
[43] Mysovskikh, I.P., On convergence of L.V. kantorovich’s method for functional equations and its applications, Doklady AN SSSR, 70, 4, 565-568, (1950)
[44] Nesterov, Yu.; Nemirovski, A., Interior-point polynomial algorithms in convex programming, (1994), SIAM Philadelphia · Zbl 0824.90112
[45] Yu. Nesterov, B. Polyak, Cubic regularization of a Newton scheme and its global performance, CORE Discussion Papers 2003, No 41, Mathematical Programming, submitted for publication.
[46] Nesterov, Yu., Introductory lectures on convex programming, (2004), Kluwer Boston
[47] Ostrowski, A.M., Solution of equations and systems of equations, (1960), Academic Press Basel · Zbl 0115.11201
[48] Ortega, J.M.; Rheinboldt, W.C., Iterative solution of nonlinear equations in several variables, (1970), Academic Press New York-London · Zbl 0241.65046
[49] Peitgen, H.O.; Saupe, D.; Haeseler, F., Cayley’s problem and Julia sets, Mathematical intelligencer, 6, 2, 11-20, (1984) · Zbl 0549.68101
[50] ()
[51] Polyak, B.T., Gradient methods for solving equations and inequalities, USSR computational mathematics and mathematical physics, 4, 6, 17-32, (1964) · Zbl 0147.35302
[52] Polyak, B.T., Convexity of nonlinear image of a small ball with applications to optimization, Set-valued analysis, 9, 1-2, 159-168, (2001) · Zbl 1006.52001
[53] Polyak, B.T., The convexity principle and its applications, Bulletin of Brazilian mathematical society, 34, 1, 59-75, (2003) · Zbl 1059.49025
[54] Polyak, B.T., Convexity of the reachable set of nonlinear systems under L2 bounded controls, Dynamics of continuous, discrete and impulsive systems, 11, 2-3, 255-268, (2004) · Zbl 1050.93007
[55] Polyak, B.T., Introduction to optimization, (1987), Optimization Software New York · Zbl 0652.49002
[56] Polyak, B.T., Iterative methods using Lagrange multipliers for solving extremal problems with equality-type constraints, USSR computational mathematics and mathematical physics, 10, 5, 42-52, (1970) · Zbl 0217.27501
[57] Polyak, B.T., Minimization of nonsmooth functionals, USSR computational mathematics and mathematical physics, 9, 3, 14-29, (1969) · Zbl 0229.65056
[58] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Mathematical programming, 58, 353-367, (1993) · Zbl 0780.90090
[59] Ramm, A.G., Acceleration of convergence: A continuous analog of the newton’s method, Applicable analysis, 81, 4, 1001-1004, (2002) · Zbl 1034.65041
[60] Rheinboldt, W.C., Methods for solving systems of nonlinear equations, (1998), SIAM Philadelphia · Zbl 0906.65051
[61] Robinson, S.M., Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming algorithms, Mathematical programming, 7, 1-16, (1974) · Zbl 0294.90078
[62] Robinson, S.M., Newton’s method for a class of nonsmooth functions, Set-valued analysis, 2, 291-305, (1994) · Zbl 0804.65062
[63] Smale, S., A convergent process of price adjustment and global newton’s methods, Journal of mathematical economics, 3, 107-120, (1976) · Zbl 0354.90018
[64] Smale, S., Newton’s method estimates from data at one point, () · Zbl 0613.65058
[65] Smale, S., Complexity theory and numerical analysis, Acta numerica, 6, 523-551, (1997) · Zbl 0883.65125
[66] Wright, S.J., Primal-dual interior-point methods, (1997), SIAM Philadelphia · Zbl 0863.65031
[67] Ypma, T.J., Historical development of the Newton-raphson method, SIAM review, 37, 4, 531-551, (1995) · Zbl 0842.01005
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.