Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

A generalization of Hull and White formula and applications to option pricing approximation

By means of Malliavin Calculus we see that the classical Hull and White formulafor option pricing can be extended to the case where the noise driving thevolatility process is correlated with the noise driving the stock prices. Thisextension will allow us to construct option pricing approximation formulas.Numerical examples are presented.

Solving higher-dimensional continuous time stochastic control problems by value function regression

The paper develops a method to solve higher-dimensional stochasticcontrol problems in continuous time. A finite difference typeapproximation scheme is used on a coarse grid of low discrepancypoints, while the value function at intermediate points is obtainedby regression. The stability properties of the method are discussed,and applications are given to test problems of up to 10 dimensions.Accurate solutions to these problems can be obtained on a personalcomputer.

A decomposition formula for option prices in the Heston model and applications to option pricing approximation

By means of classical Itô's calculus we decompose option prices asthe sum of the classical Black-Scholes formula with volatility parameterequal to the root-mean-square future average volatility plus a term dueby correlation and a term due to the volatility of the volatility. Thisdecomposition allows us to develop first and second-order approximationformulas for option prices and implied volatilities in the Heston volatilityframework, as well as to study their accuracy. Numerical examples aregiven.

Stochastic evolution of rules for playing normal form games

The evolution of boundedly rational rules for playing normal form games is studied within stationary environments ofstochastically changing games. Rules are viewed as algorithms prescribing strategies for the different normal formgames that arise. It is shown that many of the folk results of evolutionary game theory typically obtained witha fixed game and fixed strategies carry over to the present case. The results are also related to recent experimentson rules and games.

Surface collective oscillations of metal clusters and spheres: Random-phase-approximation sum-rules approach

Using the once and thrice energy-weighted moments of the random-phase-approximation strength function, we have derived compact expressions for the average energy of surface collective oscillations of clusters and spheres of metal atoms. The L=0 volume mode has also been studied. We have carried out quantal and semiclassical calculations for Na and Ag systems in the spherical-jellium approximation. We present a rather thorough discussion of surface diffuseness and quantal size effects on the resonance energies.

Kinematic reduction of reaction-diffusion fronts with multiplicative noise. Derivation of stochastic sharp-interface equations

We study the dynamics of generic reaction-diffusion fronts, including pulses and chemical waves, in the presence of multiplicative noise. We discuss the connection between the reaction-diffusion Langevin-like field equations and the kinematic (eikonal) description in terms of a stochastic moving-boundary or sharp-interface approximation. We find that the effective noise is additive and we relate its strength to the noise parameters in the original field equations, to first order in noise strength, but including a partial resummation to all orders which captures the singular dependence on the microscopic cutoff associated with the spatial correlation of the noise. This dependence is essential for a quantitative and qualitative understanding of fluctuating fronts, affecting both scaling properties and nonuniversal quantities. Our results predict phenomena such as the shift of the transition point between the pushed and pulled regimes of front propagation, in terms of the noise parameters, and the corresponding transition to a non-Kardar-Parisi-Zhang universality class. We assess the quantitative validity of the results in several examples including equilibrium fluctuations and kinetic roughening. We also predict and observe a noise-induced pushed-pulled transition. The analytical predictions are successfully tested against rigorous results and show excellent agreement with numerical simulations of reaction-diffusion field equations with multiplicative noise.

Stochastic generation of homogeneous isotropic turbulence with well-defined-spectra

A precise and simple computational model to generate well-behaved two-dimensional turbulent flows is presented. The whole approach rests on the use of stochastic differential equations and is general enough to reproduce a variety of energy spectra and spatiotemporal correlation functions. Analytical expressions for both the continuous and the discrete versions, together with simulation algorithms, are derived. Results for two relevant spectra, covering distinct ranges of wave numbers, are given.

Cosmological perturbations from stochastic gravity

In inflationary cosmological models driven by an inflaton field the origin of the primordial inhomogeneities which are responsible for large-scale structure formation are the quantum fluctuations of the inflaton field. These are usually calculated using the standard theory of cosmological perturbations, where both the gravitational and the inflaton fields are linearly perturbed and quantized. The correlation functions for the primordial metric fluctuations and their power spectrum are then computed. Here we introduce an alternative procedure for calculating the metric correlations based on the Einstein-Langevin equation which emerges in the framework of stochastic semiclassical gravity. We show that the correlation functions for the metric perturbations that follow from the Einstein-Langevin formalism coincide with those obtained with the usual quantization procedures when the scalar field perturbations are linearized. This method is explicitly applied to a simple model of chaotic inflation consisting of a Robertson-Walker background, which undergoes a quasi-de Sitter expansion, minimally coupled to a free massive quantum scalar field. The technique based on the Einstein-Langevin equation can, however, deal naturally with the perturbations of the scalar field even beyond the linear approximation, as is actually required in inflationary models which are not driven by an inflaton field, such as Starobinsky¿s trace-anomaly driven inflation or when calculating corrections due to nonlinear quantum effects in the usual inflaton driven models.

