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.     

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.     

Lower semicontinuity of the solution map to a parametric vector variational inequality

This paper is concerned with the study of solution stability of a parametric vector variational inequality, where mappings may not be strongly monotone. Under some requirements that the operator of a unperturbed problem is monotone or it satisfies degree conditions then we show that the solution map of a parametric vector variational inequality is lower semicontinuous.     

Two-stage stochastic variational inequalities: an ERM-solution procedure

We propose a two-stage stochastic variational inequality model to deal with random variables in variational inequalities, and formulate this model as a two-stage stochastic programming with recourse by using an expected residual minimization solution procedure. The solvability, differentiability and convexity of the two-stage stochastic programming and the convergence of its sample average approximation are established. Examples of this model are given, including the optimality conditions for stochastic programs, a Walras equilibrium problem and Wardrop flow equilibrium. We also formulate stochastic traffic assignments on arcs flow as a two-stage stochastic variational inequality based on Wardrop flow equilibrium and present numerical results of the Douglas–Rachford splitting method for the corresponding two-stage stochastic programming with recourse.     

Stability and Sensitivity Analysis of Solutions to Weak Vector Variational Inequalities

The paper mainly concerns the study of a parametric weak vector variational inequality. Robinson’s metric regularity and Lipschitzian stability of the solution mapping for the parametric weak vector variational inequality are firstly established. Then sensitivity analysis of the solution mapping for the parametric weak vector variational inequality is discussed. As applications, Lipschitzian continuity and differentiability of the solution mapping are also investigated for a parametric variational inequality.     

Lower semicontinuity of the solution map to a parametric elliptic optimal control problem with mixed pointwise constraints

This paper studies the solution stability of a parametric optimal control problem governed by single linear elliptic equations with mixed control-state constraints and convex cost functions. By reducing the problem to a parametric programming problem and a parametric variational inequality, we obtain sufficient conditions under which the solution map to an elliptic optimal control problem is lower semicontinuous.     

Lower Semicontinuity of the Solution Map to a Parametric Generalized Variational Inequality in Reflexive Banach Spaces

This paper is concerned with the study of solution stability of a parametric generalized variational inequality in reflexive Banach spaces. Under the requirements that the operator of a unperturbed problem is of class (S)_?+? and operators under consideration are pseudo-monotone and demicontinuous, we show that the solution map of a parametric generalized variational inequality is lower semicontinuous. The obtained results are proved without conditions related to the degree theory and the metric projection.     

Expected Residual Minimization Formulation for a Class of Stochastic Vector Variational Inequalities

This paper considers a class of vector variational inequalities. First, we present an equivalent formulation, which is a scalar variational inequality, for the deterministic vector variational inequality. Then we concentrate on the stochastic circumstance. By noting that the stochastic vector variational inequality may not have a solution feasible for all realizations of the random variable in general, for tractability, we employ the expected residual minimization approach, which aims at minimizing the expected residual of the so-called regularized gap function. We investigate the properties of the expected residual minimization problem, and furthermore, we propose a sample average approximation method for solving the expected residual minimization problem. Comprehensive convergence analysis for the approximation approach is established as well.     

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.     

Two-Stage Stochastic Variational Inequality Arising from Stochastic Programming

We consider a two-stage stochastic variational inequality arising from a general convex two-stage stochastic programming problem, where the random variables have continuous distributions. The equivalence between the two problems is shown under some moderate conditions, and the monotonicity of the two-stage stochastic variational inequality is discussed under additional conditions. We provide a discretization scheme with convergence results and employ the progressive hedging method with double parameterization to solve the discretized stochastic variational inequality. As an application, we show how the water resources management problem under uncertainty can be transformed from a two-stage stochastic programming problem to a two-stage stochastic variational inequality, and how to solve it, using the discretization scheme and the progressive hedging method with double parameterization.

     

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.     

Gap functions for constrained vector variational inequalities with applications

In this paper, the image space analysis is applied to investigate scalar-valued gap functions and their applications for a (parametric)-constrained vector variational inequality. Firstly, using a non-linear regular weak separation function in image space, a gap function of a constrained vector variational inequality is obtained without any assumptions. Then, as an application of the gap function, two error bounds for the constrained vector variational inequality are derived by means of the gap function under some mild assumptions. Further, a parametric gap function of a parametric constrained vector variational inequality is presented. As an application of the parametric gap function, a sufficient condition for the continuity of the solution map of the parametric constrained vector variational inequality is established within the continuity and strict convexity of the parametric gap function. These assumptions do not include any information on the solution set of the parametric constrained vector variational inequality.     

Iterative Algorithm for Solving Triple-Hierarchical Constrained Optimization Problem

Many practical problems such as signal processing and network resource allocation are formulated as the monotone variational inequality over the fixed point set of a nonexpansive mapping, and iterative algorithms to solve these problems have been proposed. This paper discusses a monotone variational inequality with variational inequality constraint over the fixed point set of a nonexpansive mapping, which is called the triple-hierarchical constrained optimization problem, and presents an iterative algorithm for solving it. Strong convergence of the algorithm to the unique solution of the problem is guaranteed under certain assumptions.     

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.     

关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注

Yair Censor,Aviv Gibali和Simeon Reich为求解变分不等式问题提出了 2-次梯度外梯度算法.关于此算法的收敛性,作者给出了部分证明,有一个问题:由算法产生的迭代点列能否收敛到变分不等式问题的一个解上,没有得到解决.此问题作为一个公开问题在文章"Extensions of Korpelevi...     

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.     

Two algorithms for solving single-valued variational inequalities and fixed point problems

In this paper, we suggest two new iterative methods for finding a common element of the solution set of a variational inequality problem and the set of fixed points of a contraction mapping in Hilbert space. We also present weak and strong convergence theorems for these new methods, provided that the fixed point mapping is a θ-strict pseudocontraction and the mapping associated with the variational inequality problem is monotone. The results presented in this paper improve and unify important recent results announced by many authors.     

Stability of weak vector variational inequality

In this paper, a key assumption is introduced by virtue of a parametric gap function. Then, by using the key assumption, sufficient conditions of the continuity and Hausdorff continuity of a solution set map for a parametric weak vector variational inequality are obtained in Banach spaces with the objective space being finite-dimensional.     

Weak convergence theorem for zero points of inverse strongly monotone mapping and fixed points of nonexpansive mapping in Hilbert space

We know that variational inequality problem is very important in the nonlinear analysis. For a variational inequality problem defined over a nonempty fixed point set of a nonexpansive mapping in Hilbert space, the strong convergence theorem has been proposed by I. Yamada. The algorithm in this theorem is named the hybrid steepest descent method. Based on this method, we propose a new weak convergence theorem for zero points of inverse strongly monotone mapping and fixed points of nonexpansive mapping in Hilbert space. Using this result, we obtain some new weak convergence theorems which are useful in nonlinear analysis and optimization 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.