• Previous Article
    Recent advances in numerical methods for nonlinear equations and nonlinear least squares
  • NACO Home
  • This Issue
  • Next Article
    Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints
2011, 1(1): 35-48. doi: 10.3934/naco.2011.1.35

CVaR-based formulation and approximation method for stochastic variational inequalities

1. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China

2. 

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Received  August 2010 Revised  November 2010 Published  February 2011

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.
Citation: Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35
References:
[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. Google Scholar

[2]

P. Artzner, F. Delbaen, J. M. Eber and D. Heath, Coherent measures of risk, , Mathematical Finance, 9 (1999), 203. doi: 10.1111/1467-9965.00068. Google Scholar

[3]

S. Boyd and L. Vandenberghe, "Convex Optimization,", Cambridge University Press, (2004). Google Scholar

[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. doi: 10.1007/BF00249052. Google Scholar

[5]

X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Mathematics of Operations Research, 30 (2005), 1022. doi: 10.1287/moor.1050.0160. Google Scholar

[6]

X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems,, Mathematical Programming, 117 (2009), 51. doi: 10.1007/s10107-007-0163-z. Google Scholar

[7]

R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem,", Academic Press, (1992). Google Scholar

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Springer-Verlag, (2003). Google Scholar

[9]

H. Fang, X. Chen and M. Fukushima, Stochastic R$_0$ matrix linear complementarity problems,, SIAM Journal on Optimization, 18 (2007), 482. doi: 10.1137/050630805. Google Scholar

[10]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Mathematical Programming, 53 (1992), 99. doi: 10.1007/BF01585696. Google Scholar

[11]

M. Fukushima, Merit functions for variational inequality and complementarity problems,, in, (1996), 155. Google Scholar

[12]

G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities,, Mathematical Programming, 84 (1999), 313. doi: 10.1007/s101070050024. Google Scholar

[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. doi: 10.1007/BF01582255. Google Scholar

[14]

W. W. Hogan, Point-to-set maps in mathematical programming,, SIAM Review, 15 (1973), 591. doi: 10.1137/1015073. Google Scholar

[15]

H. Jiang and H. Xu, Stochastic approximation approaches to the stochastic variational inequality problem,, IEEE Transactions on Automatic Control, 53 (2008), 1462. doi: 10.1109/TAC.2008.925853. Google Scholar

[16]

I. V. Konnov, "Equilibrium Models and Variational Inequalities,", Elsevier, (2007). Google Scholar

[17]

D. Kinderlehrer and G. Stampacchia, "An Introduction to Variational Inequalities and Their Applications,", Academic Press, (1980). Google Scholar

[18]

T. Larsson and M. Patriksson, A class of gap functions for variational inequalities,, Mathematical Programming, 64 (1994), 53. doi: 10.1007/BF01582565. Google Scholar

[19]

G. H. Lin, Combined Monte Carlo sampling and penalty method for stochastic nonlinear complementarity problems,, Mathematics of Computation, 78 (2009), 1671. doi: 10.1090/S0025-5718-09-02206-6. Google Scholar

[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. doi: 10.1080/02331930701617320. Google Scholar

[21]

G. H. Lin and M. Fukushima, New reformulations for stochastic complementarity problems,, Optimization Methods and Software, 21 (2006), 551. doi: 10.1080/10556780600627610. Google Scholar

[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. Google Scholar

[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. doi: 10.1016/j.orl.2008.01.010. Google Scholar

[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. doi: 10.1007/s10957-008-9439-6. Google Scholar

[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. doi: 10.1007/s10957-009-9534-3. Google Scholar

[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, (). Google Scholar

[27]

J. S. Pang, Complementarity problems,, in, (1994). Google Scholar

[28]

J. M. Peng, Convexity of the implicit Lagrangian,, Journal of Optimization Theory and Applications, 92 (1997), 331. doi: 10.1023/A:1022607213765. Google Scholar

[29]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions,, Journal of Banking and Finance, 26 (2002), 1443. doi: 10.1016/S0378-4266(02)00271-6. Google Scholar

[30]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Springer, (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar

[31]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk,, Journal of Risk, 2 (2000), 493. Google Scholar

[32]

A. Ruszczynski and A. Shapiro, "Stochastic Programming, Handbooks in Operations Research and Management Science,", Elsevier, (2003). Google Scholar

[33]

H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems,, Asia-Pacific Journal of Operations Research, 27 (2010), 103. Google Scholar

[34]

H. Xu and D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications,, Mathematical Programming, 119 (2009), 371. doi: 10.1007/s10107-008-0214-0. Google Scholar

[35]

N. Yamashita, K. Taji and M. Fukushima, Unconstrained optimization reformulations of variational inequality problems,, Journal of Optimization Theory and Applications, 92 (1997), 439. doi: 10.1023/A:1022660704427. Google Scholar

[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. doi: 10.1007/s10957-008-9358-6. Google Scholar

[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). Google Scholar

[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. doi: 10.1007/s10957-008-9406-2. Google Scholar

show all references

References:
[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. Google Scholar

[2]

P. Artzner, F. Delbaen, J. M. Eber and D. Heath, Coherent measures of risk, , Mathematical Finance, 9 (1999), 203. doi: 10.1111/1467-9965.00068. Google Scholar

[3]

S. Boyd and L. Vandenberghe, "Convex Optimization,", Cambridge University Press, (2004). Google Scholar

[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. doi: 10.1007/BF00249052. Google Scholar

[5]

X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Mathematics of Operations Research, 30 (2005), 1022. doi: 10.1287/moor.1050.0160. Google Scholar

[6]

X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems,, Mathematical Programming, 117 (2009), 51. doi: 10.1007/s10107-007-0163-z. Google Scholar

[7]

R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem,", Academic Press, (1992). Google Scholar

[8]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Springer-Verlag, (2003). Google Scholar

[9]

H. Fang, X. Chen and M. Fukushima, Stochastic R$_0$ matrix linear complementarity problems,, SIAM Journal on Optimization, 18 (2007), 482. doi: 10.1137/050630805. Google Scholar

[10]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Mathematical Programming, 53 (1992), 99. doi: 10.1007/BF01585696. Google Scholar

[11]

M. Fukushima, Merit functions for variational inequality and complementarity problems,, in, (1996), 155. Google Scholar

[12]

G. Gürkan, A. Y. Özge and S. M. Robinson, Sample-path solution of stochastic variational inequalities,, Mathematical Programming, 84 (1999), 313. doi: 10.1007/s101070050024. Google Scholar

[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. doi: 10.1007/BF01582255. Google Scholar

[14]

W. W. Hogan, Point-to-set maps in mathematical programming,, SIAM Review, 15 (1973), 591. doi: 10.1137/1015073. Google Scholar

[15]

H. Jiang and H. Xu, Stochastic approximation approaches to the stochastic variational inequality problem,, IEEE Transactions on Automatic Control, 53 (2008), 1462. doi: 10.1109/TAC.2008.925853. Google Scholar

[16]

I. V. Konnov, "Equilibrium Models and Variational Inequalities,", Elsevier, (2007). Google Scholar

[17]

D. Kinderlehrer and G. Stampacchia, "An Introduction to Variational Inequalities and Their Applications,", Academic Press, (1980). Google Scholar

[18]

T. Larsson and M. Patriksson, A class of gap functions for variational inequalities,, Mathematical Programming, 64 (1994), 53. doi: 10.1007/BF01582565. Google Scholar

[19]

G. H. Lin, Combined Monte Carlo sampling and penalty method for stochastic nonlinear complementarity problems,, Mathematics of Computation, 78 (2009), 1671. doi: 10.1090/S0025-5718-09-02206-6. Google Scholar

[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. doi: 10.1080/02331930701617320. Google Scholar

[21]

G. H. Lin and M. Fukushima, New reformulations for stochastic complementarity problems,, Optimization Methods and Software, 21 (2006), 551. doi: 10.1080/10556780600627610. Google Scholar

[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. Google Scholar

[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. doi: 10.1016/j.orl.2008.01.010. Google Scholar

[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. doi: 10.1007/s10957-008-9439-6. Google Scholar

[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. doi: 10.1007/s10957-009-9534-3. Google Scholar

[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, (). Google Scholar

[27]

J. S. Pang, Complementarity problems,, in, (1994). Google Scholar

[28]

J. M. Peng, Convexity of the implicit Lagrangian,, Journal of Optimization Theory and Applications, 92 (1997), 331. doi: 10.1023/A:1022607213765. Google Scholar

[29]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions,, Journal of Banking and Finance, 26 (2002), 1443. doi: 10.1016/S0378-4266(02)00271-6. Google Scholar

[30]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Springer, (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar

[31]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk,, Journal of Risk, 2 (2000), 493. Google Scholar

[32]

A. Ruszczynski and A. Shapiro, "Stochastic Programming, Handbooks in Operations Research and Management Science,", Elsevier, (2003). Google Scholar

[33]

H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems,, Asia-Pacific Journal of Operations Research, 27 (2010), 103. Google Scholar

[34]

H. Xu and D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications,, Mathematical Programming, 119 (2009), 371. doi: 10.1007/s10107-008-0214-0. Google Scholar

[35]

N. Yamashita, K. Taji and M. Fukushima, Unconstrained optimization reformulations of variational inequality problems,, Journal of Optimization Theory and Applications, 92 (1997), 439. doi: 10.1023/A:1022660704427. Google Scholar

[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. doi: 10.1007/s10957-008-9358-6. Google Scholar

[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). Google Scholar

[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. doi: 10.1007/s10957-008-9406-2. Google Scholar

[1]

Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977

[2]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333

[3]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

[4]

Lori Badea, Marius Cocou. Approximation results and subspace correction algorithms for implicit variational inequalities. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1507-1524. doi: 10.3934/dcdss.2013.6.1507

[5]

Yusuke Murase, Atsushi Kadoya, Nobuyuki Kenmochi. Optimal control problems for quasi-variational inequalities and its numerical approximation. Conference Publications, 2011, 2011 (Special) : 1101-1110. doi: 10.3934/proc.2011.2011.1101

[6]

Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial & Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467

[7]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533

[8]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1

[9]

George Avalos, Thomas J. Clark. A mixed variational formulation for the wellposedness and numerical approximation of a PDE model arising in a 3-D fluid-structure interaction. Evolution Equations & Control Theory, 2014, 3 (4) : 557-578. doi: 10.3934/eect.2014.3.557

[10]

Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial & Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191

[11]

Esther S. Daus, Shi Jin, Liu Liu. Spectral convergence of the stochastic galerkin approximation to the boltzmann equation with multiple scales and large random perturbation in the collision kernel. Kinetic & Related Models, 2019, 12 (4) : 909-922. doi: 10.3934/krm.2019034

[12]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems & Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81

[13]

Giacomo Dimarco. The moment guided Monte Carlo method for the Boltzmann equation. Kinetic & Related Models, 2013, 6 (2) : 291-315. doi: 10.3934/krm.2013.6.291

[14]

Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219

[15]

Ugo Bessi. The stochastic value function in metric measure spaces. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076

[16]

Nikolai Dokuchaev. On strong causal binomial approximation for stochastic processes. Discrete & Continuous Dynamical Systems - B, 2014, 19 (6) : 1549-1562. doi: 10.3934/dcdsb.2014.19.1549

[17]

Jiakou Wang, Margaret J. Slattery, Meghan Henty Hoskins, Shile Liang, Cheng Dong, Qiang Du. Monte carlo simulation of heterotypic cell aggregation in nonlinear shear flow. Mathematical Biosciences & Engineering, 2006, 3 (4) : 683-696. doi: 10.3934/mbe.2006.3.683

[18]

Michael B. Giles, Kristian Debrabant, Andreas Rössler. Analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3881-3903. doi: 10.3934/dcdsb.2018335

[19]

Zhi-Min Chen. Straightforward approximation of the translating and pulsating free surface Green function. Discrete & Continuous Dynamical Systems - B, 2014, 19 (9) : 2767-2783. doi: 10.3934/dcdsb.2014.19.2767

[20]

Giovanni Colombo, Thuy T. T. Le. Higher order discrete controllability and the approximation of the minimum time function. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4293-4322. doi: 10.3934/dcds.2015.35.4293

 Impact Factor: 

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]