(249z) Novel Sampling Technique for High Dimensionalstochastic Optimization/Stochastic Programmingproblems
AIChE Annual Meeting
2016
2016 AIChE Annual Meeting
Computing and Systems Technology Division
Interactive Session: Systems and Process Operations
Monday, November 14, 2016 - 3:45pm to 5:45pm
Uncertainty is essence of real world optimization problem. Computational speed is critical
in optimizing large scale stochastic problems. The major bottleneck in solving large scale
stochastic optimization/stochastic programming problems is the computational intensity
of scenarios or samples. To this end, this paper presents a novel sampling approach.
There are two important properties for sampling randomness and uniformity. It is the
uniformity that is important for accuracy of the sampling. Latin Hypercube sampling
(LHS) provide good convergence rate as compared to random Monte Carlo simulations
but LHS shows uniformity in single dimension only. For Multi Dimension it computes
stratied sampling for each uncertainty but randomly pairs to form a K dimensional
sample set. Due to this random combination; good uniformity for single dimension is
lost for K dimension. Furthermore quasi random sequences like Hammersley, sobol, and
Halton sequences show better uniformity in k-dimensions but are not one dimensionally
uniform. For Quasi Monte Carlo sequence sampling pairings are done as per Hammersley
or Sobol sequence points to form a sample set of K dimension. For higher dimension
(more than 40) some of these quasi-random sequences like Hammersley and Halton show
clustering and correlation pattern eects due to exponential increase in prime base. This
pattern can be broken by coupling LHS with HSS. Similarly Sobol sequence sampling
is not linked to the prime base so for dimension more than 40 there are no clustering
or correlation patterns upto 100 variables. In this work, we combine one dimensional
uniformity of LHS with k-dimensional uniformity of sobol to generate a new sampling
called LHS-Sobol sampling. This sampling breaks the correlation patterns for sobol and
shows superior convergence for larger dimensions. This sampling plays an important role
innancial modeling.
in optimizing large scale stochastic problems. The major bottleneck in solving large scale
stochastic optimization/stochastic programming problems is the computational intensity
of scenarios or samples. To this end, this paper presents a novel sampling approach.
There are two important properties for sampling randomness and uniformity. It is the
uniformity that is important for accuracy of the sampling. Latin Hypercube sampling
(LHS) provide good convergence rate as compared to random Monte Carlo simulations
but LHS shows uniformity in single dimension only. For Multi Dimension it computes
stratied sampling for each uncertainty but randomly pairs to form a K dimensional
sample set. Due to this random combination; good uniformity for single dimension is
lost for K dimension. Furthermore quasi random sequences like Hammersley, sobol, and
Halton sequences show better uniformity in k-dimensions but are not one dimensionally
uniform. For Quasi Monte Carlo sequence sampling pairings are done as per Hammersley
or Sobol sequence points to form a sample set of K dimension. For higher dimension
(more than 40) some of these quasi-random sequences like Hammersley and Halton show
clustering and correlation pattern eects due to exponential increase in prime base. This
pattern can be broken by coupling LHS with HSS. Similarly Sobol sequence sampling
is not linked to the prime base so for dimension more than 40 there are no clustering
or correlation patterns upto 100 variables. In this work, we combine one dimensional
uniformity of LHS with k-dimensional uniformity of sobol to generate a new sampling
called LHS-Sobol sampling. This sampling breaks the correlation patterns for sobol and
shows superior convergence for larger dimensions. This sampling plays an important role
innancial modeling.
References
[1] U. Diwekar, Introduction to Applied Optimization, 2nd Edition, 2008, Springer.
[2] J. Kalagnanam and U. Diwekar, An ecient sampling technique for oine qual-
ity control, Technometrics, 43, 440, 1997.
[3] F. Akesson and J. Lehoczky, Path generation for quasi-Monte carlo simulation
of morgage backed securities, Management Science, 46(9), 1171, 2003.