Ecuación de Bellman

La ecuación de Bellman, también conocida como la ecuación de programación dinámica, nombrada en honor de su descubridor, Richard Bellman, es una condición necesaria para la optimalidad asociada con el método de la optimización matemática conocida como programación dinámica. Se escribe el valor de un problema de decisión en un determinado punto en el tiempo en términos de la recompensa que dan algunas opciones iniciales y el valor del problema de decisión restante que resulta de esas opciones iniciales. Esto rompe un problema de optimización dinámica en subproblemas más simples, tal como el Principio de optimalidad de Bellman establece.

La ecuación de Bellman se aplicó primero a la ingeniería en la teoría de control y otros temas de matemática aplicada y, posteriormente, se convirtió en una herramienta importante en la teoría económica.

Casi cualquier problema que puede ser resuelto usando la teoría de control óptimo también se puede resolver mediante el análisis de la ecuación de Bellman apropiada. Sin embargo, el término "ecuación de Bellman" por lo general se refiere a la ecuación de programación dinámica asociada a tiempo discreto problemas de optimización. En los problemas de optimización en tiempo continuo, la ecuación análoga es una ecuación diferencial parcial que generalmente se llama la ecuación de Hamilton-Jacobi-Bellman.

Conceptos analíticos en programación dinámica

Para entender la ecuación de Bellman, varios conceptos subyacentes deben ser entendidos. En primer lugar, cualquier problema de optimización debe tener un objetivo - reducir al mínimo el tiempo de viaje, reduciendo al mínimo coste, maximizar los beneficios, maximización de la utilidad, etcétera. La función matemática que describe este objetivo se denomina función objetivo.

La programación dinámica descompone un problema de planificación de múltiples períodos en pasos más simples para diferentes momentos. Por lo tanto, se requiere hacer el seguimiento de cómo la situación de decisión está evolucionando en el tiempo. La información sobre la situación actual que se necesita para tomar una decisión correcta se llama el estado (Ver Bellman, 1957, cap. III.2).^[1]^[2] Por ejemplo, para decidir cuánto consumir y gastar en cada punto en el tiempo, la gente tendría que 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 seleccionadas en cualquier punto dado en el tiempo se llaman variables de control. Por ejemplo, dada su riqueza actual, la gente podría decidir cuánto consumir ahora. La elección de las variables de control ahora puede ser equivalente a la elección de la siguiente estado; más en general, el siguiente estado se ve afectada por otros factores, además de la regulación de corriente. Por ejemplo, en el caso más sencillo, la riqueza de hoy (el estado) y el consumo (el control) pueden determinar con exactitud la riqueza de mañana (el nuevo estado), aunque por lo general otros factores pueden afectar la riqueza de mañana también.

El enfoque de programación dinámica describe el plan óptimo mediante la búsqueda de una regla que dice lo que los controles deben ser, teniendo en cuenta cualquier posible valor del estado. Por ejemplo, si el consumo (c) solo depende de la riqueza (W), entonces se buscaría una regla $c(W)$ que da el consumo en función de la riqueza. Tal regla general, la determinación de los controles como una función de los estados, se llama una función de política (Ver Bellman, 1957, cap. III.2).^[1]

Por último, 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, la riqueza dada, con el fin de maximizar la felicidad (suponiendo que la felicidad H puede ser representado por una función matemática, tal como una utilidad de función), a continuación, cada nivel de la riqueza se asocia con algún nivel más alto posible de la felicidad, $H(W)$ . El mejor valor posible del objetivo, escrita como una función del estado, se llama la función de valor.

Richard Bellman mostró que una dinámica de optimización de un problema en tiempo discreto se puede afirmar en un recursivo forma, paso a paso, anotando la relación entre la función de valor en un período y el valor de la función en el próximo período. La relación entre estas dos funciones de valor se llama la ecuación de Bellman.

Derivación de la ecuación de Bellman

Un problema de decisión dinámico

