New efficient numerical procedures for solving stochastic variational problems with a priori maximum pointwise error estimates

In a previous paper we gave a new formulation and derived the Euler equations and other necessary conditions to solve strong, pathwise, stochastic variational problems with trajectories driven by Brownian motion. Thus, unlike current methods which minimize the control over deterministic functionals (the expected value), we find the control which gives the critical point solution of random functionals of a Brownian path and then, if we choose, find the expected value.This increase in information is balanced by the fact that our methods are anticipative while current methods are not. However, our methods are more directly connected to the theory and meaningful examples of deterministic variational theory and provide better means of solution for free and constrained problems. In addition, examples indicate that there are methods to obtain nonanticipative solutions from our equations although the anticipative optimal cost function has smaller expected value.In this paper we give new, efficient numerical methods to find the solution of these problems in the quadratic case. Of interest is that our numerical solution has a maximal, a priori, pointwise error of O(h3/2) where h is the node size. We believe our results are unique for any theory of stochastic control and that our methods of proof involve new and sophisticated ideas for strong solutions which extend previous deterministic results by the first author where the error was O(h²).We note that, although our solutions are given in terms of stochastic differential equations, we are not using the now standard numerical methods for stochastic differential equations. Instead we find an approximation to the critical point solution of the variational problem using relations derived from setting to zero the directional derivative of the cost functional in the direction of simple test functions.Our results are even more significant than they first appear because we can reformulate stochastic control problems or constrained calculus of variations problems in the unconstrained, stochastic calculus of variations formulation of this paper. This will allow us to find efficient and accurate numerical solutions for general constrained, stochastic optimization problems. This is not yet being done, even in the deterministic case, except by the first author.     

Solution of a class of stochastic linear-convex control problems using deterministic equivalents

In this paper, we identify a new class of stochastic linearconvex optimal control problems, whose solution can be obtained by solving appropriate equivalent deterministic optimal control problems. The term linear-convex is meant to imply that the dynamics is linear and the cost function is convex in the state variables, linear in the control variables, and separable. Moreover, some of the coefficients in the dynamics are allowed to be random and the expectations of the control variables are allowed to be constrained. For any stochastic linear-convex problem, the equivalent deterministic problem is obtained. Furthermore, it is shown that the optimal feedback policy of the stochastic problem is affine in its current state, where the affine transformation depends explicitly on the optimal solution of the equivalent deterministic problem in a simple way. The result is illustrated by its application to a simple stochastic inventory control problem.This research was supported in part by NSERC Grant A4617, by SSHRC Grant 410-83-0888, and by an INRIA Post-Doctoral Fellowship.     

Stochastic scalar conservation laws

We introduce a notion of stochastic entropic solution à la Kruzkov, but with Ito's calculus replacing deterministic calculus. This results in a rich family of stochastic inequalities defining what we mean by a solution. A uniqueness theory is then developed following a stochastic generalization of L¹ contraction estimate. An existence theory is also developed by adapting compensated compactness arguments to stochastic setting. We use approximating models of vanishing viscosity solution type for the construction. While the uniqueness result applies to any spatial dimensions, the existence result, in the absence of special structural assumptions, is restricted to one spatial dimension only.     

Stochastic processes adapted by neural networks with application to climate, energy, and finance

Local climate parameters may naturally effect the price of many commodities and their derivatives. Therefore we propose a joint framework for stochastic modeling of climate and commodity prices. In our setting, a stable Levy process is drift augmented to a generalized SDE. The related nonlinear function on the state space typically exhibits deterministic chaos. Additionally, a neural network adapts the parameters of the stable process such that the latter produces increasingly optimal differences between simulated output and observed data. Thus we propose a novel method of “intelligent” calibration of the stochastic process, using learning neural networks in order to dynamically adapt the parameters of the stochastic model.     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

A stochastic and asymmetric-information framework for a dominant-manufacturer supply chain

Consider a dominant manufacturer wholesaling a product to a retailer, who in turn retails it to the consumers at $p/unit. The retail-market demand volume varies with p according to a given demand curve. This basic system is commonly modeled as a manufacturer-Stackelberg ([mS]) game under a “deterministic and symmetric-information” (“det-sym-i”) framework. We first explain the logical flaws of this framework, which are (i) the dominant manufacturer-leader will have a lower profit than the retailer under an iso-elastic demand curve; (ii) in some situations the system’s “correct solution” can be hyper-sensitive to minute changes in the demand curve; (iii) applying volume discounting while keeping the original [mS] profit-maximizing objective leads to an implausible degenerate solution in which the manufacturer has dictatorial power over the channel. We then present an extension of the “stochastic and asymmetric-information” (“sto-asy-i”) framework proposed in Lau and Lau [Lau, A., Lau, H.-S., 2005. Some two-echelon supply-chain games: Improving from deterministic–symmetric-information to stochastic-asymmetric-information models. European Journal of Operational Research 161 (1), 203–223], coupled with the notion that a profit-maximizing dominant manufacturer may implement not only [mS] but also “[pm]”—i.e., using a manufacturer-imposed maximum retail price. We show that this new framework resolves all the logical flaws stated above. Along the way, we also present a procedure for the dominant manufacturer to design a profit-maximizing volume-discount scheme using stochastic and asymmetric demand information.     

