Introducción a La Optimización Dinámica
-
Upload
juancho-pal -
Category
Documents
-
view
25 -
download
4
description
Transcript of Introducción a La Optimización Dinámica
Introducción a la optimización dinámica
Aplicaciones económicas
María José Bianco
SECRETARÍA ACADÉMICA
Departamento Pedagógico de Matemática
Clase 3
“Yo estaba intrigado por la programación dinámica. Era claro para mí que no había una buena
oferta de un buen análisis allí. Además, pude ver muchas aplicaciones. Fue una elección clara.
Yo podría ser un intelectual tradicional, o un intelectual moderno utilizando los resultados de
mi investigación para los problemas de la sociedad contemporánea. Este era un camino
peligroso. O yo podría hacer demasiada investigación y poca aplicación o podía hacer poca
investigación y mucha aplicación. Yo tenía confianza de que podía hacer esta actividad
delicada, “pie a la mode””.
Richard E. Bellman 1952
CONTROL ÓPTIMO EN TIEMPO DISCRETO El problema básico que vamos a estudiar es optimizar un problema donde las acciones tomadas en un período afectan las decisiones óptimas que se tomarán en períodos futuros. En problemas de programación dinámica un agente optimizador resuelve un problema de optimización intertemporal. Él elige la secuencia de decisiones que maximiza la función objetivo. Normalmente se denota al período donde se hizo toda la secuencia de decisiones tiempo cero. Es importante notar que las decisiones con respecto a todos los períodos son hechas en el tiempo cero, no sólo las decisiones con respecto al tiempo cero. Por eso se dice que el agente optimizador elige una secuencia de decisiones, una para cada período.
Breve historia del control óptimo en tiempo discreto
Durante los años previos al estallido de la Segunda Guerra Mundial, Alemania, Inglaterra, Estados Unidos y la U.R.S.S. formaron equipos de investigación, cuyos trabajos fueron la base de muchos de los inventos que aparecieron en funcionamiento durante la guerra (el radar, por ejemplo) y que abrieron las nuevas ramas de la matemática que se desarrollarían enormemente después de 1945. La primera gran disciplina que surgió a partir del abordaje matemático de los problemas específicos de la guerra fue, seguramente, la Investigación Operativa. El término Operations
Research fue utilizado por primera vez en Inglaterra, en 1941. Las investigaciones realizadas en los centros de Investigación Operativa de la Royal Air Force y otros organismos militares británicos permitieron, entre otras cosas, incrementar la eficacia de la los patrullajes aéreos en busca de submarinos alemanes, y consecuentemente, la cantidad de submarinos dañados o hundidos.
Inmediatamente después de la guerra y con el comienzo de la Guerra Fría, las dos superpotencias, EEUU y URSS incrementaron sus esfuerzos en utilizar matemáticos para desarrollar estrategias de defensa. Por eso no es de extrañar que tanto matemáticos del este como del oeste encontraran casi simultáneamente respuesta a los problemas que más tarde se llamarían de control óptimo. En Rusia entre tanto Pontryagin como ya vimos desarrollaba el principio del máximo trabajando con un grupo de colaboradores para la Fuerza Aérea. En EEUU, después de la Segunda Guerra Mundial, se creó RAND Corporation (Research and
Development) por la fuerza Aérea como una usina de investigación para las Fuerzas Armadas. Alrededor de 1950 simultáneamente se encontraban trabajando: Magnus Hestenes (1906-1991), Rufus Isaacs (1914-1981) y Richard Bellman (1920-1984). Hestenes redactó dos investigaciones para RAND donde desarrolló una guía para el cómputo numérico de las trayectorias de tiempo mínimo para aeronaves en los comienzos de las computadoras digitales.
Entre estos nuevos temas se encontraba la teoría de los Procesos de Decisión en Múltiples
Pasos, que Richard Bellman abordó alrededor de 1952, y para los cuales fue pensada
originalmente la Programación Dinámica.
"¿De dónde vino el nombre, programación dinámica? La década de 1950 no fueron buenos años para la investigación matemática. Tuvimos un señor muy interesante en Washington llamado Wilson. Era Secretario de Defensa y tenía un miedo y un odio patológico de la palabra “investigación”. No estoy usando el término a la ligera sino que lo estoy usando precisamente. Su rostro se teñía, se volvía rojo y se ponía violento si las personas utilizaban el término “investigación” en su presencia. Te puedes imaginar cómo se sentía, pues, sobre el término “matemática”. La RAND Corporation fue empleada por la Fuerza Aérea y la Fuerza Aérea tenía Wilson como su jefe, esencialmente. Por lo tanto, me sentí que tenía que hacer algo para proteger de Wilson y la Fuerza Aérea el hecho de que yo estaba en realidad haciendo matemáticas dentro de la RAND Corporation. ¿Qué título, qué nombre, podía elegir? En primer lugar, yo estaba interesado en la planificación, en la toma de decisiones, en el pensamiento. Pero “planificación” no es una buena palabra por varias razones. Decidí por lo tanto, utilizar la palabra "programación". Yo quería transmitir la idea de que esto era dinámico, que esto era en varias etapas, esto variaba en el tiempo. Pensé, vamos a matar dos pájaros de un tiro. Tomemos una palabra que tiene un significado absolutamente preciso como “dinámico”, en el sentido físico clásico. Además tiene una propiedad muy interesante como un adjetivo y es imposible usar la palabra dinámico, en un sentido peyorativo. Intenta pensar en una combinación que posiblemente le dé un sentido peyorativo. Es imposible. Por lo tanto, pensé “programación dinámica” era un buen nombre. Era algo que ni siquiera un Congresista podría objetar. Así que lo utilicé como un paraguas para mis actividades".
El problema general El problema general al que nos enfrentamos es:
==+
+
dado con
,,0 para ),( a sujeto
),,,,,,(max
)(
0
1
1110
x
Ttuxgx
uuxxxV
Pttt
TTut
K
KK
=tx variable de estado
=t
u variable control =•)(g ecuación de movimiento o transición (diferenciable)
V = funcional objetivo (diferenciable)
Para resolver este problema utilizando programación dinámica vamos a tener que introducir hipótesis fuertes. a) Propiedad de aditividad: El funcional objetivo V es la suma de las funciones de retorno
),(tt
uxf en los T períodos, es decir:
)(),(1
0
+
=
+=∑ T
T
t
ttxSuxfV
donde S es una función diferenciable evaluada al final del programa, donde ya no se toman más decisiones. b) Propiedad de separabilidad: Para todo t, las funciones de retorno f y de transición g
dependen de t y de los valores contemporáneos de las variables control y estado, pero no de sus valores pasados o futuros.
Por lo tanto el problema (P) queda reformulado de la siguiente forma:
==
+=
+
+
=
∑
dado con
,,0 para ),( a sujeto
)(),(max
)(
0
1
1
0
x
Ttuxgx
xSuxfV
Pttt
T
T
t
ttut
K
Resolución por el método de los multiplicadores de Lagrange
La función de Lagrange correspondiente al problema (P) es:
[ ]∑∑=
++
=
−++=
T
t
ttttT
T
t
ttxuxgxSuxfL
0
11
0
),()(),( λ
Las derivadas con respecto a tu
0=∂
∂+
∂
∂=
∂
∂
t
t
ttu
g
u
f
u
Lλ Tt ,,0 K=∀
Las derivadas con respecto a tx
0
1
1
11
=−∂
∂+
∂
∂=
∂
∂
+
+
++
t
t
t
ttx
g
x
f
x
Lλλ 1,,0 −=∀ Tt K
0
11
=−∂
∂=
∂
∂
++
T
TTx
S
x
Lλ Tt =
Las derivadas con respecto a t
λ
0),(1=−=
∂
∂+ttt
t
xuxgL
λ Tt ,,0 K=∀
Ejemplo 1:
2,
5 con
1,0 para 2 a sujeto
)(max
0
1
2
3
2
0
22
=
=+=
−+−=
+
=
∑
x
tuxx
xuxV
ttt
t
ttut
[ ]∑∑=
+
=
−++−+−=
2
0
1
2
3
2
0
22 2)(t
tttt
t
ttxuxxuxL λ
Desarrollando obtenemos:
[ ] [ ] [ ]322221111000
2
3
2
2
2
2
2
1
2
1
2
0
2
0222 xuxxuxxuxxuxuxuxL −++−++−++−−−−−−−= λλλ
Reemplazando 50=x y derivando:
0200
0
=+−=∂
∂λu
u
L
022011
1
=−+−=∂
∂λλx
x
L
0210
0
=−+=∂
∂xu
L
λ
0211
1
=+−=∂
∂λu
u
L
022122
2
=−+−=∂
∂λλx
x
L
02211
1
=−+=∂
∂xux
L
λ
0222
2
=+−=∂
∂λu
u
L
0223
3
=−−=∂
∂λx
x
L
02322
2
=−+=∂
∂xux
L
λ
Al resolver este sistema nos queda:
80
−=u 31
−=u 12
−=u 21=x 1
2=x 1
3=x
Ejemplo 2: Asignación de consumo y ahorro
Un individuo cuenta con un stock de ahorro ts . Cada período el agente retira de sus ahorros
un monto igual a tc para destinarlo a bienes de consumo. El stock de ahorro remanente
)(ttcs − se deposita en un banco que pasa una tasa de interés constante r ( 10 << r ). De este
modo en el siguiente período el nuevo stock de ahorros será igual a )()1(ttcsr −+ .
Esta operación se repita período a período hasta el momento T, cuando termina el horizonte de optimización del individuo. El comportamiento de los ahorros puede ser expresado de una manera simple a través de una ecuación de movimiento:
)()1(1 ttt
csrs −+=+ con Tt ,,1K=
Dado un stock inicial de ahorros 0s y asumiendo que el ahorro en el último período es igual a
cero ( 01=
+Ts ), el objetivo del individuo consiste en maximizar su bienestar intertemporal
hasta el período T, empleando una tasa de descuento β ( 10 << β ):
∑=
=
T
t
t
tcU
0
lnβ
Por lo tanto el problema que enfrenta el consumidor se resume del siguiente modo:
=
+==−=
=
+
+
=
∑
0
dado s con
1con ,,0 para )( a sujeto
lnmax
1
0
1
0
T
ttt
T
t
t
t
c
s
rTtcss
cUt
αα
β
K
[ ]∑∑=
+
=
−−+=
T
t
tttt
T
t
t
tscscL
0
1
0
)( ln αλβ
0=−=∂
∂
t
t
t
tcc
Lλα
β Tt ,,0 K=∀
01
1
=−=∂
∂
+
+
tt
ts
Lλλα 1,,0 −=∀ Tt K
0
1
=∂
∂
+Ts
L
Tt =
0)(1=−−=
∂
∂+ttt
t
scsL
αλ Tt ,,0 K=∀
Al resolver las ecuaciones en diferencias obtenemos
t
tk
=
αλ
1
1 ( )t
t
kc αβ
α1
1=
tt
t
kks )(
)1(
1
1
2αβ
βαα
−
+=
Resolución utilizando programación dinámica. Horizonte temporal finito
La resolución del problema (P) a través de los multiplicadores de Lagrange, si bien es correcta, no es la manera más eficiente de enfrentar el problema. En general, involucra cálculos engorrosos para despejar las variables de control y de estado óptimas y puede llegar a hacerse extremadamente largo si T es suficientemente grande.
Principio de optimalidad de Bellman
La secuencia de variables control ),,(0
∗∗∗
=T
uuu K es óptima para el problema (P) sí y sólo sí ∗
ju
con Ttttj ,,2,1, K++= resuelve el siguiente problema para todo Tt ,,0 K= :
==
+=
+
+
=
∑
dado con
,, para ),( a sujeto
)(),(max
)(1
1
t
jjj
T
T
tj
jjtu
t
x
Ttjuxgx
xSuxfV
P
t
K
Aclaración: La esencia del principio de optimalidad puede resumirse en el siguiente esquema:
444444 3444444 21
444 3444 21
KK
A
B
TTttuuuuuuu∗∗
−
∗
+
∗∗∗∗
,,,,,,,,11210
La secuencia de variables control ),,(0
∗∗∗
=T
uuu K , perteneciente al conjunto A, es óptima para el problema (P) sí y sólo sí cualquier subconjunto de variables control (desde cualquier t hasta T) como B también es óptima. Observación: Si el problema (P) es de minimización, en el principio de optimalidad también se
minimiza el problema )(tP .
El problema )(tP del principio de optimalidad puede ser planteado en términos de una
relación recursiva:
[ ]
==
+=
+
++
dado con
,,0 para ),( a sujeto
)(),(max)(
)(1
11
t
ttt
ttttu
tt
t
x
Ttuxgx
xVuxfxV
P
t
K
Donde la ecuación [ ])(),,(max)(11 ++
+=tttt
utt
xVuxtfxVt
se denomina ecuación de Bellman.
Observemos que en esta formulación del problema la maximización se realiza exclusivamente con respecto a la variable control mientras la variable de estado se mantiene constante. En la
ecuación de Bellman, tV representa la función de valor para el problema (P) en el período t.
El valor óptimo del problema (P) está dado por 0V
Procedimiento paso a paso
Definimos )()(111 +++
=TTTxSxV
• Sea Tt = . Debemos resolver el siguiente problema:
=
+
+
++
),( a sujeto
)(),(max
1
11
TTT
TTTTu
uxgx
xVuxfT
o equivalentemente (1) + ) ),((),(max
TTTTu
uxgSuxfT
Al derivar esta función con respecto a Tu e igualarla a cero (condición de primer orden de
optimización libre) nos queda que )(TTxhu =
∗
que es la llamada función de política. Reemplazamos en (1) y llamamos:
) ),((),()( ∗∗
+=TTTTTT
uxgSuxfxV
• Sea 1−= Tt . Debemos resolver el siguiente problema:
=
+
−−
−−
−
),( a sujeto
)(),(max
11
11
1
TTT
TTTTu
uxgx
xVuxfT
o equivalentemente (2) +
−−−−
−
) ),((),(max1111
1
TTTTTu
uxgVuxfT
Al derivar esta función con respecto a 1−Tu e igualarla a cero (condición de primer orden de
optimización libre) nos queda que )(11 −
∗
−=
TTxhu
Reemplazamos en (2) y llamamos:
) ),((),()(111111
∗
−−
∗
−−−−+=
TTTTTTTuxgVuxfxV
………………………………………………………
• Sea 0=t . Debemos resolver el siguiente problema:
=
+
),( a sujeto
)(),(max
001
11000
uxgx
xVuxfu
o equivalentemente + ) ),((),(max
001000
uxgVuxfu
Al derivar esta función con respecto a 0u e igualarla a cero (condición de primer orden de
optimización libre) nos queda que )(00xhu =
∗
Luego como 0x es dado, volviendo para arriba realizamos la siguiente secuencia:
00ux
h→
1100),( uxuxg
h→=
2211),( uxuxg
h→= ………
Ejemplo 3: Continuamos con el ejemplo 1
2,
5 con
1,0 para 2 a sujeto
)(max
0
1
2
3
2
0
22
=
=+=
−+−=
+
=
∑
x
tuxx
xuxV
ttt
t
ttut
Ecuación de Bellman para problemas que contienen factor de descuento El problema que vamos a considerar ahora es:
==
+=
+
+
=
∑
dado con
,,0 para ),( a sujeto
)(),(max
)(
0
1
1
0
x
Ttuxgx
xSuxfV
Pttt
T
T
T
t
tt
t
ut
K
ββ
con 10 << β
La ecuación de Bellman para este problema es:
[ ])(),(max)(11 ++
+=tttt
utt
xWuxfxWt
β
A W se la llama función valor corriente.
Ejemplo 4: Continuamos con el ejemplo 2
=
+==−=
=
+
+
=
∑
0
dado s con
1con ,,0 para )( a sujeto
lnmax
1
0
1
0
T
ttt
T
t
t
t
c
s
rTtcss
cUt
αα
β
K
∑−
=
=tT
k
k
t
t
s
c
0
β pero como β
ββ
−
−
=
+−−
=
∑1
11
0
tTtT
k
k
nos queda: 11
)1(+−
−
−
=tT
t
t
s
c
β
β
La función valor corriente, después de operar, nos queda:
KsWt
tT
t+
−
−=
+−
ln1
11
β
β
−
−
−
−+
−
−
−
−−=
+−
+−+−+−−
=
∑ 1
111
0 1
1ln
1
1
1
1ln
1
1)ln(
tT
tTtTtTtT
k
kkK
β
β
β
β
β
β
β
βαββ
Ecuación de Euler
Vamos a obtener la ecuación de Euler a partir de la ecuación de Bellman. Si el conjunto de variables de estado es convexo para todo t y para toda x y la función f es
estrictamente cóncava (para un problema de maximización) y diferenciable para ),( ux , entonces la función valor es diferenciable.
Dada la función de política )(ttxhu =
∗
, se reemplaza en la función de transición, obteniendo
))(,( ),(1 ttttt
xhxguxgx ==+ . Reemplazamos ambas ecuaciones en la ecuación de Bellman
maximizada, con lo cual se obtiene la siguiente relación:
)))(,(())(,()(),()(111 ttttttttttt
xhxgVxhxfxVuxfxV+++
+=+=
Por lo tanto la variación de tx afecta directamente a la función valor a través de la ecuación
de movimiento y a través de la función de política. Luego, por el teorema de la envolvente:
tt
t
tt
t
x
g
x
V
x
f
x
V
∂
∂
∂
∂+
∂
∂=
∂
∂
+
+
1
1
Ecuación de Benveniste y Scheinkman
Los pasos a seguir para obtener la ecuación de Euler son: 1) La condición de primer orden de la ecuación de Bellman es:
0
1
1=
∂
∂
∂
∂+
∂
∂=
∂
∂
+
+
tt
t
tt
t
u
g
x
V
u
f
u
V (*)
2) Despejamos de (*) 1
1
+
+
∂
∂
t
t
x
V
:
t
t
t
t
u
g
u
f
x
V
∂
∂
∂
∂
−=∂
∂
+
+
1
1
(**)
3) Reemplazamos la expresión (**) en la ecuación de Benveniste y Scheinkman:
t
t
t
tt
t
x
g
u
g
u
f
x
f
x
V
∂
∂
∂
∂
∂
∂
−∂
∂=
∂
∂
(***)
4) Adelantamos un período la expresión (***):
1
1
1
11
1
+
+
+
++
+
∂
∂
∂
∂
∂
∂
−∂
∂=
∂
∂
t
t
t
tt
t
x
g
u
g
u
f
x
f
x
V
5) Reemplazamos esta última expresión en la condición de primer orden:
0
1
1
1
1
=∂
∂
∂
∂
∂
∂
∂
∂
−∂
∂+
∂
∂
+
+
+
+ tt
t
t
ttu
g
x
g
u
g
u
f
x
f
u
f
Ecuación de Euler
Ejemplo 5: Continuamos con el ejemplo 2
• Aplicamos la condición de primer orden:
01
1
1=
∂
∂−=
∂
∂
+
+
t
t
tt
t
s
W
cc
Wαβ
• Despejamos 1
1
+
+
∂
∂
t
t
s
W
tt
t
cs
W
αβ
1
1
1=
∂
∂
+
+
(1)
• Hallamos la ecuación de Benveniste y Scheinkman
1
1
+
+
∂
∂=
∂
∂
t
t
t
t
s
W
s
Wαβ (2)
• Reemplazamos (1) en (2) y adelantamos un período
11
111
++
+
=∂
∂⇒=
∂
∂
tt
t
tt
t
cs
W
cs
W
• Reemplazamos en la condición de primer orden:
⇒=−
+
011
1ttcc
αβ ttcc αβ=
+1
Se debe resolver ahora el sistema de ecuaciones en diferencias
−=−
=−
+
+
ttt
tt
css
cc
αα
αβ
1
10
Obteniendo la siguiente solución
( )tt
Kc αβ1
= tt
t
KKs )(
1
1
2αβ
βα
−
+=
Horizonte temporal infinito
Al igual que en control óptimo existen problemas de optimización dinámica donde el horizonte temporal relevante es infinito. El problema general es:
==
=
+
∞
=
∑
dado con
,2,1,0 para ),( a sujeto
),(max
)(
0
1
0
x
tuxgx
uxfV
Pttt
t
tt
t
ut
K
β
La ecuación de Bellman para este problema es igual a la vista para los problemas con factor de descuento. Las dos metodologías más conocidas para hallar la función de política y la función valor en este tipo de problemas son la de aproximaciones sucesivas y la adivinar y verificar
Método de aproximaciones sucesivas
Ejemplo 7: Continuamos con el ejemplo 2
=
+==−=
=
+
+
∞
=
∑
0
dado s con
1con ,,0 para )( a sujeto
lnmax
1
0
1
0
T
ttt
t
t
t
c
s
rTtcss
cUt
αα
β
K
11
)1(+−
−
−
=tT
t
t
s
c
β
β
Luego:
ttT
t
Tt
s
s
c )1(1
)1(lim
1β
β
β−=
−
−
=+−
∞→
Teniendo en cuenta que:
2
0 )1( β
ββ
−
=∑−
=
tT
k
kk
La función valor queda:
( ) Bs
skW
t
ttT
tTtTtTtT
k
k
Tt
+−
=
=
−
−
−
−+
−
−
−
−−=
+−
+−+−+−−
=
∞→∑
ln1
1
1
1ln
1
1
1
1ln
1
1)ln(lim
1
111
0
β
β
β
β
β
β
β
β
βαββ
( )βββ
αββ−
−
+
−
= 1ln1
1
)1(
)ln(2
B
Método de adivinar y verificar
Este método consiste en adivinar la función valor o la función de política y posteriormente verificar la adivinanza a través de la ecuación de Bellman y la ecuación de Benveniste y Scheinkman. La eficiencia de este método para resolver el problema (P) dependerá:
a) de la existencia de una solución única del problema. b) La suerte al realizar la adivinanza
Ejemplo 8: Continuando con el ejemplo 7
i) Nuestra adivinanza en este caso será:
ttsAc = (1)
Donde A es una constante a determinar. Para hallar el valor de A, reemplazamos (1) en la ecuación de Euler hallada en el ejemplo 7.
ttttttsssAsAcc αβαβαβ =⇒=⇒=
+++ 111
Reemplazando por la ecuación de transición: βαβααβ =−⇒=−⇒=
+AsAssss
ttttt1)(
1 Por lo tanto la función de política es:
ttsc )1( β−=
La cual coincide con la hallada en el ejemplo 7.
ii) También se podría partir de una adivinanza sobre la ecuación de Bellman:
BsAWtt+= ln
Para encontrar las constantes se resuelve el siguiente problema:
[ ]BcsαAcsW csαs
sWcsW
ttttt
ttt
ttttt
+−+=⇒
−=
+=
+
++
))(ln(ln)()(
)(ln)(
1
11
ββ
A
sc
csα
A
cc
Wt
t
tttt
t
βαβ
+=⇒=
−−=
∂
∂
10
)(
1
Al regresar a la ecuación de Bellman, reemplazar e igualar se obtiene:
+++−++=+
A
AAABsABsA
tt
β
αβββββ
1ln)1ln(ln)1(ln
Por lo tanto:
β−=
1
1A
( )βββ
αββ−
−
+
−
= 1ln1
1
)1(
)ln(2
B
¡¡¡¡HASTA EL VIERNES!!!