The Dual Approach to Recursive Optimization: Theory and Examples

We bring together the theories of duality and dynamic programming. We show that the dual of a separable dynamic optimization problem can be recursively decomposed. We provide a dual version of the principle of optimality and give conditions under which the dual Bellman operator is a contraction with the optimal dual value function its unique fixed point. We relate primal and dual problems, address computational issues and give examples.