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.     

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.     

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.     

Metric regularity of a positive order for generalized equations

This paper focuses on the metric regularity of a positive order for generalized equations. More concretely, we establish verifiable sufficient conditions for a generalized equation to achieve the metric regularity of a positive order at its a given solution. The provided conditions are expressed in terms of the Fréchet coderivative/or the Mordukhovich coderivative/or the Clarke one of the corresponding multifunction formulated the generalized equation. In addition, we show that such sufficient conditions turn out to be also necessary for the metric regularity of a positive order of the generalized equation in the case where the multifunction established the generalized equation is closed and convex.     

Lipschitz-like property of an implicit multifunction and its applications

The aim of this work is twofold. First, we use the advanced tools of modern variational analysis and generalized differentiation to study the Lipschitz-like property of an implicit multifunction. More explicitly, new sufficient conditions in terms of the Fréchet coderivative and the normal/Mordukhovich coderivative of parametric multifunctions for this implicit multifunction to have the Lipschitz-like property at a given point are established. Then we derive sufficient conditions ensuring the Lipschitz-like property of an efficient solution map in parametric vector optimization problems by employing the above implicit multifunction results.     

Coderivatives in parametric optimization

We consider parametric families of constrained problems in mathematical programming and conduct a local sensitivity analysis for multivalued solution maps. Coderivatives of set-valued mappings are our basic tool to analyze the parametric sensitivity of either stationary points or stationary point-multiplier pairs associated with parameterized optimization problems. An implicit mapping theorem for coderivatives is one key to this analysis for either of these objects, and in addition, a partial coderivative rule is essential for the analysis of stationary points. We develop general results along both of these lines and apply them to study the parametric sensitivity of stationary points alone, as well as stationary point-multiplier pairs. Estimates are computed for the coderivative of the stationary point multifunction associated with a general parametric optimization model, and these estimates are refined and augmented by estimates for the coderivative of the stationary point-multiplier multifunction in the case when the constraints are representable in a special composite form. When combined with existing coderivative formulas, our estimates are entirely computable in terms of the original data of the problem. Key words.parametric optimization – variational analysis – sensitivity – Lipschitzian stability – generalized differentiation – coderivativesThis research was partly supported by the National Science Foundation under grant DMS-0072179.     

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.     

Local behavior of an iterative framework for generalized equations with nonisolated solutions

 An iterative framework for solving generalized equations with nonisolated solutions is presented. For generalized equations with the structure , where is a multifunction and F is single-valued, the framework covers methods that, at each step, solve subproblems of the type . The multifunction approximates F around s. Besides a condition on the quality of this approximation, two other basic assumptions are employed to show Q-superlinear or Q-quadratic convergence of the iterates to a solution. A key assumption is the upper Lipschitz-continuity of the solution set map of the perturbed generalized equation . Moreover, the solvability of the subproblems is required. Conditions that ensure these assumptions are discussed in general and by means of several applications. They include monotone mixed complementarity problems, Karush-Kuhn-Tucker systems arising from nonlinear programs, and nonlinear equations. Particular results deal with error bounds and upper Lipschitz-continuity properties for these problems. Received: November 2001 / Accepted: November 2002 Published online: December 9, 2002 Key Words. generalized equation – nonisolated solutions – Newton's method – superlinear convergence – upper Lipschitz-continuity – mixed complementarity problem – error bounds Mathematics Subject Classification (1991): 90C30, 65K05, 90C31, 90C33     

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.     

On the Transfer of Generalized Functions by an Evolution Flow

We investigate properties of a solution of a stochastic differential equation with interaction and their dependence on a space variable. It is shown that x(u, t) − u belongs to S under certain conditions imposed on the coefficients, and, furthermore, it depends continuously on the initial measure as an element of S. We also study the problem of the existence of a solution of the equation governed by a generalized function. __________ Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 8, pp. 1020 – 1029, August, 2005.     

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.     

Solution of boundary-value problems for elliptic equations in the space of distributions

We extend the well-known approach to solution of generalized boundary-value problems for second-order elliptic and parabolic equations and for second-order strongly elliptic systems of variational type to the case of a general normal boundary-value problem for an elliptic equation of order2m. The representation of a distribution from (C ^∞ (S))’ is established and is usedfor the proof of convergence of an approximate method of solution of a normal elliptic boundary-value problem in unnormed spaces of distributions.     

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.     

Well-posedness and stability of solutions for set optimization problems

In this paper, some characterizations for the generalized l-B-well-posedness and the generalized u-B-well-posedness of set optimization problems are given. Moreover, the Hausdorff upper semi-continuity of l-minimal solution mapping and u-minimal solution mapping are established by assuming that the set optimization problem is l-H-well-posed and u-H-well-posed, respectively. Finally, the upper semi-continuity and the lower semi-continuity of solution mappings to parametric set optimization problems are investigated under some suitable conditions.     

On Stability of M-stationary Points in MPCCs

We consider parameterized Mathematical Programs with Complementarity Constraints arising, e.g., in modeling of deregulated electricity markets. Using the standard rules of the generalized differential calculus we analyze qualitative stability of solutions to the respective M-stationarity conditions. In particular, we provide characterizations and criteria for the isolated calmness and the Aubin properties of the stationarity map. To this end, we introduce the second-order limiting coderivative of mappings and provide formulas for this notion and for the graphical derivative of the limiting coderivative in the case of the normal cone mapping to \(\mathbb {R}^{n}_{+}\) .     

Convergence analysis of sample average approximation for a class of stochastic nonlinear complementarity problems: from two-stage to multistage

In this paper, we consider the sample average approximation (SAA) approach for a class of stochastic nonlinear complementarity problems (SNCPs) and study the corresponding convergence properties. We first investigate the convergence of the SAA counterparts of two-stage SNCPs when the first-stage problem is continuously differentiable and the second-stage problem is locally Lipschitz continuous. After that, we extend the convergence results to a class of multistage SNCPs whose decision variable of each stage is influenced only by the decision variables of adjacent stages. Finally, some preliminary numerical tests are presented to illustrate the convergence results.

     

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 mathematical programs with equilibrium constraints,modelling and sample average approximation

In this article, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate the structure of both–the lower level equilibrium solution and objective integrand. We show almost sure convergence of optimal values, optimal solutions (both local and global) and generalized Karush–Kuhn–Tucker points of the SAA program to their true counterparts. We also study uniform exponential convergence of the sample average approximations, and as a consequence derive estimates of the sample size required to solve the true problem with a given accuracy. Finally, we present some preliminary numerical test results.     

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.