stringtranslate.com

Ecuación de Bellman

Diagrama de flujo de Bellman.

Una ecuación de Bellman , llamada así en honor a Richard E. Bellman , es una condición necesaria para la optimalidad 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 punto determinado en el tiempo 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. [2] Esto divide un problema de optimización dinámica en una secuencia de subproblemas más simples, como prescribe el "principio de optimalidad" de Bellman. [3] La ecuación se aplica a estructuras algebraicas con un ordenamiento total; para estructuras algebraicas con un ordenamiento parcial, se puede utilizar la ecuación genérica de Bellman. [4]

La ecuación de Bellman se aplicó por primera vez a la teoría de control de 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 están prefigurados en la Teoría de juegos y comportamiento económico de John von Neumann y Oskar Morgenstern y el análisis secuencial de Abraham Wald . [ cita requerida ] El término "ecuación de Bellman" generalmente se refiere a la ecuación de programación dinámica (DPE) asociada con problemas de optimización de tiempo discreto . [5] 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 . [6] [7]

En tiempo discreto, cualquier problema de optimización de múltiples etapas puede resolverse analizando la ecuación de Bellman adecuada. La ecuación de Bellman adecuada puede encontrarse introduciendo nuevas variables de estado (aumento de estado). [8] Sin embargo, el problema de optimización de múltiples etapas de estado aumentado resultante tiene un espacio de estado de mayor dimensión 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 la ecuación de Bellman adecuada puede encontrarse sin aumento de estado. [9]

Conceptos analíticos en programación dinámica

Para entender la ecuación de Bellman es necesario comprender varios conceptos subyacentes. En primer lugar, 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 denomina función objetivo . [ cita requerida ]

La programación dinámica divide un problema de planificación de múltiples períodos en pasos más simples en diferentes puntos del tiempo. Por lo tanto, requiere realizar un seguimiento de cómo evoluciona 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 denomina "estado". [10] [11] Por ejemplo, para decidir cuánto consumir y gastar en cada punto del tiempo, las personas necesitarían saber (entre otras cosas) su riqueza inicial. Por lo tanto, la riqueza sería una de sus variables de estado , pero probablemente habría otras.

Las variables elegidas en un momento dado suelen denominarse variables de control . Por ejemplo, dada su riqueza actual, las personas podrían decidir cuánto consumir ahora. Elegir las variables de control ahora puede ser equivalente a elegir el próximo estado; de manera más general, el próximo estado se ve afectado por otros factores además del control actual. Por ejemplo, en el caso más simple, la riqueza actual (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. [ cita requerida ]

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 regla que dé el consumo como una función de la riqueza. Una regla de este tipo, que determina los controles como una función de los estados, se denomina función de política . [12] [10]

Finalmente, por definición, la regla de decisión óptima es la 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 estará asociado con un nivel más alto posible de felicidad, . El mejor valor posible del objetivo, escrito como una función del estado, se llama función de valor . [ cita requerida ]

Bellman demostró que un problema de optimización dinámica en tiempo discreto puede plantearse 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, lo que da como resultado que la política óptima de ese período dependa del valor de la variable de estado a partir de la decisión del penúltimo período. [ aclaración necesaria ] Esta lógica continúa recursivamente hacia atrás en el tiempo, hasta que se deriva la regla de decisión del primer período, como una función del valor de la variable de estado inicial, mediante la optimización de la suma de la función objetivo específica del primer período y el valor de la función de valor del segundo período, que da el valor para 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. [ cita requerida ]

Derivación

Un problema de decisión dinámico

Sea el estado en el momento . Para una decisión que comienza en el momento 0, tomamos como dado el estado inicial . En cualquier momento, el conjunto de acciones posibles depende del estado actual; lo expresamos como , donde una acción particular representa valores particulares para una o más variables de control, y es el conjunto de acciones disponibles para ser tomadas en el estado . También se supone que el estado cambia de a un nuevo estado cuando se toma la acción, y que la recompensa actual por tomar la acción en el estado es . Finalmente, suponemos 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 restricciones

Observe que hemos definido la notación para indicar el valor óptimo que se puede obtener al maximizar 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 obtenible 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 hacerlo:

Principio de optimalidad: 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.) [10] [11] [13]

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 que toma la decisión elijan políticas igualmente óptimas desde sus puntos de vista.

Como lo 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 reunir 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 restricciones

Aquí elegimos , sabiendo que nuestra elección hará que el estado en el momento 1 sea . Ese nuevo estado afectará entonces el problema de decisión a partir del momento 1. Todo el problema de decisión futuro aparece dentro de los corchetes a la derecha. [ aclaración necesaria ] [ explicación adicional necesaria ]

La ecuación de Bellman

Hasta ahora parece que solo hemos empeorado el problema al separar la decisión de hoy de las decisiones futuras. Pero podemos simplificarlo notando que lo que está dentro de los corchetes a la derecha es el valor del problema de decisión de tiempo 1, comenzando desde el estado .

