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.

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

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

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

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

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

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

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

[9]

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

[10]

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

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

[12]

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

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

[14]

S. A. Gabriel and J. J. More, Smoothing of mixed complementarity problems,, in, (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, 48 (1990), 161.

[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. doi: 10.1080/02331930701617320.

[18]

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

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

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

[21]

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

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

[23]

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

[24]

E. Polak, "Optimization: Algorithms and Consistent Approximation,", Springer-Verlag, (1997).

[25]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970).

[26]

R. T. Rockafellar and R. J. Wets, "Variational Analysis,", Springer, (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. 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. doi: 10.1007/s10107-003-0380-z.

[29]

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

show all references

References:
[1]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Math. Programming, 95 (2003), 3.

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

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

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

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

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

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

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

[9]

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

[10]

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

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

[12]

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

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

[14]

S. A. Gabriel and J. J. More, Smoothing of mixed complementarity problems,, in, (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, 48 (1990), 161.

[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. doi: 10.1080/02331930701617320.

[18]

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

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

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

[21]

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

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

[23]

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

[24]

E. Polak, "Optimization: Algorithms and Consistent Approximation,", Springer-Verlag, (1997).

[25]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970).

[26]

R. T. Rockafellar and R. J. Wets, "Variational Analysis,", Springer, (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. 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. doi: 10.1007/s10107-003-0380-z.

[29]

D. Sun and L. Qi, On NCP-functions,, Comp. Optim. Appl., 13 (1999), 201. 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. 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 & 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

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]