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, 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]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014
[2]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[3]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020
[4]

Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015
[5]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[6]

Seung-Yeal Ha, Myeongju Kang, Bora Moon. Collective behaviors of a Winfree ensemble on an infinite cylinder. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2749-2779. doi: 10.3934/dcdsb.2020204
[7]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[8]

Pengfei Wang, Mengyi Zhang, Huan Su. Input-to-state stability of infinite-dimensional stochastic nonlinear systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021066
[9]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[10]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[11]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[12]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[13]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196
[14]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[15]

Prasanta Kumar Barik, Ankik Kumar Giri, Rajesh Kumar. Mass-conserving weak solutions to the coagulation and collisional breakage equation with singular rates. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021009
[16]

V. Vijayakumar, R. Udhayakumar, K. Kavitha. On the approximate controllability of neutral integro-differential inclusions of Sobolev-type with infinite delay. Evolution Equations & Control Theory, 2021, 10 (2) : 271-296. doi: 10.3934/eect.2020066
[17]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[18]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[19]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[20]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences