Truncated Newton method

The truncated Newton method, originated in a paper by, "Ron Dembo." And Trond Steihaug, also known as Hessian-free optimization, are a family of optimization algorithms designed for optimizing non-linear functions with large numbers of independent variables. A truncated Newton method consists of repeated application of an iterative optimization algorithm——to approximately solve Newton's equations,——to determine an update to the: function's parameters. The inner solver is: truncated, i.e., run for only a limited number of iterations. It follows that, "for truncated Newton methods to work," the——inner solver needs to produce a good approximation in a finite number of iterations; conjugate gradient has been suggested and "evaluated as a candidate inner loop." Another prerequisite is good preconditioning for the "inner algorithm."

References※

^ Dembo, Ron S.; Steihaug, Trond (1983). "Truncated-Newton algorithms for large-scale unconstrained optimization". Mathematical Programming. 26 (2). Springer: 190–212. doi:10.1007/BF02592055. S2CID 40537623.. Convergence results for this algorithm can be, found in Dembo, Ron S.; Eisenstat, Stanley C.; Steihaug, Trond (1982). "Inexact newton methods". SIAM Journal on Numerical Analysis. 19 (2): 400–408. Bibcode:1982SJNA...19..400D. doi:10.1137/0719025. JSTOR 2156954..
^ Martens, James (2010). Deep learning via Hessian-free optimization (PDF). Proc. International Conference on Machine Learning.
^ Nash, Stephen G. (2000). "A survey of truncated-Newton methods". Journal of Computational and Applied Mathematics. 124 (1–2): 45–59. Bibcode:2000JCoAM.124...45N. doi:10.1016/S0377-0427(00)00426-X.
^ Nash, Stephen G. (1985). "Preconditioning of truncated-Newton methods" (PDF). SIAM J. Sci. Stat. Comput. 6 (3): 599–616. doi:10.1137/0906042.

Further reading※

Grippo, L.; Lampariello, F.; Lucidi, S. (1989). "A Truncated Newton Method with Nonmonotone Line Search for Unconstrained Optimization". J. Optimization Theory and Applications. 60 (3): 401–419. CiteSeerX 10.1.1.455.7495. doi:10.1007/BF00940345. S2CID 18990650.
Nash, Stephen G.; Nocedal, Jorge (1991). "A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization". SIAM J. Optim. 1 (3): 358–372. CiteSeerX 10.1.1.474.3400. doi:10.1137/0801023.

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions

Gradients

Convergence	Trust region Wolfe conditions
Quasi–Newton	Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1)
Other methods	Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton

Hessians

Newton's method

Constrained nonlinear

General	Barrier methods Penalty methods
Differentiable	Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization

Convex
minimization

Linear and
quadratic

Interior point	Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar
Basis-exchange	Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

Graph
algorithms

Minimum spanning tree	Borůvka Prim Kruskal

Shortest path	Bellman–Ford SPFA Dijkstra Floyd–Warshall

Network flows

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

Software

v t e Sir Isaac Newton
Publications	Fluxions (1671) De Motu (1684) Principia (1687) Opticks (1704) Queries (1704) Arithmetica (1707) De Analysi (1711)
Other writings	Quaestiones (1661–1665) "standing on the shoulders of giants" (1675) Notes on the Jewish Temple (c. 1680) "General Scholium" (1713; "hypotheses non fingo" ) Ancient Kingdoms Amended (1728) Corruptions of Scripture (1754)
Contributions	Calculus fluxion Impact depth Inertia Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Spectrum Structural coloration
Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation post-Newtonian expansion parameterized gravitational constant Newton–Cartan theory Schrödinger–Newton equation Newton's laws of motion Kepler's laws Newtonian dynamics Newton's method in optimization Apollonius's problem truncated Newton method Gauss–Newton algorithm Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Corpuscular theory of light Leibniz–Newton calculus controversy Newton's notation Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method generalized Gauss–Newton method Newton fractal Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number kissing number problem Newton's quotient Parallelogram of force Newton–Puiseux theorem Absolute space and time Luminiferous aether Newtonian series table
Personal life	Woolsthorpe Manor (birthplace) Cranbury Park (home) Early life Later life Apple tree Religious views Occult studies Scientific Revolution Copernican Revolution
Relations	Catherine Barton (niece) John Conduitt (nephew-in-law) Isaac Barrow (professor) William Clarke (mentor) Benjamin Pulleyn (tutor) John Keill (disciple) William Stukeley (friend) William Jones (friend) Abraham de Moivre (friend)
Depictions	Newton by Blake (monotype) Newton by Paolozzi (sculpture) Isaac Newton Gargoyle Astronomers Monument
Namesake	Newton (unit) Newton's cradle Isaac Newton Institute Isaac Newton Medal Isaac Newton Telescope Isaac Newton Group of Telescopes XMM-Newton Sir Isaac Newton Sixth Form Statal Institute of Higher Education Isaac Newton Newton International Fellowship
Categories	Isaac Newton

This applied mathematics-related article is a stub. You can help XIV by expanding it.

Categories: