Discounted Profits Problem utilizando Programação Dinâmica

Question

O problema abaixo faz referência à seção 2.9 (páginas 58-59) do livro Lew, A., & Mauch, H. (2006). Dynamic programming: A computational tool (Vol. 38). Springer.

O problema dos lucros descontados (DPP) é um problema intertemporal de otimização que pode ser resolvido por programação dinâmica.

Assuma que nos seja dado um lago com população inicial de peixes igual a \( b_1 \), no começo do ano 1. A população no começo do ano \( t \) é denotada por \( b_t \). Ao vender \( x_t \) peixes no ano \( t \), uma receita \( r(x_t) \) é auferida. O custo de se pescar os peixes é dado pela função \( c(x_t,b_t) \), que depende do número de peixes que se deseja pescar e da quantidade deles ainda existente no lago. Os peixes se reproduzem a uma taxa anual constante. O horizonte de planejamento finito se estende de \( 1 \) a \( T \), período sobre o qual incide uma taxa de juros \( y \). A variável de decisão \( x_t \) denota o número de peixes a ser pescado e vendido no ano \( t \). O objetivo é maximizar o lucro líquido (em unidades monetárias do ano 1) que pode ser ganho durante os anos \( 1,...,T \) do horizonte de planejamento. Tipicamente, esse tipo de problema de decisão possui um tradeoff entre benefícios correntes e benefícios futuros.

Um estado nesse modelo de programação dinâmica é um par \( (t,b) \) representado pelo ano corrente t e a população de peixes no lago no começo de tal ano. A equação funcional de programação dinâmica se torna então:

\[ f(t,b) = \left\{ \begin{array}{lcl}\{\max_{\{ x_t \varepsilon \{0,...,b\}} \{r(x_t) - c(x_t,b) + \\ \quad \quad \quad \quad \quad \quad + \frac{1}{1+y} f(t+1,[s(b - x_t)]\} & \mbox{if} & {t \ \lt \ T} \\ 0 & \mbox{if} & {t = T+1} \end{array}\right\} \]

O problema consiste em discutir uma implementação em Python.

Answer 1

Programação Dinâmica

Existem algumas formas de resolvermos o problema de programação dinâmica descrito acima. Podemos categorizá-lo como um problema determinístico de horizonte finito. King (2002) e Ljungqvist & Sargent (2018) são referências úteis para economistas. A descrição do problema é simples e envolve a escolha de uma sequência finita de controles \( \{ u_t \}_{t=0 }^{T} \) que maximiza o seguinte problema intertemporal:

\[ \sum_{t=0}^{T} \beta^{t} r \ (x_t,u_t) \quad (2) \]

em que \( \beta \) é um fator de desconto intertemporal, \( r(.) \) é uma função côncava e \( x_t \) é uma variável de estado. O problema está sujeito a uma regra de movimento do estado no tempo, dado por uma função \( G(.) \):

\[ x_{t+1}=g(x_t,u_t ) \quad (3) \]

A programação dinâmica procura uma função política \( h(.) \) invariante no tempo que mapeia o estado \( x_t \) no controle \( u_t \) de forma a encontrar uma sequência \( \{u_t \}_{t=0}^{T} \) que parta de uma condição inicial \( x_0 \) em \( t=0 \) e resolva o problema original, sujeito a (3). Para encontrar a função política \( h(.) \), nós precisamos de outra função \( V(x) \) que expresse o valor ótimo do problema original partindo de um uma condição inicial arbitrária \( x \ \varepsilon \ X \). Essa função é chamada de função valor:

\[ V(x_0) = \max_{\{u_{s}\}_{s=0}^{T}} \ \sum_{t=0}^{T} \ \beta^{t} r(x_t,u_t) \quad (4) \\ \textrm{Sujeito a:} \\ i)x_{t+1} = g(x_t,u_t) \\ ii)x_0 = \overline{x} \ \textrm{dado} \]

Para resolvê-lo, consideramos um sub-problema, idêntico ao primeiro, porém começando em \( s_0>0 \):

\[ V(x_0) = \max_{\{u_{s}\}_{s_{0}}^{T}} \ \sum_{t=0}^{T} \ \beta^{t} r(x_t,u_t) \quad (5) \]

Sendo \( V(x_{t_0},T-t_0) \) a solução do problema (5), o princípio da otimalidade de Bellman nos garantirá que qualquer solução do problema (4) (isto é, no intervalo de \( 0,…,T \)) que nos dará o valor ótimo em \( t_0 \) igual a \( x_{t_0} \), deverá resolver o problema (5) no intervalo \( t_0,…,T \). Fazendo analogia ao exemplo dado em sala de aula, se quisermos sair de um ponto A e chegar em C passando por B, o melhor caminho de A até B será utilizado também no melhor caminho de A até C. Na verdade, esse resultado depende da separabilidade de tempo aditivo, de forma que podemos “quebrar” o problema maior em problemas maiores. O princípio da otimalidade de Bellman nos permite definir \( t_0 \) de forma arbitrária em \( T-1 \) e resolver o problema simples com dois períodos de tempo. A solução desse problema, é então levada recursivamente para os demais períodos. Em cada etapa, basta resolvermos:

\[ V(x_t) = \max_{u_t} \{r(x_t,u_t\} \ + \ \beta V(x_{t+1}) \quad (6) \]

O que – ao se substituir a restrição – torna-se:

\[ V(x_t) = \max_{u_t} \{r(x_t,u_t\} \ + \ \beta V(g(x_t,u_t)) \quad (7) \]

Em que a solução nos dá uma função política \( u_t=h(x_t) \), que nos retorna a solução ótima \( u_t \) a partir do valor do estado \( x_t \). Quando \( t=0 \), o estado será dado, o que nos permitirá encontrar \( u_0 \). Com \( u_0 \) e \( x_o \), encontramos o estado \( x_1 \). Esse processo segue até que se resolva todo o problema.

Answer 2

Solução Analítica

Podemos reescrever o problema original do livro de Lew e Mauch como:

\[ \max_{x_t \varepsilon \{0,...,b_t\}} \ \sum_{t=0}^{T=1} \left[ \frac{1}{1+y} \right] \ [r(x_t) - c(x_t)] \quad (8) \\ \textrm{Sujeito a:} \\ i) \ b_{t+1}=s(b_t - x_t)\\ ii) \ b_0, \ s, \ y \ \textrm{dados.} \]

Note que i) é a nossa versão de (3) – muitas vezes chamadas de equações de transição. Ela nos diz como será o estado no próximo período dado o quanto pescamos de peixe no estado anterior (aqui, o estado é dado pelo par ano, população de peixes no lago). Note também que \( \beta \) – o desconto intertemporal – assume a forma \( \frac{1}{1+y} \), em que \( y \) é uma taxa de juros igual a 0,05. Além disso, \( r(x_t )=3x_t, c(x_t )=2x_t, s=2 \) e \( b_0=10 \).

