Sorger Abordagem Recursiva (5 4)

Prévia do material em texto

Sorger – Abordagem Recursiva (5.4) 
	A abordagem recursiva não requer argumentos variáveis ou premissas interiores e retorna condições ótimas, necessárias e suficientes sem premissas de convexidade, diferente da abordagem de Lagrange e da equação de Euler.
	Retome o problema de otimização dinâmica na forma reduzida da seção 5.1. O espaço de estado é um conjunto arbitrário não-vazio e o conjunto de transições é não-vazio para todo e . Isso nos garante que para todo período inicial e para todo estado inicial , existe, ao menos, uma sequência satisfazendo e . Ou seja, existe ao menos uma trajetória factível para o problema , onde é definido como 
Denotamos o conjunto de todas as trajetórias factíveis do problema por . Além disso, mantemos a premissa de que 
existe para todas as trajetórias factíveis, o que garante que a função objetiva seja um número real bem definido quando . No coração da abordagem recursiva para a otimização dinâmica está a função valor ótimo , definida porDefinição de Supremo: Seja . Um elemento é dito Supremo de se é o mínimo do conjunto de todos os upper bounds.
Definição de Upper Bound: Seja . Um elemento é dito Upper Bound de se 
Definição de Mínimo: Seja . Um elemento é dito mínimo em se .
[Função valor ótimo retorna o supremo do problema de otimização]
a equação de Bellman
Prova – Teorema 5.7:
Tome como uma trajetória factível qualquer para . Note que
[ pode ser escrito como a utilidade do primeiro período , , acrescido de seus valores nos outros períodos, isso é, a partir de , denotado por ]
e que
Assim, temos que 
Note que
Como 
Temos que 
que representa a equação de Bellman. Assim, provamos que as funções de valor ótimo sempre satisfazem a equação de Bellman.
Teorema 5.8 (Suficiência de Bellman e Condição ): suponha que a função satisfaz a equação de Bellman e que a condição é satisfeita para todas as trajetórias factíveis e todo . Assim, temos que é a função valor ótima.
Teorema 5.7 (necessidade de Bellman): A função valor ótimo satisfaz a equação de Bellman.
Prova – Teorema 5.8: tome como uma solução arbitrária da equação de Bellman e tome como uma trajetória factível arbitrária. Assim, temos:
[Essa desigualdade deriva do fato de a função satisfazer a definição de Equação de Bellman: como , assume um valor pelo menos tão grande quanto o supremo da soma ]
Explicitando alguns termos de , temos
Com , essa desigualdade, em conjunto com a condição, implica que
[Observe que e que ]
Como a trajetóra foi escolhida arbitrariamente de , temos que 
	Isso demonstra que é ao menos tão grande quanto o valor ótimo do problema de otimização dinâmica. Para completar a prova, basta mostrarmos que não pode ser estritamente maior que o valor ótimo (precisa ser igual ao supremo). Para isso, suponha, por contradição, que essa essa propriedade é falsa, ou seja, que existe um estado e um número positivo real tal que para toda trajetória factível é verdade que
[Ao adicionar estamos assumindo que vai ser estritamente maior que o supremo, ou seja, é ao menos tão grande quanto o supremo acrescido de um valor real ].
Em particular, é verdade para a trajetória factível , que é construída da seguinte maneira.
Tome como uma sequência de números positivos tal que ela converge para , isso é
Como é solução da equação de Bellman e porque é positiva, existe um tal que
[Estamos mostrando que haverá algum valor que irá ultrapassar . Esse valor será o próprio supremo, ou algum valor próximo dele.]
Tome na desigualdade e combine os resultados de e .
Portanto
Subtraindo de ambos os lados, temos
Podemos repitir esse processo indefinidamente para , e obteremos
Quando , temos que
Isso segue de e e do fato de ser um número finito.
[Note que o fato de ser um número finito ser um número finito implica que os útimos valores da soma são nulos, ou seja, não aumentam o somatório. Assim, quando iniciamos o somatório em , estamos apenas somando zeros, de tal forma que o limite do somatório quando é zero]
 Assim, 
implica em
o que é uma contradição.
Desse lema, segue o Teorema 5.9.Prova – Lema 5.1 – Princípio da Otimalidade: suponha, por com tradição, que não é uma trajetória ótima do problema . Então existe uma trajetória factível tal que 
Considere a trajetória definida por
Essa trajetória é factível pois e são factíveis. Assim, é óbvio que e, portanto
Uma vez que temos , podemos decompor os somatórios, de forma a obter
Disso segue que
Portanto,
Ou seja, 
Isso é uma contradição à otimalidade de para .
[Nessa prova mostramos que se é necessário reavaliar a trajetória em um período futuro, então é melhor fazê-lo no início da trajetória, ao invés de ao longo dele].
Lema 5.1 – Princípio da Otimalidade: Tome como uma trajetória ótima para o problema . Para todo , temos que é uma trajetória ótima para o problema . Ou seja, quando temos uma trajetória ótima até o ponto , se continuarmos a seguir tal trajetória para além de , isso é, , continuamos em uma trajetória ótima. Sucintamente, uma trajetória ótima é ótima em todos os seus pontos.
Teorema 5.10 (Suficiência de Bellman e Condição ): Se é a função valor ótima do peoblema de otimização e se é uma trajetória factível para tal problema e satisfaz a condição , e a Equação de Bellman, , então temos que é uma trajetória ótima.
Prova – Teorema 5.10: Da Equação de Bellman,
temos que, para todo ,
Tomando e utilizando da Condição de Transversalidade, temos que
Assim, 
Uma vez que é a função valor ótima, temos que é uma trajetória ótima do problema .
Prova – Teorema 5.9: Uma vez que é a função valor ótimo e dado que é uma trajetória ótima, temos 
Do princípio da otimalidade, temos que é uma trajetória ótima para tal que
Com essas duas equações provamos o teorema para . Além disso, como é ótima para (Princípio da Otimalidade), podemos repetir todo esse argumento para . Fazendo isso podemos provar que é verdade para todo .
Teorema 5.9 (Se temos função valor ótimo e a trajetória ótima, então Bellman é satisfeito): Se é a função valor ótima do peoblema de otimização e se é uma trajetória ótima, então temos que a equação 
é satisfeita.
[estamos inserindo a equação de Bellman no Princípio da Otimalidade. Se tivermos a função valor ótimo e uma trajetória ótima, então a equação de Bellamn é satisfeita com igualdade em . Isso implica que a trajetória ótima sempre atingirá o supremo.]