Sea $x_{t}$ el estado en el momento $t$ . Para una decisión que comienza en el momento 0, tomamos como dado el estado inicial $x_{0}$ . En cualquier momento, el conjunto de posibles acciones depende del estado actual; podemos escribir esto como $a_{t}\in \Gamma (x_{t})$ , donde la acción $a_{t}$ representa una o más variables de control. También suponemos que el estado cambia de $x$ a un nuevo estado $T(x,a)$ cuando la acción $a$ se toma, y que el pago actual de tomar la acción $a$ en el estado $x$ es $F(x,a)$ . Por último, asumimos la impaciencia, representado por un factor de descuento $0<\beta <1$ .

Bajo estos supuestos, un problema de decisión de horizonte infinito toma la siguiente forma:

$V(x_{0})\;=\;\max _{\left\{a_{t}\right\}_{t=0}^{\infty }}\sum _{t=0}^{\infty }\beta ^{t}F(x_{t},a_{t}),$

sujeto a las limitaciones:

$a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t=0,1,2,\dots$

Nótese que se ha definido la notación $V(x_{0})$ para representar el valor óptimo que se puede obtener mediante la maximización de la función objetivo con sujeción a las limitaciones asumidas. Esta función es la función de valor. Es una función de la variable de estado inicial $x_{0}$ , ya que la mejor relación obtenible depende de la situación inicial.

Principio de Bellman de optimalidad

El método de programación dinámica rompe este problema de decisión en subproblemas más pequeños. El principio de optimalidad de Bellman explica 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 en relación con el estado resultante de la primera decisión. (Ver Bellman, 1957, Cap. III.3.)^[1]^[2]^[3]

En ciencias de la computación, se dice que un problema que puede ser descompuesto de esta forma tiene subestructura óptima. En el contexto de la dinámica de la teoría de juegos, este principio es análogo al concepto de equilibrio perfecto en subjuegos, a pesar de lo que constituye una política óptima en este caso, está condicionado a los opositores del decisor elegir 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 (vamos a empezar de nuevo de vez en 1 con el nuevo estado $x_{1}$ ). La recogida de las futuras decisiones entre paréntesis a la derecha, el problema anterior es equivalente a:

$\max _{a_{0}}\left\{F(x_{0},a_{0})+\beta \left[\max _{\left\{a_{t}\right\}_{t=1}^{\infty }}\sum _{t=1}^{\infty }\beta ^{t-1}F(x_{t},a_{t})\;\;s.t.\;\;a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t=1,2,\dots \right]\right\}$

sujeto a las restricciones:

$a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).$

Aquí estamos eligiendo $a_{0}$ , sabiendo que nuestra elección hará que el tiempo de 1 estado sea $x_{1}=T(x_{0},a_{0})$ . Ese nuevo estado será entonces afectar el problema de decisión de vez en 1. Todo el problema de decisión futura aparece dentro de los corchetes de la derecha.

Ecuación de Bellman

De momento parece que solo hemos hecho el problema más complicado al separar la decisión de hoy de las decisiones futuras. Pero podemos simplificar por darse cuenta de que lo que está dentro de los corchetes de la derecha es el valor del tiempo de problema de decisión 1, a partir de un estado $x_{1}=T(x_{0},a_{0})$ .

Por lo tanto se puede reescribir el problema como un recurrente definición de la función de valor:

$V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}$

sujeto a la restricción:

$a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).$

Esta es la ecuación de Bellman. Se puede simplificar aún más si se cae subíndices de tiempo y el enchufe en el valor del siguiente estado:

$V(x)=\max _{a\in \Gamma (x)}\{F(x,a)+\beta V(T(x,a))\}.$

La ecuación de Bellman se clasifica como una ecuación funcional, porque resolver que significa la búsqueda de la función desconocida V, que es la función de valor. Recordemos que la función de valor describe el mejor valor posible del objetivo, como una función del estado x. Mediante el cálculo de la función de valor, también se encuentra la función a (x) que describe la acción óptima en función de la situación, lo que se llama a la función política.

La ecuación de Bellman en un problema estocástico

Las técnicas de programación dinámica presentan dificultades cuando las toma de decisiones son variables aleatorias a(t,w), y es un enfoque que se vuelve conveniente desarrollar para aproximarse a la realidad.

Sea el ejemplo en el que se considera un consumidor con una dotación inicial de riqueza en t=0. Él cuenta con una función de utilidad U(c) donde c denota el consumo afectada por una tasa de descuento 0 <β <1. Supongamos ahora que no se consume en el período t y se traslada al próximo período con tasa de interés r. El problema de maximización de utilidad del consumidor es elegir un plan de consumo {c(t)} que resuelve:

