Truncated Newton method

Truncated Newton methods, also known as Hessian-free optimization,^[1] 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;^[2] conjugate gradient has been suggested and evaluated as a candidate inner loop.^[1] Another prerequisite is good preconditioning for the inner algorithm.^[3]

References

1 2 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. doi:10.1016/S0377-0427(00)00426-X.
↑ Nash, Stephen G. (1985). "Preconditioning of truncated-Newton methods". SIAM J. Sci. Stat. Comput. 6 (3): 599–616.

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). CiteSeerX 10.1.1.455.7495 .
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. Optimization. 1 (3): 358–372. CiteSeerX 10.1.1.474.3400 .

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling …

… functions

… and gradients

Convergence	Trust region Wolfe conditions
Quasi–Newton	BFGS and L-BFGS DFP Symmetric rank-one (SR1)
Other methods	Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient Truncated Newton

… and Hessians

Newton's method

Graph of a strictly concave quadratic function with unique maximum.

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	Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal

Network flows

Metaheuristics
Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search

Software

Isaac Newton
Publications	De analysi per aequationes numero terminorum infinitas (1669, published 1711) Method of Fluxions (1671) De motu corporum in gyrum (1684) Philosophiæ Naturalis Principia Mathematica (1687) General Scholium (1713) Opticks (1704) The Queries (1704) Arithmetica Universalis (1707)
Other writings	Notes on the Jewish Temple Quaestiones quaedam philosophicae The Chronology of Ancient Kingdoms Amended (1728) An Historical Account of Two Notable Corruptions of Scripture (1754)
Discoveries and inventions	Calculus Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Newton's cradle Sextant
Theory expansions	Kepler's laws of planetary motion Problem of Apollonius
Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation Post-Newtonian expansion Parameterized post-Newtonian formalism Newton–Cartan theory Schrödinger–Newton equation Gravitational constant Newton's laws of motion Newtonian dynamics Newton's method in optimization Gauss–Newton algorithm Truncated Newton method Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Newtonian fluid Corpuscular theory of light Leibniz–Newton calculus controversy Newton's notation Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method Newton fractal Generalized Gauss–Newton method Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number Kissing number problem Power number Newton's quotient Newton–Puiseux theorem Solar mass Dynamics Absolute time and space Finite difference Table of Newtonian series Impact depth Structural coloration Inertia
Phrases	"Hypotheses non fingo" "Standing on the shoulders of giants"
Life	Cranbury Park Woolsthorpe Manor Early life Later life Religious views Occult studies The Mysteryes of Nature and Art Scientific revolution Copernican Revolution
Friends and family	Catherine Barton John Conduitt William Clarke Benjamin Pulleyn William Stukeley William Jones Isaac Barrow Abraham de Moivre John Keill
Cultural depictions	Newton (Blake) Newton (Paolozzi) In popular culture
Related	Writing of Principia Mathematica List of things names after Newton Isaac Newton Institute Isaac Newton Medal Isaac Newton Group of Telescopes Isaac Newton Telescope Newton (unit) Elements of the Philosophy of Newton Isaac Newton S/O Philipose

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Truncated Newton method

References

Further reading