# On a Nonsmooth Gauss-Newton Algorithms for Solving Nonlinear Complementarity Problems
## 2 Materials and Methods
### The Algorithm and Its Convergence  
Consider nonlinear equation \(G(\mathbf{x})=0\) defined by \(\varphi_{3}\). The equivalence of solving this equation and problem (NCP) is described by the following theorem:  
**Theorem 1** (Mangasarian [1]). : _Let \(\theta\) be any strictly increasing function from \(R\) into \(R\), that is, \(a>b\Leftrightarrow\theta(a)>\theta(b)\), and let \(\theta(0)=0\). Then, \(\mathbf{x}\) solves the complementarity problem (1) if and only if_  
\[\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x}))-\theta(x_{i})= 0,\ i=1,2,...,n. \tag{4}\]  
For the convenience, denote  
\[G_{i}(\mathbf{x}):=\theta(\left|F_{i}(\mathbf{x})-x_{i}\right|)-\theta(F_{i}(\mathbf{x})) -\theta(x_{i}) \tag{5}\]  
for \(i=1,2,...,n\). We assume that the function \(\theta\) in Theorem 1 has the form  
\[\theta(\xi)=\xi\left|\xi\right|.\]  
Let \(G(\mathbf{x})\) be the associated function. We define function \(g\) in the following way:  
\[g(\mathbf{x})=\frac{1}{2}\left\|G(\mathbf{x})\right\|^{2},\]  
which allows for solving system \(G(\mathbf{x})=0\) based on solving the nonlinear least-square problem  
\[\min_{\mathbf{x}}g(\mathbf{x}). \tag{6}\]  
Let us note that \(\mathbf{x}^{*}\) solves \(G(\mathbf{x})=0\) if and only if it is a stationary point of \(g\). Thus, from Theorem 1, \(\mathbf{x}^{*}\) solves (1). **Remark 2**. : _On the other hand, the first-order optimality conditions for problem (6) are equivalent to the nonlinear system_  
\[\
abla g(\mathbf{x})=G^{\prime}(\mathbf{x})^{T}G(\mathbf{x})=0,\]  
_where \(\
abla g\) is the gradient of \(g\), provided \(G\) is differentiable and \(G^{\prime}\) is the Jacobian matrix of \(G\)._  
The continuous differentiability of the merit function \(g\) for some kind of nonsmooth functions was established by [PERSON] in the following lemma:  
**Lemma 1** ([PERSON], [19]). : _Assume that the function \(G:R^{n}\supset D\to R^{n}\) is semismooth, or, stronger, \(p\)-order semismooth, \(0<p\leq 1\), then the merit function \(\frac{1}{2}\left\|G(\mathbf{x})\right\|^{2}\) is continuously differentiable on \(D\) with gradient \(\
abla g(\mathbf{x})=\mathbf{V}^{T}G(\mathbf{x})\), where \(\mathbf{V}\in\partial G(\mathbf{x})\) is arbitrary._  
**Lemma 2**. : _For any \(\mathbf{x}\in R^{n}\), let \(\mathbf{A}_{x}=\mathbf{V}_{x}^{T}\mathbf{V}_{x}\), where \(\mathbf{V}_{x}\in\partial_{B}G(\mathbf{x})\). Suppose that \(\
abla g(\mathbf{x})\
eq 0\). Then, given \(\lambda>0\), the direction \(\mathbf{d}\) given by_  
\[(\mathbf{A}_{x}+\lambda\mathbf{I})\mathbf{d}=\
abla g(\mathbf{x})\]  
_is an ascent direction for \(g\). In particular, there is a positive \(\mathbf{w}\) such that \(g(\mathbf{x}-\mathbf{w}\mathbf{d})<g(\mathbf{x})\)._Proof. : There exist constants \(\beta\geq 0\) and \(\gamma>0\) such that  
\[\beta\left\|\mathbf{h}\right\|^{2}\leq\mathbf{h}^{T}\mathbf{A}_{x}\mathbf{h}\leq \gamma\left\|\mathbf{h}\right\|^{2}\text{ for all }\mathbf{h}\in R^{n},\]  
because \(\mathbf{A}_{x}\) defined as \(\mathbf{V}_{x}^{T}\mathbf{V}_{x}\) is symmetric and positive semidefinite. It follows that  
\[(\beta+\lambda)\left\|\mathbf{h}\right\|^{2}\leq\mathbf{h}^{T}(\mathbf{A}_{x} +\lambda\mathbf{I})\mathbf{h}\leq(\gamma+\lambda)\left\|\mathbf{h}\right\|^{2}\text{ for all }\mathbf{h}\in R^{n}.\]  
Since \(\
abla g(\mathbf{x})\
eq 0\), \(\mathbf{d}\
eq 0\). If we take \(\mathbf{h}=\mathbf{d}\), we obtain  
\[\mathbf{d}^{T}\
abla g(\mathbf{x})\geq(\beta+\lambda)\left\|\mathbf{d}\right\|^{2}>0.\]  
It follows that \(\
abla g(\mathbf{x})\mathbf{d}>0\) and that \(\mathbf{d}\) is a ascent direction for \(g\) (Section 8.2.1 in [4]). Now, we present the generalized version of the damped Gauss-Newton method for solving the nonlinear complementarity problem. ```
Let \(\beta,\delta\in(0,1)\) be given. Let \(\mathbf{x}^{(0)}\) be a starting point. Given \(\mathbf{x}^{(k)}\), the steps for obtaining \(\mathbf{x}^{(k+1)}\) are: Step 1: If \(\
abla g(\mathbf{x}^{(k)})=0\), then stop.