$\max \sum _{0}^{\infty }\beta ^{t}u(c_{t})$

sujeto a:

$a_{t+1}=(1+r)(a_{t}-c_{t}),\;c_{t}\geq 0,$

y

$\lim _{t\rightarrow \infty }a_{t}\geq 0.$

La primera restricción es la acumulación de capital / ley de movimiento especificado por el problema, mientras que la segunda restricción es una condición de transversalidad en la que el consumidor no paga la deuda al final de su vida. La ecuación de Bellman es

$V(a)=\max _{0\leq c\leq a}\{u(c)+\beta V((1+r)(a-c))\},$

Como alternativa, se puede tratar el problema directamente con la secuencia, por ejemplo, la ecuación de hamiltonianos.

Ahora, si la tasa de interés varía de un período a otro, el consumidor se enfrenta con un problema de optimización estocástica. En donde el interés r sigue un proceso de Markov con función de probabilidad de transición Q (r, dμ r) donde dμ r denota la medida de probabilidad que rige la distribución del próximo periodo de tipos de interés, siempre y cuando la tasa de interés actual sea r. En el calendario de este modelo es que el consumidor decide su consumo actual por un periodo clarividente proporcionado que indique o dé su pronóstico de la tasa de interés.

En lugar de simplemente eligir una secuencia única {c} t, el consumidor debe ahora elegir una secuencia {c(w)} t para cada posible realización de un r {t} de tal manera que su utilidad esperada maximiza sea:

$\max E(\sum _{0}^{\infty }\beta ^{t}u(c_{t})).$

La expectativa E se toma con respecto a la medida de probabilidad apropiada dada por Q en las secuencias de variables aleatorias. Debido a que r es gobernado por un proceso de Markov en cada intervalo de tiempo. A continuación, la ecuación Bellman es:

