This paper considers robust dynamic optimization problems, where the unknown parameters are modeled as uncertainty sets. We seek to bridge two classical paradigms for solving such problems, namely (1) Dynamic Programming (DP), and (2) policies parameterized in model uncertainties (also known as decision rules), obtained by solving tractable convex optimization problems. We provide a set of unifying conditions (based on the interplay between the convexity and supermodularity of the DP value functions, and the lattice structure of the uncertainty sets) that, taken together, guarantee the optimality of the class of affine decision rules. We also derive conditions under which such affine rules can be obtained by optimizing simple (e.g., linear) objective functions over the uncertainty sets. Our results suggest new modeling paradigms for dynamic robust optimization, and our proofs, which bring together ideas from three areas of optimization typically studied separately (robust optimization, combinatorial optimization – the theory of lattice programming and supermodularity, and global optimization – the theory of concave envelopes), may be of independent interest. We exemplify our findings in an application concerning the design of flexible contracts in a two-echelon supply chain, where the optimal contractual pre-commitments and the optimal ordering quantities can be found by solving a single linear program of small size.
Citation
Submitted for publication.