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

The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.

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

Categories
- Algorithms and methods
- Heuristics
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)

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 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 Solar mass Dynamics Absolute time and space Finite difference Table of Newtonian series Impact depth Structural coloration Inertia

Life	Cranbury Park Woolsthorpe Manor Early life of Isaac Newton Later life of Isaac Newton Religious views of Isaac Newton Isaac Newton's 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

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

Phrases	"Hypotheses non fingo" "Standing on the shoulders of giants"

Theory expansions	Kepler's laws of planetary motion Problem of Apollonius

Related	Writing of Principia Mathematica Newton (Blake) List of things named after Isaac Newton Newton (unit) Isaac Newton in popular culture Elements of the Philosophy of Newton Isaac Newton S/O Philipose

This article is issued from Wikipedia - version of the 10/30/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Truncated Newton method

References

Further reading