stringtranslate.com

ecuación de Bellman

Diagrama de flujo de botones

Una ecuación de Bellman , que lleva el nombre de 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. [2] Esto divide un problema de optimización dinámica en una secuencia de subproblemas más simples, como prescribe el “principio de optimización” de Bellman. [3] La ecuación se aplica a estructuras algebraicas con un ordenamiento total; para estructuras algebraicas con un ordenamiento parcial, la ecuación genérica de Bellman Se puede utilizar la ecuación [4] .

La ecuación de Bellman se aplicó por primera vez a la teoría del 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 los juegos y el comportamiento económico de John von Neumann y Oskar Morgenstern y en el análisis secuencial de Abraham Wald . [ cita necesaria ] 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 en tiempo discreto . [5] En los 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 se puede resolver analizando la ecuación de Bellman adecuada. La ecuación de Bellman adecuada se puede encontrar 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 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 costos 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. [9]

Conceptos analíticos en programación dinámica.

Para comprender la ecuación de Bellman, se deben comprender varios conceptos subyacentes. En primer lugar, cualquier problema de optimización tiene algún objetivo: minimizar el tiempo de viaje, minimizar el coste, maximizar los beneficios, maximizar la utilidad, etc. La función matemática que describe este objetivo se llama función objetivo . [ cita necesaria ]

La programación dinámica divide un problema de planificación de varios períodos en pasos más simples en diferentes momentos. 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 llama "estado". [10] [11] Por ejemplo, para decidir cuánto consumir y gastar en cada momento, las personas necesitarían saber (entre otras cosas) su riqueza inicial. Por tanto, la riqueza sería una de sus variables de estado , pero probablemente habría otras. [ cita necesaria ]

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 equivaler 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 (el Estado) y el consumo (el control) de hoy 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 necesaria ]

El enfoque de programación dinámica describe el plan óptimo al encontrar una regla que indica cuáles deberían ser los controles, dado cualquier valor posible del estado. Por ejemplo, si el consumo ( c ) depende sólo de la riqueza ( W ), buscaríamos una regla que dé 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 . [12] [10]

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 (asumiendo 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 algún nivel más alto posible de felicidad, . El mejor valor posible del objetivo, escrito como función del estado, se llama función de valor . [ cita necesaria ]

Bellman demostró que un problema de optimización dinámica en tiempo discreto se puede plantear de 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 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 hace que la política óptima de ese período dependa del valor de la variable de estado a partir del siguiente. decisión del último período. [ se necesita aclaración ] Esta lógica continúa recursivamente 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, 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. [ cita necesaria ]

Derivación

Un problema de decisión dinámica

Sea el estado en el momento . Para una decisión que comienza en el tiempo 0, tomamos como dado el estado inicial . En cualquier momento, el conjunto de acciones posibles depende del estado actual; expresamos esto 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 suponemos que el estado cambia de un nuevo estado cuando se toma una acción, y que el beneficio actual de tomar una acción en el 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 indicar 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 obtenible depende de la situación inicial.

Principio de optimización 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 optimización de Bellman describe cómo hacer esto:

Principio de Optimidad: Una política óptima tiene la propiedad de que cualesquiera que sean 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. (Ver Bellman, 1957, Capítulo III.3.) [10] [11] [13]

En informática, se dice que un problema que se puede dividir 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 de quien toma las decisiones elijan políticas óptimas similares desde sus puntos de vista.

Como lo sugiere el principio de optimización , 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 ). Reuniendo las decisiones futuras entre paréntesis a la derecha, el problema de decisión de horizonte infinito anterior equivale a: [ se necesita aclaración ]

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 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 sólo hemos empeorado 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 de la derecha es el valor del problema de decisión de tiempo 1, comenzando desde el estado .

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

, sujeto a las restricciones:

Esta es la ecuación de Bellman. Se puede simplificar aún más si eliminamos los subíndices de tiempo e ingresamos 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, como función del estado . Calculando la función de valor, también encontraremos la función que 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 suele ser el método más conveniente para resolver problemas de control óptimo estocástico .

Para ver un ejemplo específico de economía, considere un consumidor de vida infinita con una dotación de riqueza inicial en el período . Tienen una función de utilidad instantánea donde denota el consumo y descuenta la utilidad del siguiente período a una tasa de . Supongamos 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 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 de que el consumidor no endeuda al final de su vida. La ecuación de Bellman es

Alternativamente, se puede tratar el problema de 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 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 el 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 única secuencia , el consumidor ahora debe elegir una secuencia para cada posible realización de a de tal manera que se maximice su utilidad esperada durante toda su vida:

La expectativa se toma con respecto a la medida de probabilidad apropiada dada por Q en las secuencias de r ' s. Debido a que r se rige por un proceso de Markov, la programación dinámica simplifica significativamente el problema. 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 mensurable .

Para un problema de optimización secuencial estocástica general 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 célebre aplicación económica de una ecuación de Bellman es el artículo fundamental de Robert C. Merton de 1973 sobre el modelo intertemporal de fijación de precios de activos de capital . [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 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 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 modelización de problemas teóricos en economía utilizando métodos recursivos. [21] Este libro condujo al empleo de la 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 de 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 el presupuesto de capital . [23] Anderson adaptó la técnica a la valoración de empresas, incluidas las empresas privadas. [24]

El uso de programación dinámica para resolver problemas concretos se complica por dificultades informativas, 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 acciones posibles y variables de estado potenciales que deben considerarse antes de poder seleccionar una estrategia óptima. Para una discusión extensa sobre cuestiones computacionales, ver Miranda y Fackler, [25] y Meyn 2007. [26]

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 estar en un estado particular y seguir alguna 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 conoce como ecuación de optimización 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 realizar la acción que genera el mayor rendimiento esperado.

Ver también

Referencias

  1. ^ 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.
  2. ^ "El principio de optimización 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. pag. 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–7, arXiv : 2204.13547 , doi : 10.1109/NOMS56928.2023.1015432 2, ISBN 978-1-6654-7716-1, S2CID  248427020
  5. ^ Kirk 1970, pag. 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 ed.). Ámsterdam: Elsevier. pag. 261.ISBN _ 0-444-01609-0.
  7. ^ Kirk 1970, pag. 88
  8. ^ Jones, Morgan; Peet, Mateo M. (2020). "Extensiones del marco de programación dinámica: programación de baterías, cargos por demanda e integración de energías renovables". Transacciones IEEE sobre control automático . 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 rutas, evitación de obstáculos y estimación de conjuntos invariantes". Automática . 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". La 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 Estados Unidos . 38 (8): 716–9. Código bibliográfico : 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 . Atenas científica. 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". Automática . 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 de tiempo discreto mediante 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.
  18. ^ Miao, Jianjun (2014). Dinámica económica en tiempo discreto. Prensa del MIT. pag. 134.ISBN _ 978-0-262-32560-8.
  19. ^ Beckmann, Martín; Muth, Richard (1954). "Sobre la solución a la 'ecuación fundamental' de la teoría de inventarios" (PDF) . Documento de debate 2116 de la Comisión Cowles .
  20. ^ Merton, Robert C. (1973). "Un modelo intertemporal de fijación de precios de activos de capital". Econométrica . 41 (5): 867–887. doi :10.2307/1913811. JSTOR  1913811.
  21. ^ Stokey, Nancy; Lucas, Robert E.; Prescott, Eduardo (1989). Métodos recursivos en dinámica económica . Prensa de la Universidad de Harvard. ISBN 0-674-75096-9.
  22. ^ Ljungqvist, Lars; Sargent, Thomas (2012). Teoría macroeconómica recursiva (3ª ed.). Prensa del MIT. ISBN 978-0-262-01874-6.
  23. ^ Dixit, Avinash; Pindyck, Robert (1994). Inversión bajo incertidumbre . Prensa de la Universidad de Princeton. ISBN 0-691-03410-9.
  24. ^ Anderson, Patrick L. (2004). "Capítulo 10". Economía y finanzas empresariales . Prensa CRC. ISBN 1-58488-348-0.
    — (2009). "El valor de las empresas privadas en Estados Unidos". Negocios económicos . 44 (2): 87-108. doi :10.1057/be.2009.4. S2CID  154743445.
    — (2013). Economía de la Valoración de Empresas . Prensa de la Universidad de Stanford. ISBN 9780804758307.Stanford Press Archivado el 8 de agosto de 2013 en la Wayback Machine.
  25. ^ Miranda, Mario J.; Fackler, Paul L. (2004). Economía y Finanzas Computacionales Aplicadas . Prensa del MIT. ISBN 978-0-262-29175-0.
  26. ^ Meyn, Sean (2008). Técnicas de Control de 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 .