American Institute of Mathematical Sciences

Advanced
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

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

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

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

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

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

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

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

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

[9]

F. H. Clarke, "Optimization and Nonsmooth Analysis," Wiley, New York, 1983.  Google Scholar

[10]

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

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

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems, I and II," Springer Verlag, New York, 2003. Google Scholar

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

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

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

[16]

E. Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications," Dordrecht: Kluwer Academic Publishers, 2002.  Google Scholar

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

[18]

G. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optim. Methods Softw., 21 (2006), 551-564. doi: 10.1080/10556780600627610.  Google Scholar

[19]

C. Ling, L. Qi, G. Zhou and L. Caccettac, The SC1 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.  Google Scholar

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

[21]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15 (1977), 957-972. doi: 10.1137/0315061.  Google Scholar

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

[23]

J.-S. Pang, Error bounds in mathematical programming, Math. Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.  Google Scholar

[24]

E. Polak, "Optimization: Algorithms and Consistent Approximation," Springer-Verlag, New York, 1997.  Google Scholar

[25]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, 1970.  Google Scholar

[26]

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

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

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

[29]

D. Sun and L. Qi, On NCP-functions, Comp. Optim. Appl., 13 (1999), 201-220. doi: 10.1023/A:1008669226453.  Google Scholar

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

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Programming, Ser. B, 95 (2003), 3-51.  Google Scholar

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

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

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

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

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

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

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

[9]

F. H. Clarke, "Optimization and Nonsmooth Analysis," Wiley, New York, 1983.  Google Scholar

[10]

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

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

[12]

F. Facchinei and J.-S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems, I and II," Springer Verlag, New York, 2003. Google Scholar

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

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

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

[16]

E. Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications," Dordrecht: Kluwer Academic Publishers, 2002.  Google Scholar

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

[18]

G. Lin and M. Fukushima, New reformulations for stochastic nonlinear complementarity problems, Optim. Methods Softw., 21 (2006), 551-564. doi: 10.1080/10556780600627610.  Google Scholar

[19]

C. Ling, L. Qi, G. Zhou and L. Caccettac, The SC1 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.  Google Scholar

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

[21]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15 (1977), 957-972. doi: 10.1137/0315061.  Google Scholar

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

[23]

J.-S. Pang, Error bounds in mathematical programming, Math. Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.  Google Scholar

[24]

E. Polak, "Optimization: Algorithms and Consistent Approximation," Springer-Verlag, New York, 1997.  Google Scholar

[25]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, 1970.  Google Scholar

[26]

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

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

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

[29]

D. Sun and L. Qi, On NCP-functions, Comp. Optim. Appl., 13 (1999), 201-220. doi: 10.1023/A:1008669226453.  Google Scholar

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

[1]

Mengmeng Zheng, Ying Zhang, Zheng-Hai Huang. Global error bounds for the tensor complementarity problem with a P-tensor. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2016, 36 (1) : 481-497. doi: 10.3934/dcds.2016.36.481
[13]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[14]

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 & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[15]

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
[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 & 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 & 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 & 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 & Management Optimization, 2020, 16 (3) : 1221-1233. doi: 10.3934/jimo.2018201

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences