2012, 2(1): 145-156. doi: 10.3934/naco.2012.2.145

A class of smoothing SAA methods for a stochastic linear complementarity problem

1. 

School of Mathematics, Liaoning Normal University, Dalian, 116029, China

2. 

School of Management, University of Southampton, Highfield Southampton SO17 1BJ, United Kingdom

3. 

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

Received  January 2011 Revised  October 2011 Published  March 2012

A class of smoothing sample average approximation (SAA) methods is proposed for solving a stochastic linear complementarity problem, where the underlying function is the expected value of stochastic function. Existence and convergence results to the proposed methods are provided and some numerical results are reported to show the efficiency of the methods proposed.
Citation: Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145
References:
[1]

B. Chen and P. T. Harker, A non-interior point continuation method for linear complementarity problems,, SIAM Journal on Matrix Analysis and Applications, 14 (1993), 1168. doi: 10.1137/0614081.

[2]

C. Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems,, Mathematical Programming, 71 (1995), 51. doi: 10.1007/BF01592244.

[3]

C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Comp. Optim. and Appl., 5 (1996), 97. doi: 10.1007/BF00249052.

[4]

X. J. Chen, Smoothing methods for complementarity problems and their applications: a survey,, J. Oper. Res. Soc. Japan, 43 (2000), 32. doi: 10.1016/S0453-4514(00)88750-5.

[5]

X. J. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Math. Oper. Res., 30 (2005), 1022. doi: 10.1287/moor.1050.0160.

[6]

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

[7]

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.

[8]

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.

[9]

C. Kanzow, "Some Tools Allowing Interior-Point Methods to Become Noninterior,", Technical Report, (1994).

[10]

J. S. Pang, Error bounds in mathematical programming,, Mathematical Programming, 79 (1997), 299. doi: 10.1007/BF02614322.

[11]

S. M. Robinson, Some continuity properties of polyhedral multifunctions,, Mathematical Programming Study, 14 (1981), 206.

[12]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Berlin Heidelberg, (1998).

[13]

A. Shapiro, D. Dentcheva and A. Ruszczynski, "Lectures on Stochastic Programming: Modeling and Theory,", SIAM, (2009). doi: 10.1137/1.9780898718751.

[14]

S. Smale, Algorithms for solving equations,, in, (1987).

[15]

J. Takaki and N. Yamashita, A derivative-free trust-region algorithm for unconstrained optimization with controlled error,, Numerical Algebra, 1 (2011), 117. doi: 10.3934/naco.2011.1.117.

[16]

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.

[17]

H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems,, Asian Pacific Journal of Operations Research, 27 (2010), 103. doi: 10.1142/S0217595910002569.

[18]

Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares,, Numerical Algebra, 1 (2011), 15. doi: 10.3934/naco.2011.1.15.

[19]

L. Zhang, J. Zhang and Y. Wu, On the convergence of coderivative of SAA solution mapping for a parametric stochastic generalized equation,, Set-valued Anal., 19 (2011), 107. doi: 10.1007/s11228-010-0141-0.

show all references

References:
[1]

B. Chen and P. T. Harker, A non-interior point continuation method for linear complementarity problems,, SIAM Journal on Matrix Analysis and Applications, 14 (1993), 1168. doi: 10.1137/0614081.

[2]

C. Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems,, Mathematical Programming, 71 (1995), 51. doi: 10.1007/BF01592244.

[3]

C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Comp. Optim. and Appl., 5 (1996), 97. doi: 10.1007/BF00249052.

[4]

X. J. Chen, Smoothing methods for complementarity problems and their applications: a survey,, J. Oper. Res. Soc. Japan, 43 (2000), 32. doi: 10.1016/S0453-4514(00)88750-5.

[5]

X. J. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems,, Math. Oper. Res., 30 (2005), 1022. doi: 10.1287/moor.1050.0160.

[6]

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

[7]

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.

[8]

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.

[9]

C. Kanzow, "Some Tools Allowing Interior-Point Methods to Become Noninterior,", Technical Report, (1994).

[10]

J. S. Pang, Error bounds in mathematical programming,, Mathematical Programming, 79 (1997), 299. doi: 10.1007/BF02614322.

[11]

S. M. Robinson, Some continuity properties of polyhedral multifunctions,, Mathematical Programming Study, 14 (1981), 206.

[12]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Berlin Heidelberg, (1998).

[13]

A. Shapiro, D. Dentcheva and A. Ruszczynski, "Lectures on Stochastic Programming: Modeling and Theory,", SIAM, (2009). doi: 10.1137/1.9780898718751.

[14]

S. Smale, Algorithms for solving equations,, in, (1987).

[15]

J. Takaki and N. Yamashita, A derivative-free trust-region algorithm for unconstrained optimization with controlled error,, Numerical Algebra, 1 (2011), 117. doi: 10.3934/naco.2011.1.117.

[16]

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.

[17]

H. Xu, Sample average approximation methods for a class of stochastic variational inequality problems,, Asian Pacific Journal of Operations Research, 27 (2010), 103. doi: 10.1142/S0217595910002569.

[18]

Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares,, Numerical Algebra, 1 (2011), 15. doi: 10.3934/naco.2011.1.15.

[19]

L. Zhang, J. Zhang and Y. Wu, On the convergence of coderivative of SAA solution mapping for a parametric stochastic generalized equation,, Set-valued Anal., 19 (2011), 107. doi: 10.1007/s11228-010-0141-0.

[1]

Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241

[2]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[3]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[4]

Liu Yang, Xiaojiao Tong, Yao Xiong, Feifei Shen. A smoothing SAA algorithm for a portfolio choice model based on second-order stochastic dominance measures. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2018198

[5]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[6]

Zhengyong Zhou, Bo Yu. A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 977-989. doi: 10.3934/jimo.2011.7.977

[7]

Qiyu Wang, Hailin Sun. Sparse markowitz portfolio selection by using stochastic linear complementarity approach. Journal of Industrial & Management Optimization, 2018, 14 (2) : 541-559. doi: 10.3934/jimo.2017059

[8]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

[9]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[10]

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

[11]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529

[12]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153

[13]

Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317

[14]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041

[15]

Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557

[16]

Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

[17]

Gabriella Pinzari. Global Kolmogorov tori in the planetary $\boldsymbol N$-body problem. Announcement of result. Electronic Research Announcements, 2015, 22: 55-75. doi: 10.3934/era.2015.22.55

[18]

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049

[19]

Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363

[20]

Shaolin Ji, Xiaole Xue. A stochastic maximum principle for linear quadratic problem with nonconvex control domain. Mathematical Control & Related Fields, 2019, 9 (3) : 495-507. doi: 10.3934/mcrf.2019022

 Impact Factor: 

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]