An iterative method for solving absolute value equations and sufficient conditions for unique solvability

Abstract

We describe an iterative method for solving absolute value equations. The result gives a sufficient condition for unique solvability of these equations for arbitrary right-hand sides. This sufficient condition is compared with that one by Mangasarian and Meyer.

1 Introduction

The absolute value equation

$$\begin{aligned} Ax+B|x|=b \end{aligned}$$

(1)

(where $A,B\in \mathbb{R }^{n\times n}$ and $b\in \mathbb{R }^n$) has been recently studied by several authors, cf. e.g. Caccetta, Qu and Zhou [1], Hu and Huang [3], Karademir and Prokopyev [4], Mangasarian [5, 6], Mangasarian and Meyer [7], Prokopyev [9], Rohn [11, 12], and Zhang and Wei [13]. The reason for recent interest in this new topic consists probably in the fact that some frequently occurring optimization problems, as e.g. linear complementarity problem, linear programming, or convex quadratic programming can be equivalently reformulated in the form (1) and thus solved as absolute value equations (Rohn [10], Murty [8]).

In the above-quoted papers various methods for solving absolute value equations were proposed, based mostly on nonlinear optimization techniques. Little attention, however, has been paid so far to iterative methods for solving (1). In this paper we formulate such a method (Theorem 1) working under assumption of existence of matrices $M$ and $R$ satisfying certain matrix inequality. In Theorem 2 we show how a specific solution of this inequality can be found. This theorem implies that the condition

$$\begin{aligned} \varrho (|A^{-1}|)<1 \end{aligned}$$

($\varrho$ denotes the spectral radius) guarantees unique solvability of the equation

$$\begin{aligned} Ax-|x|=b \end{aligned}$$

for arbitrary right-hand side $b$. In Sect. 5 we compare this condition with the Mangasarian–Meyer condition

$$\begin{aligned} {\sigma }_{\max }(A^{-1})<1 \end{aligned}$$

(${\sigma }_{\max }$ denotes the largest singular value) and we show that they are independent of each other. In the last Theorem 4 we propose merging the two conditions into a single one. Some brief comments about possibility of finding a necessary and sufficient condition of unique solvability of an absolute value equation for each right-hand side conclude the paper.

2 General condition

Our main result in Sect. 3 will be delivered under assumption of existence of matrices $M,R\in \mathbb{R }^{n\times n}$ satisfying

$$\begin{aligned} M\ge I+|M|(|I-RA|+|RB|) \end{aligned}$$

(2)

(where $I$ denotes the identity matrix). As this inequality looks complicated at the first glance, we shall bring it to some simpler, albeit two-line form. To this end, let

$$\begin{aligned} G=|I-RA|+|RB|, \end{aligned}$$

(3)

then $G$ is nonnegative and the condition (2) can be equivalently written as

$$\begin{aligned} M\ge I+|M|G. \end{aligned}$$

(4)

Now, since the right-hand side of (4) is nonnegative, we have that $M\ge 0$, hence $|M|=M$ and (4) implies

$$\begin{aligned}&\displaystyle M(I-G)\ge I,\end{aligned}$$

(5)

$$\begin{aligned}&\displaystyle M\ge 0. \end{aligned}$$

(6)

Conversely, if (5), (6) hold, then $M=|M|$ and (5) turns into (4), which is (2). Hence, under notation (3), the condition (2) can be written either in one-line form (4), or in equivalent two-line form (5), (6). The former option is shorter whereas the latter is more descriptive.

3 Iterative method under general condition

The following theorem is the basic result of this paper. ${\sigma }_{\max }(A)$ stands for the largest singular value of $A$.

Theorem 1

Let $M$ and $R$ satisfy (2). Then the sequence $\{x^i\}_{i=0}^{\infty }$ given by $x^0=Rb$ and

$$\begin{aligned} x^{i+1}=(I-RA)x^i-RB|x^i|+Rb \qquad (i=0,1,\ldots ) \end{aligned}$$

(7)

