Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian P/P

Previous 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
JIMO Home
This Issue
Next Article
Global optimality conditions for some classes of polynomial integer programming problems

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

Abstract
Related Papers

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. 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., 106 (2006), 177. 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. 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. 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., 106 (2006), 513. 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. doi: 10.1016/j.nonrwa.2008.02.010. Google Scholar
[7]	F. H. Clarke, "Optimization and Nonsmooth Analysis,", Wiley Press, (1983). Google Scholar
[8]	J. Faraut and A. Koranyi, "Analysis on Symmetric Cones,", Clarendon Press, (1994). Google Scholar
[9]	F. Facchinei and F. Pang, "Finite-dimensional Variational Ineqaulities and Complementarity Problems, vol. I and II,", Springer-Verlag, (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. 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. 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. 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. 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., 99 (2004), 423. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Google Scholar
[25]	L. Q. Qi and J. Sun, A nonsmooth version of Newton's method,, Math. Program. Ser. A, 58 (1993), 353. 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. 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. 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. 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. 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., 106 (2006), 177. 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. 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. 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., 106 (2006), 513. 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. doi: 10.1016/j.nonrwa.2008.02.010. Google Scholar
[7]	F. H. Clarke, "Optimization and Nonsmooth Analysis,", Wiley Press, (1983). Google Scholar
[8]	J. Faraut and A. Koranyi, "Analysis on Symmetric Cones,", Clarendon Press, (1994). Google Scholar
[9]	F. Facchinei and F. Pang, "Finite-dimensional Variational Ineqaulities and Complementarity Problems, vol. I and II,", Springer-Verlag, (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. 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. 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. 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. 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., 99 (2004), 423. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Google Scholar
[25]	L. Q. Qi and J. Sun, A nonsmooth version of Newton's method,, Math. Program. Ser. A, 58 (1993), 353. 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. 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. 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. 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]	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
[9]	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
[10]	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
[11]	Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971
[12]	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
[13]	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
[14]	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
[15]	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
[16]	Raffaele D’Ambrosio, Giuseppe De Martino, Beatrice Paternoster. A symmetric nearly preserving general linear method for Hamiltonian problems. Conference Publications, 2015, 2015 (special) : 330-339. doi: 10.3934/proc.2015.0330
[17]	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
[18]	Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[19]	Jiří Benedikt. Continuous dependence of eigenvalues of $p$-biharmonic problems on $p$. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1469-1486. doi: 10.3934/cpaa.2013.12.1469
[20]	Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences