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.     

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.     

Stochastic Nonlinear Complementarity Problem and?Applications to?Traffic Equilibrium under?Uncertainty

The expected residual minimization (ERM) formulation for the stochastic nonlinear complementarity problem (SNCP) is studied in this paper. We show that the involved function is a stochastic R ₀ function if and only if the objective function in the ERM formulation is coercive under a mild assumption. Moreover, we model the traffic equilibrium problem (TEP) under uncertainty as SNCP and show that the objective function in the ERM formulation is a stochastic R ₀ function. Numerical experiments show that the ERM-SNCP model for TEP under uncertainty has various desirable properties. This work was partially supported by a Grant-in-Aid from the Japan Society for the Promotion of Science. The authors thank Professor Guihua Lin for pointing out an error in Proposition 2.1 on an earlier version of this paper. The authors are also grateful to the referees for their insightful comments.     

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.     

Existence of optimal solutions for general stochastic linear complementarity problems

In this paper we show the solvability of the expected residual minimization (ERM) formulation for the general stochastic linear complementarity problem (SLCP) under mild assumptions. The properties of the ERM formulation are dependent on the choice of NCP functions. We focus on the ERM formulations defined by the “min” NCP function and the penalized FB function, both of which are nonconvex programs on the nonnegative orthant.     

随机P矩阵和随机P0矩阵线性互补问题

定义了随机P矩阵和随机P0矩阵,给出了矩阵为随机P矩阵或随机P0矩阵的充要条件.研究了随机线性互补问题(SLCP)的矩阵为随机P矩阵时,期望残差方法(ERM)解集的有界性.得到了期望矩阵为P矩阵时,(ERM)解集非空有界.并且研究离散情形(ERM)与期望值方法(EV)解的关系,给出了(ERM)解唯一的条件.     

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.     

Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush–Kuhn–Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network.     

Stochastic weighted variational inequalities in non-pivot Hilbert spaces with applications to a transportation model

A class of stochastic weighted variational inequalities in non-pivot Hilbert spaces is proposed. Existence and continuity results are proved. These theoretical results play a prominent role in order to introduce a new weighted transportation model with uncertainty. Moreover, they allow to establish the equivalence between the random weighted equilibrium principle and a suitable stochastic weighted variational inequality. At the end, a numerical model is discussed.     

Stochastic differential reinsurance games with capital injections

This paper investigates a class of reinsurance game problems between two insurance companies under the framework of non-zero-sum stochastic differential games. Both insurers can purchase proportional reinsurance contracts from reinsurance markets and have the option of conducting capital injections. We assume the reinsurance premium is calculated under the generalized variance premium principle. The objective of each insurer is to maximize the expected value that synthesizes the discounted utility of his surplus relative to a reference point, the penalties caused by his own capital injection interventions, and the gains brought by capital injections of his competitor. We prove the verification theorem and derive explicit expressions of the Nash equilibrium strategy by solving the corresponding quasi-variational inequalities. Numerical examples are also conducted to illustrate our results.     

Two-stage non-cooperative games with risk-averse players

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent’s overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent’s risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents’ objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents’ objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players’ optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players’ smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.     

Systems of generalized variational inequalities and their applications ∗

In this paper, we first introduce the system of generalized implicit variational inequalities and prove the existence of its solution. Then we derive existence results for systems of generalized variational and variational like inequalities and system of variational inequalities. As applications, we establish some existence results for a solution to the system of optimization problems which includes the Nash equilibrium problem as a special case     

Generalized solutions of quasi variational inequalities

This paper deals with multivalued quasi variational inequalities with pseudo-monotone and monotone maps. The primary objective of this work is to show that the notion of generalized solutions can be employed to investigate multivalued pseudo-monotone quasi variational inequalities. It is a well-known fact that a quasi variational inequality can conveniently be posed as a fixed point problem through the so-called variational selection. For pseudo-monotone maps, the associated variational selection is a nonconvex map, and the fixed point theorems can only be applied under restrictive assumptions on the data of quasi variational inequalities. On the other hand, the generalized solutions are defined by posing a minimization problem which can be solved by a variant of classical Weierstrass theorem. It turns out that far less restrictive assumptions on the data are needed in this case. To emphasis on the strong difference between a classical solution and a generalized solution, we also give a new existence theorem for quasi variational inequalities with monotone maps. The main existence result is proved under a milder coercivity condition. We also relax a few other conditions from the monotone map. Due to its flexibility, it seems that the notion of generalized solutions can be employed to study quasi variational inequalities for other classes of maps as well.     

