Robust stochastic dominance and its application to risk-averse optimization

We introduce a new preference relation in the space of random variables, which we call robust stochastic dominance. We consider stochastic optimization problems where risk-aversion is expressed by a robust stochastic dominance constraint. These are composite semi-infinite optimization problems with constraints on compositions of measures of risk and utility functions. We develop necessary and sufficient conditions of optimality for such optimization problems in the convex case. In the nonconvex case, we derive necessary conditions of optimality under additional smoothness assumptions of some mappings involved in the problem.     

Stochastic optimization on Bayesian nets

In this paper we are concerned with stochastic optimization problems in the case when the joint probability distribution, associated with random parameters, can be described by means of a Bayesian net. In such a case we suggest that the structured nature of the probability distribution can be exploited for designing efficient gradient estimation algorithm. Such gradient estimates can be used within the general framework of stochastic gradient (quasi-gradient) solution procedures in order to solve complex non-linear stochastic optimization problems. We describe a gradient estimation algorithm and present a case study related to the reliability of semiconductor manufacturing together with numerical experiments.     

A model of distributionally robust two-stage stochastic convex programming with linear recourse

We consider distributionally robust two-stage stochastic convex programming problems, in which the recourse problem is linear. Other than analyzing these new models case by case for different ambiguity sets, we adopt a unified form of ambiguity sets proposed by Wiesemann, Kuhn and Sim, and extend their analysis from a single stochastic constraint to the two-stage stochastic programming setting. It is shown that under a standard set of regularity conditions, this class of problems can be converted to a conic optimization problem. Numerical results are presented to show the efficiency of the distributionally robust approach.     

Stochastic uncapacitated hub location

We study stochastic uncapacitated hub location problems in which uncertainty is associated to demands and transportation costs. We show that the stochastic problems with uncertain demands or dependent transportation costs are equivalent to their associated deterministic expected value problem (EVP), in which random variables are replaced by their expectations. In the case of uncertain independent transportation costs, the corresponding stochastic problem is not equivalent to its EVP and specific solution methods need to be developed. We describe a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with a Benders decomposition algorithm to solve problems having stochastic independent transportation costs. Numerical results on a set of instances with up to 50 nodes are reported.     

On nonsmooth and discontinuous problems of stochastic systems optimization

A class of stochastic optimization problems is analyzed that cannot be solved by deterministic and standard stochastic approximation methods. We consider risk-control problems, optimization of stochastic networks and discrete event systems, screening irreversible changes, and pollution control. The results of Ermoliev et al. are extended to the case of stochastic systems and general constraints. It is shown that the concept of stochastic mollifier gradient leads to easily implementable computational procedures for systems with Lipschitz and discontinuous objective functions. New optimality conditions are formulated for designing stochastic search procedures for constrained optimization of discontinuous systems.     

A necessary condition for optimal control of?initial coupled forward-backward stochastic differential equations with?partial information

This paper is concerned with a class of optimal control problems of forward-backward stochastic differential equations. One feature of these problems is that they are in the case of partial information and state equations are coupled at initial time. In terms of a classical convex variational technique, we establish a partial information maximum principle for the foregoing optimization problems. We also work out an example of partial information linear-quadratic optimal control to illustrate the application of the theoretical results; meanwhile, we find a forward-backward stochastic differential filtering equation, which is essentially different from classical forward stochastic filtering equations.     

随机需求的车辆路线问题的新模型

本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。     

Quadratic Control for Stochastic Systems Defined by Evolution Operators and Square Integrable Martingales

The infinite dimensional version of the linear quadratic cost control problem is studied by Curtain and Pritchard [2], Gibson [5] by using Riccati integral equations, instead of differential equations. In the present paper the corresponding stochastic case over a finite horizon is considered. The stochastic perturbations are given by Hilbert valued square integrable martingales and it is shown that the deterministic optimal feedback control is also optimal in the stochastic case. Sufficient conditions are given for the convergence of approximate solutions of optimal control problems.     

Modelli stocastici nella riduzione del rischio sismico

In this paper three problems of seismic risk reduction are discussed. They pertain to three different temporal phases of intervention: the definition of design seismic coefficients (long term), the antiseismic strenghtening of existing constructions (medium term), the alarm for a possible forthcoming earthquake (short term). The characteristics of the stochastic models that can represent these seismic events are different in the three cases: the stochastic process is stationary in the first case, with memory in the second case, with memory and external information in the third case. If a renewal process is assumed in the second case, the other two processes are obtained by adding suitable hypoteses. Finally, it is examined how the stochastic hypotheses affect the evaluation of future damage.     

APPROXIMATION THEOREMS BASED ON RANDOM PARTITIONS FOR STOCHASTIC DIFFERENTIAL EQUATION AND THEIR APPLICATIONS

This kind of problems is discussed:When we use certain smooth approximations of theBrownian motion W as substitutes for it in stochastic line integral and stochastic differentialequation,do these resultant integrals and solutions converge to the original one?Thecorresponding approximation theoroms for two kinds of apprximations are proved,whichare wider than those discussed in[1].Some limit theorems about stochastic line integral andsolutions of stochastic differential equations with respect to random walks are obtained byusing the idea of“embeding a random walk into the Brownian motion”first proposed byA.V.Skorohod.It seems to be remarkable that the method used here is not only effectivefor the one dimensional case,but also for the multi-dimensional case.     

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.     

Assessing mutual funds’ corporate social responsibility: a multistakeholder-AHP based methodology

Currently, stochastic optimization on the one hand and multi-objective optimization on the other hand are rich and well-established special fields of Operations Research. Much less developed, however, is their intersection: the analysis of decision problems involving multiple objectives and stochastically represented uncertainty simultaneously. This is amazing, since in economic and managerial applications, the features of multiple decision criteria and uncertainty are very frequently co-occurring. Part of the existing quantitative approaches to deal with problems of this class apply scalarization techniques in order to reduce a given stochastic multi-objective problem to a stochastic single-objective one. The present article gives an overview over a second strand of the recent literature, namely methods that preserve the multi-objective nature of the problem during the computational analysis. We survey publications assuming a risk-neutral decision maker, but also articles addressing the situation where the decision maker is risk-averse. In the second case, modern risk measures play a prominent role, and generalizations of stochastic orders from the univariate to the multivariate case have recently turned out as a promising methodological tool. Modeling questions as well as issues of computational solution are discussed.     

Stochastic programming with simple integer recourse

Stochastic integer programs are notoriously difficult. Very few properties are known and solution algorithms are very scarce. In this paper, we introduce the class of stochastic programs with simple integer recourse, a natural extension of the simple recourse case extensively studied in stochastic continuous programs.Analytical as well as computational properties of the expected recourse function of simple integer recourse problems are studied. This includes sharp bounds on this function and the study of the convex hull. Finally, a finite termination algorithm is obtained that solves two classes of stochastic simple integer recourse problems.Supported by the National Operations Research Network in the Netherlands (LNMB).     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

Monotonic bounds in multistage mixed-integer stochastic programming

Multistage stochastic programs bring computational complexity which may increase exponentially with the size of the scenario tree in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal value are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. The computational complexity of the proposed lower and upper bounds is discussed and an algorithmic procedure to use them is provided. Numerical results on a real case transportation problem are presented.     

Probability maximization models for portfolio selection under ambiguity

This paper considers several probability maximization models for multi-scenario portfolio selection problems in the case that future returns in possible scenarios are multi-dimensional random variables. In order to consider occurrence probabilities and decision makers’ predictions with respect to all scenarios, a portfolio selection problem setting a weight with flexibility to each scenario is proposed. Furthermore, by introducing aspiration levels to occurrence probabilities or future target profit and maximizing the minimum aspiration level, a robust portfolio selection problem is considered. Since these problems are formulated as stochastic programming problems due to the inclusion of random variables, they are transformed into deterministic equivalent problems introducing chance constraints based on the stochastic programming approach. Then, using a relation between the variance and absolute deviation of random variables, our proposed models are transformed into linear programming problems and efficient solution methods are developed to obtain the global optimal solution. Furthermore, a numerical example of a portfolio selection problem is provided to compare our proposed models with the basic model.     

Scenario reduction for stochastic programs with Conditional Value-at-Risk

In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem easier to solve. The majority of works for scenario reduction are designed for classical risk-neutral stochastic optimization problems; however, it is intuitive that in the risk-averse case one is more concerned with scenarios that correspond to high cost. By building upon the notion of effective scenarios recently introduced in the literature, we formalize that intuitive idea and propose a scenario reduction technique for stochastic optimization problems where the objective function is a Conditional Value-at-Risk. Numerical results presented with problems from the literature illustrate the performance of the method and indicate the cases where we expect it to perform well.     

Forward–Backward Stochastic Differential Games and Stochastic Control under Model Uncertainty

We study optimal stochastic control problems with jumps under model uncertainty. We rewrite such problems as stochastic differential games of forward–backward stochastic differential equations. We prove general stochastic maximum principles for such games, both in the zero-sum case (finding conditions for saddle points) and for the nonzero sum games (finding conditions for Nash equilibria). We then apply these results to study robust optimal portfolio-consumption problems with penalty. We establish a connection between market viability under model uncertainty and equivalent martingale measures. In the case with entropic penalty, we prove a general reduction theorem, stating that a optimal portfolio-consumption problem under model uncertainty can be reduced to a classical portfolio-consumption problem under model certainty, with a change in the utility function, and we relate this to risk sensitive control. In particular, this result shows that model uncertainty increases the Arrow–Pratt risk aversion index.     

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.     

A chance-constrained approach to stochastic line balancing problem

In this paper, chance-constrained 0–1 integer programming models for the stochastic traditional and U-type line balancing (ULB) problem are developed. These models are solved for several test problems that are well known in the literature and the computational results are given. In addition, a goal programming approach is presented in order to increase the system reliability, which is arising from the stochastic case.