Solution properties and error bounds for semi-infinite complementarity problems

Previous Article
Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints
JIMO Home
This Issue
Next Article
A class of nonlinear Lagrangian algorithms for minimax problems

January 2013, 9(1): 99-115. doi: 10.3934/jimo.2013.9.99

Solution properties and error bounds for semi-infinite complementarity problems

Jinchuan Zhou ^1, , Naihua Xiu ^2, and Jein-Shan Chen ^3,

1.	Department of Mathematics, Shandong University of Technology, Zibo 255049, China
2.	Department of Mathematics, Beijing Jiaotong University, Beijing 100044, China
3.	Department of Mathematics, National Taiwan Normal University, Taipei 11677, Taiwan

Received May 2011 Revised May 2012 Published December 2012

Abstract
Related Papers

In this paper, we deal with the semi-infinite complementarity problems (SICP), in which several important issues are covered, such as solvability, semismoothness of residual functions, and error bounds. In particular, we characterize the solution set by investigating the relationship between SICP and the classical complementarity problem. Furthermore, we show that the SICP can be equivalently reformulated as a typical semi-infinite min-max programming problem by employing NCP functions. Finally, we study the concept of error bounds and introduce its two variants, $\varepsilon$-error bounds and weak error bounds, where the concept of weak error bounds is highly desirable in that the solution set is not restricted to be nonempty.

Keywords: weak error bounds., error bounds, semidifferentiable and semismooth, Semi-infinite complementarity problem.

Mathematics Subject Classification: 90C33, 90C34, 65K1.

Citation: Jinchuan Zhou, Naihua Xiu, Jein-Shan Chen. Solution properties and error bounds for semi-infinite complementarity problems. Journal of Industrial and Management Optimization, 2013, 9 (1) : 99-115. doi: 10.3934/jimo.2013.9.99

References:

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Programming, Ser. B, 95 (2003), 3-51.
[2]	A. Baken, F. Deutsch and W. Li, Strong CHIP, normality, and linear regularity of convex sets, Trans. Amer. Math. Soc., 357 (2005), 3831-3863. doi: 10.1090/S0002-9947-05-03945-0.
[3]	H. H. Bauschke, J. M. Borwein and W. Li, Strong conical hull intersection property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimization, Math. Programming, 86 (1999), 135-160. doi: 10.1007/s101070050083.
[4]	H. H. Bauschke, J. M. Borwein and P. Tseng, Bounded linear regularity, strong CHIP, and CHIP are distinct properties, Journal of Convex Analysis, 7 (2000), 395-412.
[5]	Q. Chen, D. Chu and R. Tan, Optimal control of obstacle for quasi-linear elliptic variational bilateral problems, SIAM J. Control Optim., 44 (2005), 1067-1080. doi: 10.1137/S0363012904443075.
[6]	X. 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.
[7]	X. Chen and S. Xiang, Computation of error bounds for $P$-matrix linear complementarity problems, Math. Programming, 106 (2006), 513-525. doi: 10.1007/s10107-005-0645-9.
[8]	X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Math. Programming, 117 (2009), 51-80. doi: 10.1007/s10107-007-0163-z.
[9]	F. H. Clarke, "Optimization and Nonsmooth Analysis," Wiley, New York, 1983.
[10]	R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem," Academic Press, New York, 1992.
[11]	F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods, Math. Programming, 117 (2009), 163-194. doi: 10.1007/s10107-007-0160-2.
[12]	F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems, I and II," Springer Verlag, New York, 2003.
[13]	H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems, SIAM J. Optim., 18 (2007), 482-506. doi: 10.1137/050630805.
[14]	S. A. Gabriel and J. J. More, Smoothing of mixed complementarity problems, in "Complementarity and Variational Problems" (ed. M. C. Ferris and J. S. Pang), SIAM Publications, Philadelphia, (1997).
[15]	P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Math. Programming, Ser. B, 48 (1990), 161-220.
[16]	E. Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications," Dordrecht: Kluwer Academic Publishers, 2002.
[17]	G. Lin, X. Chen and M. Fukushima, New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC, Optimization, 56 (2007), 641-653. doi: 10.1080/02331930701617320.
[18]	G. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optim. Methods Softw., 21 (2006), 551-564. doi: 10.1080/10556780600627610.
[19]	C. Ling, L. Qi, G. Zhou and L. Caccettac, The SC¹ property of an expected residual function arising from stochastic complementarity problems, Oper. Res. Lett., 36 (2008), 456-460. doi: 10.1016/j.orl.2008.01.010.
[20]	O. L. Mangasarian and J. Ren, New improved error bounds for the linear complementarity problem, Math. Programming, 66 (1994), 241-255. doi: 10.1007/BF01581148.
[21]	R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15 (1977), 957-972. doi: 10.1137/0315061.
[22]	K. F. Ng and W. H. Yang, Regularities and their relations to error bounds, Math. Programming, 99 (2004), 521-538. doi: 10.1007/s10107-003-0464-9.
[23]	J.-S. Pang, Error bounds in mathematical programming, Math. Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.
[24]	E. Polak, "Optimization: Algorithms and Consistent Approximation," Springer-Verlag, New York, 1997.
[25]	R. T. Rockafellar, "Convex Analysis," Princeton University Press, 1970.
[26]	R. T. Rockafellar and R. J. Wets, "Variational Analysis," Springer, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[27]	S. H. Schmieta and F. Alizadeh, Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones, Math. Oper. Res., 26 (2001), 543-564. doi: 10.1287/moor.26.3.543.10582.
[28]	S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Programming, 96 (2003), 409-438. doi: 10.1007/s10107-003-0380-z.
[29]	D. Sun and L. Qi, On NCP-functions, Comp. Optim. Appl., 13 (1999), 201-220. doi: 10.1023/A:1008669226453.
[30]	X. Y. Zheng and K. F. Ng, Linear regularity for a collection of subsmooth sets in Banach spaces, SIAM J. Optim., 19 (2008), 62-76. doi: 10.1137/060659132.

show all references

References:

[1]	F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Programming, Ser. B, 95 (2003), 3-51.
[2]	A. Baken, F. Deutsch and W. Li, Strong CHIP, normality, and linear regularity of convex sets, Trans. Amer. Math. Soc., 357 (2005), 3831-3863. doi: 10.1090/S0002-9947-05-03945-0.
[3]	H. H. Bauschke, J. M. Borwein and W. Li, Strong conical hull intersection property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimization, Math. Programming, 86 (1999), 135-160. doi: 10.1007/s101070050083.
[4]	H. H. Bauschke, J. M. Borwein and P. Tseng, Bounded linear regularity, strong CHIP, and CHIP are distinct properties, Journal of Convex Analysis, 7 (2000), 395-412.
[5]	Q. Chen, D. Chu and R. Tan, Optimal control of obstacle for quasi-linear elliptic variational bilateral problems, SIAM J. Control Optim., 44 (2005), 1067-1080. doi: 10.1137/S0363012904443075.
[6]	X. 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.
[7]	X. Chen and S. Xiang, Computation of error bounds for $P$-matrix linear complementarity problems, Math. Programming, 106 (2006), 513-525. doi: 10.1007/s10107-005-0645-9.
[8]	X. Chen, C. Zhang and M. Fukushima, Robust solution of monotone stochastic linear complementarity problems, Math. Programming, 117 (2009), 51-80. doi: 10.1007/s10107-007-0163-z.
[9]	F. H. Clarke, "Optimization and Nonsmooth Analysis," Wiley, New York, 1983.
[10]	R. W. Cottle, J. S. Pang and R. E. Stone, "The Linear Complementarity Problem," Academic Press, New York, 1992.
[11]	F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods, Math. Programming, 117 (2009), 163-194. doi: 10.1007/s10107-007-0160-2.
[12]	F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems, I and II," Springer Verlag, New York, 2003.
[13]	H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems, SIAM J. Optim., 18 (2007), 482-506. doi: 10.1137/050630805.
[14]	S. A. Gabriel and J. J. More, Smoothing of mixed complementarity problems, in "Complementarity and Variational Problems" (ed. M. C. Ferris and J. S. Pang), SIAM Publications, Philadelphia, (1997).
[15]	P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Math. Programming, Ser. B, 48 (1990), 161-220.
[16]	E. Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications," Dordrecht: Kluwer Academic Publishers, 2002.
[17]	G. Lin, X. Chen and M. Fukushima, New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC, Optimization, 56 (2007), 641-653. doi: 10.1080/02331930701617320.
[18]	G. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optim. Methods Softw., 21 (2006), 551-564. doi: 10.1080/10556780600627610.
[19]	C. Ling, L. Qi, G. Zhou and L. Caccettac, The SC¹ property of an expected residual function arising from stochastic complementarity problems, Oper. Res. Lett., 36 (2008), 456-460. doi: 10.1016/j.orl.2008.01.010.
[20]	O. L. Mangasarian and J. Ren, New improved error bounds for the linear complementarity problem, Math. Programming, 66 (1994), 241-255. doi: 10.1007/BF01581148.
[21]	R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15 (1977), 957-972. doi: 10.1137/0315061.
[22]	K. F. Ng and W. H. Yang, Regularities and their relations to error bounds, Math. Programming, 99 (2004), 521-538. doi: 10.1007/s10107-003-0464-9.
[23]	J.-S. Pang, Error bounds in mathematical programming, Math. Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.
[24]	E. Polak, "Optimization: Algorithms and Consistent Approximation," Springer-Verlag, New York, 1997.
[25]	R. T. Rockafellar, "Convex Analysis," Princeton University Press, 1970.
[26]	R. T. Rockafellar and R. J. Wets, "Variational Analysis," Springer, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[27]	S. H. Schmieta and F. Alizadeh, Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones, Math. Oper. Res., 26 (2001), 543-564. doi: 10.1287/moor.26.3.543.10582.
[28]	S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Programming, 96 (2003), 409-438. doi: 10.1007/s10107-003-0380-z.
[29]	D. Sun and L. Qi, On NCP-functions, Comp. Optim. Appl., 13 (1999), 201-220. doi: 10.1023/A:1008669226453.
[30]	X. Y. Zheng and K. F. Ng, Linear regularity for a collection of subsmooth sets in Banach spaces, SIAM J. Optim., 19 (2008), 62-76. doi: 10.1137/060659132.

[1]	Mengmeng Zheng, Ying Zhang, Zheng-Hai Huang. Global error bounds for the tensor complementarity problem with a P-tensor. Journal of Industrial and Management Optimization, 2019, 15 (2) : 933-946. doi: 10.3934/jimo.2018078
[2]	Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[3]	Ye Sun, Daniel B. Work. Error bounds for Kalman filters on traffic networks. Networks and Heterogeneous Media, 2018, 13 (2) : 261-295. doi: 10.3934/nhm.2018012
[4]	Idan Goldenberg, David Burshtein. Error bounds for repeat-accumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555-570. doi: 10.3934/amc.2011.5.555
[5]	Pavel Krejčí. The Preisach hysteresis model: Error bounds for numerical identification and inversion. Discrete and Continuous Dynamical Systems - S, 2013, 6 (1) : 101-119. doi: 10.3934/dcdss.2013.6.101
[6]	Minghua Li, Chunrong Chen, Shengjie Li. Error bounds of regularized gap functions for nonmonotone Ky Fan inequalities. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1261-1272. doi: 10.3934/jimo.2019001
[7]	Jeremiah Birrell. A posteriori error bounds for two point boundary value problems: A green's function approach. Journal of Computational Dynamics, 2015, 2 (2) : 143-164. doi: 10.3934/jcd.2015001
[8]	Chengxiang Wang, Li Zeng. Error bounds and stability in the $l_{0}$ regularized for CT reconstruction from small projections. Inverse Problems and Imaging, 2016, 10 (3) : 829-853. doi: 10.3934/ipi.2016023
[9]	Walter Alt, Robert Baier, Matthias Gerdts, Frank Lempio. Error bounds for Euler approximation of linear-quadratic control problems with bang-bang solutions. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 547-570. doi: 10.3934/naco.2012.2.547
[10]	Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[11]	Roman Chapko, B. Tomas Johansson. An alternating boundary integral based method for a Cauchy problem for the Laplace equation in semi-infinite regions. Inverse Problems and Imaging, 2008, 2 (3) : 317-333. doi: 10.3934/ipi.2008.2.317
[12]	Xiaojie Wang. Weak error estimates of the exponential Euler scheme for semi-linear SPDEs without Malliavin calculus. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 481-497. doi: 10.3934/dcds.2016.36.481
[13]	Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[14]	Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[15]	Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1133-1144. doi: 10.3934/jimo.2021012
[16]	Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete and Continuous Dynamical Systems - B, 2021, 26 (10) : 5217-5226. doi: 10.3934/dcdsb.2020340
[17]	Qilong Zhai, Ran Zhang. Lower and upper bounds of Laplacian eigenvalue problem by weak Galerkin method on triangular meshes. Discrete and Continuous Dynamical Systems - B, 2019, 24 (1) : 403-413. doi: 10.3934/dcdsb.2018091
[18]	Yao Lu, Rui Zhang, Dongdai Lin. Improved bounds for the implicit factorization problem. Advances in Mathematics of Communications, 2013, 7 (3) : 243-251. doi: 10.3934/amc.2013.7.243
[19]	Azhar Ali Zafar, Khurram Shabbir, Asim Naseem, Muhammad Waqas Ashraf. MHD natural convection boundary-layer flow over a semi-infinite heated plate with arbitrary inclination. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 1007-1015. doi: 10.3934/dcdss.2020059
[20]	Xiaodong Fan, Tian Qin. Stability analysis for generalized semi-infinite optimization problems under functional perturbations. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1221-1233. doi: 10.3934/jimo.2018201

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Jinchuan Zhou Naihua Xiu Jein-Shan Chen
on Google Scholar
Jinchuan Zhou Naihua Xiu Jein-Shan Chen

[Back to Top]