Richard E. Bellman: Difference between revisions
Added fair use image |
→See also: Work |
||
Line 24: | Line 24: | ||
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]]. |
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]]. |
||
== |
== Work == |
||
===Bellman equation=== |
|||
A [[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]]. |
|||
*[[Bellman-Ford algorithm]] |
|||
⚫ | |||
=== 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 (graph theory)|edge]] weights may be negative). [[Dijkstra's algorithm]] 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. |
|||
⚫ | |||
The [[Curse of dimensionality]]", 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. |
|||
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 10<sup>20</sup> sample points: thus, in some sense, the 10-dimensional hypercube can be said to be a factor of 10<sup>18</sup> "larger" than the unit interval. (Adapted from an example by R. E. Bellman, see below.) |
|||
⚫ | |||
The [[Hamilton-Jacobi-Bellman equation]] (HJB) equation is a [[partial differential equation]] 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]]. |
|||
== Publications == |
== Publications == |
Revision as of 23:46, 23 April 2008
Richard E. Bellman | |
---|---|
File:Richard E. Bellman.jpg | |
Born | 26 August 1920 |
Died | 19 March 1984 | (aged 63)
Nationality | American |
Alma mater | Princeton University University of Wisconsin-Madison Brooklyn College |
Scientific career | |
Fields | Mathematics |
Institutions | University of Southern California |
Richard Ernest Bellman (August 26, 1920 – March 19, 1984) was an applied mathematician, celebrated for his invention of dynamic programming in 1953, and important contributions in other fields of mathematics.
Biography
Bellman was born in 1920 and studied mathematics at Brooklyn College (B.A. 1941) and the University of Wisconsin-Madison (M.A.). He then went to work for a Theoretical Physics Division group in Los Alamos. In 1946 he received his Ph.D. at Princeton under the supervision of Solomon Lefschetz[1].
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.
Work
Bellman equation
A 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.
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 algorithm 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.
Curse of dimensionality
The Curse of dimensionality", 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.
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.)
Hamilton-Jacobi-Bellman
The Hamilton-Jacobi-Bellman equation (HJB) equation is a partial differential equation 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.
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).
References
- ^ Mathematics Genealogy Project http://genealogy.math.ndsu.nodak.edu/id.php?id=12968
- Bellman, Richard, Eye of the Hurricane, an Autobiography, World Scientific Publishing, 1984.
- IEEE History Center - Legacies
- Int. Trans. in Op. Res. Biographical Article on Bellman
- Harold J. Kushner's speech when accepting the Richard E. Bellman Control Heritage Award
- S. Dreyfus, Richard Bellman on the Birth of Dynamic Programming
- Sanabria, Salvador. [1] Richard Bellman's Biography.
- J.J. O'Connor and E.F. Robertson. Biography of Richard Bellman from the MacTutor History of Mathematics.
- 1920 births
- 1984 deaths
- 20th century mathematicians
- American mathematicians
- American Jews
- Control theorists
- Jewish American scientists
- John von Neumann Theory Prize winners
- IEEE Medal of Honor recipients
- University of Wisconsin-Madison alumni
- Princeton University alumni
- University of Southern California faculty
- City University of New York people
- Jewish inventors
- American mathematician stubs