$V(a,r)=\max _{0\leq c\leq a}\{u(c)+\beta \int V((1+r)(a-c),r')Q(r,d\mu _{r})\}.$

Bajo algunas hipótesis, la política de la función óptima resultante g(a, r) es medible.

Para un problema de optimización estocástica secuencial general, la ecuación de Bellman toma la forma:

$V(x,z)=\max _{c\in \Gamma (x,z)}F(x,c,z)+\beta \int V(T(x,c),z')d\mu _{z}(z').$

Métodos de solución

El método de coeficientes indeterminados , también conocido como "adivinar y verificar", se puede utilizar para resolver algunos de horizonte infinito, autónomas ecuaciones de Bellman.

La ecuación de Bellman puede ser resuelta por inducción hacia atrás , ya sea analíticamente en unos pocos casos especiales, o numéricamente en un ordenador. La inducción hacia atrás numérica es aplicable a una amplia variedad de problemas, pero puede ser no factible cuando hay muchas variables de estado, debido a la maldición de la dimensionalidad. Programación aproximado dinámica ha sido introducido por DP Bertsekas y JN Tsitsiklis con el uso de redes neuronales artificiales ( perceptrones multicapa ) para la aproximación de la función de Bellman. [4] Esta es una estrategia de mitigación eficaz para reducir el impacto de la dimensionalidad mediante la sustitución de la memorización de la correlación de funciones completo para el dominio de todo el espacio con la memorización de los únicos parámetros de la red neural.

Mediante el cálculo de las condiciones de primer orden asociados con la ecuación de Bellman y, a continuación, utilizando el teorema de la envolvente para eliminar los derivados de la función de valor, es posible obtener un sistema de ecuaciones en diferencias o ecuaciones diferenciales llamados los " ecuaciones de Euler . Las técnicas estándar para la solución de la diferencia o ecuaciones diferenciales pueden usarse entonces para calcular la dinámica de las variables de estado y las variables de control del problema de optimización.

Aplicaciones en economía

El primer uso conocido de una ecuación de Bellman en la economía se debe a Martin Beckmann y Richard Muth.^[4] Martin Beckmann también escribió extensamente sobre la teoría del consumo mediante la ecuación de Bellman en 1959. Su obra influyó Edmund S. Phelps, entre otros.

Una aplicación económica celebrado de una ecuación de Bellman es seminal artículo de Merton 1973 en el Capital Asset Pricing Model intertemporal.^[5] (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 optaron entre el ingreso actual y el ingreso futuro o ganancias de capital, es una forma de la ecuación de Bellman. Dado que las aplicaciones económicas de programación dinámica suelen dar lugar a 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 un subcampo de la economía recursivas es ahora reconocido en Economía.

Nancy Stokey, Robert E. Lucas y Edward C. Prescott describen la programación dinámica estocástica y no estocástica en un detalle considerable 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.^[6] Este libro llevó a la programación dinámica que se utiliza para resolver una amplia gama de problemas teóricos en la economía, incluyendo el crecimiento económico óptimo, la extracción de recursos, los problemas agente principal , las finanzas públicas , la inversión empresarial, la fijación de precios de los activos, el suministro de factores y la organización industrial. Lars Ljungqvist y Thomas Sargent aplican una 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 del trabajo . [8] Avinash Dixit y Robert Pindyck mostraron el valor del método para pensar en el presupuesto de capital.^[7] Anderson adaptó la técnica a la valuación del negocio, incluyendo negocios privados.^[8]

Referencias

↑ ^a ^b ^c Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Republished 2003: Dover, ISBN 0-486-42809-5.
↑ ^a ^b S. Dreyfus (2002), 'Richard Bellman on the birth of dynamic programming' Operations Research 50 (1), pp. 48–51.
↑ Bellman, R (August 1952). «On the Theory of Dynamic Programming». Proc Natl Acad Sci U S A 38 (8): 716-9. Bibcode:1952PNAS...38..716B. PMC 1063639. PMID 16589166. doi:10.1073/pnas.38.8.716.
↑ Martin Beckmann and Richard Muth, 1954, "On the solution to the fundamental equation of inventory theory," Cowles Commission Discussion Paper 2116.
↑ Robert C. Merton, 1973, "An Intertemporal Capital Asset Pricing Model," Econometrica 41: 867–887.
↑ Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989). Recursive Methods in Economic Dynamics. Harvard Univ. Press. ISBN 0-674-75096-9.
↑ Dixit, Avinash; Pindyck, Robert (1994). Investment Under Uncertainty. Princeton Univ. Press. ISBN 0-691-03410-9.
↑ Anderson, Patrick L., Business Economics & Finance, CRC Press, 2004 (chapter 10), ISBN 1-58488-348-0; The Value of Private Businesses in the United States, Business Economics (2009) 44, 87–108. doi 10.1057/be.2009.4. Economics of Business Valuation, Stanford University Press (2013); ISBN 9780804758307. Stanford Press Archivado el 8 de agosto de 2013 en Wayback Machine.

Datos: Q1430750

[BellmanDP-1] Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Republished 2003: Dover, ISBN 0-486-42809-5.

[dreyfus-2] S. Dreyfus (2002), 'Richard Bellman on the birth of dynamic programming' Operations Research 50 (1), pp. 48–51.

[BellmanTheory-3] Bellman, R (August 1952). «On the Theory of Dynamic Programming». Proc Natl Acad Sci U S A 38 (8): 716-9. Bibcode:1952PNAS...38..716B. PMC 1063639. PMID 16589166. doi:10.1073/pnas.38.8.716.

[4] Martin Beckmann and Richard Muth, 1954, "On the solution to the fundamental equation of inventory theory," Cowles Commission Discussion Paper 2116.

[5] Robert C. Merton, 1973, "An Intertemporal Capital Asset Pricing Model," Econometrica 41: 867–887.

[6] Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989). Recursive Methods in Economic Dynamics. Harvard Univ. Press. ISBN 0-674-75096-9.

[7] Dixit, Avinash; Pindyck, Robert (1994). Investment Under Uncertainty. Princeton Univ. Press. ISBN 0-691-03410-9.

[8] Anderson, Patrick L., Business Economics & Finance, CRC Press, 2004 (chapter 10), ISBN 1-58488-348-0; The Value of Private Businesses in the United States, Business Economics (2009) 44, 87–108. doi 10.1057/be.2009.4. Economics of Business Valuation, Stanford University Press (2013); ISBN 9780804758307. Stanford Press Archivado el 8 de agosto de 2013 en Wayback Machine.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]