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.     

Risk-averse feasible policies for large-scale multistage stochastic linear programs

We develop tractable semidefinite programming based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove that this approximation is exact for robust individual chance constraints with concave or (not necessarily concave) quadratic constraint functions, and we demonstrate that the Worst-Case CVaR can be computed efficiently for these classes of constraint functions. Next, we study the Worst-Case CVaR approximation for joint chance constraints. This approximation affords intuitive dual interpretations and is provably tighter than two popular benchmark approximations. The tightness depends on a set of scaling parameters, which can be tuned via a sequential convex optimization algorithm. We show that the approximation becomes essentially exact when the scaling parameters are chosen optimally and that the Worst-Case CVaR can be evaluated efficiently if the scaling parameters are kept constant. We evaluate our joint chance constraint approximation in the context of a dynamic water reservoir control problem and numerically demonstrate its superiority over the two benchmark approximations.     

Stochastic Optimization Problems with CVaR Risk Measure and Their Sample Average Approximation

We provide a refined convergence analysis for the SAA (sample average approximation) method applied to stochastic optimization problems with either single or mixed CVaR (conditional value-at-risk) measures. Under certain regularity conditions, it is shown that any accumulation point of the weak GKKT (generalized Karush-Kuhn-Tucker) points produced by the SAA method is almost surely a weak stationary point of the original CVaR or mixed CVaR optimization problems. In addition, it is shown that, as the sample size increases, the difference of the optimal values between the SAA problems and the original problem tends to zero with probability approaching one exponentially fast.     

A smoothing sample average approximation method for stochastic optimization problems with CVaR risk measure

This paper is concerned with solving single CVaR and mixed CVaR minimization problems. A CHKS-type smoothing sample average approximation (SAA) method is proposed for solving these two problems, which retains the convexity and smoothness of the original problem and is easy to implement. For any fixed smoothing constant ε, this method produces a sequence whose cluster points are weak stationary points of the CVaR optimization problems with probability one. This framework of combining smoothing technique and SAA scheme can be extended to other smoothing functions as well. Practical numerical examples arising from logistics management are presented to show the usefulness of this method.     

Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications

Inspired by a recent work by Alexander et al. (J Bank Finance 30:583–605, 2006) which proposes a smoothing method to deal with nonsmoothness in a conditional value-at-risk problem, we consider a smoothing scheme for a general class of nonsmooth stochastic problems. Assuming that a smoothed problem is solved by a sample average approximation method, we investigate the convergence of stationary points of the smoothed sample average approximation problem as sample size increases and show that w.p.1 accumulation points of the stationary points of the approximation problem are weak stationary points of their counterparts of the true problem. Moreover, under some metric regularity conditions, we obtain an error bound on approximate stationary points. The convergence result is applied to a conditional value-at-risk problem and an inventory control problem.      

Approximating Stationary Points of Stochastic Mathematical Programs with Equilibrium Constraints via Sample Averaging

We investigate sample average approximation of a general class of one-stage stochastic mathematical programs with equilibrium constraints. By using graphical convergence of unbounded set-valued mappings, we demonstrate almost sure convergence of a sequence of stationary points of sample average approximation problems to their true counterparts as the sample size increases. In particular we show the convergence of M(Mordukhovich)-stationary point and C(Clarke)-stationary point of the sample average approximation problem to those of the true problem. The research complements the existing work in the literature by considering a general constraint to be represented by a stochastic generalized equation and exploiting graphical convergence of coderivative mappings.     

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.     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

Approximating stationary points of stochastic optimization problems in Banach space

In this paper, we present a uniform strong law of large numbers for random set-valued mappings in separable Banach space and apply it to analyze the sample average approximation of Clarke stationary points of a nonsmooth one stage stochastic minimization problem in separable Banach space. Moreover, under Hausdorff continuity, we show that with probability approaching one exponentially fast with the increase of sample size, the sample average of a convex compact set-valued mapping converges to its expected value uniformly. The result is used to establish exponential convergence of stationary sequence under some metric regularity conditions.     

Single and multi-period optimal inventory control models with risk-averse constraints

This paper presents some convex stochastic programming models for single and multi-period inventory control problems where the market demand is random and order quantities need to be decided before demand is realized. Both models minimize the expected losses subject to risk aversion constraints expressed through Value at Risk (VaR) and Conditional Value at Risk (CVaR) as risk measures. A sample average approximation method is proposed for solving the models and convergence analysis of optimal solutions of the sample average approximation problem is presented. Finally, some numerical examples are given to illustrate the convergence of the algorithm.     

Distributionally robust chance constrained problem under interval distribution information

