Stochastic Dynamic Cutting Plane for Multistage Stochastic Convex Programs
| Autor: | Renato D. C. Monteiro, Vincent Guigues |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
021103 operations research Control and Optimization Applied Mathematics 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Management Science and Operations Research 01 natural sciences Dynamic programming Convergence of random variables Bounded function Convex optimization Theory of computation Affine transformation Differentiable function 0101 mathematics Cutting-plane method Mathematics |
| Zdroj: | Journal of Optimization Theory and Applications. 189:513-559 |
| ISSN: | 1573-2878 0022-3239 |
| DOI: | 10.1007/s10957-021-01842-x |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink