Motivación Control óptimo en tiempo discreto Aplicaciones

Teorı́a Económica y Finanzas

Optimización dinámica: Programación dinámica

David Huari Leasaski

GRUPO LAMBDA PERÚ

Agosto 2016

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 1 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Contenido

1 Motivación

2 Control óptimo en tiempo discreto

Planteamiento del problema
Principio de optimalidad de Bellman

3 Aplicaciones
Brock - Mirman

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 2 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Contenido

1 Motivación

2 Control óptimo en tiempo discreto

Planteamiento del problema
Principio de optimalidad de Bellman

3 Aplicaciones
Brock - Mirman

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 3 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Optimización dinámica
Cálculo de variaciones (Bernoulli, siglo XVII)
Control óptimo (Pontryagin, 1950-1960)
Programación dinámica (Bellman, 1957)

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 4 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 1

Problema: ‘? De cuántas formas posibles se puede escribir n = 5 como

suma de 1, 3, 4? Respuesta: C5 = 6

5=1+1+1+1+1
=1+1+3
=1+3+1
=3+1+1
=1+4
=4+1

Subproblema: Considere una posible solución: 5 = x1 + x2 + . . . + xm

Suponga xm = 1 ⇒ m−1
P
i=1 xi = 4. Por tanto, el número de sumas con final
xm = 1 es C5−1 = C4

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 5 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 1

Tomando en cuenta los otros casos (xm = 3, xm = 4), se formula la

recurrencia:
C5 = C4 + C2 + C1
donde C4 = 4
5=1+1+1+1+1
=1+3+1
=3+1+1
=4+1

C2 = 2
5=1+1+3

C1 = 1
5=1+4
David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 6 / 25
Motivación Control óptimo en tiempo discreto Aplicaciones

Que sucede cuando n ≈ 108

Implementación
En general, para cualquier n ∈ N se tiene,

Cn = Cn−1 + Cn−3 + Cn−4

C0 = 1
C[0] = C[1] = C[2] = 1; C[3] = 2;
for(i = 4; i <= n; i++)
C[i] = C[i-1] + C[i-3] + C[i-4];

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 7 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 2: ruta óptima

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 8 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 2: ruta óptima

El problema de rutas se puede dividir en tres etapas

1 Etapa 1: Desde A hasta B, C o D
2 Etapa 2: Desde B, C o D hasta E , F o G
3 Etapa 3: Desde E , F o G hasta H
Se resolverá el problema de forma regresiva. La solución óptima es:

A−B−G −H

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 9 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 2: ruta óptima

Etapa 3
Partida Acción Distancia a H
E H 3
F H 6
G H 2
Cuadro: Información relevante de la tercera etapa

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 10 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 2: ruta óptima

Etapa 2
Partida Acción Distancia a H
B E 7
B F 12
B G 4
C E 7
C F 11
C G 9
D E 11
D F 10
D G 7
Cuadro: Información relevante de la segunda etapa

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 11 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 2: ruta óptima

Etapa 1
Partida Acción Distancia a H
A B 11
A C 15
A D 12
Cuadro: Información relevante de la tercera etapa

Para el paso de A a B tomo en cuenta los pasos anteriores.

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 12 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Ejemplo 2: ruta óptima

Si observamos por ejemplo el el paso 2, se ha construido una función que

hace corresponder a cada posible ciudad inicial la distancia mı́nima a
recorrer a partir de ella (Función valor), en esta función y la acción a
tomar se resume toda la información sobre la etapa correspondiente.

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 13 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Contenido

1 Motivación

2 Control óptimo en tiempo discreto

Planteamiento del problema
Principio de optimalidad de Bellman

3 Aplicaciones
Brock - Mirman

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 14 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Programación dinámica

Método para resolver problemas complejos a través de subproblemas

más simples
Reconocer y resolver en el escenario base
Cada etapa es importante

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 15 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Planteamiento del problema

N−1
X
máx J= F (x (k), u(k), k) + S(x (N))
{u(k)}N−1
k=0 k=0

sa :
x (k + 1) = f (x (k), u(k), k), k = 0, 1, . . . , N − 1

x (0) = x0 ,

u(k) ∈ U(k)

recuerde que la sumatoria va hasta N − 1 y el horizonte se completa con

S(x (N))

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 16 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Planteamiento del problema

x es variable de estado y u variable de control

J es una función objetivo
f se define como
f : A × B × {0, 1, . . . , N − 1} −→ R

(x , uk) 7−→ f (x , u, k)
F se define como
F : A × B × {0, 1, . . . , N − 1} −→ R

(x , u, k) 7−→ F (x , u, k)
S se define como S : A × B −→ R
x 7−→ S(x )
U ⊂ R conjunto de controles admisibles
donde A, B ⊂ R
David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 17 / 25
Motivación Control óptimo en tiempo discreto Aplicaciones

Planteamiento del problema

Proposition
Propiedad de Causalidad . ∀j, r ∈ {0, 1, . . . , N − 1}, con j < r , se
verifica que x (r ) depende únicamente de x (j) y de los controles
{u(j), u(j + 1), . . . , u(r − 1)}