This paper is concerned with distributionally robust chance constrained problem under interval distribution information. Using worst-case CVaR approximation, we present a tractable convex programming approximation for distributionally robust individual chance constrained problem under interval sets of mean and covariance information. We prove the worst-case CVaR approximation problem is an exact form of the distributionally robust individual chance constrained problem. Then, our result is applied to worst-case Value-at-Risk optimization problem. Moreover, we discuss the problem under several ambiguous distribution information and investigate tractable approximations for distributionally robust joint chance constrained problem. Finally, we provide an illustrative example to show our results.     

Sample average approximation of expected value constrained stochastic programs

We propose a sample average approximation (SAA) method for stochastic programming problems with expected value constraints. Such problems arise, for example, in portfolio selection with constraints on conditional value-at-risk (CVaR). We provide a convergence analysis and a statistical validation scheme for the proposed method.     

规避风险的多阶段最优库存研究

基于市场需求是随机的,并且在进行市场销售前,就要确定每个阶段的生产数量的背景下,建立了具有规避风险的多阶段库存凸随机规划模型.该模型以最小化损失函数的期望值为目标函数,以规避风险为约束条件,以价值风险(VaR)和条件价值风险(CVaR)为风险度量;采用样本平均近似方法(SAA)求解该模型,并分析样本平均近似方法的收敛性;最后,给出数值结果.     

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.     

On stability in multiobjective programming — A stochastic approach

In this paper we assume that a deterministic multiobjective programming problem is approximated by surrogate problems based on estimations for the objective functions and the constraints. Making use of a large deviations approach, we investigate the behaviour of the constraint sets, the sets of efficient points and the solution sets if the size of the underlying sample tends to infinity. The results are illustrated by applying them to stochastic programming with chance constraints, where (i) the distribution function of the random variable is estimated by the empirical distribution function, (ii) certain parameters have to be estimated.     

半线性抛物最优控制问题全离散插值系数有限元方法的收敛性分析

本文考虑全离散插值系数有限元方法求解半线性抛物最优控制问题,其中控制变量用分片常数函数逼近,状态变量和对偶状态变量用分片线性函数逼近.对于方程中的半线性项,先用插值系数技巧处理,再用牛顿迭代法求解.通过引入一些辅助变量和投影算子,并利用有限元空间的逼近性质,得到半线性抛物最优控制问题插值系数有限元方法的收敛性结果;数值算例结果验证了理论结果的正确性.     

CVaR-constrained stochastic programming reformulation for stochastic nonlinear complementarity problems

We reformulate a stochastic nonlinear complementarity problem as a stochastic programming problem which minimizes an expected residual defined by a restricted NCP function with nonnegative constraints and CVaR constraints which guarantee the stochastic nonlinear function being nonnegative with a high probability. By applying smoothing technique and penalty method, we propose a penalized smoothing sample average approximation algorithm to solve the CVaR-constrained stochastic programming. We show that the optimal solution of the penalized smoothing sample average approximation problem converges to the solution of the corresponding nonsmooth CVaR-constrained stochastic programming problem almost surely. Finally, we report some preliminary numerical test results.     

Call Center Staffing with Simulation and Cutting Plane Methods

We present an iterative cutting plane method for minimizing staffing costs in a service system subject to satisfying acceptable service level requirements over multiple time periods. We assume that the service level cannot be easily computed, and instead is evaluated using simulation. The simulation uses the method of common random numbers, so that the same sequence of random phenomena is observed when evaluating different staffing plans. In other words, we solve a sample average approximation problem. We establish convergence of the cutting plane method on a given sample average approximation. We also establish both convergence, and the rate of convergence, of the solutions to the sample average approximation to solutions of the original problem as the sample size increases. The cutting plane method relies on the service level functions being concave in the number of servers. We show how to verify this requirement as our algorithm proceeds. A numerical example showcases the properties of our method, and sheds light on when the concavity requirement can be expected to hold.     

A stochastic algorithm using one sample point per iteration and diminishing stepsizes

A stochastic algorithm for finding stationary points of real-valued functions defined on a Euclidean space is analyzed. It is based on the Robbins-Monro stochastic approximation procedure. Gradient evaluations are done by means of Monte Carlo simulations. At each iteratex _i , one sample point is drawn from an underlying probability space, based on which the gradient is approximated. The descent direction is against the approximation of the gradient, and the stepsize is 1/i. It is shown that, under broad conditions, w.p.1 if the sequence of iteratesx ₁,x ₂,...generated by the algorithm is bounded, then all of its accumulation points are stationary.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Generalized Equation

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 generalized equation. It is demonstrated that, under suitable conditions, both the cosmic deviation and the ρ-deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic generalized equation 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 generalized equations 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 mathematical program with complementarity constraints.