Robustness in stochastic programs with risk constraints

This paper is a contribution to the robustness analysis for stochastic programs whose set of feasible solutions depends on the probability distribution?P. For various reasons, probability distribution P may not be precisely specified and we study robustness of results with respect to perturbations of?P. The main tool is the contamination technique. For the optimal value, local contamination bounds are derived and applied to robustness analysis of the optimal value of a portfolio performance under risk-shaping CVaR constraints. A?new robust portfolio efficiency test with respect to the second order stochastic dominance criterion is suggested and the contamination methodology is exploited to analyze its resistance with respect to additional scenarios.     

Progressive hedging for stochastic programs with cross-scenario inequality constraints

Computational Management Science - In this paper, we show how progressive hedging may be used to solve stochastic programming problems that involve cross-scenario inequality constraints. In...     

Stability analysis of stochastic programs with second order dominance constraints

In this paper we present a stability analysis of a stochastic optimization problem with stochastic second order dominance constraints. We consider a perturbation of the underlying probability measure in the space of regular measures equipped with pseudometric discrepancy distance (Römisch in Stochastic Programming. Elsevier, Amsterdam, pp 483–554, 2003). By exploiting a result on error bounds in semi-infinite programming due to Gugat (Math Program Ser B 88:255–275, 2000), we show under the Slater constraint qualification that the optimal value function is Lipschitz continuous and the optimal solution set mapping is upper semicontinuous with respect to the perturbation of the probability measure. In particular, we consider the case when the probability measure is approximated by an empirical probability measure and show an exponential rate of convergence of the sequence of optimal solutions obtained from solving the approximation problem. The analysis is extended to the stationary points.     

Iterative estimation maximization for stochastic linear programs with conditional value-at-risk constraints

We present a new algorithm, iterative estimation maximization (IEM), for stochastic linear programs with conditional value-at-risk constraints. IEM iteratively constructs a sequence of linear optimization problems, and solves them sequentially to find the optimal solution. The size of the problem that IEM solves in each iteration is unaffected by the size of random sample points, which makes it extremely efficient for real-world, large-scale problems. We prove the convergence of IEM, and give a lower bound on the number of sample points required to probabilistically bound the solution error. We also present computational performance on large problem instances and a financial portfolio optimization example using an S&P 500 data set.     

Metric regularity and quantitative stability in stochastic programs with probabilistic constraints

Received January 24, 1996 / Revised version received December 24, 1997 Published online October 21, 1998     

Controlled Ornstein-Uhlenbeck process with chance constraints

In Ref. 1, existence and optimality conditions were given for control systems whose dynamics are determined by a linear stochastic differential equation with linear feedback controls; moreover, the state variables satisfy probability constraints. Here, for the simplest case of such a model, the Ornstein-Uhlenbeck velocity process, we evaluate the necessary conditions derived in Ref. 1 and compute a time-optimal control such that a given threshold value > 0 is crossed with probability of at least 1 – .This work was supported by the Sonderforschungsbereiche 21 and 72, University of Bonn, Bonn, West Germany.     

An algorithm for stochastic programs with first-order dominance constraints induced by linear recourse

We derive a cutting plane decomposition method for stochastic programs with first-order dominance constraints induced by linear recourse models with continuous variables in the second stage.     

A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints

We consider distributionally robust two-stage stochastic linear optimization problems with higher-order (say \(p\ge 3\) and even possibly irrational) moment constraints in their ambiguity sets. We suggest to solve the dual form of the problem by a semi-infinite programming approach, which deals with a much simpler reformulation than the conic optimization approach. Some preliminary numerical results are reported.     

General sum games with joint chance constraints

We consider an $n$-player non-cooperative game with continuous strategy sets. The strategy set of each player contains a set of stochastic linear constraints. We model the stochastic linear constraints of each player as a joint chance constraint. We assume that the row vectors of a matrix defining the stochastic constraints of each player are independent and each row vector follows a multivariate normal distribution. Under certain conditions, we show the existence of a Nash equilibrium for this game.     

Numerical methods for stochastic programs with second order dominance constraints with applications to portfolio optimization

Inspired by the successful applications of the stochastic optimization with second order stochastic dominance (SSD) model in portfolio optimization, we study new numerical methods for a general SSD model where the underlying functions are not necessarily linear. Specifically, we penalize the SSD constraints to the objective under Slater’s constraint qualification and then apply the well known stochastic approximation (SA) method and the level function method to solve the penalized problem. Both methods are iterative: the former requires to calculate an approximate subgradient of the objective function of the penalized problem at each iterate while the latter requires to calculate a subgradient. Under some moderate conditions, we show that w.p.1 the sequence of approximated solutions generated by the SA method converges to an optimal solution of the true problem. As for the level function method, the convergence is deterministic and in some cases we are able to estimate the number of iterations for a given precision. Both methods are applied to portfolio optimization problem where the return functions are not necessarily linear and some numerical test results are reported.     

Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization

In this paper, we consider the stochastic mathematical programs with linear complementarity constraints, which include two kinds of models called here-and-now and lower-level wait-and-see problems. We present a combined smoothing implicit programming and penalty method for the problems with a finite sample space. Then, we suggest a quasi-Monte Carlo approximation method for solving a problem with continuous random variables. A comprehensive convergence theory is included as well. We further report numerical results with the so-called picnic vender decision problem.     