Another set of conditions for Markov decision processes with average sample-path costs

This paper deals with discrete-time Markov decision processes with average sample-path costs (ASPC) in Borel spaces. The costs may have neither upper nor lower bounds. We propose new conditions for the existence of ε-ASPC-optimal (deterministic) stationary policies in the class of all randomized history-dependent policies. Our conditions are weaker than those in the previous literature. Moreover, some sufficient conditions for the existence of ASPC optimal stationary policies are imposed on the primitive data of the model. In particular, the stochastic monotonicity condition in this paper has first been used to study the ASPC criterion. Also, the approach provided here is slightly different from the “optimality equation approach” widely used in the previous literature. On the other hand, under mild assumptions we show that average expected cost optimality and ASPC-optimality are equivalent. Finally, we use a controlled queueing system to illustrate our results.     

Improved moment estimates for invariant measures of semilinear diffusions in Hilbert spaces and applications

We study regularity properties for invariant measures of semilinear diffusions in a separable Hilbert space. Based on a pathwise estimate for the underlying stochastic convolution, we prove a priori estimates on such invariant measures. As an application, we combine such estimates with a new technique to prove the L¹-uniqueness of the induced Kolmogorov operator, defined on a space of cylindrical functions. Finally, examples of stochastic Burgers equations and thin-film growth models are given to illustrate our abstract result.     

Stochastic H2/H∞ Control with Random Coefficients

This paper is concerned with the mixed H2/H∞ control for stochastic systems with random coefcients,which is actually a control combining the H2 optimization with the H∞robust performance as the name of H2/H∞ reveals.Based on the classical theory of linear-quadratic(LQ,for short)optimal control,the sufcient and necessary conditions for the existence and uniqueness of the solution to the indefinite backward stochastic Riccati equation(BSRE,for short)associated with H∞ robustness are derived.Then the sufcient and necessary conditions for the existence of the H2/H∞ control are given utilizing a pair of coupled stochastic Riccati equations.     

A generalized stochastic goal programming model

In this paper we show how one can get stochastic solutions of Stochastic Multi-objective Problem (SMOP) using goal programming models. In literature it is well known that one can reduce a SMOP to deterministic equivalent problems and reduce the analysis of a stochastic problem to a collection of deterministic problems. The first sections of this paper will be devoted to the introduction of deterministic equivalent problems when the feasible set is a random set and we show how to solve them using goal programming technique. In the second part we try to go more in depth on notion of SMOP solution and we suppose that it has to be a random variable. We will present stochastic goal programming model for finding stochastic solutions of SMOP. Our approach requires more computational time than the one based on deterministic equivalent problems due to the fact that several optimization programs (which depend on the number of experiments to be run) needed to be solved. On the other hand, since in our approach we suppose that a SMOP solution is a random variable, according to the Central Limit Theorem the larger will be the sample size and the more precise will be the estimation of the statistical moments of a SMOP solution. The developed model will be illustrated through numerical examples.     

On the stochastic Benjamin-Ono equation

We discuss the Cauchy problem for the stochastic Benjamin-Ono equation in the function class Hs(R), s>3/2. When there is a zero-order dissipation, we also establish the existence of an invariant measure with support in H²(R). Many authors have discussed the Cauchy problem for the deterministic Benjamin-Ono equation. But our results are new for the stochastic Benjamin-Ono equation. Our goal is to extend known results for the deterministic equation to the stochastic equation.     

Time-adaptive and history-adaptive multicriterion routing in stochastic, time-dependent networks

We compare two different models for multicriterion routing in stochastic time-dependent networks: the classic “time-adaptive” model and the more flexible “history-adaptive” one. We point out several properties of the sets of efficient solutions found under the two models. We also devise a method for finding supported history-adaptive solutions.     

Analysis of industry equilibria in models with sustaining and disruptive technology

