dualdynamic

Dualdynamic is a framework for solving sequential decision problems by integrating dual optimization techniques with dynamic programming. It aims to decompose complex multistage decisions into more manageable components while maintaining global feasibility through dual variables.

The approach builds on Lagrangian relaxation: constraints that link stages are dualized, producing a dual objective that depends on multipliers. A dynamic programming process then propagates cost-to-go information backward or forward, using these multipliers to guide stagewise decisions.

During iterations, subproblems at each stage are solved with fixed multipliers, yielding primal policies and local costs. The resulting information is used to update piecewise-affine approximations of the value function, producing cuts that tighten the dual or primal bounds.

Convergence typically requires convexity or convexification of subproblems and appropriate sampling in stochastic settings. In practice, dualdynamic methods are valued for scalability and for producing dual bounds on the optimal value.

Applications span energy planning, such as hydroelectric reservoir management, water resources, and multistage portfolio optimization; the approach is also used in supply chain design and infrastructure planning under uncertainty.

Note that dualdynamic may be used as a general term for related hybrids of dual methods and dynamic programming, and should be distinguished from established formulations such as dual dynamic programming or stochastic dual dynamic programming in specific literatures.