A stochastic algorithm for deterministic multistage optimization problems

Marianne Akian (), Jean-Philippe Chancelier () and Benoît Tran ()
Additional contact information
Marianne Akian: INRIA Saclay and CMAP, École polytechnique, IP Paris, CNRS
Jean-Philippe Chancelier: CERMICS, École des Ponts ParisTech
Benoît Tran: CERMICS, École des Ponts ParisTech

Annals of Operations Research, 2025, vol. 345, issue 1, No 1, 38 pages

Abstract: Abstract Several attempts to dampen the curse of dimensionality problem of the Dynamic Programming approach for solving multistage optimization problems have been investigated. One popular way to address this issue is the Stochastic Dual Dynamic Programming method (Sddp) introduced by Pereira and Pinto (Math Program 52(1–3):359–375. https://doi.org/10.1007/BF01582895 ). Assuming that the value function is convex (for a minimization problem), one builds a non-decreasing sequence of lower (or outer) convex approximations of the value function. Those convex approximations are constructed as a supremum of affine cuts. On continuous time deterministic optimal control problems, assuming that the value function is semiconvex, Zheng Qu, inspired by the work of McEneaney, introduced in 2013 a stochastic max-plus scheme that builds a non-increasing sequence of upper (or inner) approximations of the value function. In this note, we build a common framework for both the Sddp and a discrete time version of Zheng Qu’s algorithm to solve deterministic multistage optimization problems. Our algorithm generates a monotone sequence of approximations of the value function as a pointwise supremum, or infimum, of basic (affine or quadratic for example) functions which are randomly selected. We give sufficient conditions on the way basic functions are selected in order to ensure almost sure convergence of the approximations to the value function on a set of interest.

Keywords: Deterministic multistage optimization problem; Min-plus algebra; Tropical algebra; Stochastic dual dynamic programming; Dynamic programming (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06153-8 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:annopr:v:345:y:2025:i:1:d:10.1007_s10479-024-06153-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06153-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().