Resolvendo para \( t = 1 \):

\[ V(b_1) = \ \max_{x_t \varepsilon \{0,...,b_1\}} \left[ \frac{1}{1+y} \right]^{1} \ [r(x_1) - c(x_1)] \ + \ V(b_2) \quad (9) \\ \]

Como o problema vai somente até \( t=1 \), temos \( V(b_2 )=0 \). Substituindo isso e as funções receita e custo:

\[ V(b_1) = \ \max_{x_t \varepsilon \{0,...,b_1\}} \left[ \frac{1}{1+y} \right] \ x_1 \quad (10) \]

Como a função é de primeiro grau e \( \frac{1}{1+y}>0 \), a solução será o valor máximo que pudermos atribuir a \( x_1 \), ou seja, \( x_1=b_1 \). O que é intuitivo, pois no último período devemos sempre pescar e vender os peixes restantes. Deixar peixes no lago em um problema de horizonte finito em que a função objetivo é estritamente crescente no número de peixes vendidos seria sub-ótimo. Substituindo a restrição:

\[ V(b_1) = \left[ \frac{1}{1+y} \right] \ s(b_0-x_0) \quad (11) \]

Resolvendo para \( t=0 \):

\[ V(b_0) = \ \max_{x_0 \varepsilon \{0,...,b_0\}} \left[ \frac{1}{1+y} \right]^{0} \ [r(x_0) - c(x_0)] \ + \ V(b_1) \quad (12) \\ \]

\[ V(b_0) = \ \max_{x_0 \varepsilon \{0,...,b_0\}} \left[ \frac{1}{1+y} \right]^{0} \ [r(x_0) - c(x_0)] \ + \ \left[ \frac{1}{1+y} \right] s(b_0 - x_0) \\ (13) \\ \]

Note que temos um problema somente em \( x_0 \). Os demais valores são conhecidos.

\[ V(b_0) = \ \max_{x_0 \varepsilon \{0,...,b_0\}} \Big\{x_0 + \ \left[ \frac{1}{1+y} \right] s(b_0 - x_0) \Big\} \quad (14) \\ \]

\[ V(b_0) = \ \max_{x_0 \varepsilon \{0,...,b_0\}} \Big\{\left[1 - \ \frac{s}{1+y} \right]x_0 + \left[ \frac{s}{1+y} \right]b_0 \Big\} \quad (15) \\ \]

Para maximizar o termo de primeiro grau \( \left[1 - \ \frac{s}{1+y} \right]x_0 \) no intervalo \( \{0,…,b_0 \} \), precisamos estudar o sinal do coeficiente de \( x_0 \). Tal termo será positivo sempre que \( 1+y>s \). No nosso exemplo, isso não é válido (\( y=0,05 \) e \( s=2 \)). Assim, o \(x_0 \) que maximiza a função é 0. Substituindo todos os valores temos a seguinte solução:

\[ x_0=0 \\ x_1=b_1=20 \\ V(b_1) \cong 19,05 \]

Assim, pescamos todos os peixes no segundo (e último) período. Devido ao fator de desconto, nossa receita de 20 é trazida a valor presente e vale 19,05 em unidades monetárias do período 0. A intuição é simples: o aumento anual da população de peixes faz com que valha a pena esperar para pescar mais, ainda que exista uma taxa de desconto monetária que faz com que a receita seja menor quando trazida a valor presente.

Note que para cada subproblema, temos uma função de primeiro grau. Assim, a solução de cada subproblema está nos extremos do intervalo que \( x \) pode assumir, sendo eles \( 0 \) (não se pesca nada) ou \( b \) (pesca tudo). Porém dado que se pesca tudo em \( t \), o lago ficará vazio nos demais períodos subsequentes. Essa solução será ótima quando o fator de desconto for muito alto, de forma que compense a taxa de crescimento do lago, dada por \( s \). No caso particular em que \( 1+y=s \), qualquer solução é ótima, mantendo-se a restrição de que no último período devemos pescar e vender o restante da população de peixes. Esse caso equivale a um cenário em que não temos inflação e o lago não cresce. Pescar tudo agora ou depois não muda o resultado. Nesse caso, o problema deixa de ser de escolha intertemporal.

Answer 3

Implementação em Python

Há dois conceitos básicos para a implementação em Python, que estão inclusive muito relacionados. O primeiro deles é a própria intuição da programação dinâmica – de que a solução do problema para \( [0,…,T] \) é a mesma para \( [T-1,T] \). O segundo é a ideia de recursão, pois, como visto acima, não precisamos passar por todos os períodos já que ela transforma o problema original com \( T \) escolhas em um problema com somente uma escolha \( x_0 \). Note que um problema de programação dinâmica nada mais que é uma otimização baseada em recursão.

A implementação desse problema é do tipo bottom-up. Nessa solução, partimos do estado no período 0 e usamos as regras de transição para chegar aos estados nos períodos mais posteriores. Dado que estamos no período final e temos aqueles estado, o problema para o período final é resolvido e tal solução é usada para encontrar as dos demais períodos. Note que o único momento em que temos que iterar sobre possíveis escolhas é no período 0.

Comentários mais específicos encontram-se no final do código:

def revenue(x):
    rev = 3*x
    return rev
def cost(x):
    c = 2*x
    return c

# PARÂMETROS #
##############
s=2
y=0.05
##############
def dpp(bt,T,t=0,decisions=None,values=None,maximum=float()):
    if decisions is None:
        decisions = {}
    if values is None:
        values = {}
    if t==T-1:
        value_functionT = (revenue(bt)-cost(bt))*(1/(1+y)**t)
        decisions[t]=int(bt)
        return (value_functionT, bt)
    else:
        for xt in range(int(bt+1)):
                if t > 0:
                    decisions[t]=xt
                    value_functiont = (revenue(xt)-cost(xt))*(1/(1+y))**t + dpp(s*(bt-xt),T,t+1,decisions)[0]
                    return (value_functiont,bt)
                else:
                    value_functiont = (revenue(xt)-cost(xt))*(1/(1+y))**t + dpp(s*(bt-xt),T,t+1,decisions)[0]
                    values[xt] = value_functiont
                    if values[xt]>maximum:
                        decisions[t]=xt
                        maximum=values[xt]
                        optimal_dec = decisions.copy()
        #return values
        return maximum, bt, optimal_dec 

if __name__ == '__main__':            
    dpp(10,2)
# Comentários sobre a função dpp:
# A função é chamada declarando-se o tamanho da população inicial (bt) e o número de 
# períodos (T).
# As demais entratadas são argumentos default e serão utilizadas na estrutura recursiva.
# t=0 sinaliza que a função começará no tempo t=0.
# 'decisions' é um dicionário que memorizará o vetor de variáveis de controle, isto é, as 
# decisões de quanto se pescar
# a cada período. As keys do dicionário são os períodos t=0,...,T.
# 'values' é outro dicionário que memorizará o lucro auferido para cada escolha possível 
# de pesca em t=0 (a nossa resposta
# é o valor mais alto desse dicionário).
# 'maximum' é um objeto em formato de número real que será utilizado em 
# comparações e a cada loop será atualizado para 
# armazenar o valor máximo obtido até então.  

Referências

King, I. (2002). A simple introduction to dynamic programming in macroeconomic models.

Ljungqvist, L., & Sargent, T. J. (2018). Recursive macroeconomic theory. MIT press.

Comments

Olá, Lucas. Tua resposta ficou muito completa, principalmente com a exposição sobre programação dinâmica de modo mais amplo. A solução analítica do problema também ajuda pois permite comparar se de fato o código produz a mesma resposta para o problema. Em relação à implementação em python, está muito bem explicada e consegui reproduzir a solução sem problemas. Uma sugestão que eu faria é colocar "s" e "y" como parâmetros da função "dpp", evitando assim o uso de variáveis globais. Sugiro algo como "dpp(bt,T,t=0,decisions=None,values=None,maximum=float(), s=2, y=0.05)" na definição da função.