Events

AdONE Seminar: Prof. Andy Sun (Massachusetts Institute of Technology)

Dual Dynamic Programming for Multistage Stochastic and Distributionally Robust Optimization: Adaptive Algorithms and Complexity Analysis

Prof. Sun giving his online presentation

Dual dynamic programming (DDP) is a classic algorithm for solving multistage stochastic linear programming. In recent years, several significant progresses have been made. The DDP framework has been significantly extended to tackle multistage stochastic mixed integer linear programming with exact cutting plane methods. The classic convergence type results have been refined to yield, for the first time, sharp iteration complexity results with nearly matching upper and lower complexity bounds. As a consequence, some open question has been answered, e.g. how does the iteration complexity of the DDP algorithm depend on the number of stages, polynomially or exponentially? (the answer is quadratically or even linearly). A new type of adaptive DDP algorithm is proposed for the more general framework of multistage distributionally robust optimization, which shows significant improvement in computational performance over the classic DDP algorithm. In this talk, we will survey these exciting advances and their applications in energy system optimization.