1.

DEFINICIN DEL PROBLEMA DE CONTROL PTIMO

Sistema determinstico si las
(
t
forman una sucesin de constantes
con valores conocidos;
Sistema incierto si se sabe que las
(
t
son constantes con valores en
algn conjunto dado, pero no se conoce el valor particular de cada
(
t
.
En todo caso (incluyendo los modelos a tiempo continuo que veremos a
continuacin), el conjunto de donde toman sus valores las variable x
t
se llama
el espacio de estados del PCO y lo denotaremos por X. Par fijar las ideas
supondremos que X es un subconjunto cerrado de

d
para algn entero d 1.
(Mas generalmente, basta suponer que X es un espacio de Borel, es decir, un
subconjunto de Borel de un espacio mtrico separable y completo
Sistemas a tiempo contino:
Caso determinstico:
Xt =F(t , Xt , At ) para 0tT , (1.1)
con T y condicin inicial dada x
0
= x.
Caso estocstico: este caso admite una gran diversidad de modelos.
El ms estudiado es el de una ecuacin diferencial estocstica
dx
t
=F (t , X
t
, a
t
) dt +(t , x
t
, a
t
) dW
t
, 0t T , x
t
=x , (1.2)
con T , y W
t
es un proceso de Wiener. El estado inicial x
0
puede ser
determinstico o estocstico. Otros modelos estocsticos a tiempo
continuo son las cadenas de Markov, los procesos de Lvy, los procesos
hbridos (e.g., el sistema (1.2) pero, adems, con una componente de
saltos),...
Definicin 1.1: Estrategias admisibles. Una estrategia de control, digamos
n = a
t

, generalmente se especifica imponiendo restricciones

(a) en las acciones de control a
t
directamente, y/o
(b) en la informacin que puede o debe usar el controlador en cada tiempo t.
Por ejemplo, en (a), n cas muy comn es pedir
a
t
A( x
t
) t , (1.3)
donde A(x) es el conjunto de acciones factibles cuando el estado es x.
Con respecto a (b), un caso muy general es el de una estrategia no-
anticipante, tambin conocida como estrategia con memoria (memory
strategy), en la que, en cada tiempo t, la accin a
t
depende de "toda la historia
del proceso hasta el tiempo t. Por ejemplo, en un PCO a tiempo discreto
tenemos
a
t
=g(t , T
0
,., x
t
, a
0
., a
t 1
) ,
donde g es una funcin dada. El otro extremo es cuando g depende de t
nicamente,
es decir,
a
t
=g(t ) t , (1.4)
en cuyo caso se dice que es una estrategia de lazo abierto (open loop). Si g
depende slo de t y x
t
, es decir,
a
t
=g(t , x
t
) t (1.5)
decimos que es una estrategia de retroalimentacin (feedback), tambin
llamada estrategia de lazo cerrado (closed loop) o estrategia
markoviana. Si adems g no depende de t, i.e.
a
t
=g( x
t
) t ,
(1.6)
entonces es una estrategia markoviana estacionaria.
Las estrategias mencionadas se dice que son determinsticas, y
generalmente son "suficientes" para estudiar problemas de control. Sin
embargo, en algunos problemas de control con restricciones o en problemas de
juegos es indispensable usar estrategias aleatorizadas, tambin conocidas
como estrategias mixtas o controles relajados (relaxed controls), en las
que cada accin de control
a
t
es una variable aleatoria con una distribucin
de probabilidad

t
concentrada en el conjunto
A( x
t
)
en (1.3), lo cual
denotamos como
a
t

t
(.) .
(1.7)
Ms explcitamente,

t
( B) :=Prob(a
t
B)
para
BA( x
t
)
. En algunos casos, la
distribucin

t
depende no slo del tiempo
t
sino tambin del estado
x
t . En
este caso escribimos
a
t

t
(./ x
t
) t.
(1.8)
Las estrategias en (1.7) y (1.8) son la versin aleatorizada (o "relajada") de las
estrategias de lazo abierto y de lazo cerrado en (1.4) y (1.5), respectivamente.
Para cada estado
x X
, el conjunto de acciones factibles
A( x)
en (1.3) es un
subconjunto cerrado de un espacio
A
que se llama el espacio de acciones. A
menos que se especifique lo contrario, supondremos que
A
es un subconjunto
cerrado de

m
para algn
m1
. (Ms generalmente, basta suponer que
A
es
un espacio de Borel.)
Definicin 1.2. Restricciones adicionales. Estas restricciones pueden
depender de la naturaleza del PCO. Por ejemplo, en un problema de control de
poblaciones (e.g. pesqueras, epidemias, etc.) el estado
x
t
del sistema es el
tamao de la poblacin al tiempo
t
, y obviamente se debe pedir una condicin
de no- negatividad,
x
t
0 t.
Esta misma restriccin se debe cumplir en problemas de control de recursos
renovables (e.g. agua, bosques) o no-renovables (e.g. petrleo, minerales), o
en problemas financieros en los que el estado es un capital. En otras
situaciones se puede requerir que el estado terminal
x
T
pertenezca a un cierto
conjunto
K
, i.e.
X
t
K.

Otro caso muy comn es cuando se desea optimizar una cierta funcin
objetivo, digamos
V
0
(n)
, sobre todas las estrategias
n
para las que
V
i
(n)b
i
i =1,., n ,
(1.9)
donde las
V
i
( )
son funciones dadas y las
b
i son constantes. Por ejemplo, en
un problema de control de produccin, tpicamente se desea maximizar la
ganancia neta
V
0
(n)
sujeta a que ciertos costos
V
i
(n)
(e.g. costos de
manufactura, de almacenamiento, de distribucin, etc.) estn acotados por
arriba, como en (1.9).
Definicin 1.3. La funcin objetivo o ndice de funcionamiento. Para un
PCO determinstico a tiempo discreto, ejemplos tpicos de funcin objetivo son:
para cada estrategia
n=a
t

y cada estado inicial

x
0
=x ,
. costo total con horizonte finito
T
:
V (n, x):=

t=0
T1
c( x
t
, a
t
)+C
T
( x
T
) ,
(1.10)
donde
c( x , a)
es el costo por etapa, y
C
T
( x)
es el costo terminal
. costo total descontado con horizonte infinito:
V (n , x):=

t =0

t
c( x
t
, a
t
) ,
(1.11)
donde O << 1 es el factor de descuento.
En un PCO estocstico a tiempo discreto se debe tomar la esperanza en el lado
derecho de (1.10) y (1.11); por ejemplo, en lugar de (1.10) tendramos
V (n, x):=E |

t=0
T1
c( x
t
, a
t
)+C
T
( x
T
) ,
(1.12)
En un PCO a tiempo continuo las sumatorias en (2.11) y (2.12) se reemplazan
por integrales. Por ejemplo, en el caso de horizonte finito
V (n, x):=

0
T
c( x
t
, a
t
) dt +C
T
( x
T
) ,
(1.13)
Si adems el PCO es estocstico, se debe tomar la esperanza en el lado
derecho, i.e.
V (n, x):=E|

0
T
c( x
t
, a
t
) dt +C
T
( x
T
) ,
(1.14)
En teora de juegos, a una funcin objetivo tambin se le llama funcin de
pago (payoff function).
Finalmente, como ya mencionamos al principio de esta seccin, en un PCO se
especifican la funcin objetivo
V (n, x)
(alguna de las funciones (1.10) a
(1.14)) y el conjunto, digamos
n
, de estrategias admisibles y entonces el PCO
consiste en optimizar (ya sea minimizar o maximizar)
V (n, x)
sobre todas las
estrategias
nH
para las que el proceso de estados
x
t

sigue el modelo
dinmico correspondiente (e.g. (1.1) a (1.3)) y satisface las restricciones
adicionales (e.g. (1.9)), si las hay. A la funcin
V( x):=inf
nH
V (n, x) xX ,
(1.15)
se le llama la funcin de valor del PCO. En el caso de "costos", como en (1.10)-
(1.14), a
V( x)
tambin se le llama funcin de costo mnimo. Si en lugar
de costos tenemos "ganancias" o "utilidades" que se desean maximizar,
entonces en lugar de (1.15) la funcin de valor es
V

( x) := s u p
nH
V (n

, x) xX ,
(1.16)
y se le llama tambin la funcin de ganancia (o de utilidad) mxima. En
todo caso, si existe una estrategia
n

H
tal que
V

( x) := s u p
nH
xX ,
(1.17)
se dice que ir es una estrategia ptima.
Ejemplo 1.1. El siguiente PCO se conoce como problema de seleccin de
portafolio (de inversin) o como problema de inversin y consumo, y se
puede plantear a tiempo discreto o a tiempo continuo.
Tiempo discreto. Considrese un mercado financiero con dos tipos de activos:
un activo libre de riesgos (e.g. algn tipo de bonos o CETES =
Certificados de la Tesorera) con una tasa fija de inters
r>0
y
un activo con riesgo (e.g. algn tipo de acciones) con una tasa
aleatoria de inters
(
t
0
. Obviamente, pedimos que
E((
t
)>r.
La variable de estado es el capital
x
t
de un cierto inversionista, que en cada
tiempo
t (t = 0,1,., T )
debe decidir cuanto consumir y cuanto invertir.
Entonces las acciones de control son
a
t
= ( c
t
, p
t
) |0, x
t
| 0,1 ,
(1.18)
donde

c
t
:=
cantidad que el inversionista decide consumir,

p
t
:=
fraccin de
x
t
c
t que decide invertir en el activo con riesgo, de
modo que
1 c
t
es la fraccin de
x
t
c
t
que invertir en el activo sin riesgo.
El conjunto
A(t ) := | 0, x | 0,1
en (1.18) es el conjunto de "acciones
factibles", como en (1.3).
El modelo dinmico del sistema es
X
t +1
= | (1P
t
)(1+r) + Pt (
t
( x
t
c
t
) t =0,1,.
(1.19)
con condicin inicial
x
0
= > 0
. Una funcin objetivo tipica es una "utilidad de
consumo"
V (n, x) := E
x
n
|

T=0
T
o
t
U (c
t
) (1.20)
donde
T , o (0,1)
es el factor de descuento, y
U(c)
es una funcin de
utilidad. El PCO consiste en maximizar la funcin en (1.20) sobre todas las
estrategias
n = a
t

con
a
t como en (1.17), bajo la "restriccin" (1.19).
Tiempo continuo. En este caso el precio b(t ) del activo sin riesgo (el bono,
digamos) varia de acuerdo a una ecuacin diferencial ordinaria
db(t ) = rb(t ) dt.
con r > 0, mientras que el precio s(t) del activo con riesgo (el "stock") est
dado por una ecuacin diferencial estocstica
ds(t ) = s(t )| mdt + cdw(t ) ,
donde
m > r
y
c 0
son constantes, y
o( )
es un proceso de Wiener
estndar. Las acciones de control
a(t ) = (C(t ) , p(t ))
tienen la misma
interpretacin que en (1.18). El modelo de sistema, en lugar de (1.19), ahora
resulta ser la ecuacin diferencial estocstica.
dx(t ) = (1 p(t )) x(t )rdt + p(t ) x (t )| mdt +c dw(t ) cd (t ) dt
(1.21)
con
x(0) = x > 0
. Los tres trminos en el lado derecho de (1.21)
corresponden, respectivamente, a la ganancia por el capital invertido en el
bono, la ganancia por la inversin en el stock, y la disminucin del capital
debida al consumo.
Por ltimo, la funcin objetivo que se desea optimizar es de nuevo como en
(1.20), pero en "tiempo continuo", i.e.
V (n, x) := E
x
n
|

0
T
e
jt
U( c(t )) dt ,
(1.22)
donde
j > 0
es el factor de descuento.
Ntese que en (1.19) necesariamente se tiene
x
t
0
para todo t, si
x
0
= x > 0 , mientras que en (1.21) la condicin de no-negatividad no es
evidente (por las propiedades del proceso
w( )
); se debe imponer la
condicional adicional x(t ) 0 . Otra forma de asegurar la condicin de no-
negatividad consiste en sustituir el tiempo terminal
T
en (1.22) por el tiempo
aleatorio
t := minT , t
0

donde
t
0
:= inf t 0 / x(t ) = 0
es el primer tiempo en el que el proceso
x( )
llega a cero.
Las aplicaciones del control ptimo a problemas de finanzas se iniciaron con los
trabajos de Samuelson (1969) y Merton (1969) para problemas a tiempo
discreto y tiempo continuo, respectivamente. Actualmente, dichas aplicaciones
son
material estndar; ver e.g. Fieming y Rishel (1975), Fieming y Soner (1992),
Sethi y Thompson (2000), Karatzas y Shreve (1998), Zariphopoulou (2002).
Procesos de Markov
Para motivar la definicin de "proceso de Markov", considrese la ecuacin
diferencial ordinaria, en

n
,
x(t ) = F( x(t )) t 0, con x(0) = x
0
(1.23)
(La funcin
F
podra depender del tiempo
t.
) Bajo ciertas hiptesis sobre
F
,
esta ecuacin tiene una solucin nica
x( s) = x
0
+

0
s
F ( x(r)) dr s 0.
Adems, para
t s 0
tenemos
x(t ) = x
0
+

s
t
F ( x(r )) dr.
(1.24)
Interpretando a
s
como el "tiempo presente" y a
t > s
como el "tiempo futuro",
la ecuacin (1.24) dice que el estado presente
x( s)
determina el futuro
x(t )
; o
bien, que dado el estado presente
x( s)
, el futuro
x(t )
es independiente del
pasado
x( r)
, para
r s.
Por este motivo se dice que (1.24) es una condicin
de causalidad (el presente determina el futuro); tambin se dice que el
sistema determinstico x(.) no tiene memoria o que satisface la condicin de
Markov (tambin llamada propiedad de Markov).
Para procesos estocsticos la condicin de Markov se expresa de manera
similar a (1.24). Por ejemplo, si
x. = x
t
, t 0
es un proceso estocstico a
tiempo continuo, con valores en algn espacio de estados X, se dice que
x.
satisface la condicin de Markov o que
x.
es un proceso de Markov si para
todo conjunto
BX
y tiempos
t s 0
se tiene
P( x
t
B / x
r
0 r s) = P( x
t
B / X
s
). (1.25)
En particular, comparando esta expresin con (1.24) vemos que el sistema
determinstico x(.) es un proceso de Markov. Los procesos de Markov incluyen
las soluciones de ecuaciones diferenciales estocsticas
dx
t
= F ( x
t
) dt + c( x
t
) dW
t
,
(1.26)
bajo ciertas hiptesis sobre los coeficientes
F
y
c
, los cuales pueden depender
tambin del tiempo
t
, no solo del estado
x
t (vea (1.2)). Otros ejemplos son las
cadenas de Markov (cuyo espacio de estados es un conjunto numerable), los
procesos de Levy, ...
Para un proceso estocstico a tiempo discreto,
x. = x
t
, t = 0,1,.
con espacio
de estados X, la propiedad de Markov se puede escribir como:
P( x
t +1
B / x
0
,., x
t
) = P( x
t +1
B / x
t
)
(1.27)
para todo
t = 0,1,.
y
BC
. Esta es una probabilidad de transicin en un paso,
de
t
a
t + 1
, pero se puede demostrar que es equivalente a una condicin en
k
pasos, de
t
a
t + k
, para
k = 1,2,.
Un proceso de Markov a tiempo discreto tambin se conoce como cadena de
Markov.
En muchsimas aplicaciones, una cadena de Markov
x. = x
t
, t = 0,1,.
se
define mediante una ecuacin de diferencias
x
t +1
= F( x
t
, (
t
) t = , 1,.; x
0
dado ,
(1.28)
donde
(
t

es una sucesin de variables aleatorias independientes, con valores

en algn conjunto
S
, e independientes del estado inicial
x
0
,
y
F : X S - X es una funcin dada. Por ejemplo, un proceso muy comn
es el proceso autoregresivo de primer orden definido por
x
t +1
= G( x
t
) + (
t
,
(1.29)
tambin conocido como proceso con "ruido aditivo". Un caso especial son
los sistemas lineales
X
t +1
= I x
t
+ (
t
con
X = S =
n
y
I
una matriz cuadrada de orden
n.
Procesos de control markovianos: tiempo discreto
Sea
x. = x
t
, t = 0,1,.
un proceso controlado con valores es un espacio
X
.
Por analoga con la propiedad de Markov (1.27), se dice que
x.
es un proceso
de control markoviano (PCM) si para cualquier estrategia
n = a
t
, t = 0,1,.
y cualquier
t = 0,1,.,
la distribucin de
x.
en el tiempo
t +1
, dada toda la
"historia del proceso hasta el tiempo
t
" depende slo del estado y la accin en
el tiempo
t
, es decir
Prob( x
t+1
B / x
0
, a
0
,., x
t
, a
t
) = Prob( x
t +1 b / X
t
, a
t
)
:= Q( B/ X
t
, a
t
)
(1.30)
para todo
B X
. La funcin
Q
en (1.31), i.e.
Q( B/ x , a) := Prob( x
t+1
B / X
t
= x , a
t
= a)
(1.31)
se llama la ley de transicin del PCM.
Por ejemplo, supngase que tenemos variables aleatorias i.i.d. como en (1.28),
(
t
independientes de
x
0
. Para cualquier estrategia dada
n = a
t

, definimos el
proceso
x.
n
= x
t

como
x
t +1
= G( x
t
, a
t
,(
t
) t = 0,1,.; x
0
dado ,
(1.32)
donde
G : X A S - X
es una funcin dada (compare con (1.28)).
Entonces
x.
es un PCM y su ley de transicin
Q
se puede calcular mediante la
distribucin comn de las vv.aa.
(
t
. Ntese tambin que si
n
es una estrategia
markoviana (por ejemplo como en (1.5) (1.6)), entonces
x.
es una cadena de
Markov. En efecto, si
a
t
= g( x
t
)
para todo
t = 0,1,.,
entonces (1.32) resulta
x
t +1
= G( x
t
, g( x
t
) ,(
t
) t = 0,1,.,
(1.33)
de modo que
x.
es precisamente de la forma (1.28).
Observe que el sistema lineal (1.7) y el modelo de inversin y consumo (1.19)
son ambos PCMs, porque son de la forma (1.32).
Un hecho muy importante es que un PCM se puede describir de manera
concisa mediante un modelo de control (MC) markoviano
MC := ( X , A, Q , c) ,
(1.34)
donde
X
es el espacio de estados del PCM, A es el conjunto de acciones,
Q
es la
ley de transicin (en (1.31)), y
c : X A -
es la funcin de costo por
etapa que se usa para definir la funcin objetivo de inters, como en (1.10)
(1.12). Algunas veces es necesario aadir componentes al modelo de control.
Por ejemplo, si consideramos un costo terminal
C
T
( x)
como es (1.12), quizs
convendra reescribir (1.34) como
MC = ( X , A, Q , c , C
T
).
Si adems hay restricciones en los controles como en (1.3), entonces
escribiramos
MC = ( X , A, A( x)/ x X ,Q , c , C
t
) .
En fin, el modelo de control markoviano se puede adaptar a cada problema
particular que se est analizando.
Procesos de control markovianos: tiempo continuo
Sea
x. = x
t
, 0 t T
un proceso controlado, el cual depende por supuesto
de la estrategia particular
n = a
t
, 0 t T
que se est usando. Decimos
que
x.
es un proceso de control markoviano (PCM) a tiempo continuo si
cuando
n
es una estrategia markoviana, el proceso
x.
resulta ser proceso de
Markov. (Esta definicin es una extensin de la idea que usamos en (2.3.4).)
Un PCM a tiempo continuo tambin se puede representar mediante un modelo
de control (MC) markoviano, pero el asunto es un poco ms complicado que a
tiempo discreto porque, en lugar de la ley de transicin
Q
en (1.34), debemos
especificar el generador infinitesimal
L
a
(a A)
del PCM, es decir, en lugar
de (1.34) ahora tenemos
MC = ( X , A, L
a
, c) ,
(1.35)
donde
L
a
es un operador definido sobre algn conjunto adecuado de funciones.
Por ejemplo, el sistema determinstico (2.2) es un PCM porque si
n = a
t

es
una estrategia markoviana, digamos
a
t
= g(t , x
t
)
, entonces (2.2) se reduce a
una ecuacin diferencial ordinaria
x
t
= F (t , x
t
, g (t , x
t
)) G(t , x
t
).
En este caso el generador infinitesimal asociado a (2.2) es el operador
L
a
v( x) := F (t , x , a) v
x
(1.36)
definido para cierta subfamilia de funciones
v( x)
de clase C
1.
Anlogamente, la ecuacin diferencial estocstica (1.2) tambin define un PCM
- bajo hiptesis adecuadas sobre
F (t , x , a) , c(t , x , a) y a
t
- y el generador
L
a
resulta ser
L
a
v( x) := F (t , x , a) v
x
+
1
2
Tr| d ( t , x , a)V
xx
, (1.37)
donde
D := cc' , v
xx
es la matriz hessiana de
v
, y
Tr (b) := 2
i
b
ii
es la traza de
una matriz
B = (b
ij
)
. Explcitamente,
Tr( D v
xx
) = 2
ij
(2
k
c
ik
c
kj
) v
xixj
(1.38)
cuando el coeficiente
c
en (1.2) es una matriz, digamos
c = (c
ij
)
. Por
supuesto, en el caso escalar (1.38) se reduce a
c
2

2
v / x
2.
Nota bibliogrfica. Para problemas de control a tiempo discreto el lector
puede consultar (por ejemplo): Arkin y Evstigneev (1987), Bertsekas (1987,
2000), HernndezLerma y Lasserre (1996, 1999), Stokey y Lucas (1989). Para
problemas a tiempo continuo: Fieming y Rishel (1975), Fieming y Soner (1992),
HernndezLerma (1994), Sethi y Thompson (2000), Yong y Zhou (1999).
2. EL PRINCIPIO DEL MXIMO
Hay varias tcnicas generales para estudiar PCOs como son el anlisis convexo
y la programacin lineal (usualmente en espacios vectoriales de dimensin
infinita). Sin embargo, por razones computacionales, en la mayora de las
aplicaciones las tcnicas ms usadas son el principio del mximo (que algunos
autores llaman el principio de Pontryagin) y la programacin dinmica. En esta
seccin veremos brevemente la primera de estas tcnicas; la segunda se
estudia en la siguiente seccin.
Para simplificar la exposicin slo consideraremos problemas determinsticos
con horizonte finito, a tiempo discreto y a tiempo continuo. Al final de la
seccin se mencionan algunas referencias sobre problemas estocsticos.
Problemas a tiempo discreto.
Considrese el PCO determinstico con espacio de estados
X =
n
, espacio de
acciones
A =
m
, y modelo dinmico
x
t +1
= F(t , x
t
, a
t
) T = 0,1, ., T 1
(2.1)
con estado inicial
x
o
= x
. La funcin objetivo que se desea minimizar es el
costo total
V (n , x) =

t=0
T1
L(t , x
t
, a
t
) + C ( x
r
) ,
(2.2)
sobre el conjunto de estrategias
n = a
t

.
A grandes rasgos, la idea del principio del mximo consiste en usar el mtodo
de multiplicadores de Lagrange para minimizar (2.2) sujeto a la "restriccin"
(2.1). Para este fin, primero expresamos (2.1) en la forma
x
t +1
F(t , x
t
, a
t
) = 0 t = 0,1,.,T 1.
Despus introducimos "multiplicadores de Lagrange"
p
0
, p
1
, ., p
T
en
n
, a los
que llamaremos vectores adjuntos (tambin llamados vectores de co-estado), y
definimos el "lagrangiano"

V (n, x , p.) := V (n, X ) +

t=0
T1
P
t+1
| x
t+1
F (t , x
t
, a
t
) ,
(2.3)
donde
p. = p
0
,., p
T

. Por lo tanto, sustituyendo (3.2) en (3.3) y usando el

hamiltoniano, definido para cada
t = 0,1,., T 1
como
H (t , x
t
, a
t
, p
t +1
) := p
t +1
F(t , x
t
, a
t
) L(t , x
t
, a
t
) ,
(2.4)
un poco de lgebra elemental nos permite reescribir (2.3) como

V (n, x , p.) =

t =0
T1
| p
t
x
t
H(t , x
t
, a
t
, p
t+1
) + c( x
T
) + p
T
x
T
p
0
x
0
.
Finalmente, bajo la siguiente hiptesis y usando resultados de optimizacin no-
lineal se obtiene el Teorema 3.2 (cuya demostracin se puede ver en Haikin
(1966), Tabak y Kuo (1971) o Sethi y Thompson (2000)).
Hiptesis 2.1.
(a) Para cada
t = 0,1,., T 1
, las funciones de costo
L(t , x , a)
y
C( x)
son de
clase
C
1
en
x
y
a
;
(b) Para cada
t = 0,1,., T 1
y
a A
,la funcin
F (t , x , a)
es de clase
C
1
en
x ;
(c) Para cada
t = 0,1,., T 1
y x
n
, el conjunto
F(t , x , a) : a A
es
convexo.
Teorema 2.2. (El principio del mximo - caso determinstico, tiempo
discreto). Suponga que se cumple la Hiptesis 2.1. Supngase tambin que
existe una estrategia ptima
a
.

= a
t

, t = 0,., T 1
para el PCO (2.1)-
(2.2), y sea
x
.

= x
t

, t = 0,., T 1
la trayectoria correspondiente que se
obtiene de (2.1) con estado inicial
x
0

= x
0
. Entonces existe un conjunto
p. = p
0
,., p
T
de vectores adjuntos que satisfacen la ecuacin adjunta
p
t
= H
x
(t , x
t

, a
t

, p
t +1
) t = 0,., T1,
(2.5)
i.e.
p
t
= F
x
(t , x
t

, a
t

) p
t +1
L
x
(t , x
t

, a
t

) ,
con la condicin terminal
P
T
= Cx( x
t

) ,
(2.6)
y la maximizacin del hamiltoniano:
H (t , x
t

, a
t

, p
t +1
) = max
aA
H (t , x
t

, a , p
t+1
)
(2.7)
para
t = 0,., T 1.
El nombre "principio del mximo" para el Teorema 2.2 viene precisamente de
la condicin (2.7).
Nota 2.3. El Teorema 3.2 da condiciones necesarias de optimalidad, a saber,
la existencia de la sucesin
p.
de vectores adjuntos que satisfacen (2.5), (2.6) y
(2.7).
Bajo hiptesis adecuadas estas condiciones tambin son suficientes. De hecho,
si tales condiciones se satisfacen, entonces la bsqueda de un "par ptimo"
(a
.

, x
.

)
se reduce a resolver un problema con valores de frontera que
consiste de
(a) las ecuaciones (2.1) y (2.5), que tambin se conocen como las ecuaciones
cannicas del PCO;
(b) las condiciones de frontera (3.6) y
x
0

= x
0
; y
(c) la maximizacin del hamiltoniano, es decir, encontrar
a
.

tal que
H (t , x
t

, a , p
t +1
) = max
aA
H(t , x
t

, a , p
t +1
).
Este procedimiento slo asegura, en general, la existencia de estrategias
ptimas de lazo abierto (ver (1.4)). En contraste, el mtodo de programacin
dinmica que veremos en la siguiente seccin necesariamente da estrategias
markovianas (como en (1.5)).
Ejemplo 2.4: Sistema LQ determinstico a tiempo discreto. Considrese
el
problema de encontrar una estrategia de control que minimize la funcin de
costo
V (n, x) =
1
2

t =0
T1
(Q x
t
2
+ Ra
t
2
) +
1
2
S x
T
2
,
(2.8)
con
n = a
t

, sujeta a
x
t +1
= o x
t
+ a
t
t = 0,1, .,T 1; x
0
= x.
(2.9)
Las constantes
Q
y
S
en (2.8) son no-negativas y
R
es positiva, mientras que los
coeficientes
o
y

en (2.9) son distintos de cero. El espacio de estados y el de

acciones son
X = A =
(Exactamente el mismo anlisis que presentamos a
continuacin se puede extender a un problema vectorial con
X =
n
y A =
m
,
en cuyo caso los coeficientes en (2.8) y (2.9) son
matrices de dimensiones adecuadas. Adems, dichos coeficientes pueden
variar con el parmetro de tiempo:
(Q
t
, R
t
, S
T
,
t
.)
Comparando (2.8)-(2.9) con (2.1)-(2.2) vemos que el hamiltoniano en (2.4)
resulta
H (t , x
t
, a
t
, p
t +1
) = (o x
t
+ a
t
) p
t +1

1
2
(Q x
t
2
+ Ra
t
2
).
Luego, como
H
x
= oP
t +1
x
t
y H
a
= P
t+1
Ra
t
,
el problema con valores de frontera mencionado en la Nota 2.3 resulta:
(a) Ecuaciones cannicas: para
t = 0,1,., T 1,
x
t +1
= o x
t
+ a
t
, P
t
= o p
t+1
Qa
t
.
(2.10)
(b) Condiciones de frontera:
x
0
= x , p
T
= S x
T
.
(c) Maximizacin del hamiltoniano: de la igualdad
H
a
= 0
obtenemos.
a
t
= R
1
P
t +1
t = 0,., T 1.
(2.11)
Como la segunda derivada parcial
H
aa
= R
es negativa, se puede demostrar
que los controles en (2.11) dan una estrategia ptima, aunque por supuesto
an falta calcular los vectores adjuntos
p
t
Con este fin, sustituimos (2.11) en
(2.10):
x
t +1
= o x
t
+ R
1

2
p
t+1
, p
t
= oP
t +1
Q x
t
(2.12)
y combinando estas ecuaciones vemos que necesariamente
p
t
es de la forma
p
t
= K
t
x
t
t = 0, ., T ,
(2.13)
donde
K
0
,., k
t
son constantes. En efecto, la condicin de frontera
p
T
= S x
T
implica que
K
T
= S
. Asimismo, de la segunda ecuacin en (2.12) tenemos
p
T1
= oP
T
Q x
T1
y usando la primera ecuacin en (2.12) podemos escribir
p
t
en funcin de
x
T1
.
En general, para obtener
k
t
procedemos como sigue.
Sustituyendo (2.13) en (2.12) obtenemos
P
t
= | o
2
RK
t +1
/ ( R
2
K
t+1
) Q x
t
De la primera de estas ecuaciones despejamos
x
t +1
y sustituimos su valor en la
segunda ecuacin. As se obtiene que
P
t
= | o
2
RK
t +1
/ ( R
2
K
t+1
) Q x
t
y comparando con (2.13) vemos que las constantes
K
t
satisfacen que
K
t
= o
2
RK
t+1
/( R
2
K
t +1
) Q t = 0,1,., T 1,
(2.14)
con condicin terminal
K
T
= S
bajo la hiptesis de que S R/
2
. La
ecuacin (3.14) es un caso especial de la llamada ecuacin de Riccati y se
resuelve "hacia atrs": empezando con
K
T
= S
, se calculan
k
T1
, K
T2
,., K
0
.
Conociendo el valor de los vectores adjuntos
p
t
podemos determinar los
controles ptimos y la correspondiente trayectoria y la funcin de costo
mnimo. Por ejemplo, sustituyendo (3.13) en (3.11) obtenemos
a
t
= R
1
K
t+1
x
t+1
= R
1
K
t +1
(o x
t
+ a
t
)
[por (2.9)]
y despejando
a
t
obtenemos los controles ptimos:
a
t

= G
t
x
t
t = 0,., T 1,
con
G
t
:= o K
t +1
/( R
2
K
t+1
).
.
Problemas a tiempo continuo.
Sea
A| 0, T
el conjunto de todas las funciones medibles
a( ) : | 0, T - A
. El
conjunto
A| 0, T
es esencialmente la familia de las estrategias de lazo abierto
definidas sobre el intervalo
| 0,T
.
Ahora consideraremos el PCO que consiste en minimizar el costo
J (a( )) :=

0
T
L(t , x(t ) , a(t )) dt + C( x(T ))
(2.15)
sobre todas las estrategias
a( ) A| 0, T
, sujetas a que
x(t ) = f (t , x(t ) , a(t )) 0 t T , x(0) = x
0
.
(2.16)
Supondremos que el espacio de estados y el conjunto de acciones son
X =
n
y A =
m.
Por supuesto, para que (2.8) y (2.9) estn bien definidas se requieren hiptesis
adecuadas de medibilidad, de Lipschitz, etc., que se pueden ver en, por
ejemplo, los libros de Fleming y Rishel (1975) o de Yong y Zhou (1999). Un
tratamiento un tanto informal del principio del mximo, pero con un buen
nmero de aplicaciones, se puede ver en Sethi y Thompson (2000). Aqu slo
enunciaremos el resultado principal, que requiere la siguiente notacin y
terminologa.
Si a(.) es una funcin en
A| 0, T
y
x( )
es la correspondiente solucin de (3.9)
se dice que
( x( ) , a( ))
es un par admisible. Adems, si
a

( )
es una
estrategia ptima y
x

( )
es la solucin de (3.9), decimos que
( x

( ) , a

( )) es un par ptimo. Dado un par admisible
( x( ) , a( ))
y una
funcin
P( ) : | 0, T -
n
, que llamaremos una (funcin o) variable
adjunta, definimos el hamiltoniano
H (t , x(t ) , a(t ) , p(t )) := p(t )F(t , X (t ) , a(t )) L(t , x(t ) , a(t )) .
(2.17)
(Compare esta definicin con (2.4).) Con esta notacin, el anlogo de las
condiciones necesarias (2.5)(2.7) resulta como sigue.
Teorema 2.5. (El principio del mximo - caso determinstico, tiempo
continuo). Supngase que existe un par ptimo para el PCO (2.8)-(2.9).
Entonces, bajo ciertas hiptesis sobre las funciones
F (t , x , a) , L(t , x , a) y C( x)
, existe una variable adjunta
P( ) : | 0, T -
n
que satisface la ecuacin
adjunta
p(t ) = H
x
(t , x

(t ) , a

(t ) , p(t ))
= F
x
(t , x

(t ) , a

(t ) , p(t )) + L
x
(t , x

(t ) , a

(t ) , p(t ))
(2.18)
con condicin terminal
P(T ) = C
x
( x

(T )) ,
(2.19)
y la maximizacin del hamiltoniano:
H (t , x

(t ) , a

(t ) , p(t )) = max
aA
H(t , x

(t ) , a

(t ) , p(t )).
(2.20)
Las ecuaciones (2.11) y (2.12) se cumplen "para casi todo"
t |0, T .
.
La Nota 2.3 (para problemas a tiempo discreto) tambin es vlida en el caso
continuo, con algunos cambios obvios de notacin.
Ejemplo 2.6: un problema de control de inventario-produccin.
Considrese un problema de control cuyos componentes son, en cada tiempo
0 t T :
:
la variable de estado
x(t ) :=
el nivel de inventario
la variable de control
a(t ) :=
la tasa de produccin
la variable exgena
s (t ) :=
la tasa de ventas.
Adems, hay dos valores de referencia, un nivel de inventario de seguridad i y
un nivel eficiente de produccin
El nivel de inventario van-a de acuerdo a la ecuacin diferencial
x(t ) = a(t ) s(t ) para t 0, x(0) = x
0
.
(2.21)
Las estrategias de control son funciones medibles
a(t )
, no-negativas. El PCO
consiste en encontrar una estrategia que minimiza la funcin objetivo.
x(t ) = a(t ) s(t ) para t 0, x(0) = x
0
.
(2.22)
donde
x = x(t ) y a = a(t ) ; h > 0
es el costo de mantenimiento y
c > 0
el
costo de produccin. La interpretacin de (3.22) es que el controlador desea
mantener el nivel de inventario
x( )
y la tasa de produccin
a( )
lo ms
cerca posible de los valores de referencia
x y a
, respectivamente. (A
problemas de este tipo se les llama problemas de seguimiento o de rastreo,
porque el estado y los controles deben seguir o rastrear lo ms cerca
posible a los valores
x , a.
)
Comparando (2.21)(2.22) con (2.15)(2.16) vemos que el hamiltoniano (en
(2.17)) resulta ser
H (t , x(t ) , a(t ) , P(t )) = p(t ) (a(t ) s(t ))
1
2
| h ( x(t ) x)
2
+ c (a a)
2
.
Luego, como
H
x
= h ( x(t ) x) y H
a
= p(t ) c codt (a(t ) a) ,
obtenemos el siguiente problema con valores de frontera:
(a) Las ecuaciones cannicas
x(t ) = a(t ) s(t ) ,
(2.23)
p(t ) = h ( x(t ) x);
(2.24)
(b) las condiciones de frontera:
x(0) = x
0
, p(T ) = 0 ;
(c) maximizacin del hamiltoniano; haciendo
H
a
= 0
vemos que
a(t ) = p(t )/ c + a.
(2.25)
Como
H
aa
= c 0
, la funcin
a( )
en (2.23) es en efecto la estrategia
ptima del problema (2.21)(2.22), pero an falta calcular la variable adjunta
p( )
.Con
esto en mente, sustituimos (2.25) en (2.23) para obtener
x(t ) = P(t )/ c + a s(t ) , x(0) = x
0
.
(2.26)
Para resolver las ecuaciones (2.24) y (2.26), primero derivamos (2.26) y as
obtenemos una ecuacin con
p
, es decir,

x(t ) = p(t )/ c s (t ).
Ahora sustituimos (2.24) en esta ltima ecuacin para obtener
x(t ) = o
2
( x(t ) x) s(t ) , con o := . h/ c ;
equivalentemente
x(t ) = o
2
x(t ) = o
2
x s(t ).
(2.27)
La solucin general de esta ecuacin es de la forma
x(t ) = o
2
x(t ) = o
2
x s(t ).
(2.28)
donde
Q(t )
es cualquier solucin particular de (2.27). (La funcin
Q
se puede
determinar si se conoce la forma explcita de
s(t )
.) Como en (3.28) hay slo
una condicin inicial, para determinar las constantes
a
1
, a
2
,
sustituimos (2.28)
en (2.26) y esto da que la variable adjunta
p(t )
satisface:
p(t ) = c(oa
1
e
ot
+oa
2
e
ot
+

Q(t ) S (t ) a) ,
(2.29)
con condicin terminal
p(T ) = 0
. Las ecuaciones (2.28) y (2.29), con sus
respectivas condiciones de frontera, dan un sistema de dos ecuaciones
algebraicas que permiten determinar los valores de
a
1
, a
2
. Habiendo
determinado estos valores se obtiene la forma explcita del control ptimo en
(2.25). (Ntese que no impusimos la condicin a(t ) 0; si la tasa de
produccin
a(t )
es negativa, significa que debemos eliminar o desechar
inventario.)
El caso estocstico.
Para sistemas estocsticos a tiempo continuo, y salvo contadas excepciones, el
principio del mximo se ha desarrollado principalmente para ecuaciones
diferenciales estocsticas, como en (2.3). Una buena referencia para este caso,
con una extensa bibliografa, es el libro de Yong y Zhou (1999). Una extensin
del principio del mximo ha permitido a Josa-Fombellida y Rincn-Zapatero
(2005) proponer un nuevo enfoque para problemas de control estocstico. Un
enfoque similar ha sido estudiado por Bourdache-Siguerdidjane y Fliess (1987)
para problemas determinsticos y por Rincn-Zapatero (2004) y Rincn-
Zapatero et al. (1998) para juegos diferenciales.
Curiosamente, para sistemas estocsticos a tiempo discreto hay poqusimas
referencias, entre las que cabe mencionar el libro de Arkin y Evstigneev (1983).
3 Programacin dinmica
Como se mencion en la Nota 2.3, para encontrar una estrategia ptima el
principio del mximo se reduce esencialmente a resolver un problema con
valores de frontera. Esto requiere determinar una estrategia ptima
simultneamente con las otras variables (la trayectoria y los vectores adjuntos)
en el problema. Un enfoque alternativo consiste en descomponer el PCO en
"etapas", cada una correspondiente a un subproblema con una sola variable,
de modo que el PCO se resuelve en forma secuencial, por etapas. Esta es la
idea del mtodo de programacin dinmica que veremos en esta seccin.
Primero consideraremos PCOs a tiempo discreto y despus a tiempo continuo.
La programacin dinmica fue introducida por Richard Bellman en la dcada de
los aos 1950 vea el libro de Bellman (1956), por ejemplo.
Problemas a tiempo discreto.
Consideraremos de nuevo el PCO determinstico en (1.1)-(1.2) pero por
conveniencia notacional escribiremos las variables
x
t
y a
t
como x(t ) y a(t )
,
respectivamente. As pues, tenemos el modelo dinmico
x(t +1) = F (t , x(t ) , a(t )) t = 0,., T 1, x(0) = x
0
,
(3.1)
con funcin objetivo
V (n , X ) :=

t =0
T1
L(t , x(t ) , a(t )) + C ( x(T )) ,
(3.2)
donde
n = a(t )
. El espacio de estados es X =
n
y el de acciones de control
es un conjunto cerrado
A
m
.
La programacin dinmica se basa en el siguiente "principio de optimalidad"
que introdujo Bellman, y cuya demostracin es evidente.
Lema 3.1. (El principio de optimalidad) Sea
a

( )=a

(0) ,., a

(T 1)
una estrategia ptima para el problema (3.1)-(3.2), y sea
x

( )=x

( 0) ,., x

(T )
trayectoria correspondiente; en particular,
x

(0) = x
0
. . Entonces para cualquier tiempo
s 0,., T1
, la estrategia
"truncada"
a

(t )
para
s t T1
, es la estrategia ptima que lleva el
sistema (4.1) del punto
x

( s)
al punto
x

(T )
.
Para ver como se usa el Lema 4.1, consideremos el PCO (4.1)(4.2) pero slo
del tiempo s en adelante (con
0 s T 1
), con estado "inicial"
x( s) = x
,
es decir, sea
V (n, s , x) :=

t =s
T1
L(t , x(t ) , a(t )) + C( x(T ))
(3.3)
y sea
v( s , x)
el correspondiente costo mnimo, i.e.
v( s , x) := inf
n
V (n, s , x).
(3.4)
Adems, como en el tiempo terminal
T
no se aplican acciones de control,
definimos
v(T , x) := C ( x) .
(3.5)
Luego, si en el Lema 3.1 interpretamos
s y x

(s) = x
como el tiempo y el
estado iniciales, se sigue de (3.3) y (3.4) que
v( s , x) = V ( a

( ) , s , x)
=

t=s
T1
L(t , x

, a

+ C( x

))
= L( s , x , a

( s)) + V ( a

( ) , s + 1, x

( s + 1))
= L( s , x , a

( s)) + v( s + 1, x

( s + 1))
Por lo tanto, como
x

( s+1) = F( s , x

, a

( s)) = F( s , x , a

( s))
, obtenemos
v( s , x) = L( s , x , a

( s)) + v( s + 1, F( s , x , a

(s)))
(3.6)
Pero, por la definicin (3.4),
v( s , x)
es el costo mnimo de operar el sistema del
tiempo
s
al tiempo
T
, de modo que
V ( s , x) L( s , x , a) + v (s + 1, F (s , x , a)) a A.
(3.7)
Finalmente, combinando (3.6) y (3.7) vemos que
v( s , x) = min
aA
| L( s , x , a) + v( s + 1, F ( s , x , a)) s = 0,., T1.
(3.8)
y que el mnimo en el lado derecho de (3.8) se alcanza en
a

( s)
, como en
(3.6).
La ecuacin (3.8) con la "condicin terminal" (3.5) se llama la ecuacin de
programacin dinmica (EPD), o ecuacin de Bellman, y es la base del
"algoritmo de programacin dinmica" (3.9)-(3.10) en el siguiente teorema
Teorema 3.2. (El teorema de programacin dinmica) Sean
J
0
, J
1
,., J
T
las funciones sobre
X
definidas "hacia atrs"
(de S = T a s = 0)
como
J
T
( x) := C( x) ,
(3.9)
y para
s = T1, T2,.,0,
J
s
( x) := min
a
| L( s , x , a) + J
s+1
( F (s , x , a)).
(3.10)
Suponga que para cada
s = 0,1,.,T 1
, existe una funcin
a
s

: X - A
que alcanza el mnimo en el lado derecho de (3.10) para todo
x X
. Entonces
la estrategia markoviana
n

= a
0

.., a
T1

es ptima y la funcin de valor

coincide con
J
0
, i.e.
inf
n
V (n, X ) = V (n

, x) = J
0
( x) x X.
(3.11)
De hecho, para cada
s = 0,., T , J
s
coincide con la funcin en (3.4)-(3.5), i.e.
v( s , x) = J
s
( x) 0 s T , x X
(3.12)
Es importante observar que (3.12) significa que algoritmo (3.9)-(3.10) da el
costo ptimo (o costo mnimo) del PCO (3.1)-(3.2) con tiempo y estado inicial
0sT1 y x (s)=x ,
respectivamente.
Consideremos ahora el sistema estocstico en el que (3.1) y (3.2) se
sustituyen por
x(t + 1) = F (t , x(t ) , a(t ). ((t )) t =0, .,T
1,
con x(0) = x ,
(3.13)
V (n , x) := E|

t =0
T1
L(t , x(t ) , a(t )) + C( x(t )) ,
(3.14)
con
n = a(t )
, y las "perturbaciones"
((0) ,., ((T 1)
en (3.13) son
variables aleatorias independientes e idnticamente distribuidas (i.i.d.) con
valores en algn espacio S . Resulta entonces que, con algunos cambios
adecuados, prcticamente todo lo que aparece en los prrafos anteriores sigue
siendo vlido. Ms precisamente, en las expresiones en las que aparece la
funcin
F
[a saber, (3.6)-(3.8) y (3.10)] debemos escribir
F ( s , x , a , (( s))
en lugar
de F ( s , x , a); adems, se debe tomar la esperanza en las expresiones donde
aparezcan trminos estocsticos, o sea, en el lado derecho de (3.3), (3.6)-(3.8),
y (3.10). Para ms detalles, vea el Ejemplo 3.4.
Nota 3.3. Una demostracin detallada del teorema de programacin dinmica
en el caso estocstico a tiempo discreto aparece en HernndezLerma y
Lasserre (1996), Seccin 3.2. Otras demostraciones, as como un buen nmero
de ejemplos y aplicaciones, aparecen en Arkin y Evstigneev (1987), Bertsekas
(1987), Le Van y Dana (2003), Luque-Vsquez et al. (1996), Stokey y Lucas
(1989), ...
Para ilustrar el algoritmo de programacin dinmica, a continuacin veremos
una versin estocstica del sistema LQ en el Ejemplo 3.4.
Ejemplo 3.4: Sistema LQ estocstico a tiempo discreto. Considere el
sistema lineal
x
t +1
= o x
t
+ a
t
+ (
t
t = 0,1,.; x
0
dado,
con coeficientes
o ,
distintos de cero. Las perturbaciones
(
t son variables
aleatorias i.i.d., independientes de
x
0
, y con media
0
y varianza c
2
finita, i.e.
E((
t
) = 0, c
2
:= E ((
t
2
) t = 0,., T 1.
(3.15)
Los espacios de estados y de acciones son X = A = setr. Se desea minimizar
la funcin de costo
v(n, x) := E|

t =0
T1
(qx
t
2
+ ra
t
2
) + q
t
x
T
2
x
0
= x ,
donde
r > 0 y q , q
r
0.
En este caso, la ecuacin de programacin dinmica (3.9)-(3.10) resulta
J
t
( x) := q
T
x
2
(3.16)
y para
s = T 1, T 2,., 0;
J
s
( x) := min
a
| qx
2
+ ra
2
+ EJ
s+1
(o x + a + +(
s
) .
(3.17)
Esta ecuacin se resuelve "hacia atrs": sustituyendo (3.16) en (3.17)
obtenemos
J
T1
( x) = min
a
| qx
2
+ ra
2
+ q
r
E(o x + a + (
T1
2
)
donde, usando (3.15),
E(o x + a + (
T1
)
2
= (o x + a)
2
+ c
2
Luego,
J
t1
( x) = min
a
|(q + q
T
o
2
) x
2
+ ( r + q
T

2
)a
2
+ 2q
T
o xa + q
T
c
2
.
El lado derecho de esta ecuacin se minimiza en
a
T1

( x) = K
T1
x , con G
T1
:= ( r + q
T

2
)
1
q
T
o
y el mnimo es
J
T1
( x) = K
T1
x
2
+ q
T
c
2.
con K
T1
:= (r + q
T

2
)
1
q
T
r c
2
+ q.
En general, es fcil ver que la estrategia ptima
n

=a
0

,., a
T1

est dada
por
a
s

( x) = G
s
x , con G
s
:= (r K
s+1

2
)
1
K
s+1
o,
(3.18)
con "ganancias"
K
s
dadas recursivamente por
K
T
:= q
T y para
s = T1,., 0;
K
s
= (r + K
s+1

2
)
1
K
2+1
r c
2
+ q.
Asimismo, el costo ptimo del tiempo
s
en adelante, en (3.12), resulta
J
s
( x) = K
s
x
2
+ c
2

n=s+1
T
K
n
para s = 0,., T 1.
(3.19)
En particular, con
s = 0
se obtiene el costo mnimo en (3.11).
Nota. Es interesante comparar el problema LQ estocstico en el ejemplo
anterior con el problema LQ determinstico en el Ejemplo 2.4: se puede ver que
en ambos casos la estrategia ptima est dada por (3.18). Sin embargo,
difieren en el costo mnimo; la diferencia est en que, en el caso
determinstico, la varianza
c
2
que aparece en (4.19) es cero.
Para referencia futura, a continuacin veremos brevemente el caso de costo
descontado con horizonte infinito. Considrese el PCO que consiste del
sistema estocstico.
x
t +1
= F( x
t
, a
t
, (
t
) t = 0,1,.; con x
0
= x ,
(3.20)
con funcin objetivo
V (n, x) := E|

t=0

o
t
c( x
t
, a
t
, (
y
)
(3.21)
en donde
c( x , a , ()
es la funcin de costo por etapa, y
o (0,1)
es el factor de
descuento. Como siempre,
X y A
representan el espacio de estados y de
acciones, respectivamente. Asimismo, denotaremos por
A( x)
el conjunto de
acciones factibles en el estado
x ;
; vase (1.3). El PCO (3.15)-(3.16) es
estacionario en el sentido de que las funciones
F ( x , a ,()
y
c( x , a ,()
no
dependen del tiempo
t
y, adems,
(
0
, (
1
,.
son variables aleatorias i.i.d. cuya
distribucin de probabilidad la denotaremos por
j
, es decir
j( B) := Prob| (
0
B B S ,
(3.22)
donde
S
es el "espacio de perturbaciones", o sea el conjunto en el que toman
valores las variables
(
t
Considrese la funcin de valor
v( x) := inf
n
V (n, x)
y la sucesin de funciones
v
n
, definidas iterativamente como
v
n
( x) = inf
aA(x)
E| c( x , a ,(
0
) + ov
n1
( F ( x , a ,(
0
))
= inf
aA( x)

S
| c( x , a , s) + ov
n1
( F( x , a , s)) j(ds)
,
(4.23)
para
n = 1,2,., con v
0
( x) 0.
Con esta notacin, se tiene el siguiente
resultado bajo una variedad de hiptesis (vanse las referencias en la Nota 4.3,
o la seccin 8.3 en HernndezLerma y Lasserre (1999)).
Teorema 3.5. Bajo hiptesis adecuadas:
(a) la funcin de valor v satisface la ecuacin de programacin dinmica
V ( x) = inf
aA( x)
s
| c( x , a , s) + ov ( F( x , a , s)) j(ds) x X.
(3.24)
(b) Supngase que existe una funcin
g : X - A
tal que
g( x) A( x) y g( x)
minimiza el lado derecho de (3.24) para todo
X X
, i.e.
v( x) =

s
| c( x , g( x) , s) + ov( F( x , g( x) , s)) j(ds).
Entonces g define una estrategia markoviana estacionaria (recurdese (1.6))
que es ptima para el PCO (3.20)-(3.22).
(c) Cuando
N - , v
n
( x) - v( x)
para todo
X X
. (Las funciones
V
n
definidas en (3.23), se llaman funciones de iteracin de valores.)
La parte (c) del Teorema 3.5 se usa para aproximar la funcin
v( x)
o para
deducir propiedades de ella.
Problemas a tiempo continuo
Consideremos el PCO (3.1)-(3.2) pero en tiempo continuo, es decir
x(t ) = F( t , x(t ) , a(t )) t | 0, T , x(0) = x ,
(3.25)
V (n , x) :=

0
T
L(t , x(t ) , a(t )) dt + C( x(T )) ,
con
n = a( ).
Asimismo, como en (3.3)-(3.5), para cada estado
s |0, T
y
"estado inicial"
X (s) = x ,
, definimos
V (n , s , x) :=

s
T
L(t , x(t ) , a(t )) dt + C( x(T ))
y
v( s , x) := inf
n
V (n, s , x) para 0 s T , v(T , x) := C( x).
En este caso, el principio de optimalidad es completamente anlogo al caso de
tiempo discreto (Lema 4.1), y el teorema de programacin dinmica es como
sigue.
Teorema 3.6 Bajo ciertas hiptesis sobre las funciones
F , C , L
y el conjunto
A
,
y suponiendo que
v( s , x)
es de clase
C
1,1
(|0, T
n
) , v
es solucin de la
ecuacin de programacin dinmica
V
s
+inf
aA
| F (s , x , a)V
x
+ L( s , x , a) = 0 ( s , x)(0,T )
n
,
(3.26)
con condicin de frontera
v(T , x) = C( x)
. Si adems
g( s , x)
es una funcin
que alcanza el mnimo en (3.21), entonces
a

( s) := g ( s , x( s)) s | 0,T
es una estrategia ptima, i.e.
v( s , x) = V (a

( ) , s , x).
Para PCOs a tiempo continuo (determinsticos o estocsticos) la ecuacin de
programacin dinmica, como (3.26), tambin se conoce como ecuacin de
HamiltonJacobiBeliman.
Usando el hamiltoniano
H ( s , x , a , p)
en (2.10) podemos expresar (3.26) como
V
s
s up
aA
H (a , x , a ,v
x
) = 0.
Esto establece un vnculo entre la programacin dinmica y el principio del
mximo.
La demostracin del Teorema 4.6 se puede ver en, por ejemplo, Fieming y
Rishel (1975), Fieming y Soner (1992), Yong y Zhou (1999). Estos libros
estudian el control de ecuaciones diferenciales ordinarias (como en (3.25)) y
estocsticas (como en (1.2)). Otros sistemas estocsticos a tiempo continuo
incluyen las cadenas de Markov - ver, por ejemplo, Guo y Hernndez-Lerma
(2003a) o Prieto-Rumeau y Hernndez-Lerma (2005a). Aunque es costumbre
estudiar cada uno de estos sistemas por separado, es posible hacer estudios
unificados que incluyen prcticamente cualquier tipo de proceso de control
markoviano (PCM) a tiempo continuo, como en (1.35)-(1.37); ver Hernndez-
Lerma (1994), Prieto-Rumeau y Hernndez-Lerma (2005a) y sus referencias,
donde en particular podemos ver lo siguiente.
Nota 3.7. Usando el generador infinitesimal (2.36) podemos expresar la
ecuacin de programacin dinmica (3.26) como
V
s
+inf
aA
| L v( s , x) + L( s , x , a) = 0 ( s , x) (0, T )
n.
(3.27)
De hecho, expresada de esta manera usando el generador infinitesimal del
PCM la ecuacin (3.27) resulta ser la ecuacin de programacin dinmica
para cualquier PCM a tiempo continuo, con horizonte finito
T
. Por ejemplo, si en
lugar del sistema determinstico (3.25) consideramos la ecuacin diferencial
estocstica (1.2), entonces el generador
L
a
en (3.27) seria el operador en
(1.37). Asimismo, si el PCM es un proceso markoviano de saltos con espacio de
estados numerable y "tasas de transicin"
q
xy
(a)
, entonces tomando
S = 0
en
(3.27) el generador L
a
resulta
L
a
v( x) :=

yX
q
xy
(a)v( y).
Para ms detalles, vea las referencias mencionadas en el prrafo anterior.