  


Stochastic Dual Dynamic Programming for Multistage Stochastic MixedInteger Nonlinear Optimization
Shixuan Zhang (szhang483gatech.edu) Abstract: In this paper, we study multistage stochastic mixedinteger nonlinear programs (MSMINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with \emph{nonLipschitzcontinuous} value functions and multistage stochastic mixedinteger linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MSMINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic nested Benders decomposition, SDDP, and SDDiP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a $(T+1)$stage stochastic MINLP with $d$dimensional state spaces, to obtain an $\epsilon$optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by $\mathcal{O}((\frac{2T}{\epsilon})^d)$, and is lower bounded by $\mathcal{O}((\frac{T}{2\epsilon})^d)$ for the nonconvex case or by $\mathcal{O}((\frac{T}{8\epsilon})^{d/21})$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends \emph{polynomially} on the number of stages. We further show that the iteration complexity depends \emph{linearly} on $T$, if all the state spaces are finite sets, or if we seek an $(T\epsilon)$optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with $T$. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed. Keywords: Multistage stochastic programming, MINLP, SDDP, complexity analysis Category 1: Stochastic Programming Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 3: Global Optimization Citation: H. Milton Stewart School of Industrial and Systems Engineering 755 Ferst Drive, NW, Atlanta, GA 30332 December 2019 Download: [PDF] Entry Submitted: 12/31/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  