Una ecuación de Bellman , llamada así por Richard E. Bellman , es una condición necesaria para la optimización asociada con el método de optimización matemática conocido como programación dinámica . [1] Escribe el "valor" de un problema de decisión en un determinado momento en términos de la recompensa de algunas elecciones iniciales y el "valor" del problema de decisión restante que resulta de esas elecciones iniciales. [ cita requerida ] Esto rompe un problema de optimización dinámica en una secuencia de subproblemas más simples, como prescribe el "principio de optimización" de Bellman . [2]
La ecuación de Bellman se aplicó por primera vez a la teoría del control de la ingeniería y a otros temas de matemáticas aplicadas, y posteriormente se convirtió en una herramienta importante en la teoría económica ; aunque los conceptos básicos de la programación dinámica se prefiguró en John von Neumann y Oskar Morgenstern 's Teoría de Juegos y Comportamiento Económico y Abraham Wald ' s análisis secuencial . [ cita requerida ] El término 'ecuación de Bellman' generalmente se refiere a la ecuación de programación dinámica asociada con problemas de optimización de tiempo discreto . [3] En problemas de optimización de tiempo continuo, la ecuación análoga es una ecuación diferencial parcial que se llama ecuación de Hamilton-Jacobi-Bellman . [4] [5]
En tiempo discreto, cualquier problema de optimización de múltiples etapas se puede resolver analizando la ecuación de Bellman apropiada. La ecuación de Bellman adecuada se puede encontrar introduciendo nuevas variables de estado (aumento de estado). [6] Sin embargo, el problema de optimización de múltiples etapas de estado aumentado resultante tiene un espacio de estado dimensional más alto que el problema de optimización de múltiples etapas original, un problema que potencialmente puede hacer que el problema aumentado sea intratable debido a la “ maldición de la dimensionalidad ”. Alternativamente, se ha demostrado que si la función de costo del problema de optimización de múltiples etapas satisface una estructura "separable hacia atrás", entonces se puede encontrar la ecuación de Bellman apropiada sin aumento de estado. [7]
Conceptos analíticos en programación dinámica
Para comprender la ecuación de Bellman, se deben comprender varios conceptos subyacentes. Primero, cualquier problema de optimización tiene algún objetivo: minimizar el tiempo de viaje, minimizar el costo, maximizar las ganancias, maximizar la utilidad, etc. La función matemática que describe este objetivo se llama función objetivo .
La programación dinámica divide un problema de planificación de períodos múltiples en pasos más simples en diferentes momentos. Por lo tanto, es necesario realizar un seguimiento de la evolución de la situación de decisión a lo largo del tiempo. La información sobre la situación actual que se necesita para tomar una decisión correcta se llama "estado". [8] [9] Por ejemplo, para decidir cuánto consumir y gastar en cada momento, la gente necesitaría saber (entre otras cosas) su riqueza inicial. Por lo tanto, la riquezasería una de sus variables de estado , pero probablemente habría otras.
Las variables elegidas en un momento dado a menudo se denominan variables de control . Por ejemplo, dada su riqueza actual, la gente podría decidir cuánto consumir ahora. Elegir las variables de control ahora puede ser equivalente a elegir el siguiente estado; de manera más general, el siguiente estado se ve afectado por otros factores además del control actual. Por ejemplo, en el caso más simple, la riqueza de hoy (el estado) y el consumo (el control) podrían determinar exactamente la riqueza de mañana (el nuevo estado), aunque normalmente otros factores también afectarán la riqueza de mañana.
El enfoque de programación dinámica describe el plan óptimo al encontrar una regla que indique cuáles deberían ser los controles, dado cualquier valor posible del estado. Por ejemplo, si el consumo ( c ) depende solo de la riqueza ( W ), buscaríamos una reglaque da el consumo en función de la riqueza. Esta regla, que determina los controles en función de los estados, se denomina función política (véase Bellman, 1957, capítulo III.2). [8]
Finalmente, por definición, la regla de decisión óptima es aquella que logra el mejor valor posible del objetivo. Por ejemplo, si alguien elige el consumo, dada la riqueza, para maximizar la felicidad (suponiendo que la felicidad H puede representarse mediante una función matemática, como una función de utilidad y es algo definido por la riqueza), entonces cada nivel de riqueza se asociará con algún nivel más alto posible de felicidad,. El mejor valor posible del objetivo, escrito en función del estado, se llama función de valor .
Bellman demostró que un problema de optimización dinámica en tiempo discreto se puede plantear en una forma recursiva , paso a paso, conocida como inducción hacia atrás escribiendo la relación entre la función de valor en un período y la función de valor en el período siguiente. La relación entre estas dos funciones de valor se denomina "ecuación de Bellman". En este enfoque, la política óptima en el último período de tiempo se especifica de antemano como una función del valor de la variable de estado en ese momento, y el valor óptimo resultante de la función objetivo se expresa así en términos de ese valor de la variable de estado. A continuación, la optimización del penúltimo período implica maximizar la suma de la función objetivo específica del período de ese período y el valor óptimo de la función objetivo futura, dando la política óptima de ese período supeditada al valor de la variable de estado a partir del siguiente. decisión del último período. [ aclaración necesaria ] Esta lógica continúa recursivamente en el tiempo, hasta que se deriva la regla de decisión del primer período, en función del valor de la variable de estado inicial, optimizando la suma de la función objetivo específica del primer período y el valor del segundo función de valor del período, que da el valor de todos los períodos futuros. Por lo tanto, la decisión de cada período se toma reconociendo explícitamente que todas las decisiones futuras se tomarán de manera óptima.
Derivación
Un problema de decisión dinámico
Deja que el estado en el momento ser . Para una decisión que comienza en el tiempo 0, tomamos como dado el estado inicial. En cualquier momento, el conjunto de posibles acciones depende del estado actual; podemos escribir esto como, donde la accion representa una o más variables de control. También asumimos que el estado cambia de a un nuevo estado cuando la acción se toma, y que la recompensa actual de tomar acción en estado es . Finalmente, asumimos impaciencia, representada por un factor de descuento. .
Bajo estos supuestos, un problema de decisión de horizonte infinito toma la siguiente forma:
sujeto a las limitaciones
Observe que hemos definido la notación para denotar el valor óptimo que se puede obtener maximizando esta función objetivo sujeta a las restricciones asumidas. Esta función es la función de valor . Es una función de la variable de estado inicial., ya que el mejor valor que se puede obtener depende de la situación inicial.
Principio de optimalidad de Bellman
El método de programación dinámica divide este problema de decisión en subproblemas más pequeños. El principio de optimalidad de Bellman describe cómo hacer esto:
Principio de Optimidad: Una política óptima tiene la propiedad de que cualquiera que sea el estado inicial y la decisión inicial, las decisiones restantes deben constituir una política óptima con respecto al estado resultante de la primera decisión. (Véase Bellman, 1957, Cap. III.3.) [8] [9] [10]
En informática, se dice que un problema que se puede descomponer de esta manera tiene una subestructura óptima . En el contexto de la teoría de juegos dinámicos , este principio es análogo al concepto de equilibrio perfecto en subjuegos , aunque lo que constituye una política óptima en este caso está condicionado a que los oponentes del tomador de decisiones elijan políticas igualmente óptimas desde sus puntos de vista.
Como sugiere el principio de optimalidad , consideraremos la primera decisión por separado, dejando de lado todas las decisiones futuras (comenzaremos de nuevo desde el momento 1 con el nuevo estado). Al recopilar las decisiones futuras entre paréntesis a la derecha, el problema de decisión de horizonte infinito anterior es equivalente a: [ aclaración necesaria ]
sujeto a las limitaciones
Aquí estamos eligiendo , sabiendo que nuestra elección hará que el estado de tiempo 1 sea . Ese nuevo estado afectará el problema de decisión desde el momento 1 en adelante. Todo el problema de la decisión futura aparece entre corchetes a la derecha. [se necesita aclaración ] [ se necesita más explicación ]
La ecuación de Bellman
Hasta ahora, parece que solo hemos agravado el problema al separar la decisión de hoy de las decisiones futuras. Pero podemos simplificar notando que lo que está dentro de los corchetes a la derecha es el valor del problema de decisión de tiempo 1, comenzando por el estado.
Por lo tanto, podemos reescribir el problema como una definición recursiva de la función de valor:
- , sujeto a las limitaciones:
Esta es la ecuación de Bellman. Se puede simplificar aún más si eliminamos los subíndices de tiempo y conectamos el valor del siguiente estado:
La ecuación de Bellman se clasifica como una ecuación funcional , porque resolverla significa encontrar la función desconocida, que es la función de valor . Recuerde que la función de valor describe el mejor valor posible del objetivo, en función del estado. Calculando la función de valor, también encontraremos la funciónque describe la acción óptima en función del estado; esto se llama función de política .
En un problema estocástico
En el entorno determinista, se pueden utilizar otras técnicas además de la programación dinámica para abordar el problema de control óptimo anterior . Sin embargo, la Ecuación de Bellman es a menudo el método más conveniente para resolver problemas estocásticos de control óptimo.
Para un ejemplo específico de la economía, considere un consumidor de vida infinita con dotación de riqueza inicial en el período . Tienen una función de utilidad instantánea dónde denota consumo y descuenta la utilidad del período siguiente a una tasa de . Suponga que lo que no se consume en el período se traslada al siguiente período con tasa de interés . Entonces, el problema de maximización de la utilidad del consumidor es elegir un plan de consumo eso resuelve
sujeto a
y
La primera restricción es la acumulación de capital / ley de movimiento especificada por el problema, mientras que la segunda restricción es una condición de transversalidad según la cual el consumidor no tiene deudas al final de su vida. La ecuación de Bellman es
Alternativamente, se puede tratar el problema de la secuencia directamente usando, por ejemplo, las ecuaciones hamiltonianas .
Ahora bien, si la tasa de interés varía de un período a otro, el consumidor se enfrenta a un problema de optimización estocástica. Deje que el interés r siga un proceso de Markov con función de transición de probabilidad dónde denota la medida de probabilidad que gobierna la distribución de la tasa de interés en el próximo período si la tasa de interés actual es. En este modelo, el consumidor decide su consumo del período actual después de que se anuncia la tasa de interés del período actual.
En lugar de simplemente elegir una sola secuencia , el consumidor ahora debe elegir una secuencia para cada posible realización de un de tal manera que se maximice su utilidad esperada de por vida:
La expectativa se toma con respecto a la medida de probabilidad apropiada dada por Q en las secuencias de r . Debido a que r se rige por un proceso de Markov, la programación dinámica simplifica el problema de manera significativa. Entonces la ecuación de Bellman es simplemente:
Bajo algún supuesto razonable, la función de política óptima resultante g ( a , r ) es medible .
Para un problema de optimización secuencial estocástica general con choques de Markov y donde el agente se enfrenta a su decisión ex post , la ecuación de Bellman adopta una forma muy similar
Métodos de solución
- El método de coeficientes indeterminados , también conocido como "adivinar y verificar", se puede utilizar para resolver algunas ecuaciones de Bellman autónomas de horizonte infinito . [11]
- La ecuación de Bellman se puede resolver por inducción hacia atrás , ya sea analíticamente en algunos casos especiales, o numéricamente en una computadora. La inducción numérica hacia atrás es aplicable a una amplia variedad de problemas, pero puede ser inviable cuando hay muchas variables de estado, debido a la maldición de la dimensionalidad . La programación dinámica aproximada ha sido introducida por DP Bertsekas y JN Tsitsiklis con el uso de redes neuronales artificiales ( perceptrones multicapa ) para aproximar la función de Bellman. [12] Esta es una estrategia de mitigación efectiva para reducir el impacto de la dimensionalidad al reemplazar la memorización del mapeo de funciones completo para todo el dominio del espacio con la memorización de los parámetros únicos de la red neuronal. En particular, para los sistemas de tiempo continuo, se introdujo un enfoque de programación dinámica aproximada que combina ambas iteraciones de políticas con redes neuronales. [13] En tiempo discreto, se introdujo un enfoque para resolver la ecuación HJB que combina iteraciones de valor y redes neuronales. [14]
- Calculando las condiciones de primer orden asociadas con la ecuación de Bellman, y luego usando el teorema de la envolvente para eliminar las derivadas de la función de valor, es posible obtener un sistema de ecuaciones en diferencias o ecuaciones diferenciales llamado las ' ecuaciones de Euler '. [15] Las técnicas estándar para la solución de ecuaciones diferenciales o diferenciales se pueden utilizar para calcular la dinámica de las variables de estado y las variables de control del problema de optimización.
Aplicaciones en economía
La primera aplicación conocida de una ecuación de Bellman en economía se debe a Martin Beckmann y Richard Muth . [16] Martin Beckmann también escribió extensamente sobre la teoría del consumo utilizando la ecuación de Bellman en 1959. Su trabajo influyó en Edmund S. Phelps , entre otros.
Una célebre aplicación económica de una ecuación de Bellman es el artículo seminal de 1973 de Robert C. Merton sobre el modelo de fijación de precios de activos de capital intertemporal . [17] (Véase también el problema de la cartera de Merton ). La solución al modelo teórico de Merton, uno en el que los inversores eligen entre los ingresos de hoy y los ingresos futuros o ganancias de capital, es una forma de la ecuación de Bellman. Debido a que las aplicaciones económicas de la programación dinámica generalmente dan como resultado una ecuación de Bellman que es una ecuación en diferencias , los economistas se refieren a la programación dinámica como un "método recursivo" y ahora se reconoce dentro de la economía un subcampo de la economía recursiva .
Nancy Stokey , Robert E. Lucas y Edward Prescott describen la programación dinámica estocástica y no estocástica con considerable detalle y desarrollan teoremas para la existencia de soluciones a problemas que cumplen determinadas condiciones. También describen muchos ejemplos de modelado de problemas teóricos en economía utilizando métodos recursivos. [18] Este libro llevó a que se empleara una programación dinámica para resolver una amplia gama de problemas teóricos en economía, incluido el crecimiento económico óptimo , la extracción de recursos , los problemas entre el principal y el agente , las finanzas públicas , la inversión empresarial , la fijación de precios de activos , la oferta de factores y la organización industrial . Lars Ljungqvist y Thomas Sargent aplican la programación dinámica para estudiar una variedad de cuestiones teóricas en política monetaria , política fiscal , impuestos , crecimiento económico , teoría de la búsqueda y economía laboral . [19] Avinash Dixit y Robert Pindyck mostraron el valor del método para pensar en el presupuesto de capital . [20] Anderson adaptó la técnica a la valoración empresarial, incluidas las empresas privadas. [21]
El uso de la programación dinámica para resolver problemas concretos se complica por las dificultades de información, como la elección de la tasa de descuento no observable. También hay problemas computacionales, el principal es la maldición de la dimensionalidad que surge de la gran cantidad de posibles acciones y posibles variables de estado que deben considerarse antes de poder seleccionar una estrategia óptima. Para una discusión extensa de problemas computacionales, vea Miranda y Fackler, [22] y Meyn 2007. [23]
Ejemplo
En los procesos de decisión de Markov , una ecuación de Bellman es una recursividad para las recompensas esperadas. Por ejemplo, la recompensa esperada por ser en un determinado Estado s y siguiendo alguna política fijo tiene la ecuación de Bellman:
Esta ecuación describe la recompensa esperada por realizar la acción prescrita por alguna política .
La ecuación para la política óptima se denomina ecuación de optimalidad de Bellman :
dónde es la política óptima y se refiere a la función de valor de la política óptima. La ecuación anterior describe la recompensa por realizar la acción que genera el mayor rendimiento esperado.
Ver también
- Método pseudoespectral Bellman
- Programación dinámica - Método de optimización de problemas.
- Ecuación de Hamilton – Jacobi – Bellman
- Proceso de decisión de Markov
- Teoría de control óptimo
- Subestructura óptima
- Equilibrio competitivo recursivo
- Programación dinámica estocástica
Referencias
- ^ Dixit, Avinash K. (1990). Optimización en Teoría Económica (2ª ed.). Prensa de la Universidad de Oxford. pag. 164. ISBN 0-19-877211-4.
- ^ Kirk, Donald E. (1970). Teoría del control óptimo: una introducción . Prentice Hall. pag. 55. ISBN 0-13-638098-0.
- ^ Kirk , 1970 , pág. 70
- ^ Kamien, Morton I .; Schwartz, Nancy L. (1991). Optimización dinámica: el cálculo de variaciones y el control óptimo en economía y gestión (Segunda ed.). Amsterdam: Elsevier. pag. 261. ISBN 0-444-01609-0.
- ^ Kirk , 1970 , pág. 88
- ^ Jones, Morgan; Peet, Matthew M. (2020). "Extensiones del marco de programación dinámica: programación de la batería, cargos por demanda e integración renovable". Transacciones IEEE sobre control automático : 1. arXiv : 1812.00792 . doi : 10.1109 / TAC.2020.3002235 . S2CID 119622206 .
- ^ Jones, Morgan; Peet, Matthew M. (2021). "Una generalización de la ecuación de Bellman con aplicación a la planificación de rutas, evitación de obstáculos y estimación de conjuntos invariantes" . Automatica : 109510. arXiv : 2006.08175 . doi : 10.1016 / j.automatica.2021.109510 .
- ^ a b c Bellman, RE (2003) [1957]. Programación dinámica . Dover. ISBN 0-486-42809-5.
- ^ a b Dreyfus, S. (2002). "Richard Bellman sobre el nacimiento de la programación dinámica" . Investigación operativa . 50 (1): 48–51. doi : 10.1287 / opre.50.1.48.17791 .
- ^ Bellman, R (agosto de 1952). "Sobre la teoría de la programación dinámica" . Proc Natl Acad Sci USA . 38 (8): 716–9. Código Bibliográfico : 1952PNAS ... 38..716B . doi : 10.1073 / pnas.38.8.716 . PMC 1063639 . PMID 16589166 .
- ^ Ljungqvist, Lars; Sargent, Thomas J. (2004). Teoría macroeconómica recursiva (2ª ed.). MIT Press. págs. 88 –90. ISBN 0-262-12274-X.
- ^ Bertsekas, Dimitri P .; Tsitsiklis, John N. (1996). Programación neurodinámica . Athena Scientific. ISBN 978-1-886529-10-6.
- ^ Abu-Khalaf, Murad; Lewis, Frank L. (2005). "Leyes de control casi óptimas para sistemas no lineales con actuadores de saturación utilizando un enfoque de red neuronal HJB". Automatica . 41 (5): 779–791. doi : 10.1016 / j.automatica.2004.11.034 .
- ^ Al-Tamimi, Asma; Lewis, Frank L .; Abu-Khalaf, Murad (2008). "Solución HJB no lineal de tiempo discreto utilizando programación dinámica aproximada: prueba de convergencia". Transacciones IEEE sobre sistemas, hombre y cibernética, parte B (cibernética) . 38 (4): 943–949. doi : 10.1109 / TSMCB.2008.926614 . PMID 18632382 . S2CID 14202785 .
- ^ Miao, Jianjun (2014). Dinámica económica en tiempo discreto . MIT Press. pag. 134. ISBN 978-0-262-32560-8.
- ^ Beckmann, Martin; Muth, Richard (1954). "Sobre la solución de la 'ecuación fundamental' de la teoría del inventario" (PDF) . Documento de debate 2116 de la Comisión Cowles .
- ^ Merton, Robert C. (1973). "Un modelo de valoración de activos de capital intertemporal". Econometrica . 41 (5): 867–887. doi : 10.2307 / 1913811 . JSTOR 1913811 .
- ^ Stokey, Nancy; Lucas, Robert E .; Prescott, Edward (1989). Métodos recursivos en dinámica económica . Prensa de la Universidad de Harvard. ISBN 0-674-75096-9.
- ^ Ljungqvist, Lars; Sargent, Thomas (2012). Teoría macroeconómica recursiva (3ª ed.). MIT Press. ISBN 978-0-262-01874-6.
- ^ Dixit, Avinash; Pindyck, Robert (1994). Inversión bajo incertidumbre . Prensa de la Universidad de Princeton. ISBN 0-691-03410-9.
- ^ Anderson, Patrick L. (2004). "Cap. 10". Economía y Finanzas Empresariales . Prensa CRC. ISBN 1-58488-348-0.
- (2009). "El valor de las empresas privadas en Estados Unidos". Economía empresarial . 44 (2): 87–108. doi : 10.1057 / be.2009.4 . S2CID 154743445 .
- (2013). Economía de la valoración empresarial . Prensa de la Universidad de Stanford. ISBN 9780804758307. Stanford Press Archivado el 8 de agosto de 2013 en la Wayback Machine. - ^ Miranda, Mario J .; Fackler, Paul L. (2004). Economía y Finanzas Computacionales Aplicadas . MIT Press. ISBN 978-0-262-29175-0.
- ^ Meyn, Sean (2008). Técnicas de control para redes complejas . Prensa de la Universidad de Cambridge. ISBN 978-0-521-88441-9.El apéndice contiene Meyn & Tweedie resumido. Archivado el 12 de octubre de 2007 en Wayback Machine .