Sub-quadratic convergence of a smoothing Newton algorithm for the P0 and monotone LCP

• 成果类型: Article
• 署名作者: Huang, ZH; Qi, LQ; Sun, DF
• 署名单位: Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Hong Kong Polytechnic University; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0457-8
• 发表日期: 2004
• 页码: 423-441
• 关键词: path-following algorithm; nonlinear complementarity-problems; variational inequality problems; noninterior continuation method; interior point algorithms; global linear convergence; regularization

摘要

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