converges to the unique solution $x^*$ of (1) and for each $i\ge 0$ there holds

$$\begin{aligned} |x^*-x^{i+1}|\le (M-I)|x^{i+1}-x^{i}| \end{aligned}$$

(8)

and

$$\begin{aligned} \Vert x^*-x^{i+1}\Vert _2\le {\sigma }_{\max }(G)\Vert x^*-x^{i}\Vert _2. \end{aligned}$$

(9)

proof

For clarity, we divide the proof into several steps.

(a) Let (2) have a solution $M$ and $R$. Using the equivalent conditions (5), (6), we have

$$\begin{aligned} I+MG\le M, \nonumber \end{aligned}$$

and postmultiplying this inequality by $G$ and adding $I$ to both sides we obtain

$$\begin{aligned} I+G+MG^2\le I+MG\le M \end{aligned}$$

and by induction

$$\begin{aligned} \sum _{j=0}^kG^j+MG^{k+1}\le M \end{aligned}$$

for $k=0,1,2,\ldots$. In view of nonnegativity of $M$, this shows that the nonnegative matrix series $\sum _{j=0}^{\infty }G^j$ satisfies

$$\begin{aligned} \sum _{j=0}^{\infty }G^j\le M, \nonumber \end{aligned}$$

hence it is convergent, so that $G^j\rightarrow 0$ and consequently

$$\begin{aligned} \varrho (G)<1. \end{aligned}$$

(10)

Now we have

$$\begin{aligned} I-RA\le |I-RA|\le G, \end{aligned}$$

hence

$$\begin{aligned} \varrho (I-RA)\le \varrho (|I-RA|)\le \varrho (G)<1. \nonumber \end{aligned}$$

Since $\varrho (I-RA)<1$, the matrix

$$\begin{aligned} RA=I-(I-RA) \nonumber \end{aligned}$$

is nonsingular, which gives that both $R$ and $A$ are nonsingular.

(b) Let $i\ge 1$. Subtracting the equations

$$\begin{aligned} x^{i+1}&= (I-RA)x^i-RB|x^i|+Rb, \\ x^{i}&= (I-RA)x^{i-1}-RB|x^{i-1}|+Rb, \end{aligned}$$

we get

$$\begin{aligned} |x^{i+1}-x^i|\le |I-RA||x^i-x^{i-1}|+|RB|||x^i|-|x^{i-1}|| \le G|x^i-x^{i-1}| \end{aligned}$$

and for each $m\ge 1$ by induction

$$\begin{aligned}&|x^{i+m}-x^i|\\&\quad =\left|\sum _{j=0}^{m-1}(x^{i+j+1}-x^{i+j})\right| \le \sum _{j=0}^{m-1} |x^{i+j+1}-x^{i+j}| \le \sum _{j=0}^{m-1}G^{j+1}|x^i-x^{i-1}|\\&\quad \le \left(\sum _{j=0}^{\infty }G^{j+1}\right)|x^i-x^{i-1}| \le (M-I)|x^i-x^{i-1}|\le (M-I)G^{i-1}|x^1-x^0|. \end{aligned}$$

From the final inequality

$$\begin{aligned} |x^{i+m}-x^i|\le (M-I)G^{i-1}|x^1-x^0|, \end{aligned}$$

in view of the fact that $G^{i-1}\rightarrow 0$ as $i\rightarrow \infty$ due to (10), we can see that the sequence $\{x^i\}$ is Cauchian, thus convergent, $x^i\rightarrow x^{*}$. Taking the limit in (7) we get

$$\begin{aligned} x^{*}=(I-RA)x^*-RB|x^*|+Rb \end{aligned}$$

which gives

$$\begin{aligned} 0=R(Ax^*+B|x^*|-b), \end{aligned}$$

and employing the above-proved nonsingularity of $R$, we can see that $x^*$ is a solution of (1). The estimation (8) follows from the above-established inequality

$$\begin{aligned} |x^{i+m}-x^i|\le (M-I)|x^i-x^{i-1}| \end{aligned}$$

by writing $i+1$ instead of $i$ and taking $m\rightarrow \infty$.

(c) To prove (9), let us subtract the Eq. (7) from the equation $Ax^*+B|x^*|=b$ written in the form

$$\begin{aligned} x^*=(I-RA)x^*-RB|x^*|+Rb. \nonumber \end{aligned}$$

Then we have

$$\begin{aligned} |x^*-x^{i+1}|&= |(I-RA)(x^*-x^i)-RB(|x^*|-|x^i|)| \\&\le |I-RA||x^*-x^i|+|RB||x^*-x^i| \\&= G|x^*-x^i| \end{aligned}$$

and taking Euclidean norm we obtain

$$\begin{aligned}\nonumber \Vert x^*-x^{i+1}\Vert _2\le \Vert G\Vert _2\Vert x^*-x^i\Vert _2={\sigma }_{\max }(G)\Vert x^*-x^i\Vert _2. \end{aligned}$$

(d) To prove uniqueness, assume that (1) has a solution $x^{\prime }$. From the equations

$$\begin{aligned} Ax^*+B|x^*|&= b, \\ Ax^{\prime }+B|x^{\prime }|&= b \end{aligned}$$

written as

$$\begin{aligned} x^*&= (I-RA)x^*-RB|x^*|+Rb, \\ x^{\prime }&= (I-RA)x^{\prime }-RB|x^{\prime }|+Rb \end{aligned}$$

we obtain

$$\begin{aligned} |x^*-x^{\prime }|\le G|x^*-x^{\prime }|, \nonumber \end{aligned}$$

hence

$$\begin{aligned} (I-G)|x^*-x^{\prime }|\le 0 \end{aligned}$$

and by (9),

$$\begin{aligned} |x^*-x^{\prime }|\le M(I-G)|x^*-x^{\prime }|\le 0, \end{aligned}$$

which shows that $x^{\prime }=x^*$.

This completes the proof. $\square$

4 Iterative method under specific condition

Let us write the condition (2), as before, in the form

$$\begin{aligned}&\displaystyle M(I-G) \ge I, \end{aligned}$$

(11)

$$\begin{aligned}&\displaystyle M \ge 0, \end{aligned}$$

(12)

where

$$\begin{aligned} G=|I-RA|+|RB|. \end{aligned}$$

Obviously, such $M$ and $R$ do not exist always because their existence implies nonsingularity of $A$ (Proof of Theorem 1, (a)). We show how $M$ and $R$ satisfying (11), (12) can be found. $\varrho (A)$ stands for the spectral radius of $A$.

Theorem 2

Let $A$ be nonsingular and let

$$\begin{aligned} \varrho (|A^{-1}B|)<1 \end{aligned}$$

(13)

hold. Then the sequence $\{x^i\}_{i=0}^{\infty }$ given by $x^0=A^{-1}b$ and

$$\begin{aligned} x^{i+1}=-A^{-1}B|x^i|+A^{-1}b \qquad (i=0,1,\ldots ) \nonumber \end{aligned}$$

converges to the unique solution $x^*$ of (1) and for each $i\ge 0$ there holds

$$\begin{aligned} |x^*-x^{i+1}|\le ((I-|A^{-1}B|)^{-1}-I)|x^{i+1}-x^{i}| \nonumber \end{aligned}$$

and

$$\begin{aligned} \Vert x^*-x^{i+1}\Vert _2\le {\sigma }_{\max }(|A^{-1}B|)\Vert x^*-x^{i}\Vert _2. \end{aligned}$$

(14)

proof

As is well known, the condition (13) is equivalent to

$$\begin{aligned} (I-|A^{-1}B|)^{-1}\ge 0 \nonumber \end{aligned}$$

(Horn and Johnson [2]). Then the matrices

$$\begin{aligned} R&= A^{-1}, \nonumber \\ M&= (I-|A^{-1}B|)^{-1} \nonumber \end{aligned}$$

satisfy (11), (12). Indeed, $M\ge 0$ by assumption, and because $G=|A^{-1}B|$, we have $M(I-G)=M(I-|A^{-1}B|)=I$. Then Theorem 1 applies. $\square$