Lemma
Sean g y h dos funciones con dominios A y A0 , respectivamente. Entonces,
asumiendo que existe un óptimo para el problema panteado, se verifica
que: n o
máx 0 {g(y ) + h(y , z)} = máx g(y ) + máx0 {h(y , z)}
y ∈A,z∈A y ∈A z∈A

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 18 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Planteamiento del problema

Proposition
(2.2) Sea J ∗ (x0 ) el valor óptimo del funcional objetivo del problema.
Entonces J ∗ (x0 ) = J0∗ (x0 ). j0∗ viene dada por el último paso del siguiente
algoritmo, que comienza al final del horizonte temporal y va hasta el
principio, y por tanto, hacia atrás en el tiempo.

JN∗ {x (N)} = s[x (N)]

además, ∀k ∈ {N − 1, N − 2, . . . , 1, 0}
n o
Jk∗ {x (k)} = máx ∗
F (x (k), u(k), k) + Jk+1 {f (x (k), u(k), k)}
u(k∈U (k)

son las ecuaciones de Bellman para el problema.

Además, si u ∗ (k) maximiza la expresión derecha de Bellman, en función de
x (k), ∀k ∈ {0, 1, . . . , N − 1}, entonces, el control óptimo viene dado por

u∗ = (u ∗ (0), u ∗ (1), . . . , u ∗ (N − 1))0

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 19 / 25
Motivación Control óptimo en tiempo discreto Aplicaciones

Principio de optimalidad de Bellman

Theorem
Principio de optimalidad de Bellman Sea u∗ = (u ∗ (0), u ∗ (1), . . . , u ∗ (N − 1))0
el control óptimo del problema y x ∗ = (x ∗ (0), x ∗ (1), . . . , x ∗ (N))0 la trayectoria
óptima correspondiente del estado. Sea el subproblema,
N−1
X
máx F (x (k), u(k), k) + S(x (N))
N−1
{u(k)}k=j
k=j

sa :
x (k + 1) = f (x (k), u(k), k), k = j, j + 1, . . . , N − 1

x (j) = x ∗ (j),

u(k) ∈ U(k), k = j, j + 1, . . . , N − 1

Es decir, el subproblema que debe encontrar los controles óptimos en las etapas
j + 1 a N − 1, partiendo de la condición inicial x ∗ (j), en la etapa j + 1. Entonces,
el control óptimo del subproblema formulado es
(u ∗ (j), u ∗ (j + 1), . . . , u ∗ (N − 1))0 , vector truncado de u∗.
David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 20 / 25
Motivación Control óptimo en tiempo discreto Aplicaciones

Principio de optimalidad de Bellman

Ejemplo 1
mı́n J = (u(0) − 2)2 + (u(1) − 4)2 + (x (2)
u(0),u(1)

sa :
x (0) = 1
x (1) = 3x (0) + u(0)
x (2) = x (1) + 2u(1)

Ejemplo 2
mı́n J = x (0)u(0) + x (1)u(1) + x (2)2
u(0),u(1)

sa :
x (0) = 2
x (k + 1) = x (k)u(k) + u(k)2 , k = 0, 1,
u(k) ∈ {−1, 0, 1}
David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 21 / 25
Motivación Control óptimo en tiempo discreto Aplicaciones

Principio de optimalidad de Bellman

Ejemplo 3
N−1
Xq
máx J= u(k)
{u(k)}N−1
k=0 k=0

sa :
x (0) = C
x (N) = 0
x (k + 1) = x (k)u(k) − u(k)2 , k = 0, 1, . . . , N − 1
0 ≤ u(k) ≤ x (k), k = 0, 1, . . . , N − 1

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 22 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Contenido

1 Motivación

2 Control óptimo en tiempo discreto

Planteamiento del problema
Principio de optimalidad de Bellman

3 Aplicaciones
Brock - Mirman

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 23 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Brock - Mirman

El problema secuencial y funcional

 P+∞ t
 sup t=0 β F (xt , xt+1 )
{xt }∞


t=0


PS s.a xt+1 ∈ Γ(xt ), t = 0, 1, . . .




x0 ∈ X dado



 sup {F (x , y ) + βV (y )}, ∀x ∈ X
PF y ∈Γ(x )


David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 24 / 25

Motivación Control óptimo en tiempo discreto Aplicaciones

Brock - Mirman

Ejemplo 4
 P+∞ t
 sup t=0 β `n(ct ),

{x }∞
t


 t=0


PS s.a kt+1 = ktα − ct ,





 ct , kt ≥ 0, t = 0, 1, . . .
k0 ∈ X dado


sup {`nc + βV (k α − c)}, ∀x ∈ X

(
PF 0≤c≤k α

donde la tasa de descuento β ∈ [0, 1] y la participación del capital en la

producción α ∈ (0, 1).

David Huari Leasaski (LAMBDA) Programación dinámica Agosto 2016 25 / 25