One-step quadratic convergence of noninterior continuation method for NCP

Variational inequalities (49J40) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: One-step quadratic convergence of noninterior continuation method for NCP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1428890)