Por lo tanto, el problema puede reescribirse como una definición recursiva de la función de valor:

, sujeto a las restricciones:

Ésta es la ecuación de Bellman. Puede simplificarse aún más si se eliminan los subíndices de tiempo y se reemplaza el valor del siguiente estado:

La ecuación de Bellman se clasifica como una ecuación funcional , porque resolverla significa hallar la función desconocida , que es la función valor . Recordemos que la función valor describe el mejor valor posible del objetivo, en función del estado . Calculando la función valor, encontraremos también la función que describe la acción óptima en función del estado; a esta se le llama función política .

En un problema estocástico

En el contexto determinista, se pueden utilizar otras técnicas además de la programación dinámica para abordar el problema de control óptimo mencionado anteriormente . Sin embargo, la ecuación de Bellman suele ser el método más conveniente para resolver problemas de control óptimo estocástico .

Para un ejemplo específico de economía, considere un consumidor de vida infinita con una dotación de riqueza inicial en el período . Tiene una función de utilidad instantánea donde denota el 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 una tasa de interés . Entonces, el problema de maximización de la utilidad del consumidor es elegir un plan de consumo que resuelva

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 deuda al final de su vida. La ecuación de Bellman es

Alternativamente, se puede tratar el problema de la secuencia directamente utilizando, 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. Dejemos que la tasa de interés r siga un proceso de Markov con una función de transición de probabilidad donde denota la medida de probabilidad que rige 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 anuncie la tasa de interés del período actual.

En lugar de simplemente elegir una única secuencia , el consumidor ahora debe elegir una secuencia para cada posible realización de un de tal manera que se maximice su utilidad esperada durante su vida útil:

La expectativa se toma con respecto a la medida de probabilidad apropiada dada por Q en las secuencias de r . Debido a que r está gobernado por un proceso de Markov, la programación dinámica simplifica el problema significativamente. 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 general de optimización secuencial estocástica con shocks markovianos y donde el agente se enfrenta a su decisión ex post , la ecuación de Bellman toma una forma muy similar.

Métodos de solució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 . [19] 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 aplicación económica célebre 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 . [20] (Véase también el problema de la cartera de Merton ). La solución al modelo teórico de Merton, en el que los inversores eligen entre los ingresos actuales y los ingresos futuros o las 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 suelen dar como resultado una ecuación de Bellman que es una ecuación diferencial , los economistas se refieren a la programación dinámica como un "método recursivo" y ahora se reconoce un subcampo de la economía recursiva dentro de la economía.

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 ciertas condiciones. También describen muchos ejemplos de modelado de problemas teóricos en economía utilizando métodos recursivos. [21] Este libro llevó a que la programación dinámica se empleara 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 principal-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 búsqueda y economía laboral . [22] Avinash Dixit y Robert Pindyck mostraron el valor del método para pensar en la presupuestación de capital . [23] Anderson adaptó la técnica a la valoración de empresas, incluidas las empresas privadas. [24]

El uso de la programación dinámica para resolver problemas concretos se complica por dificultades de información, como la elección de la tasa de descuento no observable. También existen problemas computacionales, siendo el principal el problema de la dimensionalidad que surge de la gran cantidad de acciones posibles y variables de estado potenciales que deben considerarse antes de poder seleccionar una estrategia óptima. Para una discusión extensa de los problemas computacionales, véase Miranda y Fackler, [25] y Meyn 2007. [26]

Ejemplo

En los procesos de decisión de Markov , una ecuación de Bellman es una recursión para las recompensas esperadas. Por ejemplo, la recompensa esperada por estar en un estado particular y seguir una política fija tiene la ecuación de Bellman:

Esta ecuación describe la recompensa esperada por tomar la acción prescrita por alguna política .

La ecuación para la política óptima se denomina ecuación de optimalidad de Bellman :

donde 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 tomar la acción que ofrece el mayor rendimiento esperado.

Véase también

