458494 Novel Sampling Technique for High Dimensionalstochastic Optimization/Stochastic Programmingproblems

Monday, November 14, 2016
Grand Ballroom B (Hilton San Francisco Union Square)
Nishant Dige, University of Illinois at Chicago, Chicago, IL and Urmila M. Diwekar, Vishwamitra Research Institute, Center for Uncertain Systems: Tools for Optimization and Management, Clarendon Hills, IL

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
strati ed 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 e ects 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
in nancial modeling.

References
[1] U. Diwekar, Introduction to Applied Optimization, 2nd Edition, 2008, Springer.

[2] J. Kalagnanam and U. Diwekar, An e cient 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.


Extended Abstract: File Not Uploaded