American Institute of Mathematical Sciences

Advanced
  • 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

Li-Xia Liu 1, , Sanyang Liu 2, and  Chun-Feng Wang 3,

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.
Keywords: smoothing Newton method., linear complementarity problems, Cartesian $P$/$P_0$-property, Symmetric cone.
Mathematics Subject Classification: Primary: 90C25; Secondary: 90C3.
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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[8]

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

[9]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[23]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[8]

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

[9]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[23]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

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

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
[3]

Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP. Journal of Industrial & Management Optimization, 2012, 8 (1) : 67-86. doi: 10.3934/jimo.2012.8.67
[4]

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
[5]

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
[6]

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

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

Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021044
[9]

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

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
[11]

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
[12]

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 & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[13]

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

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

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

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

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

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

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

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences