\(^\ast \) Department of Mathematics, University of Abbas Ferhat Sétif 1, Sétif, Algeria, e-mail: achache_m@univ-setif.dz.

1 Introduction

We consider the following absolute value equations (AVE) of the type:

where \(A,B\in \mathbb {R}^{n\times n}\) (\(B\neq 0\)), \(b\in \mathbb {R}^{n}\) and \(\left| x\right|\) denotes the vector with absolute values of each component of \(x\in \mathbb {R}^{n}\). When \(B=I\) where \(I\) is the identity matrix, the AVE (1) reduces to the absolute value equations of the type:

In [ 6 ] , [ 8 ] , [ 9 ] , [ 14 ] , some frequently optimization problems such as linear programming, convex quadratic programming, bimatrix games [ 4 ] and the linear complementarity problem (LCP) can be equivalently reformulated as the AVE (1)–(2). Up to now several authors interested to study this topic, cf. e.g. Mangasarian [ 6 ] , Mangasarian and Meyer [ 9 ] , Prokopyev [ 14 ] , Rohn [ 16 ] , [ 18 ] and Lotfi and Veiseh [ 12 ] . Besides, various numerical methods for solving the AVE (1)–(2) have been proposed, cf. e.g. Cacetta [ 3 ] , Haghani et al. [ 5 ] , Noor et al. [ 10 ] , Jiang and Zhang [ 15 ] , Rhon [ 17 ] , Abdallah et al. [ 2 ] and recently, Achache and Hazzam [ 1 ] . Generally, the AVE problem is an NP-hard in its general form since the LCP can be formulated as the AVE (see [ 8 ] ). In [ 7 ] , a generalized Newton algorithm for the AVE (2) was investigated, in which it was proved that this method converges globally linear from any starting point to the unique solution of the AVE (2) under the condition that \(\| A^{-1}\| {\lt}\tfrac {1}{4}\). Later on, Li [ 11 ] , developed a modified generalized Newton for solving the AVE (2). His approach is based on introducing an identity matrix such that a modified generalized Newton method for solving the AVE (2) can be established. He showed under certain conditions that this method converges linearly global to a solution of AVE (2).

In this paper we are interested in a first part of it in the unique solvability of the AVE (1). We show that the condition \(\| A^{-1}\| {\lt}\tfrac {1}{\left\| B\right\| }\) is sufficient to guarantee the unique solvability of the AVE (1) for each \(b\in \mathbb {R}^{n}.\) This generalizes an earlier result by Mangasarian and Meyer who showed in [ 9 , Proposition 4 ] , that the absolute value equations of the type (2) is uniquely solvable for each \(b\in \mathbb {R}^{n}\) if \(\| A^{-1}\| {\lt}1.\) To do so, we transform the AVE (1) into a standard linear complementarity problem (LCP) and show under the above mentioned condition that the LCP has a unique solution, so is the AVE (1) for every \(b\in \mathbb {R}^{n}\).

In the second part, inspired by the work of Mangasarian [ 7 ] , we propose a generalized Newton method to solve the AVE (1). When \(\| A^{-1}\| {\lt}\tfrac {1}{4\left\| B\right\| },\) we show that the method is globally convergent to the unique solution of AVE (1) for every \(b\in \mathbb {R}^{n}\). Finally, some numerical results are presented to show the efficiency of this approach. In addition, a numerical comparison is made with an available method.

The paper is built as follows. In section 2, the main result of the unique solvability of the AVE (1) is stated. In section 3, a generalized Newton method is proposed for solving the AVE (1). The linearly global convergence of the method is established. In section 4, numerical results are reported to validate the efficiency of our approach. In section 5, some concluding remarks are given.

The notation used throughout the paper is as follows. The scalar product of two vectors \(x\) and \(y\) in \(\mathbb {R}^{n}\) will be denoted by \(\langle x,y\rangle =x^{T}y.\) For \(x\in \mathbb {R}^{n},\) the norm \(\Vert x\Vert \) will denote the Euclidean norm \((x^{T}x)^{\frac{1}{2}}.\) For a matrix \(A\in \mathbb {R}^{n\times n},\) the transpose of \(A\) is denoted by \(A^{T}.\) The induced spectral norm of a matrix \(A\) is denoted by \(\Vert A\Vert =\max _{\left\Vert x\right\Vert =1}\Vert Ax\Vert .\) This definition implies that \(\Vert Ax\Vert \leq \Vert A\Vert \) \(\Vert x\Vert \) and \(\Vert AB\Vert \leq \Vert A\Vert \Vert B\Vert \) for any matrices \(A,B\in \mathbb {R}^{n\times n}.\) Let \(\left\{ \alpha _{k}\right\} \) be a non negative sequence of real numbers converging to zero, then the convergence of \(\left\{ \alpha _{k}\right\} \) is said to be linear if there exists \(\rho \in \left( 0,1\right)\) such that \(\alpha _{k+1}\leq \rho \alpha _{k}\) for \(k\geq k_{0}.\) For a matrix \(A\in {\mathbb R}^{n\times n}\), its eigenvalues are denoted by \(\lambda (A)\) with \(\lambda _{\min }(A)\) and \(\lambda _{\max }(A)\) are called the smallest and the greatest eigenvalue of \(A\), respectively. Finally, the notation \(x\geq 0,\) means that the components of \(x\) are greater or equal to zero.

2 The unique solvability of the AVE

Throughout the paper, we make the following assumption on the AVE (1).

In the proof of the main result, we shall reformulate the AVE (1) as an equivalent standard LCP. Then, one may investigate the AVE (1) across the LCP by making use of the theory of LCP where we invoke under our assumption the class of \(\mathcal{P}\)-matrix, to conclude the unique solvability of the AVE (1) for each \(b\in \mathbb {R}^{n}.\)

Now, we recall some necessary definitions and auxiliary results that will be used later to prove the unique solvability of the AVE (1).

As a consequence an important result has been proved by Cottle et al. [ 4 ] , where any \(\mathcal{P}\)-LCP has a unique solution for every \(q\in \mathbb {R}^{n}.\) Indeed \((A-B)\) is nonsingular. For if not then for some \(x\neq 0,\) we have \((A-B)x=0,\) which will derive a contradiction. This implies that \(x=A^{-1}Bx.\) Hence by Assumption 1 it follows that \(\Vert x\Vert \leq \Vert A^{-1}\Vert \Vert B\Vert \Vert x\Vert {\lt}\Vert x\Vert \) which is a contradiction. Therefore \((A-B)\) is nonsingular. This achieves the proof. â–¡

2.1 Reformulation of the AVE as a standard LCP

According to the decomposition of \(x\) and \(\vert x\vert \) in (4), the AVE (1) can be reformulated to the following standard LCP: find \(x^{+}\geq 0,x^{-}\geq 0,\) such that

where \(M=(A-B)^{-1}(A+B)\) and \(q=(A-B)^{-1}b.\) This achieves the proof.â–¡

We are now ready to state our main result concerning the unique solvability of the AVEs.

We shall prove that the LCP in (5) has a unique solution i.e., we prove \(M=(A-B)^{-1}(A+B)\) is positive definite. We have for all \(x\neq 0\),

Letting \((A^{T}-B^{T})^{-1}x=z,\) hence we get,

since \(\langle (BA^{T}-AB^{T})z,z\rangle =0,\) for all \(z\in \mathbb {R}^{n}.\) We have by Cauchy-Schwartz inequality and Assumption 1 that

where \(y=Az.\) Therefore \((A-B)^{-1}(A+B)\) is positive definite and the LCP in (5) is a \(\mathcal{P}-\)LCP. By Theorem 4, the LCP has a unique solution for each \(b\) and so the AVE (1). This achieves the proof. â–¡

In the next section, we propose a generalized Newton method for solving the AVE (1). In the sequel of the analysis of the proposed method, we will guard the Assumption 1, where we prove under this latter that the generalized Newton method is well-defined i.e., the generalized Jacobian matrix is nonsingular.

3 A generalized Newton method for the AVE

By defining the function \(f:\mathbb {R}^{n}\rightarrow \mathbb {R}^{n}\) by

it is clear that \(x\) is a solution of the AVE (1) if and only if

Notice that \(|x|\) is not differentiable. A generalized Jacobian \(\partial \vert x\vert \) of \(\vert x\vert \) based on a subgradient [ 13 ] of its components is given by the diagonal matrix \(D(x)\): \(\partial \vert x\vert = D(x) = \operatorname {diag}(\operatorname {sign}(x))\), with

Noting that \(D(x)x=\vert x\vert \) and \(\left\Vert D(x)\right\Vert \leq 1\) for all \(x\).

To solve the equation (7), we use the Newton method with a generalized Jacobian \(\partial f(x)\) of \(f(x)\) given by:

The generalized Newton method for finding a zero of the equation \(f(x) = 0\) consists of the following iteration:

Based on the values of \(f(x)\) and \(\partial f(x)\) in (6) and (8), the generalized Newton iteration in (9), for solving the AVE (1), simplifies to

The next lemma establishes under Assumption 1 that the generalized Newton iteration in (10), is well-defined.

If \((A-BD)\) is singular then for some \(x\neq 0,\) we have \((A-BD)x=0\). It follows that \(x=A^{-1}BDx.\) By Assumption 1, it follows that

Then we have a contradiction. Hence \((A-BD)\) is nonsingular. This completes the proof.â–¡

Now, we can formally describe the corresponding generalized Newton algorithm for solving the AVE (1) as follows.

3.1 Algorithm

Following Mangasarian [ 7 ] , we establish the boundedness of the iterates of (10) and hence the existence of an accumulation point for them.

By Lemma 6, the matrix \((A-BD)^{-1}\) exists and therefore the sequence of the generalized Newton iterations in 10, is well-defined. Suppose now on the contrary that the sequence \(\{ x^{k}\} \) is unbounded. Then there exists a subsequence \(\{ x^{k_{i}+1}\} \rightarrow \infty \) with nonzero \(x^{k_{i}+1}\) such that \(D(\) \(x^{k_{i}})=\tilde{D}\) where \(\tilde{D}\) is a fixed diagonal matrix whose diagonal elements equal \(\pm 1\) or \(0\) extracted from the finite number of possible configurations for \(D(x^{k})\) in the sequence \(\{ D(x^{k})\} \) and such that the bounded subsequence \(\big\{ \tfrac {x^{k_{i}+1}}{\Vert x^{k_{i}+1}\Vert }\big\} \) converges to \(\tilde{x}\). Hence,

Letting \(i\rightarrow \infty ,\) gives \((A-B\tilde{D})\tilde{x}=0,\Vert \tilde{x}\Vert =1.\) In summary, there exists a \(\tilde{x}\neq 0\) such that \((A-B\tilde{D})\tilde{x}=0,\) which is a contradiction to Lemma 9. Consequently, the sequence \(\{ x^{k}\} \) is bounded and there exists an accumulation point \(\bar{x},\) of \(\{ x^{k}\} \) such that \(f(\bar{x}) = 0\). This completes the proof. â–¡

We are now ready to study the global convergence of the generalized Newton method. First we give the following lemma.

For a detailed proof, see Lemma 5 in [ 7 ] . â–¡ Let \(x^{\ast }\) be a solution of the AVE (1), then \((A-BD(x^{\ast }))x^{\ast }=b.\) Noting that \(\vert x^{\ast }\vert =D(x^{\ast })x^{\ast }\) and \(\vert x^{k}\vert =D(x^{k})x^{k}\). Now, subtracting \((A-BD(x^{\ast }))x^{\ast }=b\) from \((A-BD(x^{k}))x^{k+1}=b,\) we obtain

Hence

Consequently,

By Lemma 7, we have,

Hence, \(\big\Vert x^{k+1}-x^{\ast }\big\Vert \leq 3\big\Vert (A-BD(x^{k}))^{-1}\big\Vert \left\Vert B\right\Vert (\big\Vert x^{k}-x^{\ast }\big\Vert )\). So by the condition \(\left\Vert (A-BD)^{-1}\right\Vert {\lt}\tfrac {1}{3\left\Vert B\right\Vert },\) it follows that \(\big\Vert x^{k+1}-x^{\ast }\big\Vert {\lt}\big\Vert x^{k}-x^{\ast }\big\Vert \). Hence the sequence \(\big\{ x^{k}\big\} \) converges linearly to \(x^{\ast }.\) This completes the proof. â–¡

We are now ready to prove our main result of the global convergence. We quote first the following lemma.

The first part follows directly from Lemma 9. For the proof of the second part, we have \((A-BD)^{-1}\) can be written in the form

But since \((I-A^{-1}BD)^{-1}(I-A^{-1}BD)=I\), it follows that

By introducing an induced matrix norm, we get

Because,

it implies that

This completes the proof. â–¡

The uniquely solvable of AVE (1) for any \(b\) follows from Theorem 8 which requires \(\Vert A^{-1}\Vert {\lt}\frac{1}{\left\Vert B\right\Vert }.\) Now by Lemma 13, we have,

Hence by Lemma 12, the sequence generated by the generalized Newton method converges to the unique solution of the AVE (1) from any starting point \(x^{0}.\) This completes the proof. â–¡

4 Numerical results

In this section, we report some numerical results of the algorithm on two examples of absolute value equations. The experiments are done by the software MATLAB on a PC. In the implementation, our tolerance is \(\epsilon =10^{-6}\) and the number of iterations and the time produced by the algorithm are denoted by It and CPU, respectively. To this end and in order to demonstrate the performance of the algorithm, we compare the obtained numerical results with those obtained by the modified generalized method in [ 11 ] . For these examples we will ensure that the sufficient condition of solvability of the AVE problem is guaranteed i.e., the AVE (1) has a unique solution for each \(b\).

5 Concluding remarks

In this paper, we have studied the unique solvability of the AVE under a suitable sufficient condition. Moreover, we have extended a generalized Newton method for solving the AVE (1) which globally and finitely converges to the unique solution of the AVE (1) when \(\left\Vert A^{-1}\right\Vert {\lt}\tfrac {1}{4\left\Vert B\right\Vert }\). We have also reported some numerical results which indicate the effectiveness of the proposed method compared with an available generalized modified Newton method. Possible future work may consist to consider Traub’s Newton method for solving the AVE (1) which is known as the two-step Newton method.