Dual Dynamic Programming with cut selection: convergence proof and numerical experiments
Abstract: We consider convex optimization problems formulated using dynamic programming equations. Such problems can be solved using the Dual Dynamic Programming algorithm combined with the Level 1 cut selection strategy or the Territory algorithm to select the most relevant Benders cuts. We propose a limited memory variant of Level 1 and show the convergence of DDP combined with the Territory algorithm, Level 1 or its variant for nonlinear optimization problems. In the special case of linear programs, we show convergence in a finite number of iterations. Numerical simulations illustrate the interest of our variant and show that it can be much quicker than a simplex algorithm on some large instances of portfolio selection and inventory problems.
Keywords: Dynamic Programming ; Nonlinear programming; Decomposition algorithms; Dual Dynamic Programming; Pruning methods
Category 1: Convex and Nonsmooth Optimization
Category 2: Other Topics (Dynamic Programming )
Citation: V. Guigues, Dual Dynamic Programing with cut selection: Convergence proof and numerical experiments, European Journal of Operational Research, 258 (1): 47-57, 2017.
Entry Submitted: 05/24/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|