Richard Bellman y la Programación Dinámica

Richard Ernest Bellman (1920 - 1984) fue un matemático aplicado, célebre por su invención de la programación dinámica en 1953, y sus importantes contribuciones en otros campos de las matemáticas.

Biografía

Bellman nació en 1920 en Nueva York, donde su padre John James Bellman tenía una tienda de abarrotes en Bergen Street, cerca de Prospect Park en Brooklyn. Bellman completó sus estudios en la Abraham Lincoln High School en 1937, y estudió matemáticas en el Brooklyn College, donde obtuvo su licenciatura en 1941. Más tarde obtuvo una maestría de la Universidad de Wisconsin-Madison. Durante la Segunda Guerra Mundial trabajó para un grupo de Física Teórica de la División de Los Álamos. En 1946 recibió su doctorado en Filosofía (Ph.D.) de Princeton bajo la supervisión de Salomón Lefschetz. A partir de 1949 Bellman trabajado durante muchos años en la corporación RAND y fue durante este tiempo que él desarrolló de programación dinámica.

Fue profesor en la Universidad del Sur de California, miembro de la Academia Americana de las Artes y las Ciencias (1975), y miembro de la Academia Nacional de Ingeniería (1977).

Fue galardonado con la Medalla de Honor del IEEE en 1979, "por sus contribuciones a los procesos de decisión y la teoría de sistemas de control, en particular por la creación y aplicación de la programación dinámica". Su obra fundamental es la ecuación de Bellman.

Trabajo

Ecuación de Bellman: Programación Dinámica

Una ecuación de Bellman, también conocida como la ecuación de programación dinámica, es una condición necesaria para la optimalidad asociado con el método de optimización matemática conocida como la programación dinámica. Casi cualquier problema que se puede resolver utilizando la teoría de control óptimo también se puede resolver mediante el análisis de la correspondiente ecuación de Bellman. La ecuación de Bellman se aplicó por primera vez a la teoría de la ingeniería de control y otros temas de matemáticas aplicadas, y, posteriormente, se convirtió en una herramienta importante en la teoría económica.

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos.

 En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

1.     Dividir el problema en subproblemas más pequeños.

2.     Resolver estos problemas de manera óptima usando este proceso de tres pasos     recursivamente.

 3.    Usar estas soluciones óptimas para construir una solución óptima al problema original.

Ecuación de Hamilton-Jacobi-Bellman

La ecuación de Hamilton-Jacobi-Bellman (HJB) es una ecuación diferencial parcial que es fundamental para la teoría de control óptimo. La solución de la ecuación HJB es la "función de valor", que da a la óptima función de los costos un determinado sistema dinámico con una función de costos asociados. Clásicos problemas variacionales, por ejemplo puede resolverse utilizando este método.

La ecuación es el resultado de la teoría de programación dinámica que fue creado en los 50’s por Richard Bellman y compañeros de trabajo. La ecuación correspondiente en tiempo discreto que normalmente se conoce como la ecuación de Bellman. En tiempo continuo, el resultado puede ser visto como una extensión del trabajo anterior en la física clásica en la ecuación de Hamilton-Jacobi por William Rowan Hamilton y Carl Gustav Jacob Jacobi.

Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford, a veces conocido como el algoritmo de corrección de la etiqueta, calcula un solo proveedor o caminos más cortos en un digrafo ponderado (donde algunos de los valores pueden ser negativos). El algoritmo de Dijkstra logra el mismo problema con un tiempo de baja en ejecución, pero requiere de pesos ventaja de ser no-negativas.

Publicaciones

A lo largo de su carrera ha publicado 619 artículos y 39 libros. Aquí una pequeña selección:

1957. Programación Dinámica
1959. Comportamiento asintótico de las soluciones de las ecuaciones diferenciales
1961. Introducción a las desigualdades
1961. Control de Procesos Adaptativos: Un Tour guiado
1962. Programación Dinámica Aplicada
1967. Introducción a la Teoría Matemática de Control de Procesos
1970. Algoritmos, Grafos y equipos
1972. Programación Dinámica y Ecuaciones Diferenciales Parciales
1982. Aspectos matemáticos de Programación y Aplicaciones
1983. Métodos Matemáticos en Medicina
1984. Ecuaciones Diferenciales Parciales
1984. Ojo del huracán: publicación de una autobiografía, Mundo Científico.
1985. Inteligencia Artificial
1995. Ecuaciones Diferenciales Elementales modernas
1997. Introducción a Análisis de matrices