5 Comparison of two sufficient conditions

In this section we shall be interested in sufficient conditions for existence of a unique solution, putting aside the computational aspects. From Theorem 2 we immediately obtain this sufficient condition.

Theorem 3

If (13) holds, then for each right-hand side $b$ the absolute value equation

$$\begin{aligned} Ax+B|x|=b \end{aligned}$$

(15)

has a unique solution.

Mangasarian and Meyer studied in [7] an absolute value equation in a simplified form

$$\begin{aligned} Ax-|x|=b, \end{aligned}$$

(16)

which is a special case of our Eq. (15) for $B=-I$. In [7, Prop. 3] they proved that the Eq. (16) is uniquely solvable for each $b$ if

$$\begin{aligned} {\sigma }_{\min }(A)>1 \end{aligned}$$

(17)

holds, where ${\sigma }_{\min }$ denotes the smallest singular value. Since

$$\begin{aligned} {\sigma }_{\min }(A)=\frac{1}{{\sigma }_{\max }(A^{-1})} \end{aligned}$$

(assuming nonsingularity of $A$), we can bring the condition (17) to an equivalent form

$$\begin{aligned} {\sigma }_{\max }(A^{-1})<1 \end{aligned}$$

(18)

which is similar to our condition (13) which in the case of Eq. (16) reads

$$\begin{aligned} \varrho (|A^{-1}|)<1. \end{aligned}$$

(19)

To compare the two sufficient conditions, we created the following MATLAB function.

As it can be seen, it generates $j$ randomly generated matrices of size $n\times n$, where $n$ varies randomly between $2$ and $m$. For each such a matrix $A$, the values

$$\begin{aligned}&r = \varrho (|A^{-1}|), \\&s = {\sigma }_{\max }(A^{-1}) \end{aligned}$$

are computed and the numbers of occurrences of the four cases

$$\begin{aligned} r&< 1,\ s<1, \nonumber \\ r&< 1<s, \nonumber \\ s&< 1<r, \nonumber \\ 1&< r,\ 1<s \nonumber \end{aligned}$$

are stored in variables $rs1, r1s, s1r$, and $ors$, respectively. We ran the function using the command

i.e., on 10,000 randomly generated matrices of random sizes varying between $2\times 2$ and $100\times 100$. The results were as follows:

Hence, both conditions (19) and (18) were satisfied in 1985 out of 10,000 examples, in 483 cases the condition (19) was satisfied whereas (18) was not, in 79 cases the two conditions reversed their roles, and in 7453 cases (almost 75 %) neither of them worked. This example reveals an important fact that the two conditions (19), (18) are independent of each other, i.e., none of them implies the second one; this is so because both cases $r<1<s, s<1<r$ can occur. To be perfectly clear, we show two specific examples illustrating occurrences of the two cases.

Here $r<1<s$.

Here, on the contrary, $s<1<r$.

In all computed sets of examples it was $r1s>s1r$, sometimes $r1s$ was greater by an order of magnitude. This shows that generally the condition (19) should be preferred. But we can merge both conditions into a single one, making use of both of them.

Theorem 4

If $A$ is invertible and

$$\begin{aligned} \min \big \{\varrho (|A^{-1}|),\,{\sigma }_{\max }(A^{-1})\big \}<1 \nonumber \end{aligned}$$

holds, then for each right-hand side $b$ the absolute value equation

$$\begin{aligned} \nonumber Ax-|x|=b \end{aligned}$$

has exactly one solution.

6 Conclusion

From our iterative method we have derived a sufficient condition for unique solvability of an absolute value equation for each right-hand side, and we have compared it with a sufficient condition by Mangasarian and Meyer. Of much greater theoretical importance would be to find a necessary and sufficient condition. What we can only say at this moment is that any necessary and sufficient such a condition would be difficult to verify considering the fact that the problem of solvability of absolute value equations is NP-hard, as proved by Mangasarian and Meyer [7].