Sample average approximation of conditional value-at-risk based variational inequalities
From MaRDI portal
Publication:6191978
DOI10.1007/S11590-023-01996-9arXiv2208.11403OpenAlexW4362666384MaRDI QIDQ6191978FDOQ6191978
Authors: Ashish Cherukuri 
Publication date: 11 March 2024
Published in: Optimization Letters (Search for Journal in Brave)
Abstract: This paper focuses on a class of variational inequalities (VIs), where the map defining the VI is given by the component-wise conditional value-at-risk (CVaR) of a random function. We focus on solving the VI using sample average approximation, where solutions of the VI are estimated with solutions of a sample average VI that uses empirical estimates of the CVaRs. We establish two properties for this scheme. First, under continuity of the random map and the uncertainty taking values in a bounded set, we prove asymptotic consistency, establishing almost sure convergence of the solution of the sample average problem to the true solution. Second, under the additional assumption of random functions being Lipschitz, we prove exponential convergence where the probability of the distance between an approximate solution and the true solution being smaller than any constant approaches unity exponentially fast. The exponential decay bound is refined for the case where random functions have a specific separable form in the decision variable and uncertainty. We adapt these results to the case of uncertain routing games and derive explicit sample guarantees for obtaining a CVaR-based Wardrop equilibria using the sample average procedure. We illustrate our theoretical findings by approximating the CVaR-based Wardrop equilibria for a modified Sioux Falls network.
Full work available at URL: https://arxiv.org/abs/2208.11403
Recommendations
- CVaR-based formulation and approximation method for stochastic variational inequalities
- CVaR-based formulation and approximation method for a class of stochastic variational inequality problems
- Sample average approximation method for a class of stochastic variational inequality problems
- Sample average approximation methods for a class of stochastic variational inequality problems
- Stochastic variational inequalities: residual minimization smoothing sample average approximations
Cites Work
- Probability. Theory and examples.
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Greedy approximation
- Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation
- Sample average approximation methods for a class of stochastic variational inequality problems
- Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming
- Lectures on stochastic programming. Modeling and theory.
- Sample-path solution of stochastic variational inequalities
- Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via conditional value at risk and difference of convex functions
- Stochastic optimization problems with CVaR risk measure and their sample average approximation
- Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming
- On robust solutions to uncertain linear complementarity problems and their variants
- Convergence of stationary points of sample average two-stage stochastic programs: a generalized equation approach
- Varying confidence levels for CVaR risk measures and minimax limits
- A mean-risk model for the traffic assignment problem with stochastic travel times
- Expected shortfall: heuristics and certificates
- Concentration bounds for empirical conditional value-at-risk: the unbounded case
- Deviation inequalities for an estimator of the conditional value-at-risk
This page was built for publication: Sample average approximation of conditional value-at-risk based variational inequalities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6191978)
