Richard Bellman
Encyclopedia
Richard Ernest Bellman was an American applied mathematician
, celebrated for his invention of dynamic programming
in 1953, and important contributions in other fields of mathematics.
, where his father John James Bellman ran a small grocery store on Bergen Street
near Prospect Park
in Brooklyn
. Bellman completed his studies at Abraham Lincoln High School in 1937, and studied mathematics
at Brooklyn College
where he received a BA
in 1941. He later earned an MA
from the University of Wisconsin–Madison
. During World War II
he worked for a Theoretical Physics
Division group in Los Alamos
. In 1946 he received his Ph.D. at Princeton
under the supervision of Solomon Lefschetz
. From 1949 Bellman worked for many years at RAND corporation and it was during this time that he developed dynamic programming
.
He was a professor at the University of Southern California
, a Fellow in the American Academy of Arts and Sciences
(1975), and a member of the National Academy of Engineering
(1977).
He was awarded the IEEE Medal of Honor
in 1979, "for contributions to decision processes and control system theory, particularly the creation and application of dynamic programming". His key work is the Bellman equation
.
, also known as a dynamic programming equation, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming
. Almost any problem which can be solved using optimal control theory can also be solved by analyzing the appropriate Bellman equation. The Bellman equation was first applied to engineering control theory
and to other topics in applied mathematics, and subsequently became an important tool in economic theory.
which is central to optimal control
theory. The solution of the HJB equation is the 'value function', which gives the optimal cost-to-go for a given dynamical system
with an associated cost function. Classical variational problems, for example, the brachistochrone problem can be solved using this method as well.
The equation is a result of the theory of dynamic programming
which was pioneered in the 1950s by Richard Bellman and coworkers. The corresponding discrete-time equation is usually referred to as the Bellman equation
. In continuous time, the result can be seen as an extension of earlier work in classical physics
on the Hamilton-Jacobi equation by William Rowan Hamilton
and Carl Gustav Jacob Jacobi.
", is a term coined by Bellman to describe the problem caused by the exponential increase in volume
associated with adding extra dimensions to a (mathematical) space. One implication of the curse of dimensionality is that some methods for numerical solution of the Bellman equation require vastly more computer time when there are more state variables in the value function.
For example, 100 evenly-spaced sample points suffice to sample a unit interval
with no more than 0.01 distance between points; an equivalent sampling of a 10-dimensional unit hypercube with a lattice with a spacing of 0.01 between adjacent points would require 1020 sample points: thus, in some sense, the 10-dimensional hypercube can be said to be a factor of 1018 "larger" than the unit interval. (Adapted from an example by R. E. Bellman, see below.)
accomplishes the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman–Ford is usually used only when there are negative edge weights.
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
, celebrated for his invention of dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
in 1953, and important contributions in other fields of mathematics.
Biography
Bellman was born in 1920 in New York CityNew York City
New York is the most populous city in the United States and the center of the New York Metropolitan Area, one of the most populous metropolitan areas in the world. New York exerts a significant impact upon global commerce, finance, media, art, fashion, research, technology, education, and...
, where his father John James Bellman ran a small grocery store on Bergen Street
Bergen Street Line
The Bergen Street Line is a public transit line in Brooklyn, New York City, United States, running westbound mostly along Bergen Street, as well as eastbound on Dean Street , between downtown Brooklyn and Ocean Hill...
near Prospect Park
Prospect Park (Brooklyn)
Prospect Park is a 585-acre public park in the New York City borough of Brooklyn located between Park Slope, Prospect-Lefferts Gardens, Kensington, Windsor Terrace and Flatbush Avenue, Grand Army Plaza and the Brooklyn Botanic Garden...
in Brooklyn
Brooklyn
Brooklyn is the most populous of New York City's five boroughs, with nearly 2.6 million residents, and the second-largest in area. Since 1896, Brooklyn has had the same boundaries as Kings County, which is now the most populous county in New York State and the second-most densely populated...
. Bellman completed his studies at Abraham Lincoln High School in 1937, and studied mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
at Brooklyn College
Brooklyn College
Brooklyn College is a senior college of the City University of New York, located in Brooklyn, New York, United States.Established in 1930 by the New York City Board of Higher Education, the College had its beginnings as the Downtown Brooklyn branches of Hunter College and the City College of New...
where he received a BA
Bachelor of Arts
A Bachelor of Arts , from the Latin artium baccalaureus, is a bachelor's degree awarded for an undergraduate course or program in either the liberal arts, the sciences, or both...
in 1941. He later earned an MA
Master of Arts (postgraduate)
A Master of Arts from the Latin Magister Artium, is a type of Master's degree awarded by universities in many countries. The M.A. is usually contrasted with the M.S. or M.Sc. degrees...
from the University of Wisconsin–Madison
University of Wisconsin–Madison
The University of Wisconsin–Madison is a public research university located in Madison, Wisconsin, United States. Founded in 1848, UW–Madison is the flagship campus of the University of Wisconsin System. It became a land-grant institution in 1866...
. During World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
he worked for a Theoretical Physics
Theoretical physics
Theoretical physics is a branch of physics which employs mathematical models and abstractions of physics to rationalize, explain and predict natural phenomena...
Division group in Los Alamos
Los Alamos National Laboratory
Los Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...
. In 1946 he received his Ph.D. at Princeton
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
under the supervision of Solomon Lefschetz
Solomon Lefschetz
Solomon Lefschetz was an American mathematician who did fundamental work on algebraic topology, its applications to algebraic geometry, and the theory of non-linear ordinary differential equations.-Life:...
. From 1949 Bellman worked for many years at RAND corporation and it was during this time that he developed dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
.
He was a professor at the University of Southern California
University of Southern California
The University of Southern California is a private, not-for-profit, nonsectarian, research university located in Los Angeles, California, United States. USC was founded in 1880, making it California's oldest private research university...
, a Fellow in the American Academy of Arts and Sciences
American Academy of Arts and Sciences
The American Academy of Arts and Sciences is an independent policy research center that conducts multidisciplinary studies of complex and emerging problems. The Academy’s elected members are leaders in the academic disciplines, the arts, business, and public affairs.James Bowdoin, John Adams, and...
(1975), and a member of the National Academy of Engineering
National Academy of Engineering
The National Academy of Engineering is a government-created non-profit institution in the United States, that was founded in 1964 under the same congressional act that led to the founding of the National Academy of Sciences...
(1977).
He was awarded the IEEE Medal of Honor
IEEE Medal of Honor
The IEEE Medal of Honor is the highest recognition of the Institute of Electrical and Electronics Engineers . It has been awarded since 1917, when its first recipient was Major Edwin H. Armstrong. It is given for an exceptional contribution or an extraordinary career in the IEEE fields of...
in 1979, "for contributions to decision processes and control system theory, particularly the creation and application of dynamic programming". His key work is the Bellman equation
Bellman equation
A Bellman equation , named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming...
.
Bellman equation
A Bellman equationBellman equation
A Bellman equation , named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming...
, also known as a dynamic programming equation, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
. Almost any problem which can be solved using optimal control theory can also be solved by analyzing the appropriate Bellman equation. The Bellman equation was first applied to engineering control theory
Control theory
Control theory is an interdisciplinary branch of engineering and mathematics that deals with the behavior of dynamical systems. The desired output of a system is called the reference...
and to other topics in applied mathematics, and subsequently became an important tool in economic theory.
Hamilton–Jacobi–Bellman equation
The Hamilton–Jacobi–Bellman equation (HJB) equation is a partial differential equationPartial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
which is central to optimal control
Optimal control
Optimal control theory, an extension of the calculus of variations, is a mathematical optimization method for deriving control policies. The method is largely due to the work of Lev Pontryagin and his collaborators in the Soviet Union and Richard Bellman in the United States.-General method:Optimal...
theory. The solution of the HJB equation is the 'value function', which gives the optimal cost-to-go for a given dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
with an associated cost function. Classical variational problems, for example, the brachistochrone problem can be solved using this method as well.
The equation is a result of the theory of dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
which was pioneered in the 1950s by Richard Bellman and coworkers. The corresponding discrete-time equation is usually referred to as the Bellman equation
Bellman equation
A Bellman equation , named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming...
. In continuous time, the result can be seen as an extension of earlier work in classical physics
Classical physics
What "classical physics" refers to depends on the context. When discussing special relativity, it refers to the Newtonian physics which preceded relativity, i.e. the branches of physics based on principles developed before the rise of relativity and quantum mechanics...
on the Hamilton-Jacobi equation by William Rowan Hamilton
William Rowan Hamilton
Sir William Rowan Hamilton was an Irish physicist, astronomer, and mathematician, who made important contributions to classical mechanics, optics, and algebra. His studies of mechanical and optical systems led him to discover new mathematical concepts and techniques...
and Carl Gustav Jacob Jacobi.
Curse of dimensionality
The "Curse of dimensionalityCurse of dimensionality
The curse of dimensionality refers to various phenomena that arise when analyzing and organizing high-dimensional spaces that do not occur in low-dimensional settings such as the physical space commonly modeled with just three dimensions.There are multiple phenomena referred to by this name in...
", is a term coined by Bellman to describe the problem caused by the exponential increase in volume
Volume
Volume is the quantity of three-dimensional space enclosed by some closed boundary, for example, the space that a substance or shape occupies or contains....
associated with adding extra dimensions to a (mathematical) space. One implication of the curse of dimensionality is that some methods for numerical solution of the Bellman equation require vastly more computer time when there are more state variables in the value function.
For example, 100 evenly-spaced sample points suffice to sample a unit interval
Unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...
with no more than 0.01 distance between points; an equivalent sampling of a 10-dimensional unit hypercube with a lattice with a spacing of 0.01 between adjacent points would require 1020 sample points: thus, in some sense, the 10-dimensional hypercube can be said to be a factor of 1018 "larger" than the unit interval. (Adapted from an example by R. E. Bellman, see below.)
Bellman–Ford algorithm
The Bellman–Ford algorithm sometimes referred to as the Label Correcting Algorithm, computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithmDijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
accomplishes the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman–Ford is usually used only when there are negative edge weights.
Publications
Over the course of his career he published 619 papers and 39 books. During the last 11 years of his life he published over 100 papers despite suffering from crippling complications of a brain surgery (Dreyfus, 2003). A selection:- 1957. Dynamic Programming
- 1959. Asymptotic Behavior of Solutions of Differential Equations
- 1961. An Introduction to Inequalities
- 1961. Adaptive Control Processes: A Guided Tour
- 1962. Applied Dynamic Programming
- 1967. Introduction to the Mathematical Theory of Control Processes
- 1970. Algorithms, Graphs and Computers
- 1972. Dynamic Programming and Partial Differential Equations
- 1982. Mathematical Aspects of Scheduling and Applications
- 1983. Mathematical Methods in Medicine
- 1984. Partial Differential Equations
- 1984. Eye of the Hurricane: An Autobiography, World Scientific Publishing.
- 1985. Artificial Intelligence
- 1995. Modern Elementary Differential Equations
- 1997. Introduction to Matrix Analysis
- 2003. Dynamic Programming
- 2003. Perturbation Techniques in Mathematics, Engineering and Physics
- 2003. Stability Theory of Differential Equations
Further reading
- J.J. O'Connor and E.F. Robertson (2005). Biography of Richard Bellman from the MacTutor History of Mathematics.
- Stuart Dreyfus (2002). "Richard Bellman on the Birth of Dynamic Programming". In: Operations Research. Vol. 50, No. 1, Jan–Feb 2002, pp. 48–51.
- Stuart Dreyfus (2003) "Richard Ernest Bellman". In: International Transactions in Operational Research. Vol 10, no. 5, Pages 543 - 545
- Salvador Sanabria. Richard Bellman's Biography. Paper at www-math.ucdenver.edu