Sub-quadratic convergence of a smoothing Newton algorithm for the P 0 ? and monotone LCP

• DOI: 10.1007/s10107-003-0457-8
• Publication Date: 2004-03-20T14:43:52Z
• Authors: Zheng-Hai Huang; Liqun Qi; Defeng Sun
• Keywords: Linear complementarity problem; Smoothing Newton method; 0211 other engineering and technologies; 02 engineering and technology; Sub-quadratic convergence; 0101 mathematics; Global convergence; 01 natural sciences; 510

Given *** equation here ***, the linear complementarity problem (LCP) is to find *** equation here *** such that (x, s)≥ 0,s=Mx+q,xTs=0. By using the Chen-Harker-Kanzow-Smale (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 [Mathematical Programming, Vol. 87, 2000, pp. 1–35], is proposed to solve the LCP with M being assumed to be a P0-matrix (P0–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 P0–LCP; (ii) it generates a bounded sequence if the P0–LCP has a nonempty and bounded solution set; (iii) if an accumulation point of the iteration sequence satisfies a nonsingularity condition, which implies the P0–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∈(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.