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

Zheng-Hai Huang; Nan Lu

doi:10.3934/jimo.2012.8.67

Previous Article
Solving Partitioning-Hub Location-Routing Problem using DCA
JIMO Home
This Issue
Next Article
A penalty method for generalized Nash equilibrium problems

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

Abstract
Related Papers

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 & 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, (1992). Google Scholar
[2]	J. Faraut and A. Korányi, "Analysis on Symmetric Cones, Oxford Mathematical Monographs,", Oxford University Press, (1994). Google Scholar
[3]	L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331. Google Scholar
[4]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms,, J. Comput. Appl. Math., 86 (1997), 149. Google Scholar
[5]	L. Faybusovich and Y. Lu, Jordan-algebraic aspects of nonconvex optimization over symmetric cones,, Appl. Math. Optim., 53 (2006), 67. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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, 52 (2009), 833. Google Scholar
[10]	Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones,, Comput. Optim. Appl., 45 (2010), 557. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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 (1991). 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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[19]	Z. Y. Luo and N. H. Xiu, Path-following interior point algorithms for the Cartesian $P_(\kappa)$-LCP over symmetric cones,, Sci. China*, 52 (2009), 1769. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[24]	S. H. Schimieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones,, Math. Program., 96 (2003), 409. Google Scholar
[25]	H. Völiaho, $P_(\kappa)$-matrices are just sufficient,, Linear Algebra Appl., 239* (1996), 103. Google Scholar
[26]	A. Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones,, SIAM J. Optim., 17 (2006), 1129. Google Scholar
[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. Google Scholar
[28]	Y. B. Zhao and D. Li, A new path-following algorithm for nonlinear $P_$ complementarity problems,, Comput. Optim. Appl.*, 34 (2005), 183. Google Scholar

show all references

References:

[1]	R. W. Cottle, J.-S. Pang and R. E. Stone, "The Linear Complementarity Problems,", Academic Press, (1992). Google Scholar
[2]	J. Faraut and A. Korányi, "Analysis on Symmetric Cones, Oxford Mathematical Monographs,", Oxford University Press, (1994). Google Scholar
[3]	L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms,, Positivity, 1 (1997), 331. Google Scholar
[4]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms,, J. Comput. Appl. Math., 86 (1997), 149. Google Scholar
[5]	L. Faybusovich and Y. Lu, Jordan-algebraic aspects of nonconvex optimization over symmetric cones,, Appl. Math. Optim., 53 (2006), 67. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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, 52 (2009), 833. Google Scholar
[10]	Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones,, Comput. Optim. Appl., 45 (2010), 557. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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 (1991). 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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[19]	Z. Y. Luo and N. H. Xiu, Path-following interior point algorithms for the Cartesian $P_(\kappa)$-LCP over symmetric cones,, Sci. China*, 52 (2009), 1769. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[24]	S. H. Schimieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones,, Math. Program., 96 (2003), 409. Google Scholar
[25]	H. Völiaho, $P_(\kappa)$-matrices are just sufficient,, Linear Algebra Appl., 239* (1996), 103. Google Scholar
[26]	A. Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones,, SIAM J. Optim., 17 (2006), 1129. Google Scholar
[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. Google Scholar
[28]	Y. B. Zhao and D. Li, A new path-following algorithm for nonlinear $P_$ complementarity problems,, Comput. Optim. Appl.*, 34 (2005), 183. Google Scholar

[1]	J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[2]	Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020027
[3]	Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[4]	Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[5]	Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[6]	Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[7]	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
[8]	Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020401
[9]	Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[10]	Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[11]	Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[12]	Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors