Article Contents
Article Contents

# CVaR-based formulation and approximation method for stochastic variational inequalities

• In this paper, we study the stochastic variational inequality problem (SVIP) from a viewpoint of minimization of conditional value-at-risk. We employ the D-gap residual function for VIPs to define a loss function for SVIPs. In order to reduce the risk of high losses in applications of SVIPs, we use the D-gap function and conditional value-at-risk to present a deterministic minimization reformulation for SVIPs. We show that the new reformulation is a convex program under suitable conditions. Furthermore, by using the smoothing techniques and the Monte Carlo methods, we propose a smoothing approximation method for finding a solution of the new reformulation and show that this method is globally convergent with probability one.
Mathematics Subject Classification: Primary: 90C33; Secondary: 90C15.

 Citation:

•  [1] R. P. Agdeppa, N. Yamashita and M. Fukushima, Convex expected residual models for stochastic affine variational inequality problems and its application to the traffic equilibrium problem, Pacific Journal of Optimization, 6 (2010), 3-19. [2] P. Artzner, F. Delbaen, J. M. Eber and D. Heath, Coherent measures of risk, Mathematical Finance, 9 (1999), 203-228.doi: 10.1111/1467-9965.00068. [3] S. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, Cambridge, 2004. [4] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, 5 (1996), 97-138.doi: 10.1007/BF00249052. [5] X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research, 30 (2005), 1022-1038.doi: 10.1287/moor.1050.0160. [6] X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Mathematical Programming, 117 (2009), 51-80.doi: 10.1007/s10107-007-0163-z. [7] R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem," Academic Press, New York, 1992. [8] F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems," Springer-Verlag, New York, 2003. [9] H. Fang, X. Chen and M. Fukushima, Stochastic R$_0$ matrix linear complementarity problems, SIAM Journal on Optimization, 18 (2007), 482-506.doi: 10.1137/050630805. [10] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Programming, 53 (1992), 99-110.doi: 10.1007/BF01585696. [11] M. Fukushima, Merit functions for variational inequality and complementarity problems, in "Nonlinear Optimization and Applications"(eds. G. Di Pillo and F. Giannessi), Plenum Press, New York, 1996, 155-170. [12] G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities, Mathematical Programming, 84 (1999), 313-333.doi: 10.1007/s101070050024. [13] P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220.doi: 10.1007/BF01582255. [14] W. W. Hogan, Point-to-set maps in mathematical programming, SIAM Review, 15 (1973), 591-603.doi: 10.1137/1015073. [15] H. Jiang and H. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Transactions on Automatic Control, 53 (2008), 1462-1475.doi: 10.1109/TAC.2008.925853. [16] I. V. Konnov, "Equilibrium Models and Variational Inequalities," Elsevier, Amsterdam, 2007. [17] D. Kinderlehrer and G. Stampacchia, "An Introduction to Variational Inequalities and Their Applications," Academic Press, New York, 1980. [18] T. Larsson and M. Patriksson, A class of gap functions for variational inequalities, Mathematical Programming, 64 (1994), 53-79.doi: 10.1007/BF01582565. [19] G. H. Lin, Combined Monte Carlo sampling and penalty method for stochastic nonlinear complementarity problems, Mathematics of Computation, 78 (2009), 1671-1686.doi: 10.1090/S0025-5718-09-02206-6. [20] G. H. Lin, X. Chen and M. Fukushima, New restricted NCP function and their applications to stochastic NCP and stochastic MPEC, Optimization, 56 (2007), 641-753.doi: 10.1080/02331930701617320. [21] G. H. Lin and M. Fukushima, New reformulations for stochastic complementarity problems, Optimization Methods and Software, 21 (2006), 551-564.doi: 10.1080/10556780600627610. [22] G. H. Lin and M. Fukushima, Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: A survey, Pacific Journal of Optimization, 6 (2010), 455-482. [23] C. Ling, L. Qi, G. Zhou and L. Caccetta, The $SC^1$ property of an expected residual function arising from stochastic complementarity problems, Operations Research Letters, 36 (2008), 456-460.doi: 10.1016/j.orl.2008.01.010. [24] M. J. Luo and G. H. Lin, Expected residual minimization method for stochastic variational inequality problems, Journal of Optimization Theory and Application, 140 (2009), 103-116.doi: 10.1007/s10957-008-9439-6. [25] M. J. Luo and G. H. Lin, Convergence results of the ERM method for nonlinear stochastic variational inequality problems, Journal of Optimization Theory and Application, 142 (2009), 569-581.doi: 10.1007/s10957-009-9534-3. [26] M. J. Luo and G. H. Lin,  Stochastic variational inequality problems with additional constraints and their applications in supply chain network equilibria, Pacific Journal of Optimization, to appear. [27] J. S. Pang, Complementarity problems, in "Handbook in Global Optimization"}(eds. R. Horst and P. Pardalos, Kluwer Academic Publishers, Boston, 1994. [28] J. M. Peng, Convexity of the implicit Lagrangian, Journal of Optimization Theory and Applications, 92 (1997), 331-341.doi: 10.1023/A:1022607213765. [29] R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions, Journal of Banking and Finance, 26 (2002), 1443-1471.doi: 10.1016/S0378-4266(02)00271-6. [30] R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer, Berlin, 1998.doi: 10.1007/978-3-642-02431-3. [31] R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 493-517. [32] A. Ruszczynski and A. Shapiro, "Stochastic Programming, Handbooks in Operations Research and Management Science," Elsevier, 2003. [33] H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems, Asia-Pacific Journal of Operations Research, 27 (2010), 103-119. [34] H. Xu and D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications, Mathematical Programming, 119 (2009), 371-401.doi: 10.1007/s10107-008-0214-0. [35] N. Yamashita, K. Taji and M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, Journal of Optimization Theory and Applications, 92 (1997), 439-456.doi: 10.1023/A:1022660704427. [36] C. Zhang and X. Chen, Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty, Journal of Optimization Theory and Applications, 137 (2008), 277-295.doi: 10.1007/s10957-008-9358-6. [37] C. Zhang, X. Chen and A. Sumalee, Robust Wardrops user equilibrium assignment under stochastic demand and supply: expected residual minimization approach, Transportation Research Part B, 2010 (Online first). [38] G. L. Zhou and L. Caccetta, Feasible semismooth Newton method for a class of stochastic linear complementarity problems, Journal of Optimization Theory and Applications, 139 (2008), 379-392.doi: 10.1007/s10957-008-9406-2.