Leonidas Sakalauskas (Institute of Mathematics and Informatics, Vilnius, Lithuania)

Parallel adaptation of Monte-Carlo method for continuous stochastic programming
Wednesday 9 December 2009 at 15.30, JCMB 6206

Abstract

The objective of the research is the development of parallel algorithms for solving stochastic programming problems by finite sequences of Monte-Carlo estimators. The algorithms are based by adaptive regulation of the Monte-Carlo sample size and the statistical termination procedure. The approach distinguishes itself by treatment of the accuracy of the solution in a statistical manner, testing the hypothesis of optimality according to statistical criteria, and estimating confidence intervals of the objective and constraint functions. The adjustment of sample size taking it inversely proportional to the square norm of Monte-Carlo estimator of gradient guarantees the convergence of the method and enables us to solve the problem by reasonable amount of computations. To avoid "jamming" or "zigzagging" in solving the problem, the ε–feasible direction approach is implemented. The method developed was applied to solve examples from the database of two-stage stochastic linear programming tests. Many solutions given in the database were achieved by the method developed and in a number of cases we had success to improve the solution given in database. High performance computers with parallel computing allowed us to perform computational statistical experiment, which has high practical importance pursuing to explore the speedup and efficiency of parallelization on the number of processors and admissible accuracy. The parallelization strategy consists of sharing the computation of identical Monte-Carlo trials among processors and using root processor to manage the adaptation of the sample size. Portable parallel programs were developed with MPICC which can be used on any parallel architecture.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996