Stochastic Dynamic Cutting Plane for Multistage Stochastic Convex Programs

Vincent Guigues () and Renato D. C. Monteiro ()
Additional contact information
Vincent Guigues: School of Applied Mathematics, FGV
Renato D. C. Monteiro: Georgia Institute of Technology

Journal of Optimization Theory and Applications, 2021, vol. 189, issue 2, No 8, 513-559

Abstract: Abstract We introduce Stochastic Dynamic Cutting Plane (StoDCuP), an extension of the Stochastic Dual Dynamic Programming (SDDP) algorithm to solve multistage stochastic convex optimization problems. At each iteration, the algorithm builds lower bounding affine functions not only for the cost-to-go functions, as SDDP does, but also for some or all nonlinear cost and constraint functions. We show the almost sure convergence of StoDCuP. We also introduce an inexact variant of StoDCuP where all subproblems are solved approximately (with bounded errors) and show the almost sure convergence of this variant for vanishing errors. Finally, numerical experiments are presented on nondifferentiable multistage stochastic programs where Inexact StoDCuP computes a good approximate policy quicker than StoDCuP while SDDP and the previous inexact variant of SDDP combined with Mosek library to solve subproblems were not able to solve the differentiable reformulation of the problem.

Keywords: Stochastic programming; Inexact cuts for value functions; SDDP; Inexact SDDP; 90C15; 90C90 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-021-01842-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:189:y:2021:i:2:d:10.1007_s10957-021-01842-x

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-021-01842-x

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().