Central Limit Theorem and Sample Complexity of Stationary Stochastic Programs

In this paper we discuss sample complexity of solving stationary stochastic programs by the Sample Average Approximation (SAA) method. We investigate this in the framework of Optimal Control (in discrete time) setting. In particular we derive a Central Limit Theorem type asymptotics for the optimal values of the SAA problems. The main conclusion is that … Read more

Dual bounds for periodical stochastic programs

In this paper we discuss construction of the dual of a periodical formulation of infinite horizon linear stochastic programs with a discount factor. The dual problem is used for computing a deterministic upper bound for the optimal value of the considered multistage stochastic program. Numerical experiments demonstrate behavior of that upper bound especially when the … Read more

Periodical Multistage Stochastic Programs

In some applications the considered multistage stochastic programs have a periodical behavior. We show that in such cases it is possible to drastically reduce the number of stages by introducing a periodical analog of the so-called Bellman equations for discounted infinite horizon problems, used in Markov Decision Processes and Stochastic Optimal Control. Furthermore, we describe … Read more

On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems

We consider well-known decomposition techniques for multistage stochastic programming and a new scheme based on normal solutions for stabilizing iterates during the solution process. The given algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. Numerical experiments on a hydrothermal scheduling … Read more

Two methods of pruning Benders’ cuts and their application to the management of a gas portfolio

In this article, we describe a gas portfolio management problem, which is solved with the SDDP (Stochastic Dual Dynamic Programming) algorithm. We present some improvements of this algorithm and focus on methods of pruning Benders’ cuts, that is to say, methods of picking out the most relevant cuts among those which have been computed. Our … Read more