This paper analyzes a special type of technology evolution, referred to in the literature as disruptive technology vs. sustaining technology. In general, “old” products based on sustaining technology are perceived to be superior to the “new” ones based on disruptive technology. However, the latter have distinctive features that allow them to attract an exclusive set of customers. Examples include notebooks vs. netbooks, hard-disk drives vs. solid-state drives, laser printers vs. inkjet printers, etc. We consider a model with an established firm and an entrant firm that have heterogeneous product-offering capabilities: the established firm can offer either or both types of products, while the entrant firm can only offer new products. Firms make capacity, pricing, and quantity decisions that maximize their ex-ante profit. Within this framework, we analyze deterministic games with perfect information and stochastic games with uncertain valuation of the disruptive technology. Equilibrium decisions are discussed under various market conditions, as well as under dedicated vs. flexible capacity assumptions.     

Meshfree Approximation for Stochastic Optimal Control Problems

In this work,we study the gradient projection method for solving a class of stochastic control problems by using a mesh free approximation ap-proach to implement spatial dimension approximation.Our main contribu-tion is to extend the existing gradient projection method to moderate high-dimensional space.The moving least square method and the general radial basis function interpolation method are introduced as showcase methods to demonstrate our computational framework,and rigorous numerical analysis is provided to prove the convergence of our meshfree approximation approach.We also present several numerical experiments to validate the theoretical re-sults of our approach and demonstrate the performance meshfree approxima-tion in solving stochastic optimal control problems.     

Diffusion approximation for signaling stochastic networks

This paper introduces an unified approach to diffusion approximations of signaling networks. This is accomplished by the characterization of a broad class of networks that can be described by a set of quantities which suffer exchanges stochastically in time. We call this class stochastic Petri nets with probabilistic transitions, since it is described as a stochastic Petri net but allows a finite set of random outcomes for each transition. This extension permits effects on the network which are commonly interpreted as “routing” in queueing systems. The class is general enough to include, for instance, G-networks with negative customers and triggers as a particular case. With this class at hand, we derive a heavy traffic approximation, where the processes that drive the transitions are given by state-dependent Poisson-type processes and where the probabilities of the random outcomes are also state-dependent. The objective of this approach is to have a diffusion approximation which can be readily applied in several practical problems. We illustrate the use of the results with some numerical experiments.     

Dynamical distance: coarse grains, pattern recognition, and network analysis

A system moves randomly in a space of states X governed by a stochastic matrix R. From the dynamics alone a distance function is defined on X. This distance allows a coarse graining that is optimal with respect to the dynamics in the following sense: if all grains are of diameter less than ? then the coarse grained dynamics and original dynamics differ by less than ?, which is to say the coarse graining is commutative up to that level. Using this distance function two applications are considered: the creation of “words” or concepts in pattern recognition and the identification of communities in networks.     

A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands

We develop methods to estimate and exactly calculate the expected cost of a priori policies for the multi-compartment vehicle routing problem with stochastic demands, an extension of the classical vehicle routing problem where customer demands are uncertain and products must be transported in separate partitions. We incorporate our estimation procedure into a cyclic-order-based simulated annealing algorithm, significantly improving the best-known solution values for a set of benchmark problems. We also extend the updating procedure for a cyclic order’s candidate route set to duration-constrained a priori policies.     

Adaptive boundary control of stochastic linear distributed parameter systems described by analytic semigroups

A stochastic adaptive control problem is formulated and solved for some unknown linear, stochastic distributed parameter systems that are described by analytic semigroups. The control occurs on the boundary. The highest-order operator is assumed to be known but the lower-order operators contain unknown parameters. Furthermore, the linear operators of the state and the control on the boundary contain unknown parameters. The noise in the system is a cylindrical white Gaussian noise. The performance measure is an ergodic, quadratic cost functional. For the identification of the unknown parameters a diminishing excitation is used that has no effect on the ergodic cost functional but ensures sufficient excitation for strong consistency. The adaptive control is the certainty equivalence control for the ergodic, quadratic cost functional with switchings to the zero control.This research was partially supported by NSF Grants ECS-9102714, ECS-9113029, and DMS-9305936.     

The rational canonical form via the splitting field

It is clear that a given rational canonical form can be further resolved to a Jordan canonical form with entries from the splitting field of its minimal polynomial. Conversely, with an a priori knowledge of the existence and uniqueness of the rational canonical form of a matrix with entries from a general field, one can modify its Jordan canonical form in the splitting field of its minimal polynomial to construct its rational canonical form in the original field. No author has tried this converse with the a priori existence–uniqueness condition removed. It is feared that “in many occasions when, after a result has been established for a matrix with entries in a given field, considered as a matrix with entries in a finite extension of that field, we cannot go back from the extension field to get the desired information in the original field” [I.N. Herstein, Topics in Algebra, Ginn and Company, Waltham, MA, 1964 (pp. 262–263)]. The present paper removes this a priori condition and uses a “symmetrization” to “integrate” back the Jordan canonical form of a matrix to its rational canonical form in the original field.