On approximating non-convex value functions in stochastic dual dynamic programming and related decomposition methods

Today, stochastic dual dynamic programming (SDDP) is one of the state-of-the-art algorithms to solve multistage stochastic optimization problems. One of its key ideas, borrowed from Benders decomposition, is to decompose a multistage problem into several subproblems which are coupled by so-called value functions. As these functions are not known explicitly, they are iteratively approximated using cutting-planes (linear cuts). However, in order for this to work, several crucial assumptions have to be satisfied, among them linearity (or at least convexity) of all occurring functions as well as stagewise independence of the uncertain data. In many applications, this is not guaranteed. For this reason, various enhancements of SDDP have been proposed which allow to relax some of these assumptions.

The research in this thesis addresses an open challenge in this regard, which is to extend SDDP to problem classes for which non-convexities arise in the value functions, and thus linear cuts are not sufficient to guarantee (almost sure) convergence to an optimal solution. The focus is on three specific types of problems: a) including integrality constraints, b) including non-convex functions, c) with the uncertain data modeled by a non-convex autoregressive process. ... mehrIt is shown that in all three cases a tight approximation of the value functions can be achieved using special non-convex cuts. By careful design, based on these results solution methods with proven convergence are developed, the one for case c) being the first of its kind. This extends the toolbox of SDDP-like algorithms substantially.

In addition, a novel framework is presented to generate linear cuts with favorable properties, which may help to improve the computational performance of the existing SDDP-derivative stochastic dual dynamic integer programming (SDDiP). Finally, as many of the proposed linear and non-convex cuts rely on special Lagrangian relaxations, a detailed theoretical study of these relaxations and their properties with respect to the value functions is conducted.

All algorithmic contributions are tested in case studies on real-world applications, such as unit commitment, hydrothermal scheduling or lot-sizing, confirming their effectiveness and their potential. However, the studies also reveal that due to a considerable computational overhead in generating and incorporating the proposed (non-convex) cuts, efficiency and computational tractability still remain major challenges for SDDP-like algorithms given non-convex problems.