On the Dual Approach to Recursive Optimization

We bring together the theories of duality and dynamic programming. We show that the dual of an additively separable dynamic optimization problem can be recursively decomposed using summaries of past Lagrange multipliers as state variables. Analogous to the Bellman decomposition of the primal problem, we prove equality of values and solution sets for recursive and sequential dual problems. In non-additively separable settings, the equivalence of the recursive and sequential dual is not guaranteed. We relate recursive dual and recursive primal problems. If the Lagrangian associated with a constrained optimization problem admits a saddle then, even in non-additively separable settings, the values of the recursive dual and recursive primal problems are equal. Additionally, the recursive dual method delivers necessary conditions for a primal optimum. If the problem is strictly concave, the recursive dual method delivers necessary and sufficient conditions for a primal optimum. When a saddle exists, states on the optimal dual path are subdifferentials of the primal value function evaluated at states on the optimal primal path and vice versa.