Complexity of Dual Dynamic Programming for Solving Infinite Horizon Optimization Problems Under Uncertainty

We present a family of dual dynamic programming approaches for solving infinite-horizon optimization problems under uncertainty. Applications include inventory management, economic dispatch for power systems, and the celebrated Brazilian hydro-planning problem problems. We present finite-time guarantees for the algorithm to converge to an approximate global solution under various problem regimes and methods, e.g., inexact inner problem solves, as well as supplement these results with numerical experiments. We highlight the capability of these algorithms to utilize parallel systems to efficiently solve large problem instances.