• Previous Article
    Global optimality conditions for some classes of polynomial integer programming problems
  • JIMO Home
  • This Issue
  • Next Article
    A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture
January  2011, 7(1): 53-66. doi: 10.3934/jimo.2011.7.53

Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property

1. 

Department of Applied Mathematics, Xidian University, Xi'an 710071, China

2. 

Department of Applied Mathematics, Xidian University, Xi'an, 710071, China

3. 

College of Mathematics and Information, Henan Normal University, Xinxiang 453007, China

Received  April 2010 Revised  September 2010 Published  January 2011

A smoothing Newton method based on the CHKS smoothing function for a class of non-monotone symmetric cone linear complementarity problem (SCLCP) with the Cartesian $P$-property and a regularization smoothing Newton method for SCLCP with the Cartesian $P_0$-property are proposed. The existence of Newton directions and the boundedness of iterates, two important theoretical issues encountered in the smoothing method, are showed for these two classes of non-monotone SCLCP. Finally, we show that these two algorithms are globally convergent. Moreover, they are globally linear and locally quadratic convergent under a nonsingular assumption.
Citation: 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
References:
[1]

X. D. Chen, D. Sun and J. Sun, Complementarity functions and numerical experiments on smoothing Newton methods for second-order-cone complementarity problems, Comput. Optim. Appl., 25 (2003), 39-56. doi: 10.1023/A:1022996819381.

[2]

X. Chen and H. D. Qi, Cartesian P-property and its applications to the semidefinite linear complementarity problem, Math. Program., Ser. A 106 (2006), 177-201.

[3]

X. J. Chen and Y. Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities, SIAM J. Control. Optim., 37 (1999), 589-616. doi: 10.1137/S0363012997315907.

[4]

X. J. Chen, Smoothing methods for complementarity problems and their applications: A survey, J. Oper. Res. Soc. Japan, 43 (2000), 32-47. doi: 10.1016/S0453-4514(00)88750-5.

[5]

X. J. Chen and S. H. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program., Ser. A 106 (2006), 513-525.

[6]

X. H. Chen and C. F. Ma, A regularization smoothing Newtone method for solving nonlinear complementarity problem, Nonlinear Anal. Real World Appl., 10 (2009), 1702-1711. doi: 10.1016/j.nonrwa.2008.02.010.

[7]

F. H. Clarke, "Optimization and Nonsmooth Analysis," Wiley Press, New York, 1983.

[8]

J. Faraut and A. Koranyi, "Analysis on Symmetric Cones," Clarendon Press, Oxford, 1994.

[9]

F. Facchinei and F. Pang, "Finite-dimensional Variational Ineqaulities and Complementarity Problems, vol. I and II," Springer-Verlag, New York, 2003.

[10]

F. Facchinei and C. Kanzow, Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM J. Control Optim., 37 (1999), 1150-1161. doi: 10.1137/S0363012997322935.

[11]

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. doi: 10.1016/j.laa.2004.03.028.

[12]

D. R. Han, On the coerciveness of some merit functions for complementarity problems over symmetric cones, J. Math. Anal. Appl., 336 (2007), 727-737. doi: 10.1016/j.jmaa.2007.03.003.

[13]

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

[14]

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

