Optimization Online


Inexact cuts in SDDP applied to multistage stochastic nondifferentiable problems

Vincent Guigues(vincent.guigues***at***fgv.br)
Renato Monteiro(renato.monteiro***at***isye.gatech)
Benar Svaiter(benar***at***impa.br)

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.

Keywords: Stochastic optimization; SDDP; Inexact cuts for value functions; Inexact SDDP

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 04/06/2020
Entry Accepted: 04/06/2020
Entry Last Modified: 04/06/2020

Modify/Update this entry

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


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