Solution properties and error bounds for semi-infinite complementarity problems

Jinchuan Zhou; Naihua Xiu; Jein-Shan Chen

doi:10.3934/jimo.2013.9.99

Article Contents

2013, Volume 9, Issue 1: 99-115. Doi: 10.3934/jimo.2013.9.99

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

Solution properties and error bounds for semi-infinite complementarity problems

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

Received: April 30, 2011

Revised: April 30, 2012

Published: December 2012

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.