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

Solution properties and error bounds for semi-infinite complementarity problems

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.
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, 95 (2003), 3.   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.  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.  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.   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.  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.  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.  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.  doi: 10.1007/s10107-007-0163-z.  Google Scholar

[9]

F. H. Clarke, "Optimization and Nonsmooth Analysis,", Wiley, (1983).   Google Scholar

[10]

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

[11]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Math. Programming, 117 (2009), 163.  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, (2003).   Google Scholar

[13]

H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems,, SIAM J. Optim., 18 (2007), 482.  doi: 10.1137/050630805.  Google Scholar

[14]

S. A. Gabriel and J. J. More, Smoothing of mixed complementarity problems,, in, (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, 48 (1990), 161.   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.  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.  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.  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.  doi: 10.1007/BF01581148.  Google Scholar

[21]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM J. Control Optim., 15 (1977), 957.  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.  doi: 10.1007/s10107-003-0464-9.  Google Scholar

[23]

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

[24]

E. Polak, "Optimization: Algorithms and Consistent Approximation,", Springer-Verlag, (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, (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.  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.  doi: 10.1007/s10107-003-0380-z.  Google Scholar

[29]

D. Sun and L. Qi, On NCP-functions,, Comp. Optim. Appl., 13 (1999), 201.  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.  doi: 10.1137/060659132.  Google Scholar

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Math. Programming, 95 (2003), 3.   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.  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.  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.   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.  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.  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.  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.  doi: 10.1007/s10107-007-0163-z.  Google Scholar

[9]

F. H. Clarke, "Optimization and Nonsmooth Analysis,", Wiley, (1983).   Google Scholar

[10]

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

[11]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Math. Programming, 117 (2009), 163.  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, (2003).   Google Scholar

[13]

H. Fang, X. Chen and M. Fukushima, Stochastic $R_0$ matrix linear complementarity problems,, SIAM J. Optim., 18 (2007), 482.  doi: 10.1137/050630805.  Google Scholar

[14]

S. A. Gabriel and J. J. More, Smoothing of mixed complementarity problems,, in, (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, 48 (1990), 161.   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.  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.  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.  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.  doi: 10.1007/BF01581148.  Google Scholar

[21]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM J. Control Optim., 15 (1977), 957.  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.  doi: 10.1007/s10107-003-0464-9.  Google Scholar

[23]

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

[24]

E. Polak, "Optimization: Algorithms and Consistent Approximation,", Springer-Verlag, (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, (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.  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.  doi: 10.1007/s10107-003-0380-z.  Google Scholar

[29]

D. Sun and L. Qi, On NCP-functions,, Comp. Optim. Appl., 13 (1999), 201.  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.  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, 2017, 13 (5) : 1-12. 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 - A, 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 & 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 & Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219

[15]

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

[16]

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

[17]

Rafael del Rio, Mikhail Kudryavtsev, Luis O. Silva. Inverse problems for Jacobi operators III: Mass-spring perturbations of semi-infinite systems. Inverse Problems & Imaging, 2012, 6 (4) : 599-621. doi: 10.3934/ipi.2012.6.599

[18]

Zhi Guo Feng, Kok Lay Teo, Volker Rehbock. A smoothing approach for semi-infinite programming with projected Newton-type algorithm. Journal of Industrial & Management Optimization, 2009, 5 (1) : 141-151. doi: 10.3934/jimo.2009.5.141

[19]

Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851

[20]

Igor Chueshov. Remark on an elastic plate interacting with a gas in a semi-infinite tube: Periodic solutions. Evolution Equations & Control Theory, 2016, 5 (4) : 561-566. doi: 10.3934/eect.2016019

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]