# On a Nonsmooth Gauss-Newton Algorithms for Solving Nonlinear Complementarity Problems
## 1 Introduction  
Let \(F:R^{n}\to R^{n}\) and let \(F_{i}\), \(i=1,...,n\) denote the components of \(F\). The nonlinear complementarity problem (NCP) is to find \(\mathbf{x}\in R^{n}\) such that  
\[\mathbf{x}\geq 0,F(\mathbf{x})\geq 0\text{ and }\mathbf{x}^{T}F(\mathbf{x})=0. \tag{1}\]  
The \(i\)th component of a vector \(\mathbf{x}\) is represented by \(x_{i}\). Solving (1) is equivalent to solving a nonlinear equation \(G(\mathbf{x})=0\), where the operator \(G:R^{n}\to R^{n}\) is defined by  
\[G(\mathbf{x})=\left[ \begin{array}{c}\varphi(x_{1},F_{1}(\mathbf{x}))\\...\\ \varphi(x_{n},F_{n}(\mathbf{x}))\end{array} \right]\]  
with some special function \(\varphi\). Function \(\varphi\) may have one of the following forms:  
\[\varphi_{1}(a,b) = \min\{a,b\};\] \[\varphi_{2}(a,b) = \sqrt{a^{2}+b^{2}}-a-b;\] \[\varphi_{3}(a,b) = \theta(|a-b|)-\theta(a)-\theta(b),\]  
where \(\theta:R\to R\) is any strictly increasing function with \(\theta(0)=0\), see [1]. The (NCP) problem is one of the fundamental problems of mathematical programming, operations research, economic equilibrium models, and in engineering sciences. A lot of interesting and important applications can be found in the papers of [PERSON] and [PERSON] [2] and [PERSON] and [PERSON] [3]. We can find the most essential applications in:engineering--optimal control problems, contact or structural mechanics problems, structural design problems, or traffic equilibrium problems,
* equilibrium modeling--general equilibrium (in production or consumption), invariant capital stock, or game-theoretic models. We borrow a technique used in solving some smooth problems. If \(g\) is a merit function of \(G\), i.e., \(g(\mathbf{x})=\frac{1}{2}G(\mathbf{x})^{T}G(\mathbf{x})\), then any stationary point of \(g(\mathbf{x})\) is a least-squares solution of the equation \(G(\mathbf{x})=0\). Then, algorithms for minimization are equivalent to algorithms for solving equations. The usual Gauss-Newton method (known also as the differential corrections method), presented by [PERSON] and [PERSON] [4] in the smooth case, has the form  
\[\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)}-\left[G^{\prime}(\mathbf{x}^{(k)})^{T}G^{\prime}(\mathbf{x }^{(k)})\right]^{-1}G^{\prime}(\mathbf{x}^{(k)})^{T}G(\mathbf{x}^{(k)}). \tag{2}\]  
Local convergence properties of the Gauss-Newton method was discussed by [PERSON] and [PERSON] [5], but only for some smooth case. The Levenberg-Marquardt method is also considered, which is a modified Gauss-Newton method, in some papers, e.g., [6] or [7]. Moreover, some comparison of semismooth algorithms for solving (NCP) problems has been made in [8]. In practice, we may also consider the damped Gauss-Newton method  
\[\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)}-\omega_{k}\left[G^{\prime}(\mathbf{x}^{(k)})^{T}G^{ \prime}(\mathbf{x}^{(k)})+\lambda_{k}I\right]^{-1}G^{\prime}(\mathbf{x}^{(k)})^{T}G( \mathbf{x}^{(k)}) \tag{3}\]  
with parameters \(\omega_{k}\) and \(\lambda_{k}\). Parameter \(\omega_{k}\) may be chosen to ensure suitable decrease of \(g\). If \(\lambda_{k}\) is positive for all \(k\), then the inverse matrix in (3) always exists because \(G^{\prime}(\mathbf{x}^{(k)})^{T}G(\mathbf{x}^{(k)})\) is a symmetric and positive semidefinite matrix. The method (3) has the important advantage: the search direction always exists, even if \(G^{\prime}(\mathbf{x})\) is singular. Naturally, in the case of nonsmooth equations, some additional assumptions are needed to allow the use of some line search strategies and to ensure the global convergence. Because, in some cases, a function \(G\) is nondifferentiable, so the equation \(G(\mathbf{x})=0\) will be nonsmooth, whereby the method (3) may be useless. Some version of the Gauss-Newton method for solving complementarity problems was also introduced by [PERSON] and [PERSON] [9] for generalized problems, but only for linear ones. Thus, for solving nonsmooth and nonlinear problems, we propose two new versions of a damped Gauss-Newton algorithm based on B-differential.