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

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378
[2]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442
[3]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075
[4]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445
[5]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[6]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[7]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[8]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHum approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[9]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[10]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168
[11]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[12]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[13]

Monia Capanna, Jean C. Nakasato, Marcone C. Pereira, Julio D. Rossi. Homogenization for nonlocal problems with smooth kernels. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020385
[14]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446
[15]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[16]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[17]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[18]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[19]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[20]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences