American Institute of Mathematical Sciences

Advanced
January  2012, 8(1): 67-86. doi: 10.3934/jimo.2012.8.67

Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP

Zheng-Hai Huang 1, and  Nan Lu 2,

1. 

Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, P.R.
2. 

Department of Mathematics, Xidian University, XiAn 710071, China

Received  October 2010 Revised  July 2011 Published  November 2011

In this paper, we consider the linear complementarity problem over Euclidean Jordan algebras with a Cartesian $P_*(\kappa)$-transformation, which is denoted by the Cartesian $P_*(\kappa)$-SCLCP. A smoothing algorithm is extended to solve the Cartesian $P_*(\kappa)$-SCLCP. We show that the algorithm is globally convergent if the problem concerned has a solution. In particular, we show that the algorithm is globally linearly convergent under a weak assumption.
Keywords: smoothing algorithm., symmetric cone, Complementarity problem, Euclidean Jordan algebra.
Mathematics Subject Classification: Primary: 90C22, 90C25; Secondary: 90C3.
Citation: Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP. Journal of Industrial and Management Optimization, 2012, 8 (1) : 67-86. doi: 10.3934/jimo.2012.8.67
References:
[1]

R. W. Cottle, J.-S. Pang and R. E. Stone, "The Linear Complementarity Problems," Academic Press, Boston, 1992.

[2]

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

[3]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.

[4]

L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86 (1997), 149-175.

[5]

L. Faybusovich and Y. Lu, Jordan-algebraic aspects of nonconvex optimization over symmetric cones, Appl. Math. Optim., 53 (2006), 67-77.

[6]

M. S. Gowda, R. Sznajder and J. Tao, Some $P$-properties for linear transformations on Euclidean Jordan algebras, Linear Algebra Appl., 393 (2004), 203-232.

[7]

Z. H. Huang, The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP, IMA J. Numer. Anal., 25 (2005), 670-684.

[8]

Z. H. Huang, Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms, Math. Meth. Oper. Res., 61 (2005), 41-55.

[9]

Z. H. Huang, S. L. Hu and J. Han, Global convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search, Sci. China, Ser. A, 52 (2009), 833-848.

[10]

Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones, Comput. Optim. Appl., 45 (2010), 557-579.

[11]

Z. H. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$- and monotone LCP, Math. Program., 99 (2004), 423-441.

[12]

Z. H. Huang and J. Sun, A non-interior continuation algorithm for the $P_0$ or $P_*$ LCP with strong global and local convergence properties, Appl. Math. Optim., 52 (2005), 237-262.

[13]

Z. H. Huang and S. W. Xu, Convergence properties of a non-interior-point smoothing algorithm for the $P_*$ NCP, J. Ind. Manag. Optim., 3 (2007), 569-584.

[14]

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems," Lecture Note in Computer Science, 538, Springer, New York, 1991.

[15]

L. C. Kong, J. Sun and N. H. Xiu, A regularized smoothing Newton method for symmetric cone complementarity problems, SIAM J. Optim., 19 (2008), 1028-1047.

[16]

L. C. Kong, L. Tunçel and N. H. Xiu, Fischer-Burmeister conplementarity function on Euclidean Jordan algebras, Pacific J. Optim., 6 (2010), 423-440.

[17]

X. H. Liu and Z. H. Huang, A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones, Math. Meth. Oper. Res., 70 (2009), 385-404.

[18]

Y. J. Liu, L. W. Zhang and Y. H. Wang, Analysis of smoothing method for symmetric conic linear programming, J. Appl. Math. Comput., 22 (2006), 133-148.

[19]

Z. Y. Luo and N. H. Xiu, Path-following interior point algorithms for the Cartesian $P_*(\kappa)$-LCP over symmetric cones, Sci. China, Ser. A, 52 (2009), 1769-1784.

[20]

S. H. Pan and J. S. Chen, A one-parametric class of merit functions for the symmetric cone complementarity problem, J. Math. Anal. Appl., 355 (2009), 195-215.

[21]

S. H. Pan and J. S. Chen, A regularization method for the second-order cone complementarity problem with the Cartesian $P_0$-property, Nonlinear Anal. - TMA, 70 (2009), 1475-1491.

[22]

L. Qi, D. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 87 (2000), 1-35.

[23]

S. H. Schimieta and F. Alizadeh, Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones, Math. Oper. Res., 26 (2001), 543-564.

[24]

S. H. Schimieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones, Math. Program., 96 (2003), 409-438.

[25]

H. Völiaho, $P_*(\kappa)$-matrices are just sufficient, Linear Algebra Appl., 239 (1996), 103-108.

[26]

A. Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones, SIAM J. Optim., 17 (2006), 1129-1153.

[27]

Y. B. Zhao and D. Li, A globally and locally superlinearly convergent non-interior-point algorithm for $P_0$ LCPs, SIAM J Optim., 13 (2003), 1196-1221.

[28]

Y. B. Zhao and D. Li, A new path-following algorithm for nonlinear $P_*$ complementarity problems, Comput. Optim. Appl., 34 (2005), 183-214.

show all references

References:
[1]

R. W. Cottle, J.-S. Pang and R. E. Stone, "The Linear Complementarity Problems," Academic Press, Boston, 1992.

[2]

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

[3]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.

[4]

L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86 (1997), 149-175.

[5]

L. Faybusovich and Y. Lu, Jordan-algebraic aspects of nonconvex optimization over symmetric cones, Appl. Math. Optim., 53 (2006), 67-77.

[6]

M. S. Gowda, R. Sznajder and J. Tao, Some $P$-properties for linear transformations on Euclidean Jordan algebras, Linear Algebra Appl., 393 (2004), 203-232.

[7]

Z. H. Huang, The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP, IMA J. Numer. Anal., 25 (2005), 670-684.

[8]

Z. H. Huang, Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms, Math. Meth. Oper. Res., 61 (2005), 41-55.

[9]

Z. H. Huang, S. L. Hu and J. Han, Global convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search, Sci. China, Ser. A, 52 (2009), 833-848.

[10]

Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones, Comput. Optim. Appl., 45 (2010), 557-579.

[11]

Z. H. Huang, L. Qi and D. Sun, Sub-quadratic convergence of a smoothing Newton algorithm for the $P_0$- and monotone LCP, Math. Program., 99 (2004), 423-441.

[12]

Z. H. Huang and J. Sun, A non-interior continuation algorithm for the $P_0$ or $P_*$ LCP with strong global and local convergence properties, Appl. Math. Optim., 52 (2005), 237-262.

[13]

Z. H. Huang and S. W. Xu, Convergence properties of a non-interior-point smoothing algorithm for the $P_*$ NCP, J. Ind. Manag. Optim., 3 (2007), 569-584.

[14]

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, "A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems," Lecture Note in Computer Science, 538, Springer, New York, 1991.

[15]

L. C. Kong, J. Sun and N. H. Xiu, A regularized smoothing Newton method for symmetric cone complementarity problems, SIAM J. Optim., 19 (2008), 1028-1047.

[16]

L. C. Kong, L. Tunçel and N. H. Xiu, Fischer-Burmeister conplementarity function on Euclidean Jordan algebras, Pacific J. Optim., 6 (2010), 423-440.

[17]

X. H. Liu and Z. H. Huang, A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones, Math. Meth. Oper. Res., 70 (2009), 385-404.

[18]

Y. J. Liu, L. W. Zhang and Y. H. Wang, Analysis of smoothing method for symmetric conic linear programming, J. Appl. Math. Comput., 22 (2006), 133-148.

[19]

Z. Y. Luo and N. H. Xiu, Path-following interior point algorithms for the Cartesian $P_*(\kappa)$-LCP over symmetric cones, Sci. China, Ser. A, 52 (2009), 1769-1784.

[20]

S. H. Pan and J. S. Chen, A one-parametric class of merit functions for the symmetric cone complementarity problem, J. Math. Anal. Appl., 355 (2009), 195-215.

[21]

S. H. Pan and J. S. Chen, A regularization method for the second-order cone complementarity problem with the Cartesian $P_0$-property, Nonlinear Anal. - TMA, 70 (2009), 1475-1491.

[22]

L. Qi, D. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 87 (2000), 1-35.

[23]

S. H. Schimieta and F. Alizadeh, Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones, Math. Oper. Res., 26 (2001), 543-564.

[24]

S. H. Schimieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones, Math. Program., 96 (2003), 409-438.

[25]

H. Völiaho, $P_*(\kappa)$-matrices are just sufficient, Linear Algebra Appl., 239 (1996), 103-108.

[26]

A. Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones, SIAM J. Optim., 17 (2006), 1129-1153.

[27]

Y. B. Zhao and D. Li, A globally and locally superlinearly convergent non-interior-point algorithm for $P_0$ LCPs, SIAM J Optim., 13 (2003), 1196-1221.

[28]

Y. B. Zhao and D. Li, A new path-following algorithm for nonlinear $P_*$ complementarity problems, Comput. Optim. Appl., 34 (2005), 183-214.

[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 and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53
[2]

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 and Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086
[3]

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 and Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363
[4]

Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[5]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[6]

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

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[8]

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

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[10]

Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145
[11]

A. S. Dzhumadil'daev. Jordan elements and Left-Center of a Free Leibniz algebra. Electronic Research Announcements, 2011, 18: 31-49. doi: 10.3934/era.2011.18.31
[12]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[13]

Yu-Lin Chang, Chin-Yu Yang. Some useful inequalities via trace function method in Euclidean Jordan algebras. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 39-48. doi: 10.3934/naco.2014.4.39
[14]

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 and Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153
[15]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066
[16]

Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021122
[17]

Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008
[18]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150
[19]

Xiaoqin Jiang, Ying Zhang. A smoothing-type algorithm for absolute value equations. Journal of Industrial and Management Optimization, 2013, 9 (4) : 789-798. doi: 10.3934/jimo.2013.9.789
[20]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (52)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy