MÜNCHENER STOCHASTIK-TAGE 1998 Sekt.-Nr.:5

Monte Carlo-Methoden und Simulation

Sektionsleiter: M. Kolonko, Clausthal-Z.

Borgwardt , Karl Heinz Hauptvortrag Universität Augsburg, Institut für Mathematik

Stochastic Geometry – A Tool for Determining the Average-Case Complexity of Optimization Algorithms

Consider the arithmetical effort to solve Linear Programming Problems

maximize v^{T} x
subject to a_{1}^{T} x ≤ 1, …, a_{m}^{T}x ≤ 1
where x, v, a_{1}, …, a_{m} ∈ IR^{n} and m ≥ n.

The lower dimension n is the number of variables, and the larger dimension m gives the number of restrictions defining the feasible polyhedron

X = {x | a_{1}^{T} x ≤ 1, …, a_{m}^{T}x ≤ 1}.

We are interested in the expected numbers of iteration steps of solution algorithms for the LP, when the problem-instances are distributed according to the so-called Rotation-Symmetry-Model (RSM):

a_{1}, …, a_{m}, v are distributed on IR^{n} \ {0} identically, independently and symmetrically under rotations.

For the most efficient classes of solution algorithms, Simplex-Methods and Interior-Point-Methods, we explain, how the question for their efficiency can be translated into the language of geometry. And we demonstrate, how the technical tools of Stochastic Geometry - for evaluation of the stochastic features of random polyhedra - can be exploited to provide significant information on the average speed of those algorithms.

Simplex-Methods calculate a vertex x_{0} of X and construct a sequence of vertices x_{0}, …, x_{s} ∈ X, such that for all i the vertices x_{i} and x_{i+1} are adjacent and v^{T} x_{i} < v^{T} x_{i+1} . The final vertex x_{s} is either optimal or a vertex where the nonexistence of an optimum becomes obvious.

We show that and how our stochastic evaluation leads to the following results:

• An upper bound on the expected value of necessary vertex-exchanges (pivot steps) for a special variant, the Shadow-Vertex-Algorithm

• A lower bound on the expected number of necessary pivot steps - valid for all variants of Simplex-Algorithms

• An upper bound on the quotient between standard deviation and expected number of necessary pivot steps - for the Shadow-Vertex-Algorithm.

Interior-Point-Methods first determine an interior point x_{0} of X suitable for initiating an iteration process. Then they construct a sequence of inner points x_{0}, …, x_{s} ∈ X, such that a certain distance function to the optimum is reduced at least linearly from step to step, and stop at a point x_{s} , where the distance gets below a certain level of approximation-quality. Starting from x_{s}, a rounding process leads to the optimal vertex of X.

Here we can show that - on the average - the number of necessary reduction steps to achieve the required quality-level is very small. Again, this insight results from an intensive evaluation of the stochastic properties of the random polyhedron X, as the distribution of the length of its edges.

Krummenauer, Frank Institut fuer Medizinische Statistik und Dokumentation der Universit Mainz

Effiziente Simulation hochdimensionaler Binomial– und Poissonverteilungen

Nicht selten stößt man bei der Untersuchung inferenz–statistischer Methoden, welche auf multivariaten diskreten Verteilungen basieren, an die Grenzen der analytischen Durchführbarkeit. Um dennoch zumindest numerisch–exemplarische Aussagen ueber Effizienz entsprechender Schätzungen oder Power korrespondierender Tests machen zu können, sind Simulationen nicht selten ein notwendiger Ausweg, insbesondere, wenn die zu Grunde liegende Abhängigkeitsstruktur zwischen den Rändern der multivariaten Verteilungen nicht nur Korrelationen, sondern auch das Beruecksichtigen höherer Interaktionen erfordert. Um dieses Vorgehen in der Praxis handhabbar zu gestalten, sind schnelle und effiziente Algorithmen zur Generierung der multivariaten Verteilungen nötig. Daher soll für die multivariate Binomial– und Poissonverteilung jeweils ein Algorithmus vorgestellt werden, der zu gegebener (beliebiger) k–variater Abhängigkeitsstruktur zwischen den marginalen Outcomes eine Realisation der zugehörigen multivariaten Verteilung generiert. Diese erfordern jeweils die einmalige Lösung eines linearen Gleichungssystems und den maximal 2^{k}–maligen Aufruf eines Zufallsgenerators der Multinormalverteilung bzw. der univariaten Poissonverteilung.

Sabelfeld , Karl ICM&MG, Novosibirsk, Russia

Stochastic Models of Turbulence

A one-particle stochastic Lagrangian model in 2D and 3D dimensions is constructed for transport of particles in horizontaly homogeneous turbulent flows with arbitrary one-point probability density function. It is shown that in the case of gaussian pdf, this model essentially differs from the known models. In this work we deal with one-particle stochastic Lagrangian models for 2D and 3D turbulent transport. Here we treat the fully developed turbulence (i.e., a flow with very high Reynolds number) as a random velocity field which is assumed to be incompressible. Therefore, the trajectories of particles in such flows are stochastic processes. To simulate these stochastic processes, two different approaches are known in the literature. The first one is based on the numerical solution of the system of random equations

