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.     

Monte Carlo methods for mean-risk optimization and portfolio selection

Stochastic programming is a well-known instrument to model many risk management problems in finance. In this paper we consider a stochastic programming model where the objective function is the variance of a random function and the constraint function is the expected value of the random function. Instead of using popular scenario tree methods, we apply the well-known sample average approximation (SAA) method to solve it. An advantage of SAA is that it can be implemented without knowing the distribution of the random data. We investigate the asymptotic properties of statistical estimators obtained from the SAA problem including examining the rate of convergence of optimal solutions of the SAA problem as sample size increases. By using the classical penalty function technique and recent results on uniform exponential convergence of sample average random functions, we show that under some mild conditions the statistical estimator of the optimal solution converges to its true counterpart at an exponential rate. We apply the proposed model and the numerical method to a portfolio management problem and present some numerical results.     

The impact of sampling methods on bias and variance in stochastic linear programs

Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1–19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely to reduce bias.     

A new method to build confidence regions for solutions of stochastic variational inequalities

Stochastic variational inequalities model a large class of equilibrium problems subject to data uncertainty. The true solution to such a problem is usually estimated by a solution to its sample average approximation (SAA) problem. This article proposed a new method to build asymptotically exact confidence regions for the true solution that are computable from the SAA solution.     

A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints

A class of smoothing sample average approximation (SAA) methods is proposed for solving the stochastic mathematical program with complementarity constraints (SMPCC) considered by Birbil et al. [S.I. Birbil, G. Gürkan, O. Listes, Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res. 31 (2006) 739–760]. The almost sure convergence of optimal solutions of the smoothed SAA problem to that of the true problem is established by the notion of epi-convergence in variational analysis. It is demonstrated that, under suitable conditions, any accumulation point of Karash–Kuhn–Tucker points of the smoothed SAA problem is almost surely a kind of stationary point of SMPCC as the sample size tends to infinity. Moreover, under a strong second-order sufficient condition for SMPCC, the exponential convergence rate of the sequence of Karash–Kuhn–Tucker points of the smoothed SAA problem is investigated through an application of Robinson?s stability theory. Some preliminary numerical results are reported to show the efficiency of proposed method.     

Penalized sample average approximation methods for stochastic programs in economic and secure dispatch of a power system

In this paper, we develop a stochastic programming model for economic dispatch of a power system with operational reliability and risk control constraints. By defining a severity-index function, we propose to use conditional value-at-risk (CVaR) for measuring the reliability and risk control of the system. The economic dispatch is subsequently formulated as a stochastic program with CVaR constraint. To solve the stochastic optimization model, we propose a penalized sample average approximation (SAA) scheme which incorporates specific features of smoothing technique and level function method. Under some moderate conditions, we demonstrate that with probability approaching to 1 at an exponential rate with the increase of sample size, the optimal solution of the smoothing SAA problem converges to its true counterpart. Numerical tests have been carried out for a standard IEEE-30 DC power system.     

Convergence theory for nonconvex stochastic programming with an application to mixed logit

Monte Carlo methods have extensively been used and studied in the area of stochastic programming. Their convergence properties typically consider global minimizers or first-order critical points of the sample average approximation (SAA) problems and minimizers of the true problem, and show that the former converge to the latter for increasing sample size. However, the assumption of global minimization essentially restricts the scope of these results to convex problems. We review and extend these results in two directions: we allow for local SAA minimizers of possibly nonconvex problems and prove, under suitable conditions, almost sure convergence of local second-order solutions of the SAA problem to second-order critical points of the true problem. We also apply this new theory to the estimation of mixed logit models for discrete choice analysis. New useful convergence properties are derived in this context, both for the constrained and unconstrained cases, and associated estimates of the simulation bias and variance are proposed. Research Fellow of the Belgian National Fund for Scientific Research     

Stability Analysis of One Stage Stochastic Mathematical Programs with Complementarity Constraints

We study the quantitative stability of the solution sets, optimal value and M-stationary points of one stage stochastic mathematical programs with complementarity constraints when the underlying probability measure varies in some metric probability space. We show under moderate conditions that the optimal solution set mapping is upper semi-continuous and the optimal value function is Lipschitz continuous with respect to probability measure. We also show that the set of M-stationary points as a mapping is upper semi-continuous with respect to the variation of the probability measure. A particular focus is given to empirical probability measure approximation which is also known as sample average approximation (SAA). It is shown that optimal value and M-stationary points of SAA programs converge to their true counterparts with probability one (w.p.1.) at exponential rate as the sample size increases.     

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.     

A smoothing SAA method for a stochastic mathematical program with complementarity constraints

A smoothing sample average approximation (SAA) method based on the log-exponential function is proposed for solving a stochastic mathematical program with complementarity constraints (SMPCC) considered by Birbil et al. (S. I. Birbil, G. Gürkan, O. Listes: Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res. 31 (2006), 739–760). It is demonstrated that, under suitable conditions, the optimal solution of the smoothed SAA problem converges almost surely to that of the true problem as the sample size tends to infinity. Moreover, under a strong second-order sufficient condition for SMPCC, the almost sure convergence of Karash-Kuhn-Tucker points of the smoothed SAA problem is established by Robinson’s stability theory. Some preliminary numerical results are reported to show the efficiency of our method.     

Asymptotic Analysis of Sample Average Approximation for Stochastic Optimization Problems with Joint Chance Constraints via Conditional Value at Risk and Difference of Convex Functions

Conditional Value at Risk (CVaR) has been recently used to approximate a chance constraint. In this paper, we study the convergence of stationary points, when sample average approximation (SAA) method is applied to a CVaR approximated joint chance constrained stochastic minimization problem. Specifically, we prove under some moderate conditions that optimal solutions and stationary points, obtained from solving sample average approximated problems, converge with probability one to their true counterparts. Moreover, by exploiting the recent results on large deviation of random functions and sensitivity results for generalized equations, we derive exponential rate of convergence of stationary points. The discussion is also extended to the case, when CVaR approximation is replaced by a difference of two convex functions (DC-approximation). Some preliminary numerical test results are reported.     

Stochastic Stackelberg differential reinsurance games under time-inconsistent mean–variance framework

We study optimal reinsurance in the framework of stochastic Stackelberg differential game, in which an insurer and a reinsurer are the two players, and more specifically are considered as the follower and the leader of the Stackelberg game, respectively. An optimal reinsurance policy is determined by the Stackelberg equilibrium of the game, consisting of an optimal reinsurance strategy chosen by the insurer and an optimal reinsurance premium strategy by the reinsurer. Both the insurer and the reinsurer aim to maximize their respective mean–variance cost functionals. To overcome the time-inconsistency issue in the game, we formulate the optimization problem of each player as an embedded game and solve it via a corresponding extended Hamilton–Jacobi–Bellman equation. It is found that the Stackelberg equilibrium can be achieved by the pair of a variance reinsurance premium principle and a proportional reinsurance treaty, or that of an expected value reinsurance premium principle and an excess-of-loss reinsurance treaty. Moreover, the former optimal reinsurance policy is determined by a unique, model-free Stackelberg equilibrium; the latter one, though exists, may be non-unique and model-dependent, and depend on the tail behavior of the claim-size distribution to be more specific. Our numerical analysis provides further support for necessity of integrating the insurer and the reinsurer into a unified framework. In this regard, the stochastic Stackelberg differential reinsurance game proposed in this paper is a good candidate to achieve this goal.     

Regularizations for Stochastic Linear Variational Inequalities

This paper applies the Moreau–Yosida regularization to a convex expected residual minimization (ERM) formulation for a class of stochastic linear variational inequalities. To have the convexity of the corresponding sample average approximation (SAA) problem, we adopt the Tikhonov regularization. We show that any cluster point of minimizers of the Tikhonov regularization for the SAA problem is a minimizer of the ERM formulation with probability one as the sample size goes to infinity and the Tikhonov regularization parameter goes to zero. Moreover, we prove that the minimizer is the least \(l_2\) -norm solution of the ERM formulation. We also prove the semismoothness of the gradient of the Moreau–Yosida and Tikhonov regularizations for the SAA problem.     

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.     

Central limit theorem and sample complexity of stationary stochastic programs

In this paper we discuss sample complexity of solving stationary stochastic programs by the Sample Average Approximation (SAA) method. We investigate this in the framework of Optimal Control (in discrete time) setting. In particular we derive a Central Limit Theorem type asymptotics for the optimal values of the SAA problems. The main conclusion is that the sample size, required to attain a given relative error of the SAA solution, is not sensitive to the discount factor, even if the discount factor is very close to one. We consider the risk neutral and risk averse settings. The presented numerical experiments confirm the theoretical analysis.     

Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications

We study sample approximations of chance constrained problems. In particular, we consider the sample average approximation (SAA) approach and discuss the convergence properties of the resulting problem. We discuss how one can use the SAA method to obtain good candidate solutions for chance constrained problems. Numerical experiments are performed to correctly tune the parameters involved in the SAA. In addition, we present a method for constructing statistical lower bounds for the optimal value of the considered problem and discuss how one should tune the underlying parameters. We apply the SAA to two chance constrained problems. The first is a linear portfolio selection problem with returns following a multivariate lognormal distribution. The second is a joint chance constrained version of a simple blending problem. B.K. Pagnoncelli’s research was supported by CAPES and FUNENSEG. S. Ahmed’s research was partly supported by the NSF Award DMI-0133943. A. Shapiro’s research was partly supported by the NSF Award DMI-0619977.     

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.     

Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

Stochastic Multiobjective Optimization: Sample Average Approximation and Applications

We investigate one stage stochastic multiobjective optimization problems where the objectives are the expected values of random functions. Assuming that the closed form of the expected values is difficult to obtain, we apply the well known Sample Average Approximation (SAA) method to solve it. We propose a smoothing infinity norm scalarization approach to solve the SAA problem and analyse the convergence of efficient solution of the SAA problem to the original problem as sample sizes increase. Under some moderate conditions, we show that, with probability approaching one exponentially fast with the increase of sample size, an ϵ-optimal solution to the SAA problem becomes an ϵ-optimal solution to its true counterpart. Moreover, under second order growth conditions, we show that an efficient point of the smoothed problem approximates an efficient solution of the true problem at a linear rate. Finally, we describe some numerical experiments on some stochastic multiobjective optimization problems and report preliminary results.     

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.