Random-Direction Optimization Algorithms with Applications to Threshold Controls

This work develops a class of stochastic optimization algorithms. It aims to provide numerical procedures for solving threshold-type optimal control problems. The main motivation stems from applications involving optimal or suboptimal hedging policies, for example, production planning of manufacturing systems including random demand and stochastic machine capacity. The proposed algorithm is a constrained stochastic approximation procedure that uses random-direction finite-difference gradient estimates. Under fairly general conditions, the convergence of the algorithm is established and the rate of convergence is also derived. A numerical example is reported to demonstrate the performance of the algorithm.     

Local strong solutions to the stochastic compressible Navier–Stokes system

We study the Navier–Stokes system describing the motion of a compressible viscous fluid driven by a nonlinear multiplicative stochastic force. We establish local in time existence (up to a positive stopping time) of a unique solution, which is strong in both PDE and probabilistic sense. Our approach relies on rewriting the problem as a symmetric hyperbolic system augmented by partial diffusion, which is solved via a suitable approximation procedure. We use the stochastic compactness method and the Yamada–Watanabe type argument based on the Gyöngy–Krylov characterization of convergence in probability. This leads to the existence of a strong (in the PDE sense) pathwise solution. Finally, we use various stopping time arguments to establish the local existence of a unique strong solution to the original problem.     

Highly Accurate Numerical Schemes for Stochastic Optimal Control via FBSDEs

This work is concerned with numerical schemes for stochastic optimal control problems (SOCPs) by means of forward backward stochastic differential equations (FBSDEs). We first convert the stochastic optimal control problem into an equivalent stochastic optimality system of FBSDEs. Then we design an efficient second order FBSDE solver and an quasi-Newton type optimization solver for the resulting system. It is noticed that our approach admits the second order rate of convergence even when the state equation is approximated by the Euler scheme. Several numerical examples are presented to illustrate the effectiveness and the accuracy of the proposed numerical schemes.     

随机规划中的一些逼近结果

主要讨论了一类随机规划的目标函数分别在概率测度序列分布收敛、函数序列上图收敛以及随机变量序列均方可积收敛等收敛意义下目标函数序列的收敛情况。基于上述收敛情况给出了一些逼近思想，这些思想可应用于求解这类随机规划问题。     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Variational Inequality

The aim of this paper is to investigate the convergence properties for Mordukhovich’s coderivative of the solution map of the sample average approximation (SAA) problem for a parametric stochastic variational inequality with equality and inequality constraints. The notion of integrated deviation is introduced to characterize the outer limit of a sequence of sets. It is demonstrated that, under suitable conditions, both the cosmic deviation and the integrated deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic variational inequality converge almost surely to zero as the sample size tends to infinity. Moreover, the exponential convergence rate of coderivatives of the solution maps to the SAA parametric stochastic variational inequality is established. The results are used to develop sufficient conditions for the consistency of the Lipschitz-like property of the solution map of SAA problem and the consistency of stationary points of the SAA estimator for a stochastic bilevel program.     

Enhancing Stochastic Search Performance by Value-Biased Randomization of Heuristics

This paper investigates the utility of introducing randomization as a means of boosting the performance of search heuristics. We introduce a particular approach to randomization, called Value-biased stochastic sampling (VBSS), which emphasizes the use of heuristic value in determining stochastic bias. We offer an empirical study of the performance of value-biased and rank-biased approaches to randomizing search heuristics. We also consider the use of these stochastic sampling techniques in conjunction with local hill-climbing. Finally, we contrast the performance of stochastic sampling search with more systematic search procedures as a means of amplifying the performance of search heuristics.     

Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems

Several exponential bounds are derived by means of the theory of large deviations for the convergence of approximate solutions of stochastic optimization problems. The basic results show that the solutions obtained by replacing the original distribution by an empirical distribution provides an effective tool for solving stochastic programming problems.Supported in part by a grant from the US-Israel Science Foundation.     

Stochastic optimization with averaging of trajectories

A recursive stochastic optimization procedure under dependent disturbances is studied. It is based on the Polyak-Ruppert algorithm with trajectory averaging. Almost sure convergence of the algorithm is proved as well as asymptotic normality of the delivered estimates. It is shown that the presented algorithm attains the highest possible asymptotic convergence rate for stochastic approximation algorithms     

A sequential data assimilation method based on the properties of a diffusion-type process

Data assimilation method, as commonly used in numerical ocean and atmospheric circulation models, produces an estimation of state variables in terms of stochastic processes. This estimation is based on limit properties of a diffusion-type process which follows from the convergence of a sequence of Markov chains with jumps. The conditions for this convergence are investigated. The optimisation problem and the optimal filtering problem associated with the search of the best possible approximation of the true state variable are posed and solved. The results of a simple numerical experiment are discussed. It is shown that the proposed data assimilation method works properly and can be used in practical applications, particularly in meteorology and oceanography.     

Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming

Sample average approximation (SAA) is one of the most popular methods for solving stochastic optimization and equilibrium problems. Research on SAA has been mostly focused on the case when sampling is independent and identically distributed (iid) with exceptions (Dai et al. (2000) [9], Homem-de-Mello (2008) [16]). In this paper we study SAA with general sampling (including iid sampling and non-iid sampling) for solving nonsmooth stochastic optimization problems, stochastic Nash equilibrium problems and stochastic generalized equations. To this end, we first derive the uniform exponential convergence of the sample average of a class of lower semicontinuous random functions and then apply it to a nonsmooth stochastic minimization problem. Exponential convergence of estimators of both optimal solutions and M-stationary points (characterized by Mordukhovich limiting subgradients (Mordukhovich (2006) [23], Rockafellar and Wets (1998) [32])) are established under mild conditions. We also use the unform convergence result to establish the exponential rate of convergence of statistical estimators of a stochastic Nash equilibrium problem and estimators of the solutions to a stochastic generalized equation problem.     

Convergence results for continuous-time adaptive stochastic filtering algorithms

The adaptive stochastic filtering problem for Gaussian processes is considered. The self-tuning synthesis procedure is used to derive two algorithms for this problem. Almost sure convergence for the parameter estimate and the filtering error will be established. The convergence analysis is based on an almost-supermartingale convergence lemma that allows a stochastic Lyapunov-like approach.     

差异驱动型评价方法的稳定性及差异凸显能力比较

针对综合评价中方法种类繁多且无统一比较标准的问题,选取了四种突出被评价对象之间差异的评价方法,采用随机模拟的方式分别从评价方法的稳定性及对差异的凸显能力两个方面进行了比较分析。得出了四种方法稳定性由高到低分别为均方差法、最大离差法、熵值法、拉开档次法,且评价方法的稳定性越高,则其对差异的凸显能力反而越差的结论。该研究不仅验证了差异驱动型评价方法的相关特性,为评价者关于评价方法的选取提供了参考意见,而且随机模拟方法的应用,可为类似的多评价方法的比较问题提供技术参考。     

Bi-objective project portfolio selection and staff assignment under uncertainty

We formulate a project portfolio selection problem under uncertainty with two optimization criteria: a weighted average of economic and strategic gains, and a risk measure expressed as the expected total overtime cost. The optimal assignment of personnel with given skills to the tasks of the selected projects is incorporated as a subproblem. Searching for Pareto-optimal portfolios satisfying the given constraints amounts to a stochastic multi-objective combinatorial optimization problem, a problem type for which only a few general solution approaches are available at present. We apply a recently developed technique called adaptive Pareto sampling, solve a linear subproblem with an LP solver and use the NSGA-II algorithm for deterministic multi-objective optimization as an auxiliary procedure. A convergence result applicable in a more general context is also shown. To obtain objective function estimates, importance sampling is applied. The technique is tested on a benchmark derived from a real-world application case provided by the E-Commerce Competence Center Austria.     

Computational scheme for solving nonlinear fractional stochastic differential equations with delay

Abstract

This paper studies the numerical solution of fractional stochastic delay differential equations driven by Brownian motion. The proposed algorithm is based on linear B-spline interpolation. The convergence and the numerical performance of the method are analyzed. The technique is adopted for determining the statistical indicators of stochastic responses of fractional Langevin and Mackey-Glass models with stochastic excitations.     

Large deviations for the 3D stochastic Navier-Stokes-Voight equations

In this paper, using the weak convergence method, a large deviation principle for 3D stochastic Navier–Stokes–Voight equations is proved.     

On the Convergence of Sampling-Based Decomposition Algorithms for Multistage Stochastic Programs

The paper presents a convergence proof for a broad class of sampling algorithms for multistage stochastic linear programs in which the uncertain parameters occur only in the constraint right-hand sides. This class includes SDDP, AND, ReSa, and CUPPS. We show that, under some independence assumptions on the sampling procedure, the algorithms converge with probability 1.The first author acknowledges support by the Swiss National Science Foundation. The second author acknowledges support by NZPGST Grant UOAX0203. The authors are grateful to the anonymous referees for comments improving the exposition of this paper.     

A New Chance-Constrained Maximum Capture Location Problem

The paper presents a new model based on the basic Maximum Capture model, MAXCAP. The new Chance-Constrained Maximum Capture model introduces a stochastic threshold constraint, which recognises the fact that a facility can be open only if a minimum level of demand is captured. A metaheuristic based on Max-Min Ant System and Tabu Search procedure is presented to solve the model. This is the first time that the Max-Min Ant system is adapted to solve a location problem. Computational experience and an application to 55-node network are also presented.     

Runge–Kutta Methods for Itô Stochastic Differential Equations with Scalar Noise

A general class of stochastic Runge–Kutta methods for Itô stochastic differential equation systems w.r.t. a one-dimensional Wiener process is introduced. The colored rooted tree analysis is applied to derive conditions for the coefficients of the stochastic Runge–Kutta method assuring convergence in the weak sense with a prescribed order. Some coefficients for new stochastic Runge–Kutta schemes of order two are calculated explicitly and a simulation study reveals their good performance.     

The Stochastic Location-Assignment Problem on a Tree

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.     

Production planning with discounting and stochastic demands

A general continuous review production planning problem with stochastic demand is considered. Conditions under which the stochastic problem may be correctly solved using an equivalent deterministic problem are developed. This deterministic problem is known to have the same solution as the stochastic problem. Moreover, conditions are established under which the deterministic equivalent problem differs from a commonly used deterministic approximation to the problem only in the interest rate used in discounting. Thus, solving the stochastic problem is no more difficult than solving a commonly used approximation of the problem.