Supermodularity and Affine Policies in Dynamic Robust Optimization
Abstract: 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.
Keywords: robust optimization, affine decision rules, supermodularity, lattice programming, concave envelopes, inventory management
Category 1: Robust Optimization
Category 2: Other Topics (Dynamic Programming )
Category 3: Combinatorial Optimization (Polyhedra )
Citation: Submitted for publication.
Entry Submitted: 06/07/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|