Stochastic programming models static or dynamic optimal decision making under uncertainty. In contrast to deterministic mathematical programming, stochastic programming generally uses expectation functionals in objective or constraints over known or partially known distributions of the problem data. Its features many decision variables under complicated constraints over discrete time periods. Its deep root in deterministic mathematical program differentiates itself from other closely related decision making tools, such as dynamic programming, statistical decision theory, Markov decision process and stochastic control. With recent advances in optimization techniques and computing facilities, many important industrial or financial problems have been successfully solved as stochastic programming problems. Despite these successes, with unknown data in high dimension, sequential decision over many periods, the stochastic programming problem remains a computational challenge due to the exponentially increasing size. In this dissertation, we exploit the special structure of the stochastic programming problem and design efficient algorithms correspondingly. Our research can be broadly divided into three parts. First, we consider multistage convex problems with discrete distributions. The L-shaped method for two stage linear problem and nested decomposition method for multistage linear problems are based on simplex method. We develop an efficient algorithm for two and multistage convex problem, based on interior point method. After regularizing the recourse function using barrier functions, we show that the barrier recourse functions at any stage form a self-concordant family with respect to the barrier parameter. We also show that the complexity value of the first stage problem increases additively with the number of stages and scenarios. We use these results to propose the primal path-following interior point decomposition algorithm for the two-stage and multistage stochastic convex problems. Secondly, we consider how to approximate a stochastic problem with continuous distribution by generating scenarios. We propose sparse grid method for the purpose of generating scenarios. As with any approximations, we analyze the error bounds of the proposed methods and prove its epi-convergent property. We also show numerically that the proposed method converges to the true optimal value fast in comparison with Monte Carlo and Quasi Monte Carlo methods. Finally, we propose a general spline approximation method for solving the chance constrained problem. We show that the proposed approximation is conservative in the sense that any feasible solution of the approximated problem is a feasible solution of the original problem as well. The spline approximation is smooth and hence we can combine it with the sparse grid method to achieve high accuracy and prove error bounds. We test the method numerically on examples from literature as well.

Last modified

• 09/13/2018

Creator

• Sheng Yuan Chen

DOI

• https://doi.org/10.21985/N2DH9T

Subject

• Industrial Engineering and Management Sciences

Keyword

• stochastic optimization
• interior point method
• sparse grid
• chance constrained problem

Date created

• 2008-07-28

Resource type

• Dissertation

Rights statement

• In Copyright