Referencias

  1. ^ Dixit, Avinash K. (1990). Optimización en la teoría económica (2.ª ed.). Oxford University Press. pág. 164. ISBN 0-19-877211-4.
  2. ^ "Principio de optimalidad de Bellman". www.ques10.com . Consultado el 17 de agosto de 2023 .
  3. ^ Kirk, Donald E. (1970). Teoría del control óptimo: una introducción. Prentice-Hall. pág. 55. ISBN 0-13-638098-0.
  4. ^ Szcześniak, Ireneusz; Woźna-Szcześniak, Bożena (2023), "Generic Dijkstra: Correctness and tractability", Simposio de gestión y operaciones de red IEEE/IFIP NOMS 2023-2023 , págs. 1 a 7, arXiv : 2204.13547 , doi : 10.1109/NOMS56928.2023.101543 22, ISBN 978-1-6654-7716-1, Número de identificación del sujeto  248427020
  5. ^ Kirk 1970, pág. 70
  6. ^ 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 edición). Ámsterdam: Elsevier. pág. 261. ISBN 0-444-01609-0.
  7. ^ Kirk 1970, pág. 88
  8. ^ Jones, Morgan; Peet, Matthew M. (2020). "Extensiones del marco de programación dinámica: programación de baterías, cargos por demanda e integración renovable". IEEE Transactions on Automatic Control . 66 (4): 1602–1617. arXiv : 1812.00792 . doi :10.1109/TAC.2020.3002235. S2CID  119622206.
  9. ^ Jones, Morgan; Peet, Matthew M. (2021). "Una generalización de la ecuación de Bellman con aplicación a la planificación de trayectorias, la evitación de obstáculos y la estimación de conjuntos invariantes". Automatica . 127 : 109510. arXiv : 2006.08175 . doi :10.1016/j.automatica.2021.109510. S2CID  222350370.
  10. ^ abc Bellman, RE (2003) [1957]. Programación dinámica . Dover. ISBN 0-486-42809-5.
  11. ^ ab Dreyfus, S. (2002). "Richard Bellman sobre el nacimiento de la programación dinámica". Investigación de operaciones . 50 (1): 48–51. doi :10.1287/opre.50.1.48.17791.
  12. ^ Bellman, 1957, Cap. III.2.
  13. ^ Bellman, R (agosto de 1952). "Sobre la teoría de la programación dinámica". Proc Natl Acad Sci USA . 38 (8): 716–9. Bibcode :1952PNAS...38..716B. doi : 10.1073/pnas.38.8.716 . PMC 1063639 . PMID  16589166. 
  14. ^ Ljungqvist, Lars; Sargent, Thomas J. (2004). Teoría macroeconómica recursiva (2ª ed.). Prensa del MIT. págs. 88–90. ISBN 0-262-12274-X.
  15. ^ Bertsekas, Dimitri P.; Tsitsiklis, John N. (1996). Programación neurodinámica . Athena Scientific. ISBN 978-1-886529-10-6.
  16. ^ Abu-Khalaf, Murad; Lewis, Frank L. (2005). "Leyes de control casi óptimas para sistemas no lineales con actuadores saturados utilizando un enfoque de red neuronal HJB". Automatica . 41 (5): 779–791. doi :10.1016/j.automatica.2004.11.034. S2CID  14757582.
  17. ^ Al-Tamimi, Asma; Lewis, Frank L.; Abu-Khalaf, Murad (2008). "Solución HJB no lineal en tiempo discreto utilizando programación dinámica aproximada: prueba de convergencia". IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics . 38 (4): 943–949. doi :10.1109/TSMCB.2008.926614. PMID  18632382. S2CID  14202785.
  18. ^ Miao, Jianjun (2014). Dinámica económica en tiempo discreto. MIT Press. pág. 134. ISBN 978-0-262-32560-8.
  19. ^ Beckmann, Martin; Muth, Richard (1954). "Sobre la solución de la 'ecuación fundamental' de la teoría de inventarios" (PDF) . Documento de debate de la Comisión Cowles n.º 2116 .
  20. ^ Merton, Robert C. (1973). "Un modelo de fijación de precios de activos de capital intertemporal". Econometrica . 41 (5): 867–887. doi :10.2307/1913811. JSTOR  1913811.
  21. ^ Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989). Métodos recursivos en dinámica económica . Harvard University Press. ISBN 0-674-75096-9.
  22. ^ Ljungqvist, Lars; Sargent, Thomas (2012). Teoría macroeconómica recursiva (3.ª ed.). MIT Press. ISBN 978-0-262-01874-6.
  23. ^ Dixit, Avinash; Pindyck, Robert (1994). Inversión en condiciones de incertidumbre . Princeton University Press. ISBN 0-691-03410-9.
  24. ^ Anderson, Patrick L. (2004). "Cap. 10". Economía y finanzas empresariales . CRC Press. ISBN 1-58488-348-0.
    — (2009). "El valor de las empresas privadas en los Estados Unidos". Economía empresarial . 44 (2): 87–108. doi :10.1057/be.2009.4. S2CID  154743445.
    — (2013). Economía de la valoración de empresas . Stanford University Press. ISBN 9780804758307.Stanford Press Archivado el 8 de agosto de 2013 en Wayback Machine.
  25. ^ Miranda, Mario J.; Fackler, Paul L. (2004). Economía computacional aplicada y finanzas . MIT Press. ISBN 978-0-262-29175-0.
  26. ^ Meyn, Sean (2008). Técnicas de control para redes complejas. Cambridge University Press. ISBN 978-0-521-88441-9. El apéndice contiene texto abreviado de Meyn y Tweedie. Archivado el 12 de octubre de 2007 en Wayback Machine .