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

Previous Article
Identification of water quality model parameters using artificial bee colony algorithm
NACO Home
This Issue
Next Article
An efficient algorithm for convex quadratic semi-definite optimization

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

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

Jie Zhang ^1, , Yue Wu ^2, and Liwei Zhang ^3,

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

Abstract
Related Papers

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.

Keywords: stochastic linear complementarity problem., Smoothing SAA method.

Mathematics Subject Classification: Primary: 90C33, 90C1.

Citation: Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control and 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-1190. 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-69. 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-138. 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-47. 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-1038. 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, New York, 2003.
[7]	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.
[8]	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.
[9]	C. Kanzow, "Some Tools Allowing Interior-Point Methods to Become Noninterior," Technical Report, Institute of Applied Mathematics, University of Hamburg, Germany, 1994.
[10]	J. S. Pang, Error bounds in mathematical programming, Mathematical Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.
[11]	S. M. Robinson, Some continuity properties of polyhedral multifunctions, Mathematical Programming Study, 14 (1981), 206-214.
[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, Philadelphia, 2009. doi: 10.1137/1.9780898718751.
[14]	S. Smale, Algorithms for solving equations, in "Proceedings of the International Congress of Mathematicians," Ameri. Math. Sot., Providence, 1987.
[15]	J. Takaki and N. Yamashita, A derivative-free trust-region algorithm for unconstrained optimization with controlled error, Numerical Algebra, Control and Optimization, 1 (2011), 117-145. 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-401. 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-119. doi: 10.1142/S0217595910002569.
[18]	Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34. 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-134. 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-1190. 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-69. 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-138. 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-47. 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-1038. 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, New York, 2003.
[7]	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.
[8]	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.
[9]	C. Kanzow, "Some Tools Allowing Interior-Point Methods to Become Noninterior," Technical Report, Institute of Applied Mathematics, University of Hamburg, Germany, 1994.
[10]	J. S. Pang, Error bounds in mathematical programming, Mathematical Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.
[11]	S. M. Robinson, Some continuity properties of polyhedral multifunctions, Mathematical Programming Study, 14 (1981), 206-214.
[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, Philadelphia, 2009. doi: 10.1137/1.9780898718751.
[14]	S. Smale, Algorithms for solving equations, in "Proceedings of the International Congress of Mathematicians," Ameri. Math. Sot., Providence, 1987.
[15]	J. Takaki and N. Yamashita, A derivative-free trust-region algorithm for unconstrained optimization with controlled error, Numerical Algebra, Control and Optimization, 1 (2011), 117-145. 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-401. 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-119. doi: 10.1142/S0217595910002569.
[18]	Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34. 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-134. doi: 10.1007/s11228-010-0141-0.

[1]	Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[2]	Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241
[3]	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 and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[4]	Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial and Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259
[5]	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 and Management Optimization, 2020, 16 (3) : 1171-1185. doi: 10.3934/jimo.2018198
[6]	ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021150
[7]	Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911
[8]	Zhengyong Zhou, Bo Yu. A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 977-989. doi: 10.3934/jimo.2011.7.977
[9]	Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044
[10]	Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
[11]	Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[12]	Qiyu Wang, Hailin Sun. Sparse markowitz portfolio selection by using stochastic linear complementarity approach. Journal of Industrial and Management Optimization, 2018, 14 (2) : 541-559. doi: 10.3934/jimo.2017059
[13]	Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645
[14]	Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021082
[15]	Yan Li, Liping Zhang. A smoothing Newton method preserving nonnegativity for solving tensor complementarity problems with $ P_0 $ mappings. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022041
[16]	Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[17]	Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[18]	Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557
[19]	Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[20]	Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial and Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Jie Zhang Yue Wu Liwei Zhang
on Google Scholar
Jie Zhang Yue Wu Liwei Zhang

[Back to Top]