Inexact cuts in stochastic dual dynamic programming

DOI10.1137/18M1211799zbMATH Open1430.90444arXiv1809.02007OpenAlexW3004455734MaRDI QIDQ5215519FDOQ5215519

Authors: Vincent Guigues 

Publication date: 12 February 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We introduce an extension of Stochastic Dual Dynamic Programming (SDDP) to solve stochastic convex dynamic programming equations. This extension applies when some or all primal and dual subproblems to be solved along the forward and backward passes of the method are solved with bounded errors (inexactly). This inexact variant of SDDP is described both for linear problems (the corresponding variant being denoted by ISDDP-LP) and nonlinear problems (the corresponding variant being denoted by ISDDP-NLP). We prove convergence theorems for ISDDP-LP and ISDDP-NLP both for bounded and asymptotically vanishing errors. Finally, we present the results of numerical experiments comparing SDDP and ISDDP-LP on portfolio problem with direct transaction costs modelled as a multistage stochastic linear optimization problem. On these experiments, ISDDP-LP allows us to obtain a good policy faster than SDDP.

Full work available at URL: https://arxiv.org/abs/1809.02007

Recommendations

• Inexact cuts in stochastic dual dynamic programming applied to multistage stochastic nondifferentiable problems
• Analysis of stochastic dual dynamic programming method
• Stochastic dual dynamic integer programming
• Stochastic dynamic cutting plane for multistage stochastic convex programs
• Exact converging bounds for stochastic dual dynamic programming via Fenchel duality

zbMATH Keywords

stochastic programmingSDDPinexact cuts for value functionsinexact SDDPbounding epsilon-optimal dual solutions

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Stochastic programming (90C15)

Cites Work

• Partitioning procedures for solving mixed-variables programming problems
• A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
• Inexact Cuts in Benders Decomposition
• On the convergence of stochastic dual dynamic programming and related methods
• Multi-stage stochastic optimization applied to energy planning
• Risk neutral and risk averse stochastic dual dynamic programming method
• Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures
• Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
• Analysis of stochastic dual dynamic programming method
• SDDP for multistage stochastic linear programs based on spectral risk measures
• Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs
• Evaluating policies in risk-averse multi-stage stochastic programming
• Dual dynamic programming with cut selection: convergence proof and numerical experiments
• Stochastic dual dynamic integer programming
• Single cut and multicut stochastic dual dynamic programming with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments

Cited In (11)

• Stochastic dynamic cutting plane for multistage stochastic convex programs
• Duality and sensitivity analysis of multistage linear stochastic programs
• Analysis of stochastic dual dynamic programming method
• Multistage stochastic programs with a random number of stages: dynamic programming equations, solution methods, and application to portfolio selection
• Constant depth decision rules for multistage optimization under uncertainty
• A time-consistent Benders decomposition method for multistage distributionally robust stochastic optimization with a scenario tree structure
• Regularized stochastic dual dynamic programming for convex nonlinear optimization problems
• Inexact Cuts in Stochastic Dual Dynamic Programming Applied to Multistage Stochastic Nondifferentiable Problems
• Exact Converging Bounds for Stochastic Dual Dynamic Programming via Fenchel Duality
• Title not available (Why is that?)
• Inexact stochastic mirror descent for two-stage nonlinear stochastic programs

Uses Software

• Mosek

This page was built for publication: Inexact cuts in stochastic dual dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215519)