Stochastic generation of homogeneous isotropic turbulence with well-defined-spectra

A precise and simple computational model to generate well-behaved two-dimensional turbulent flows is presented. The whole approach rests on the use of stochastic differential equations and is general enough to reproduce a variety of energy spectra and spatiotemporal correlation functions. Analytical expressions for both the continuous and the discrete versions, together with simulation algorithms, are derived. Results for two relevant spectra, covering distinct ranges of wave numbers, are given.

Approximation and support theorem for a wave equation in two space dimensions

We prove a characterization of the support of the law of the solution for a stochastic wave equation with two-dimensional space variable, driven by a noise white in time and correlated in space. The result is a consequence of an approximation theorem, in the convergence of probability, for equations obtained by smoothing the random noise. For some particular classes of coefficients, approximation in the Lp-norm for p¿1 is also proved.

A Fast Gradient Approximation for Nonlinear Blind Signal Processing

When dealing with nonlinear blind processing algorithms (deconvolution or post-nonlinear source separation), complex mathematical estimations must be done giving as a result very slow algorithms. This is the case, for example, in speech processing, spike signals deconvolution or microarray data analysis. In this paper, we propose a simple method to reduce computational time for the inversion of Wiener systems or the separation of post-nonlinear mixtures, by using a linear approximation in a minimum mutual information algorithm. Simulation results demonstrate that linear spline interpolation is fast and accurate, obtaining very good results (similar to those obtained without approximation) while computational time is dramatically decreased. On the other hand, cubic spline interpolation also obtains similar good results, but due to its intrinsic complexity, the global algorithm is much more slow and hence not useful for our purpose.

A hybrid algorithm combining metaheuristic with Monte Carlo simulation for solving the Stochastic Flow Shop problem

In this paper, a hybrid simulation-based algorithm is proposed for the StochasticFlow Shop Problem. The main idea of the methodology is to transform the stochastic problem into a deterministic problem and then apply simulation to the latter. In order to achieve this goal, we rely on Monte Carlo Simulation and an adapted version of a deterministic heuristic. This approach aims to provide flexibility and simplicity due to the fact that it is not constrained by any previous assumption and relies in well-tested heuristics.

A hybrid algorithm combining metaheuristic with Monte Carlo simulation for solving the Stochastic Flow Shop problem

In this paper, a hybrid simulation-based algorithm is proposed for the StochasticFlow Shop Problem. The main idea of the methodology is to transform the stochastic problem into a deterministic problem and then apply simulation to the latter. In order to achieve this goal, we rely on Monte Carlo Simulation and an adapted version of a deterministic heuristic. This approach aims to provide flexibility and simplicity due to the fact that it is not constrained by any previous assumption and relies in well-tested heuristics.

Environmental data mining and modeling based on machine learning algorithms and geostatistics

The paper presents some contemporary approaches to spatial environmental data analysis. The main topics are concentrated on the decision-oriented problems of environmental spatial data mining and modeling: valorization and representativity of data with the help of exploratory data analysis, spatial predictions, probabilistic and risk mapping, development and application of conditional stochastic simulation models. The innovative part of the paper presents integrated/hybrid model-machine learning (ML) residuals sequential simulations-MLRSS. The models are based on multilayer perceptron and support vector regression ML algorithms used for modeling long-range spatial trends and sequential simulations of the residuals. NIL algorithms deliver non-linear solution for the spatial non-stationary problems, which are difficult for geostatistical approach. Geostatistical tools (variography) are used to characterize performance of ML algorithms, by analyzing quality and quantity of the spatially structured information extracted from data with ML algorithms. Sequential simulations provide efficient assessment of uncertainty and spatial variability. Case study from the Chernobyl fallouts illustrates the performance of the proposed model. It is shown that probability mapping, provided by the combination of ML data driven and geostatistical model based approaches, can be efficiently used in decision-making process. (C) 2003 Elsevier Ltd. All rights reserved.