一类随机线性互补问题的求法

考虑一类随机互线性补问题的求解方法,目的是通过定义NCP函数来使正则化期望残差最小化.通过拟蒙洛包洛方法产生一系列观察值并且证得离散近似问题最小值解的聚点就是相应随机线性互补问题的期望残差最小值ERM,同时得到利用ERM到解为有界的充分条件.进一步证明ERM法能够得到具有稳定性和最小灵敏度的稳健解.     

Newsvendor solutions via conditional value-at-risk minimization

In this paper, we consider the minimization of the conditional value-at-risk (CVaR), a most preferable risk measure in financial risk management, in the context of the well-known single-period newsvendor problem, which is originally formulated as the maximization of the expected profit or the minimization of the expected cost. We show that downside risk measures including the CVaR are tractable in the problem due to their convexity, and consequently, under mild assumptions on the probability distribution of products’ demand, we provide analytical solutions or linear programming (LP) formulation of the minimization of the CVaR measures defined with two different loss functions. Numerical examples are also exhibited, clarifying the difference among the models analyzed in this paper, and demonstrating the efficiency of the LP solutions.     

Superquantile regression with applications to buffered reliability,uncertainty quantification,and conditional value-at-risk

The paper presents a generalized regression technique centered on a superquantile (also called conditional value-at-risk) that is consistent with that coherent measure of risk and yields more conservatively fitted curves than classical least-squares and quantile regression. In contrast to other generalized regression techniques that approximate conditional superquantiles by various combinations of conditional quantiles, we directly and in perfect analog to classical regression obtain superquantile regression functions as optimal solutions of certain error minimization problems. We show the existence and possible uniqueness of regression functions, discuss the stability of regression functions under perturbations and approximation of the underlying data, and propose an extension of the coefficient of determination R-squared for assessing the goodness of fit. The paper presents two numerical methods for solving the error minimization problems and illustrates the methodology in several numerical examples in the areas of uncertainty quantification, reliability engineering, and financial risk management.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality

We define the concept of reproducible map and show that, whenever the constraint map defining the quasivariational inequality (QVI) is reproducible then one can characterize the whole solution set of the QVI as a union of solution sets of some variational inequalities (VI). By exploiting this property, we give sufficient conditions to compute any solution of a generalized Nash equilibrium problem (GNEP) by solving a suitable VI. Finally, we define the class of pseudo-Nash equilibrium problems, which are (not necessarily convex) GNEPs whose solutions can be computed by solving suitable Nash equilibrium problems.     

Stochastic Mirror Descent Dynamics and Their Convergence in Monotone Variational Inequalities

We examine a class of stochastic mirror descent dynamics in the context of monotone variational inequalities (including Nash equilibrium and saddle-point problems). The dynamics under study are formulated as a stochastic differential equation, driven by a (single-valued) monotone operator and perturbed by a Brownian motion. The system’s controllable parameters are two variable weight sequences, that, respectively, pre- and post-multiply the driver of the process. By carefully tuning these parameters, we obtain global convergence in the ergodic sense, and we estimate the average rate of convergence of the process. We also establish a large deviations principle, showing that individual trajectories exhibit exponential concentration around this average.     

Robust solution of monotone stochastic linear complementarity problems

We consider the stochastic linear complementarity problem (SLCP) involving a random matrix whose expectation matrix is positive semi-definite. We show that the expected residual minimization (ERM) formulation of this problem has a nonempty and bounded solution set if the expected value (EV) formulation, which reduces to the LCP with the positive semi-definite expectation matrix, has a nonempty and bounded solution set. We give a new error bound for the monotone LCP and use it to show that solutions of the ERM formulation are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in SLCP. Numerical examples including a stochastic traffic equilibrium problem are given to illustrate the characteristics of the solutions.