Convergence analysis of stationary points in sample average approximation of stochastic programs with second order stochastic dominance constraints

Sample average approximation (SAA) method has recently been applied to solve stochastic programs with second order stochastic dominance (SSD) constraints. In particular, Hu et al. (Math Program 133:171–201, 2012) presented a detailed convergence analysis of $\epsilon $ -optimal values and $\epsilon $ -optimal solutions of sample average approximated stochastic programs with polyhedral SSD constraints. In this paper, we complement the existing research by presenting convergence analysis of stationary points when SAA is applied to a class of stochastic minimization problems with SSD constraints. Specifically, under some moderate conditions we prove that optimal solutions and stationary points obtained from solving sample average approximated problems converge with probability one to their true counterparts. Moreover, by exploiting some recent results on large deviation of random functions and sensitivity analysis of generalized equations, we derive exponential rate of convergence of stationary points.     

Approximate Lagrange multiplier algorithm for stochastic programs with complete recourse: Nonlinear deterministic constraints

In this paper we design an approximation method for solving stochastic programs with complete recourse and nonlinear deterministic constraints. This method is obtained by combining approximation method and Lagrange multiplier algorithm of Bertsekas type. Thus this method has the advantages of both the two.This project is supported by the National Natural Science Foundation of China.     

Stochastic programming problems with generalized integrated chance constraints

If the constraints in an optimization problem are dependent on a random parameter, we would like to ensure that they are fulfilled with a high level of reliability. The most natural way is to employ chance constraints. However, the resulting problem is very hard to solve. We propose an alternative formulation of stochastic programs using penalty functions. The expectations of penalties can be left as constraints leading to generalized integrated chance constraints, or incorporated into the objective as a penalty term. We show that the penalty problems are asymptotically equivalent under quite mild conditions. We discuss applications of sample-approximation techniques to the problems with generalized integrated chance constraints and propose rates of convergence for the set of feasible solutions. We will direct our attention to the case when the set of feasible solutions is finite, which can appear in integer programming. The results are then extended to the bounded sets with continuous variables. Additional binary variables are necessary to solve sample-approximated chance-constrained problems, leading to a large mixed-integer non-linear program. On the other hand, the problems with penalties can be solved without adding binary variables; just continuous variables are necessary to model the penalties. The introduced approaches are applied to the blending problem leading to comparably reliable solutions.     

Convexity of chance constraints with independent random variables

We investigate the convexity of chance constraints with independent random variables. It will be shown, how concavity properties of the mapping related to the decision vector have to be combined with a suitable property of decrease for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels. It turns out that the required decrease can be verified for most prominent density functions. The results are applied then, to derive convexity of linear chance constraints with normally distributed stochastic coefficients when assuming independence of the rows of the coefficient matrix.     

A note on the sample average approximation method for stochastic mathematical programs with complementarity constraints

Meng and Xu (2006) [3] proposed a sample average approximation (SAA) method for solving a class of stochastic mathematical programs with complementarity constraints (SMPCCs). After showing that under some moderate conditions, a sequence of weak stationary points of SAA problems converge to a weak stationary point of the original SMPCC with probability approaching one at exponential rate as the sample size tends to infinity, the authors proposed an open question, that is, whether similar results can be obtained under some relatively weaker conditions. In this paper, we try to answer the open question. Based on the reformulation of stationary condition of MPCCs and new stability results on generalized equations, we present a similar convergence theory without any information of second order derivative and strict complementarity conditions. Moreover, we carry out convergence analysis of the regularized SAA method proposed by Meng and Xu (2006) [3] where the convergence results have not been considered.     

Lifting mathematical programs with complementarity constraints

We present a new smoothing approach for mathematical programs with complementarity constraints, based on the orthogonal projection of a smooth manifold. We study regularity of the lifted feasible set and, since the corresponding optimality conditions are inherently degenerate, introduce a regularization approach involving a novel concept of tilting stability. A correspondence between the C-index in the original problem and the quadratic index in the lifted problem is shown. In particular, a local minimizer of the mathematical program with complementarity constraints may numerically be found by minimization of the lifted, smooth problem. We report preliminary computational experience with the lifting approach.     

Optimization with multivariate stochastic dominance constraints

We consider stochastic optimization problems where risk-aversion is expressed by a stochastic ordering constraint. The constraint requires that a random vector depending on our decisions stochastically dominates a given benchmark random vector. We identify a suitable multivariate stochastic order and describe its generator in terms of von Neumann–Morgenstern utility functions. We develop necessary and sufficient conditions of optimality and duality relations for optimization problems with this constraint. Assuming convexity we show that the Lagrange multipliers corresponding to dominance constraints are elements of the generator of this order, thus refining and generalizing earlier results for optimization under univariate stochastic dominance constraints. Furthermore, we obtain necessary conditions of optimality for non-convex problems under additional smoothness assumptions.     

Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. The first author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science and SRF for ROCS, SEM. The second author’s work was supported in part by the United Kingdom Engineering and Physical Sciences Research Council grant. The third author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.