Orateur
Yifan Hu
(EPFL)
Description
Algorithms for solving Multistage Stochastic Programming (MSP) are long known to suffer from the curse of dimension and horizon. Stochastic Dual Dynamic Programming (SDDP) for stage-wise independence MSP problem admits a complexity of scales exponentially with respect to the decision dimension $d$ in terms of accuracy $\epsilon$, i.e., $O(\epsilon^{-d})$. On the other hand, Stochastic Approximation (SA) and Sample Average Approximation (SAA) type of methods admit a complexity that scales exponentially with respect to the horizon $T$, i.e., $O(\epsilon^{-T})$ for general MSP. In this talk, we discuss a novel approximation-based algorithm that achieves $O(poly(1/\epsilon))$ dependence in a class of MSP problems.
