Dual Dynamic Programming with cut selection: convergence proof and numerical experiments

2017/05/24 by Guigues, Vincent
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1705.08941

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.

Related

• Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems
• Inexact cuts in Stochastic Dual Dynamic Programming
• Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments
• Inexact cuts in Deterministic and Stochastic Dual Dynamic Programming\n applied to linear optimization problems
• Regularized Stochastic Dual Dynamic Programming for convex nonlinear optimization problems