Ẋ(t) = u(X, Y, Z, t),
Ẏ (t) = v(X, Y, Z, t),  (1)
Ż(t) = w(X, Y, Z, t).

Here X(t), Y (t), Z(t) are the coordinates of the Lagrangian trajectory at the time t, u, v, w are the components of the Eulerian velocity. The random fields u, v, w are simulated by Monte Carlo methods, and the random trajectories are then obtained by numerical solution of (1) with the relevant initial data. In the second approach the true trajectory X(t), Y (t), Z(t) is assumed to be approximated by a model trajectory X̂(t), Ŷ (t), Ẑ(t), a solution to a stochastic differential equation of Ito type:

dX̂ = Ûdt,
dŶ = V̂ dt,

dẐ = Ŵ dt
dÛ = a_{u}(t, X̂, Ŷ , Ẑ, Û, V̂ , Ŵ)dt + b_{u}(t, X̂, Ŷ , Ẑ, Û, V̂ , Ŵ)dB_{u}(t),
dV̂ = a_{v}(t, X̂, Ŷ , Ẑ, Û, V̂ , Ŵ)dt + b_{v}(t, X̂, Ŷ , Ẑ, Û, V̂ , Ŵ)dB_{v}(t),
dŴ = a_{w}(t, X̂, Ŷ , Ẑ, Û, V̂ , Ŵ)dt + b_{w}(t, X̂, Ŷ , Ẑ, Û, V̂ , Ŵ)dB_{w}(t),

Here Û, V̂ , Ŵ are the components of the model Lagrangian velocity, B_{u}(t), B_{v}(t), B_{w}(t) are three standard independent Wiener processes. In this work we study the relations between the Eulerian and Lagrangian models, and present some numerical results concerning the coagulation of aerosol particles in a turbulent collision regime.

Simonov , Nikolai ICM&MG, Novosibirsk, Russia

Monte Carlo solution of the diffusion equation with random absorption

Consider a random parabolic equation

w_{t} = νΔw + cw + f  (1)

in a cylinder G × (0, T], where G ⊂ IR^{m} is either bounded simple connected with a simple connected boundary or external to such a domain. Suppose c, f, g, w_{0} to be random over (Ω, A, P), some suitable probability space, with uniformly bounded second moments and continuous sample functions. Here g = Bw on ∂G, B being a boundary operator, w_{0} = w|_{t=0}. w linearly depends on f, g and w_{0}. So, in the case c being non-random, the mean value and the second moment of the solution can be found as the solutions to the correspondent averaged equations. The potential representation can be used in particular, the parametrix Z_{0} being the kernel of the heat potentials. Monte Carlo estimators for \overline{w} = IE_{ω}w and IE_{ω}w(x_{1}, t_{1}; x_{2}, t_{2}) based on such a representation have been constructed [1]. It is clear that the averaging of the problem is not applicable in the case of random c. Denote by Z_{c}

the fundamental solution to (1) in L_{2}(Ω) sense: Z_{c} = ∑_{i=0}^{∞} K_{cZ_{0}}^{i}cZ_{0}, K being the integral operator

with the kernel cZ_{0}. This means that the solution to (1) in L_{2}(Ω) can be represented as a sum of random heat potentials with Z_{c} (or its normal derivative) as the kernel. We propose to use here Monte Carlo methods analogous to those constructed for non-random parabolic equations. The simplest estimator (that is a priori more efficient than the conventional deterministic methods) is based on the double randomization principle: simulate sample values of stochastic fields c, f, w_{0}, g, and construct a Monte Carlo estimator ξ(η)(x, t) for the solution of (1), random parameters fixed. Then IE_{ω,η}ξ(η)(x, t) = \overline{w}(x, t). Consider e.g. Cauchy problem with f = 0. Then

ξ = ∑_{n=0}^{N} Q_{n}F_{0}(x_{n}, t_{n}),  (2)

Q_{0} = 1, F_{0}(x, t) = ∫_{IR^{m}} dx′Z_{0}(x − x′, t)w_{0}(x′), Q_{n+1} = Q_{n} \frac{t_{n}c(x_{n+1}, t_{n+1})}{q}, where q is a survival

probability, η belongs to the space of Markov chain’ {(x_{n}, t_{n}) ∈ Q_{T} , n = 0, 1, …} paths. It is clear that IEξ^{2} is bounded. The efficiency of the estimator (2) substantially depends on the information given. Suppose that the solution’s moments are to be calculated and that all the moment functions for c, w_{0} are known. So, there is no need in the simulation of these random fields since moment functions can be substituted directly into (2).

[1] N. A. Simonov, Stochastic computational methods for parabolic equations with random data, 15th IMACS World Congress, Berlin, August 1997. Proceedings. A.Sydow, ed. Vol. 1, P. 449-452.