-

 

 

 




Optimization Online





 

Inexact cuts in Stochastic Dual Dynamic Programming

Vincent Guigues (vincent.guigues***at***gmail.com)

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 a 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.

Keywords: Stochastic programming, Inexact cuts for value functions, Bounding epsilon-optimal dual solutions, SDDP, Inexact SDDP

Category 1: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 09/04/2018
Entry Accepted: 09/05/2018
Entry Last Modified: 07/07/2019

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society