  In this paper, we study multistage stochastic mixed-integer nonlinear
programs (MS-MINLP). This general class of problems encompasses, as important
special cases, multistage stochastic convex optimization with non-Lipschitzian
value functions and multistage stochastic mixed-integer 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 MS-MINLP are identified, where the new algorithms are
guaranteed to obtain the global optimum without the assumption of complete
recourse. This significantly generalizes the classic SDDP 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}{4\epsilon})^d)$ for the general case or by
$\mathcal{O}((\frac{T}{8\epsilon})^{d/2-1})$ for the convex case. This shows
that the obtained complexity bounds are rather sharp. It also reveals that the
iteration complexity depends polynomially on the number of stages. We further
show that the iteration complexity depends linearly on $T$, if all the state
spaces are finite sets, or if we seek a $(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.
