Dual dynamic programming with cut selection: convergence proof and numerical experiments
From MaRDI portal
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.
Recommendations
- Inexact cuts in stochastic dual dynamic programming
- Exact converging bounds for stochastic dual dynamic programming via Fenchel duality
- Regularized stochastic dual dynamic programming for convex nonlinear optimization problems
- On the convergence of stochastic dual dynamic programming and related methods
- Stochastic dual dynamic integer programming
Cites work
- Analysis of stochastic dual dynamic programming method
- Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
- Evaluating policies in risk-averse multi-stage stochastic programming
- Improving the performance of stochastic dual dynamic programming
- Lectures on Stochastic Programming
- Multi-stage stochastic optimization applied to energy planning
- On the convergence of stochastic dual dynamic programming and related methods
- Parallel decomposition of multistage stochastic programming problems
- SDDP for multistage stochastic linear programs based on spectral risk measures
- SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
- Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures
- Worst-case-expectation approach to optimization under uncertainty
Cited in
(15)- Stochastic dynamic cutting plane for multistage stochastic convex programs
- Duality and sensitivity analysis of multistage linear stochastic programs
- Exact converging bounds for stochastic dual dynamic programming via Fenchel duality
- Stochastic decomposition applied to large-scale hydro valleys management
- Inexact cuts in stochastic dual dynamic programming
- Dual-based methods for solving infinite-horizon nonstationary deterministic dynamic programs
- Periodical multistage stochastic programs
- GDDP: Generalized dual dynamic programming theory
- A time-consistent Benders decomposition method for multistage distributionally robust stochastic optimization with a scenario tree structure
- Risk neutral reformulation approach to risk averse stochastic programming
- Regularized stochastic dual dynamic programming for convex nonlinear optimization problems
- Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
- Parallel and distributed computing for stochastic dual dynamic programming
- Single cut and multicut stochastic dual dynamic programming with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments
- Risk-averse stochastic optimal control: an efficiently computable statistical upper bound
This page was built for publication: Dual dynamic programming with cut selection: convergence proof and numerical experiments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1698882)
