O problemaO Modelo de Bertsimas e Lo
MAC 5796. Aula 17
Walter Mascarenhas
01/06/2011
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Resumo
1 O problema
2 O Modelo de Bertsimas e Lo
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Problema:
Minimizar o custo esperado ao comprar Q contratos em T períodos
minE
(T
∑t=1
utqt
)
sujeito aT
∑t=1
qt = Q.
qt é a quantidade comprada no instante t,
ut é o preço unitário pago nesta compra,
Q é a quantidade total a ser comprada.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
O Modelo de Bertsimas e Lo
Custos de execução dependentes do volume.
O preço de compra depende da quantidade comprada.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Modelo geral, não linear.
No instante t:
ut = f (pt ,qt)
⎧⎨⎩pt = preco de mercado,qt = quantidade comprada,ut = preco unitario de compra.
pt+1 = g(ut ,εt) εt = choque aleatorio,
E(εt) = 0,
σ2(εt) = σ
2ε .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Linearização:
ut = pt + θqt ,
pt+1 = g(p,0)+∂g∂u
(p,0)(ut −p)+∂g∂ε
(p,0)εt = p +a (ut −p)+εt ,
onde:
θ =∂ f∂q
(p,0), a =∂g∂u
(p,0) e normalizamos∂g∂ε
(p,0) = 1.
Assumiremos p = 0. Isso não altera a minimização do preço totalda compra ∑utqt sujeito a ∑qt = Q = constante:
∑utqt = ∑(ut −p) +p∑qt = ∑(ut −p)qt + cte.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
A evolução de p fica então
pt+1 = a (pt + θqt) + εt
e pode ser escrita assim
p1 = p1,
pt = a (pt−1 + θqt−1) + εt−1 para 2≤ t ≤ T .
Esta é a essência do modelo de Bertsimas e Lo.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Em termos matriciais o modelo de Berstimas e Lo é
p = p1e1 +S(ap+aθq+ ε) ,
onde e1 é o vetor (1,0,0, . . . ,0)′ e S é a matriz T ×T de shift:
S =
⎛⎜⎜⎜⎜⎜⎝0 0 . . . 0 01 0 . . . 0 00 1 . . . 0 0...
.... . . . . .
...0 0 1 0
⎞⎟⎟⎟⎟⎟⎠ .
Lembre-se sempre que T é o número de períodos.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Para entender a expressão envolvendo matrizes e vetores para p,
p = p1e1 +S(ap+aθq+ ε) ,
é bom ilustrá-la no caso T = 3:⎛⎝ p1
p2p3
⎞⎠= p1
⎛⎝ 100
⎞⎠+
⎛⎝ 0 0 01 0 00 1 0
⎞⎠⎛⎝a
⎛⎝ p1p2p3
⎞⎠+aθ
⎛⎝ q1q2q3
⎞⎠+
⎛⎝ ε1ε2ε3
⎞⎠⎞⎠
Multiplicando a matriz pelos vetores obtemos⎛⎝ p1
p2p3
⎞⎠=
⎛⎝ p1ap1 +aθp1 + ε1ap2 +aθp2 + ε2
⎞⎠ ,
o que confere com a equação de evolução do preço.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
A representação matricial é interessante porque leva a
(I−aS)p = p1e1 +S(aθq+ ε)
e daqui é fácil encontrar p:
p = (I−aS)−1 (p1e1 +S(aθq+ ε)),
pois ST = 0 (a matrix S é nil potente) e
(I −aS)−1 =∞
∑i=0
aiSi =T−1
∑i=0
aiSi .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
S =
⎛⎜⎜⎝0 0 0 01 0 0 00 1 0 00 0 1 0
⎞⎟⎟⎠⇒ S2 =
⎛⎜⎜⎝0 0 0 00 0 0 01 0 0 00 1 0 0
⎞⎟⎟⎠
⇒ S3 =
⎛⎜⎜⎝0 0 0 00 0 0 00 0 0 01 0 0 0
⎞⎟⎟⎠⇒ S4 =
⎛⎜⎜⎝0 0 0 00 0 0 00 0 0 00 0 0 0
⎞⎟⎟⎠ .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Formulação vetorial
Lembrando que u = p+ θq, temos
minq∈RT
E(q′ (p+ θq)
)sujeito a 1′q = Q.
onde 1 ∈RT é o vetor (1,1, . . . ,1)′. Como
p = (I−aS)−1 (p1e1 +S(aθq+ ε))
o problema se torna
minq∈RT
E(q′ (I−aS)−1 (p1e1 +S(aθq+ ε)
)+ θq′q
)sujeito a 1′q = Q.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Resolução do Modelo
Solução estática: o vetor q é escolhido no começo do período.A estratégia leva em conta apenas a informação disponívelneste momento. A cada passo a estratégia é recalculada.Programação dinâmica, ou princípio de Bellman. A soluçãoconsidera a evolução das esperanças condicionais com achegada de novas informações. Esta é a solução proposta porBertsimas e Lo.
Neste caso particular, os dois métodos são equivalentes. Em geralprogramação dinâmica descreve corretamente a solução ótima, mascostuma ser impraticável. Já a solução estática pode não ser ótima,mas é prática e pode dar boas aproximações do ótimo.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Método estático
Como E(ε) = 0 e os demais termos são determinísticos temos
minq∈RT
q′Aq+b′q,
sujeito a 1′q = Q,
para A = aθ (I−aS)−1 S+ θ I,
e b = p1 (I−aS)−1 e1.
A solução desse problema é encontrada pelo método de Lagrange,ou seja, devemos resolver o sistema(
A+A′)q+b = λ1,
1′q = Q.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Em termos matriciais isso é escrito como(−(A+A′) 1
1′ 0
)(qλ
)=
(bQ
)
Resolvendo este sistema encontramos o vetor q, no qual qtrepresenta as quantidades comprada no instante t.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Quando a = 1 a evolução do preço fica
pt+1 = pt + θqt + εt .
e quando não há impacto de preço, θ = 0, os preços seguem umpasseio aleatório. Por isto chamaremos este caso de passeioaleatório.
Deduziremos agora a política estática ótima para este caso segundoo modelo de Bertsimas e Lo.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Em particular, quando a = 1 (passeio aleatório) temos
A = θ (I−S)−1 S+ θ I
e
(I−S)−1 =T−1
∑t=0
St =
⎛⎜⎜⎜⎜⎜⎝1 0 0 . . . 01 1 0 . . . 01 1 1 . . . 0...
......
. . ....
1 1 1 1 1
⎞⎟⎟⎟⎟⎟⎠ .
Exemplo para T = 3:⎛⎝ 1 0 00 1 00 0 1
⎞⎠+
⎛⎝ 0 0 01 0 00 1 0
⎞⎠+
⎛⎝ 0 0 00 0 01 0 0
⎞⎠=
⎛⎝ 1 0 01 1 01 1 1
⎞⎠ .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Continuando, para a = 1,
A = θ (I−S)−1 S+ θ I
e
(I−S)−1S =
⎛⎜⎜⎜⎜⎜⎝1 0 0 . . . 01 1 0 . . . 01 1 1 . . . 0...
......
. . ....
1 1 1 1 1
⎞⎟⎟⎟⎟⎟⎠
⎛⎜⎜⎜⎜⎜⎝0 0 0 . . . 01 0 0 . . . 00 1 0 . . . 0...
......
. . ....
0 0 0 1 0
⎞⎟⎟⎟⎟⎟⎠
=
⎛⎜⎜⎜⎜⎜⎝0 0 0 . . . 01 0 0 . . . 01 1 0 . . . 0...
......
. . ....
1 1 1 1 0
⎞⎟⎟⎟⎟⎟⎠⇒ A = θ
⎛⎜⎜⎜⎜⎜⎝1 0 0 . . . 01 1 0 . . . 01 1 1 . . . 0...
......
. . ....
1 1 1 1 1
⎞⎟⎟⎟⎟⎟⎠ .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Logo, para a = 1,
A+A′ = θ
⎛⎜⎜⎜⎜⎜⎝1 1 1 . . . 11 1 1 . . . 11 1 1 . . . 1...
......
. . ....
1 1 1 1 1
⎞⎟⎟⎟⎟⎟⎠+ θ I = θ(11′+ I
)
Além disso,
b = p1 (I−S)−1 e1 = p1
⎛⎜⎜⎜⎜⎜⎝1 0 0 . . . 01 1 0 . . . 01 1 1 . . . 0...
......
. . ....
1 1 1 1 1
⎞⎟⎟⎟⎟⎟⎠
⎛⎜⎜⎜⎜⎜⎝100...0
⎞⎟⎟⎟⎟⎟⎠= p1
⎛⎜⎜⎜⎜⎜⎝111...1
⎞⎟⎟⎟⎟⎟⎠= p11.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
O problema matricial no caso a = 1 é então(−θ (11′+ I) 1
1′ 0
)(qλ
)=
(p11Q
).
Como 1′1 = T , este sistema tem solução
q =QT
1 e λ = p1 +θQT
(T +1) .
Ou seja, quando a = 1 (passeio aleatório) a solução ótima consisteem distribuir as compras igualmente nos T instantes.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Na análise estática, a função objetivo é
E(q′ (p+ θq)
),
ondep = (I−aS)−1
(p1e1 +S(aθq+ ε)
).
Nesta abordagem a variabilidade do resultado é descrita por
s = q′ (I−aS)−1 Sε = v′ε,
ondev = S′
(I−aS′
)−1 q.
Analisaremos agora a variância de s.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Como vimos, a variabilidade do gasto é descrita por
s = q′ (I−aS)−1 Sε = v′ε
Como ε tem média zero,
E(s) = 0.
Logo, a variância de s é
σ2(s) = E
((v′ε)2)
= E((
v′ε)(
v′ε))
= E(v′εε
′v)
= v′Σv,
ondeΣ = εε
′
é a matriz de covariância de ε . Por exemplo, se ε ∼ N(0,σ2
ε I)
entãoσ
2(s) = σ2ε q′ (I−aS)−1 SS′
(I−aS′
)−1 q.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Poderíamos então considerar o problema de minimizar o gastoesperado sujeito à uma limitação na variância deste gasto. Ou seja,teríamos o problema (determinístico)
minq∈RT
q′Aq+b′q,
sujeito a 1′q = Q,
e q′Vq≤ τ,
para V = (I−aS)−1 SΣS′(I−aS′
)−1.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Há duas situações:
1) q′Vq < τ e 2) q′Vq = τ.
A primeira é como no caso no qual desconsideramos a variância.
A segunda tem condições de Lagrange
1′q = Q,
q′Vq = τ,
(A+A′)q+b+ λ1+ µVq = 0,µ ≥ 0 e λ irrestrito
d′(A+A′+ µV
)d≥ 0 ∀ d com q′Vd = 1′d = 0.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
1′q = Q e q′Vq = τ,
(A+A′)q+b+ λ1+ µVq = 0, µ ≥ 0 e λ irrestrito
d′(A+A′+ µV
)d≥ 0 ∀ d com q′Vd = 1′d = 0.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Este problema não tem solução fechada, mesmo para o caso a = 1.Ele teria que ser resolvido numericamente. Poderíamos entãoconsiderar restrições adicionais, como q≥ 0.
Do ponto de vista numérico o problema é relativamente simplespois é estritamente convexo. Isto garante que há um, e só um,valor ótimo e há algoritmos eficientes para encontrá-lo.
Resolvendo este problema para vários τ ’s podemos traçar a curvade risco × retorno para este modelo: quanto maior o τ menor ocusto esperado da compra, mas maior a sua variância.
O método do R. Almgren é uma variação disto, levando em contaum modelo um pouco diferente para o impacto no preço.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Há um detalhe importante porém:
No caso de otimização com restrições de desigualdade a solução doproblema estático NÃO É ÓTIMA. Ou seja, a curva risco × custodescrita no slide anterior é só uma aproximação.
Se realmente quisermos descrever esta curva então será necessáriousar programação dinâmica (e arcar com o custo computacionalexorbitante.)
Este é o próximo assunto.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
O princípio de Bellman:
Se as compras q1, . . . ,qT determinam o modo ótimo decomprar Q contratos nos instantes 1, . . . ,T então, paratodo k = 1, . . . ,T −1 as compras qk+1, . . . ,qTdeterminam o modo ótimo de comprar
rk = Q−k
∑t=1
qt
contratos nos instantes (k +1), . . . ,T.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
O princípio de Bellman
-
6
T
Q t
T −1
∑T−1t=1 qt t
T −2
∑T−2t=1 qt t
k
∑kt=1 qt t
rk =Q−∑kt=1 qt
t
Tempo
Quantidade
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
O princípio de Bellman é usado de trás para frente, do passo T atéo passo 1. Começamos determinando como atingir nosso objetivode comprar Q contratos assumindo que no passo T o preço vigenteé p e nos resta comprar r contratos.
Neste caso não há opção: devemos comprar
qT = r
contratos e o gasto esperado com isso será
CT (p, r) = E((p + θ r)r) = (p + θ r)r .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Uma vez obtido CT (p, r) determinamos indutivamente aquantidade qk que devemos comprar no passo k de modo aminimizar o custo esperado Ck(p, r) de compra de r contratos se opreço vigente no passo k for p.
Para determinarmos qk e Ck(p, r) para k < T é conveniente usar
ck (p, r ,q,ε) = minqk+⋅⋅⋅+qT=r
E
(T
∑t=k
(pt + θqt)qt ∣qk = q,pk = p,εk = ε
)
Em palavras, ck(p, r ,q,ε) é o melhor resultado possível dado queno passo k o preço é p, restam r unidades a comprar, compramos qe o choque aleatório é ε .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
A definição
ck (p, r ,q,ε) = minqk+⋅⋅⋅+qT=r
E
(T
∑t=k
(pt + θqt)qt ∣qk = q,pk = p,εk = ε
)
implica queCk (p, r) = min
q∈RE(ck (p, r ,q,ε) ;ε)
e podemos expressar formalmente o princípio de Bellman como
ck (p, r ,q,ε) = (p + θq)q +Ck+1 (a (p + θq) + ε, r −q) .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Informalmente o princípio de Bellman é óbvio (e era conhecido porséculos antes de Bellman...)
A equação
ck (p, r ,q,ε) = (p + θq)q +Ck+1 (a (p + θq) + ε, r −q) .
quer dizer que se estamos no passo k e tomamos a decisão decomprar q então o melhor que poderemos fazer dai para frente éseguir a melhor estratégia para comprar r −q unidades dado que opreço é o novo preço: a (p + θq) + ε .
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Podemos então calcular cT−1:
cT−1 (p, r ,q,ε) = (p + θq)q + (a (p + θq) + ε + θ(r −q))(r −q).
Logo,
E(cT−1 (p, r ,q,ε) ;ε) = (p + θq)q + (a (p + θq) + θ(r −q))(r −q)
e CT−1(p, r) é o mínimo do lado direito da equação acima comrespeito a q.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
E(cT−1 (p, r ,q,ε) ;ε) = (p + θq)q + (a (p + θq) + θ(r −q))(r −q)
Derivando com respeito a q e igualando a 0 obtemos
p +2θq + (aθ −θ)(r −q)− (a (p + θq) + θ(r −q)) = 0
e usando o Mathematica concluímos que
q = qT−1 =(1−a)
2θ (a−2)p +
r2. (1)
Substituindo q por esse valor na expressão por E(cT−1) obtemos
CT−1 (p, r) =14
((a−1)2
(a−2)θp2 +2(a +1)rp + (a +2)θ r2
).
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
As equações anteriores mostram que
qT−1 =1θ
αT−1p + βT−1r ,
CT−1 (p, r) =1θ
δT−1p2 +2γT−1rp + ηT−1θ r2 +0×σ2ε
para
αT−1 =1−a
2(a−2), βT−1 =
12, δT−1 =
(a−1)2
4(a−2),
γT−1 =a +14
, ηT−1 =a +24
.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Assumindo indutivamente que
Ck+1(p, r) = δk+1r2 +2γk+1rp + ηk+1p2 + (T −k−1)σ2ε ,
obtemos
ck (p, r ,q,ε) = (p + θq)q +Ck+1 (a (p + θq) , r −q)
+2(γk+1r + ηk+1p) ε + ε2.
e
E(ck (p, r ,q,ε)) = (p + θq)q +Ck+1 (a (p + θq) , r −q) + σ2ε .
Derivando em q e igualando a 0 obtemos
qk =1θ
αkp + βk r ,
para
αk =2a(γk+1−aδk+1)−1
2(δk+1a2−2γk+1a + ηk+1 +1),
βk =ηk+1−aγk+1
δk+1a2−2γk+1a + ηk+1 +1.
Walter Mascarenhas MAC 5796. Aula 17
O problemaO Modelo de Bertsimas e Lo
Substituindo q por qk chegamos a
Ck(p, r) = δk r2 +2γk rp + ηkp2 + (T −k−1)σ2ε
para
δk =4a(γk+1 +aδk+1ηk+1−aγ2
k+1
)−1
4(δk+1a2−2γk+1a + ηk+1 +1),
γk =ηk+1 +a
(γk+1 +2aδk+1ηk+1−2aγ2
k+1
)2(δk+1a2−2γk+1a + ηk+1 +1)
,
ηk =
(δk+1ηk+1− γ2
k+1
)a2 + ηk+1
δk+1a2−2γk+1a + ηk+1 +1.
Estas expressões são simples quando a = 1. Neste caso
δk = 0, γk = 1/2, e ηk =T −k +12(T −k)
,
αk = 0 e βk =1
T −k +1.
Walter Mascarenhas MAC 5796. Aula 17