CSpace
Sub-quadratic convergence of a smoothing Newton algorithm for the P(0) and monotone LCP
Huang, ZH; Qi, LQ; Sun, DF
2004-04-01
Source PublicationMATHEMATICAL PROGRAMMING
ISSN0025-5610
Volume99Issue:3Pages:423-441
AbstractGiven M is an element of R(nxn) and q is an element of R(n), the linear complementarity problem (LCP) is to find (x, s) is an element of R(n) x R(n) such that (x, s) greater than or equal to 0, s = M(x) + q, x(T)s = 0. By using the Chen-Harker-Kanzow-Sniale (CHKS) smoothing function, the LCP is reformulated as a system of parameterized smooth-nonsmooth equations. As a result, a smoothing Newton algorithm, which is a modified version of the Qi-Sun-Zhou algorithm [Matheniatical Programming, Vol. 87, 2000, pp. 1-35], is proposed to solve the LCP with M being assumed to be a P(0)-matrix (P(0)-LCP). The proposed algorithm needs only to solve one system of linear equations and to do one line search at each iteration. It is proved in this paper that the proposed algorithm has the following convergence properties: (i) it is well-defined and any accumulation point of the iteration sequence is a solution of the P(0)-LCP: (ii) it generates a bounded sequence if the P(0)-LCP has a nonempty and bounded solution set: (iii) if an accumulation point of the iteration sequence satisfies a nonsingularity condition, which implies the P(0)-LCP has a unique solution, then the whole iteration sequence converges to this accumulation point sub-quadratically with a Q-rate 2 - t, where t is an element of (0, 1) is a parameter; and (iv) if M is positive semidefinite and an accumulation point of the iteration sequence satisfies a strict complementarity condition, then the whole sequence converges to the accumulation point quadratically.
Keywordlinear complementarity problem smoothing Newton method global convergence sub-quadratic convergence
DOI10.1007/s10107-003-0457-8
Language英语
WOS Research AreaComputer Science ; Operations Research & Management Science ; Mathematics
WOS SubjectComputer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000220991700002
PublisherSPRINGER
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/714
Collection中国科学院数学与系统科学研究院
Corresponding AuthorHuang, ZH
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100080, Peoples R China
2.Hong Kong Polytech Univ, Dept Appl Math, Hong Kong, Hong Kong, Peoples R China
3.Natl Univ Singapore, Dept Math, Singapore 117543, Singapore
Recommended Citation
GB/T 7714
Huang, ZH,Qi, LQ,Sun, DF. Sub-quadratic convergence of a smoothing Newton algorithm for the P(0) and monotone LCP[J]. MATHEMATICAL PROGRAMMING,2004,99(3):423-441.
APA Huang, ZH,Qi, LQ,&Sun, DF.(2004).Sub-quadratic convergence of a smoothing Newton algorithm for the P(0) and monotone LCP.MATHEMATICAL PROGRAMMING,99(3),423-441.
MLA Huang, ZH,et al."Sub-quadratic convergence of a smoothing Newton algorithm for the P(0) and monotone LCP".MATHEMATICAL PROGRAMMING 99.3(2004):423-441.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Huang, ZH]'s Articles
[Qi, LQ]'s Articles
[Sun, DF]'s Articles
Baidu academic
Similar articles in Baidu academic
[Huang, ZH]'s Articles
[Qi, LQ]'s Articles
[Sun, DF]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Huang, ZH]'s Articles
[Qi, LQ]'s Articles
[Sun, DF]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.