[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. doi: 10.1137/060676775.

[16]

L. C. Kong, L. Tuncel and N. H. Xiu, Vector-valued implicit Lagrangian for Symmetric cone complementarity problems, Asia-Pac. J. Oper. Res., 26 (2009), 199-233.

[17]

M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Application of second-order cone programming, Linear Algebra Appl., 284 (1998), 193-228. doi: 10.1016/S0024-3795(98)10032-0.

[18]

Y. J. Liu, L. W. Zhang and Y. H. Wang, Some properties of a class of merit functions for symmetric cone complementarity problems, Asia-Pac. J. Oper. Res., 23 (2006), 473-495.

[19]

Y. J. Liu, L. W. Zhang and M. J. Liu, Extension of smoothing functions to symmetric cone complementarity problems, Appl. Math. J. Chinese Univ. Ser. B, 22 (2007), 245-252. doi: 10.1007/s11766-007-0214-5.

[20]

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

[21]

X. H. Liu and W. Z. Gu, Smoothing Newton algorithms based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones, J. Ind. Manag Optim., 6 (2010), 363-380.

[22]

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. doi: 10.1007/s11425-008-0174-0.

[23]

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

[24]

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

[25]

L. Q. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program. Ser. A, 58 (1993), 353-367. doi: 10.1007/BF01581275.

[26]

D. F. Sun and J. Sun, Löwner's operator and spectral functions in euclidean Jordan algebras, Math. Oper. Res., 33 (2008), 421-445. doi: 10.1287/moor.1070.0300.

[27]

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

[28]

L. P. Zhang and X. S. Zhang, Global linear and quadratic one-step smoothing Newton method for $P_0$-LCP, J. Global Optim., 25 (2003), 363-376. doi: 10.1023/A:1022528320719.

show all references

References:
[1]

X. D. Chen, D. Sun and J. Sun, Complementarity functions and numerical experiments on smoothing Newton methods for second-order-cone complementarity problems, Comput. Optim. Appl., 25 (2003), 39-56. doi: 10.1023/A:1022996819381.

[2]

X. Chen and H. D. Qi, Cartesian P-property and its applications to the semidefinite linear complementarity problem, Math. Program., Ser. A 106 (2006), 177-201.

[3]

X. J. Chen and Y. Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities, SIAM J. Control. Optim., 37 (1999), 589-616. doi: 10.1137/S0363012997315907.

[4]

X. J. Chen, Smoothing methods for complementarity problems and their applications: A survey, J. Oper. Res. Soc. Japan, 43 (2000), 32-47. doi: 10.1016/S0453-4514(00)88750-5.

[5]

X. J. Chen and S. H. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program., Ser. A 106 (2006), 513-525.

[6]

X. H. Chen and C. F. Ma, A regularization smoothing Newtone method for solving nonlinear complementarity problem, Nonlinear Anal. Real World Appl., 10 (2009), 1702-1711. doi: 10.1016/j.nonrwa.2008.02.010.

[7]

F. H. Clarke, "Optimization and Nonsmooth Analysis," Wiley Press, New York, 1983.

[8]

J. Faraut and A. Koranyi, "Analysis on Symmetric Cones," Clarendon Press, Oxford, 1994.

[9]

F. Facchinei and F. Pang, "Finite-dimensional Variational Ineqaulities and Complementarity Problems, vol. I and II," Springer-Verlag, New York, 2003.

[10]

F. Facchinei and C. Kanzow, Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM J. Control Optim., 37 (1999), 1150-1161. doi: 10.1137/S0363012997322935.

[11]

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. doi: 10.1016/j.laa.2004.03.028.

[12]

D. R. Han, On the coerciveness of some merit functions for complementarity problems over symmetric cones, J. Math. Anal. Appl., 336 (2007), 727-737. doi: 10.1016/j.jmaa.2007.03.003.

[13]

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

[14]

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

[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. doi: 10.1137/060676775.

[16]

L. C. Kong, L. Tuncel and N. H. Xiu, Vector-valued implicit Lagrangian for Symmetric cone complementarity problems, Asia-Pac. J. Oper. Res., 26 (2009), 199-233.

[17]

M. S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Application of second-order cone programming, Linear Algebra Appl., 284 (1998), 193-228. doi: 10.1016/S0024-3795(98)10032-0.

[18]

Y. J. Liu, L. W. Zhang and Y. H. Wang, Some properties of a class of merit functions for symmetric cone complementarity problems, Asia-Pac. J. Oper. Res., 23 (2006), 473-495.

[19]

Y. J. Liu, L. W. Zhang and M. J. Liu, Extension of smoothing functions to symmetric cone complementarity problems, Appl. Math. J. Chinese Univ. Ser. B, 22 (2007), 245-252. doi: 10.1007/s11766-007-0214-5.

[20]

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

[21]

X. H. Liu and W. Z. Gu, Smoothing Newton algorithms based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones, J. Ind. Manag Optim., 6 (2010), 363-380.

[22]

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. doi: 10.1007/s11425-008-0174-0.

[23]

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

[24]

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

[25]

L. Q. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program. Ser. A, 58 (1993), 353-367. doi: 10.1007/BF01581275.

[26]

D. F. Sun and J. Sun, Löwner's operator and spectral functions in euclidean Jordan algebras, Math. Oper. Res., 33 (2008), 421-445. doi: 10.1287/moor.1070.0300.

[27]

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

[28]

L. P. Zhang and X. S. Zhang, Global linear and quadratic one-step smoothing Newton method for $P_0$-LCP, J. Global Optim., 25 (2003), 363-376. doi: 10.1023/A:1022528320719.

[1]

Yan Li, Liping Zhang. A smoothing Newton method preserving nonnegativity for solving tensor complementarity problems with $ P_0 $ mappings. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022041

[2]

Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial and Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

[8]

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

[9]

Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044

[10]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[11]

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

[12]

Jianguo Huang, Sen Lin. A $ C^0P_2 $ time-stepping virtual element method for linear wave equations on polygonal meshes. Electronic Research Archive, 2020, 28 (2) : 911-933. doi: 10.3934/era.2020048

[13]

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

[14]

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

[15]

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

[16]

Zhengyong Zhou, Bo Yu. A smoothing homotopy method based on Robinson's normal equation for mixed complementarity problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 977-989. doi: 10.3934/jimo.2011.7.977

[17]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[18]

Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete and Continuous Dynamical Systems, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971

[19]

Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial and Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006

[20]

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

2020 Impact Factor: 1.801

Metrics

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

Other articles
by authors

[Back to Top]