Inexact cuts in stochastic dual dynamic programming applied to multistage stochastic nondifferentiable problems
From MaRDI portal
(Redirected from Publication:5152472)
Abstract: In [13], an Inexact variant of Stochastic Dual Dynamic Programming (SDDP) called ISDDP was introduced which uses approximate (instead of exact with SDDP) primal dual solutions of the problems solved in the forward and backward passes of the method. That variant of SDDP was studied in [13] for linear and for differentiable nonlinear Multistage Stochastic Programs (MSPs). In this paper, we extend ISDDP to nondifferentiable MSPs. We first provide formulas for inexact cuts for value functions of convex nondifferentiable optimization problems. We then combine these cuts with SDDP to describe ISDDP for nondifferentiable MSPs and analyze the convergence of the method. More precisely, for a problem with T stages, we show that for errors bounded from above by epsilon, the limit superior and limit inferior of sequences of upper and lower bounds on the optimal value of the problem are at most at distance 3*epsilon*T to the optimal value and that for asymptotically vanishing errors ISDDP converges to an optimal policy. [13] V. Guigues, Inexact cuts in Stochastic Dual Dynamic Programming, Siam Journal on Optimization, 30(1), 407-438, 2020.
Recommendations
- Inexact cuts in stochastic dual dynamic programming
- Stochastic dynamic cutting plane for multistage stochastic convex programs
- Stochastic dual dynamic integer programming
- Analysis of stochastic dual dynamic programming method
- Exact converging bounds for stochastic dual dynamic programming via Fenchel duality
Cites work
- Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems
- Adjustable robust solutions of uncertain linear programs
- Analysis of stochastic dual dynamic programming method
- Approximate dynamic programming. Solving the curses of dimensionality
- Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
- Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
- Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
- Evaluating policies in risk-averse multi-stage stochastic programming
- Inexact Cuts in Benders Decomposition
- Inexact cuts in stochastic dual dynamic programming
- Inexact stochastic mirror descent for two-stage nonlinear stochastic programs
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lectures on Stochastic Programming
- MIDAS: a mixed integer dynamic approximation scheme
- Multi-stage stochastic optimization applied to energy planning
- On the convergence of decomposition methods for multistage stochastic convex programs
- On the convergence of stochastic dual dynamic programming and related methods
- Partitioning procedures for solving mixed-variables programming problems
- Periodical multistage stochastic programs
- Primal and dual linear decision rules in stochastic and robust optimization
- Risk neutral reformulation approach to risk averse stochastic programming
- Robust optimization
- Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures
- SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
- Single cut and multicut stochastic dual dynamic programming with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments
- Smooth minimization of non-smooth functions
- Stochastic decomposition. A statistical method for large scale stochastic linear programming
- Stochastic dual dynamic integer programming
- Stochastic dynamic cutting plane for multistage stochastic convex programs
- The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse
Cited in
(7)- Inexact stochastic mirror descent for two-stage nonlinear stochastic programs
- Stochastic dynamic cutting plane for multistage stochastic convex programs
- Exact converging bounds for stochastic dual dynamic programming via Fenchel duality
- Inexact cuts in stochastic dual dynamic programming
- A Decomposition Algorithm for Two-Stage Stochastic Programs with Nonconvex Recourse Functions
- Stochastic dual dynamic programming and its variants: a review
- Coordinating international humanitarian inventory by stochastic dual dynamic programming
This page was built for publication: Inexact cuts in stochastic dual dynamic programming applied to multistage stochastic nondifferentiable problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5152472)
