One-step quadratic convergence of noninterior continuation method for NCP (Q1428890)

We consider the complementarity problem which is to find a vector \(x\in\mathbb{R}^n\) such that \[ x^TF(x)=0,\;x\geq 0,\;F(x)\geq 0,\tag{1} \] where \(F(x):\mathbb{R}^n \to\mathbb{R}^n\) is a continuously differentiable \(P_0\)-function on \(\mathbb{R}^n\) and \(\nabla F(x)\) is Lipschitz continuous on \(\mathbb{R}^n\). If \(F(x)=Mx +q(M\in\mathbb{R}^{n\times n}\), \(q\in\mathbb{R}^n)\), (1) is called the linear complementarity problem (LCP); otherwise, (1) is called the nonlinear complementarity problem (NCP). \textit{B. Chen} and \textit{N. Xiu} [SIAM J. Optim. 9, 605--623 (1999; Zbl 1037.90052] proposed the first globally linear and locally quadratic noninterior continuation algorithm for (1) based on the Chen-Mangasarian smoothing functions. In their algorithm, both the centering step and the approximate Newton step are used. The former guarantees the globally linear convergence; the latter ensures the locally quadratic convergence. Here a noninterior continuation method is presented, with only the certering step used at each iteration, for nonlinear complementarity problem. It is shown that the algorithm is globally linearly and locally quadratically convergent under certain conditions.