2013, 3(4): 627-641. doi: 10.3934/naco.2013.3.627

Error bounds for symmetric cone complementarity problems

1. 

Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, China

2. 

Department of Mathematics, National Taiwan Normal University, Taipei 11677

Received  May 2013 Revised  August 2013 Published  October 2013

In this paper, we investigate the issue of error bounds for symmetric cone complementarity problems (SCCPs). In particular, we show that the distance between an arbitrary point in Euclidean Jordan algebra and the solution set of the symmetric cone complementarity problem can be bounded above by some merit functions such as Fischer-Burmeister merit function, the natural residual function and the implicit Lagrangian function. The so-called $R_0$-type conditions, which are new and weaker than existing ones in the literature, are assumed to guarantee that such merit functions can provide local and global error bounds for SCCPs. Moreover, when SCCPs reduce to linear cases, we demonstrate such merit functions cannot serve as global error bounds under general monotone condition, which implicitly indicates that the proposed $R_0$-type conditions cannot be replaced by $P$-type conditions which include monotone condition as special cases.
Citation: 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
References:
[1]

S.-J. Bi, S.-H. Pan and J.-S. Chen, The same growth of FB and NR symmetric cone complementarity functions,, Optimization Letters, 6 (2012), 153.

[2]

B. Chen, Error bounds for R0-type and monotone nonlinear complementarity problems,, Journal of Optimization Theorey and Applications, 108 (2001), 297. doi: 10.1023/A:1026434200384.

[3]

J.-S. Chen, Conditions for error bounds and bounded Level sets of some merit functions for the second-order cone complementarity problem,, Journal of Optimization Theory and Applications, 135 (2007), 459. doi: 10.1007/s10957-007-9279-9.

[4]

B. Chen and P. T. Harker, Smoothing Approximations to nonlinear complementarity problems,, SIAM Journal on Optimization, 7 (1997), 403. doi: 10.1137/S1052623495280615.

[5]

X. Chen and S. Xiang, Computation of error bounds for P-matrix linear complementarity problems,, Mathematical Programming, 106 (2006), 513. doi: 10.1007/s10107-005-0645-9.

[6]

J. Faraut and A. Korányi, "Analysis on Symmetric Cones,", Oxford Mathematical Monographs Oxford University Press, (1994).

[7]

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

[8]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Mathematical Programming, 53 (1992), 99. doi: 10.1007/BF01585696.

[9]

M. S. Gowda, R. Sznajder and J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras,, Linear Algebra Appl., 393 (2004), 203. doi: 10.1016/j.laa.2004.03.028.

[10]

Z. H. Huang, S. L. Hu and J. Y. Han, Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search,, Science China Mathematics, 52 (2009), 833. doi: 10.1007/s11425-008-0170-4.

[11]

Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones,, Comprtational Optimization and Applications, 45 (2010), 557. doi: 10.1007/s10589-008-9180-y.

[12]

C. Kanzow and M. Fukushima, Equivalence of the generalized complementarity problem to differentiable unconstrained minimization,, Journal of Optimization Theory and Applications, 90 (1996), 581. doi: 10.1007/BF02189797.

[13]

L. C. Kong, J. Sun and N. H. Xiu, A regularized smoothing Newton method for symmetric cone complementarity problems,, SIAM Journal on Optimization, 19 (2008), 1028. doi: 10.1137/060676775.

[14]

L. C. Kong, L. Tuncel and N. H. Xiu, Vector-valued implicit Lagrangian for symmetric cone complementarity problems,, Asia-Pacific Journal of Operational Research, 26 (2009), 199. doi: 10.1142/S0217595909002171.

[15]

Z. Q. Luo, O. L. Mangasarian, J. Ren and M. V. Solodov, New error bounds for the linear complementarity problem,, Mathematics of Operations Research, 19 (1994), 880. doi: 10.1287/moor.19.4.880.

[16]

Z. Q. Luo and P. Tseng, Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem,, SIAM Journal on Optimization, 2 (1992), 43. doi: 10.1137/0802004.

[17]

Y. J. Liu, Z. W. Zhang and Y. H. Wang, Some properties of a class of merit functions for symmetric cone complementarity problems,, Asia Pacific Journal of Operational Research, 23 (2006), 473. doi: 10.1142/S0217595906000991.

[18]

R. Mathias and J. S. Pang, Error bounds for the linear complementarity problem with a P-Matrix,, Linear Algebra and Applications, 36 (1986), 81.

[19]

O. L. Mangasarian and J. Ren, New improved error bounds for the linear complementarity problem,, Mathematical Programming, 66 (1994), 241. doi: 10.1007/BF01581148.

[20]

O. L. Mangasarian and T.-H. Shiau, Error bounds for monotone linear complementarity problems,, Mathematical Programming, 36 (1986), 81. doi: 10.1007/BF02591991.

[21]

J. S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms,, SIAM Journal on Optimization, 3 (1993), 443. doi: 10.1137/0803021.

[22]

S.-H. Pan and J.-S. Chen, A one-parametric class of merit functions for the symmetric cone complementarity problem,, Journal of Mathematical Analysis and Applications, 355 (2009), 195. doi: 10.1016/j.jmaa.2009.01.064.

[23]

J. M. Peng, Equivalence of variational inequality problems to unconstrained minimization,, Mathematical Programming, 78 (1997), 347. doi: 10.1016/S0025-5610(96)00077-9.

[24]

D. Sun and J. Sun, Löwner's operator and spectral functions on Euclidean Jordan algebras,, Mathematics of Operations Research, 33 (2008), 421. doi: 10.1287/moor.1070.0300.

[25]

P. Tseng, Growth behavior of a class of merit functions for the nonlinear complementarity problems,, Journal of Optimization Theory and Applications, 89 (1996), 17. doi: 10.1007/BF02192639.

[26]

J. Tao and M. S. Gowda, Some P-properties for nonlinear transformations on Euclidean Jordan algebras,, Mathematics of Operations Research, 30 (2005), 985. doi: 10.1287/moor.1050.0157.

show all references

References:
[1]

S.-J. Bi, S.-H. Pan and J.-S. Chen, The same growth of FB and NR symmetric cone complementarity functions,, Optimization Letters, 6 (2012), 153.

[2]

B. Chen, Error bounds for R0-type and monotone nonlinear complementarity problems,, Journal of Optimization Theorey and Applications, 108 (2001), 297. doi: 10.1023/A:1026434200384.

[3]

J.-S. Chen, Conditions for error bounds and bounded Level sets of some merit functions for the second-order cone complementarity problem,, Journal of Optimization Theory and Applications, 135 (2007), 459. doi: 10.1007/s10957-007-9279-9.

[4]

B. Chen and P. T. Harker, Smoothing Approximations to nonlinear complementarity problems,, SIAM Journal on Optimization, 7 (1997), 403. doi: 10.1137/S1052623495280615.

[5]

X. Chen and S. Xiang, Computation of error bounds for P-matrix linear complementarity problems,, Mathematical Programming, 106 (2006), 513. doi: 10.1007/s10107-005-0645-9.

[6]

J. Faraut and A. Korányi, "Analysis on Symmetric Cones,", Oxford Mathematical Monographs Oxford University Press, (1994).

[7]

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

[8]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Mathematical Programming, 53 (1992), 99. doi: 10.1007/BF01585696.

[9]

M. S. Gowda, R. Sznajder and J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras,, Linear Algebra Appl., 393 (2004), 203. doi: 10.1016/j.laa.2004.03.028.

[10]

Z. H. Huang, S. L. Hu and J. Y. Han, Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search,, Science China Mathematics, 52 (2009), 833. doi: 10.1007/s11425-008-0170-4.

[11]

Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones,, Comprtational Optimization and Applications, 45 (2010), 557. doi: 10.1007/s10589-008-9180-y.

[12]

C. Kanzow and M. Fukushima, Equivalence of the generalized complementarity problem to differentiable unconstrained minimization,, Journal of Optimization Theory and Applications, 90 (1996), 581. doi: 10.1007/BF02189797.

[13]

L. C. Kong, J. Sun and N. H. Xiu, A regularized smoothing Newton method for symmetric cone complementarity problems,, SIAM Journal on Optimization, 19 (2008), 1028. doi: 10.1137/060676775.

[14]

L. C. Kong, L. Tuncel and N. H. Xiu, Vector-valued implicit Lagrangian for symmetric cone complementarity problems,, Asia-Pacific Journal of Operational Research, 26 (2009), 199. doi: 10.1142/S0217595909002171.

[15]

Z. Q. Luo, O. L. Mangasarian, J. Ren and M. V. Solodov, New error bounds for the linear complementarity problem,, Mathematics of Operations Research, 19 (1994), 880. doi: 10.1287/moor.19.4.880.

[16]

Z. Q. Luo and P. Tseng, Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem,, SIAM Journal on Optimization, 2 (1992), 43. doi: 10.1137/0802004.

[17]

Y. J. Liu, Z. W. Zhang and Y. H. Wang, Some properties of a class of merit functions for symmetric cone complementarity problems,, Asia Pacific Journal of Operational Research, 23 (2006), 473. doi: 10.1142/S0217595906000991.

[18]

R. Mathias and J. S. Pang, Error bounds for the linear complementarity problem with a P-Matrix,, Linear Algebra and Applications, 36 (1986), 81.

[19]

O. L. Mangasarian and J. Ren, New improved error bounds for the linear complementarity problem,, Mathematical Programming, 66 (1994), 241. doi: 10.1007/BF01581148.

[20]

O. L. Mangasarian and T.-H. Shiau, Error bounds for monotone linear complementarity problems,, Mathematical Programming, 36 (1986), 81. doi: 10.1007/BF02591991.

[21]

J. S. Pang and L. Qi, Nonsmooth equations: Motivation and algorithms,, SIAM Journal on Optimization, 3 (1993), 443. doi: 10.1137/0803021.

[22]

S.-H. Pan and J.-S. Chen, A one-parametric class of merit functions for the symmetric cone complementarity problem,, Journal of Mathematical Analysis and Applications, 355 (2009), 195. doi: 10.1016/j.jmaa.2009.01.064.

[23]

J. M. Peng, Equivalence of variational inequality problems to unconstrained minimization,, Mathematical Programming, 78 (1997), 347. doi: 10.1016/S0025-5610(96)00077-9.

[24]

D. Sun and J. Sun, Löwner's operator and spectral functions on Euclidean Jordan algebras,, Mathematics of Operations Research, 33 (2008), 421. doi: 10.1287/moor.1070.0300.

[25]

P. Tseng, Growth behavior of a class of merit functions for the nonlinear complementarity problems,, Journal of Optimization Theory and Applications, 89 (1996), 17. doi: 10.1007/BF02192639.

[26]

J. Tao and M. S. Gowda, Some P-properties for nonlinear transformations on Euclidean Jordan algebras,, Mathematics of Operations Research, 30 (2005), 985. doi: 10.1287/moor.1050.0157.

[1]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[2]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

[3]

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

[4]

Xiao-Hong Liu, Wei Wu. Coerciveness of some merit functions over symmetric cones. Journal of Industrial & Management Optimization, 2009, 5 (3) : 603-613. doi: 10.3934/jimo.2009.5.603

[5]

Hisashi Inaba. The Malthusian parameter and $R_0$ for heterogeneous populations in periodic environments. Mathematical Biosciences & Engineering, 2012, 9 (2) : 313-346. doi: 10.3934/mbe.2012.9.313

[6]

Christine K. Yang, Fred Brauer. Calculation of $R_0$ for age-of-infection models. Mathematical Biosciences & Engineering, 2008, 5 (3) : 585-599. doi: 10.3934/mbe.2008.5.585

[7]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

[8]

Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

[9]

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

[10]

Toshikazu Kuniya, Mimmo Iannelli. $R_0$ and the global behavior of an age-structured SIS epidemic model with periodicity and vertical transmission. Mathematical Biosciences & Engineering, 2014, 11 (4) : 929-945. doi: 10.3934/mbe.2014.11.929

[11]

Nicolas Bacaër, Xamxinur Abdurahman, Jianli Ye, Pierre Auger. On the basic reproduction number $R_0$ in sexual activity models for HIV/AIDS epidemics: Example from Yunnan, China. Mathematical Biosciences & Engineering, 2007, 4 (4) : 595-607. doi: 10.3934/mbe.2007.4.595

[12]

Benjamin H. Singer, Denise E. Kirschner. Influence of backward bifurcation on interpretation of $R_0$ in a model of epidemic tuberculosis with reinfection. Mathematical Biosciences & Engineering, 2004, 1 (1) : 81-93. doi: 10.3934/mbe.2004.1.81

[13]

Cameron J. Browne, Sergei S. Pilyugin. Minimizing $\mathcal R_0$ for in-host virus model with periodic combination antiviral therapy. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3315-3330. doi: 10.3934/dcdsb.2016099

[14]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[15]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[16]

Gerardo Chowell, R. Fuentes, A. Olea, X. Aguilera, H. Nesse, J. M. Hyman. The basic reproduction number $R_0$ and effectiveness of reactive interventions during dengue epidemics: The 2002 dengue outbreak in Easter Island, Chile. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1455-1474. doi: 10.3934/mbe.2013.10.1455

[17]

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

[18]

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

[19]

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

[20]

Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363

 Impact Factor: 

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]