# On a Nonsmooth Gauss-Newton Algorithms for Solving Nonlinear Complementarity Problems
## 2 Materials and Methods
### The Algorithm and Its Convergence
Otherwise, choose any matrix \(\mathbf{V}_{k}\in\partial_{B}G(\mathbf{x}^{(k)})\) and let \(\mathbf{A}_{k}=\mathbf{V}_{k}^{T}\mathbf{V}_{k}\). Step 2: Let \(\lambda_{k}=g(\mathbf{x}^{(k)})\). Step 3: Find \(\mathbf{d}^{(k)}\) that is a solution of the linear system \[G_{i}(\mathbf{x}):=\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x})) -\theta(x_{i}) \tag{5}\]0 Step 4: Compute the smallest nonnegative integer \(m_{k}\) such that \[G_{i}(\mathbf{x}):=\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x})) -\theta(x_{i}) \tag{5}\]1 and set \[G_{i}(\mathbf{x}):=\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x})) -\theta(x_{i}) \tag{5}\]2
```  
**Algorithm 1**The damped Gauss-Newton method for solving NCP  
**Remark 3**. : _(i) In Step 2, letting \(\lambda_{k}=g(\mathbf{x}^{(k)})\) is one of the simplest strategy because then \(\{\lambda_{k}\}\) converges to 0. (ii) The line search step (Step 4) in the algorithm follows the Arnijo rule._  
**Theorem 2**. : _Let \(\mathbf{x}^{(0)}\) be a starting point and \(\{\mathbf{x}^{(k)}\}\) be a sequence generated by Algorithm 1. Assume that: (a) \(\sup_{k}\left\|\mathbf{V}_{k}\right\|<\infty\) for all \(\mathbf{V}_{k}\in\partial_{B}G(\mathbf{x}^{(k)})\); (b) \(\
abla g(\mathbf{x})\) is Lipschitzian with a constant \(\mathrm{L}_{g}>0\) on the level set \(\mathrm{L}=\Big{\{}\mathbf{x}:g(\mathbf{x})\leq g(\mathbf{x}^{(0)})\Big{\}}\)._  
_Then, the generalized damped Gauss-Newton method described by Algorithm 1 is well defined and either \(\{\mathbf{x}^{(k)}\}\) terminates at a stationary point of \(g\), or else every accumulation point of \(\{\mathbf{x}^{(k)}\}\), if it exists, is a stationary point of \(g\)._  
Proof. : The proof is almost the same as Theorem 2.1 in [10], providing appropriately modified assumptions. For the nonsmooth case, the alternative condition may be considered instead of Lipschitz continuity of \(\
abla g(\mathbf{x})\) (similar as in [10]). Thus, we have the following convergence theorem:  
**Theorem 3**. : _Let \(\mathbf{x}^{(0)}\) be a starting point and \(\{x^{(k)}\}\) be a sequence generated by Algorithm 1. Assume that: (a) the level set \(\mathrm{L}=\left\{\mathbf{x}:g(\mathbf{x})\leq g(\mathbf{x}^{(0)})\right\}\) is bounded; (b) \(G\) is semismooth on \(\mathrm{L}\)._  
_Then, the generalized damped Gauss-Newton method described by Algorithm 1 is well defined and either \(\{\mathbf{x}^{(k)}\}\) terminates at a stationary point of \(g\), or else every accumulation point of \(\{\mathbf{x}^{(k)}\}\), if it exists, is a stationary point of \(g\)._  
Now, we take up the rate of convergence of the considered algorithm. The following theorem shows suitable conditions in various cases. **Theorem 4**. : _Suppose that \(\mathbf{x}^{*}\) is a solution of problem (1), \(G\) is semismooth, and \(G\) is BD-regular at \(\mathbf{x}^{*}\). Then, there exists a neighborhood \(N_{*}\) of \(\mathbf{x}^{*}\) such that, if \(\mathbf{x}^{(0)}\in N_{*}\) and the sequence \(\{\mathbf{x}^{(k)}\}\) is generated by Algorithm 1, we have: (i) \(\mathbf{x}^{(k)}\in N_{*}\) for all \(k\) and the sequence \(\{\mathbf{x}^{(k)}\}\) is linear convergent to \(x^{*}\); (ii) if \(\delta<0.5\), then the convergence is at least superlinear; (iii) If \(G\) is strongly semismooth, then the convergence is quadratic._  
Proof. : The proof of similar theorem given by [PERSON] and [PERSON] [10] is based on three lemmas, which have the same assumptions as theorem. Now, we present these lemmas in versions adapted to our nonsmooth case. **Lemma 3**. : _Assume that \(\mathbf{d}_{x}\) is a solution of the equation_  
\[G_{i}(\mathbf{x}):=\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x})) -\theta(x_{i}) \tag{5}\]3  
_where_  
\[G_{i}(\mathbf{x}):=\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x})) -\theta(x_{i}) \tag{5}\]4  
_for some matrix \(\mathbf{V}_{x}\) taken from \(\partial_{B}G(\mathbf{x})\).