# A Three-Step Iterative Method for Solving Absolute Value Equations

Authors: Jing-Mei Feng; San-Yang Liu
Journal: Journal of Mathematics
 (2020)

---

## Abstract

In this paper, we transform the problem of solving the absolute value equations (AVEs)Ax−x=b with singular values of A greater than 1 into the problem of finding the root of the system of nonlinear equation and propose a three-step algorithm for solving the system of nonlinear equation. The proposed method has the global linear convergence and the local quadratic convergence. Numerical examples show that this algorithm has high accuracy and fast convergence speed for solving the system of nonlinear equations.


---

## Body

## 1. Introduction

In the last few decades, the system of absolute value equations has been recognized as a kind of NP-hard and nondifferentiable problem, which can be equivalent to many mathematical problems, such as generalized linear complementarity problem, bilinear programming problem [1], knapsack feasibility problem [2], traveling agent problem [3], etc…However, compared with the above problems, it has the characteristics of simple structure and easy solution, which attracts much attention. This paper mainly designed a three-step iterative algorithm to solve the absolute value equations (AVEs) of the following type:(1)Ax−x=b,where A∈Rn×n, b∈Rn , and ⋅ indicates the absolute value. In [4], some theoretical conclusions about the solutions of AVEs (1) are given, and the sufficient conditions for the existence of unique solutions, nonnegative solutions, 2n solutions, and no solutions are given for the first time. Next, many scholars began to design effective algorithms to solve equations with different types of solutions. Mangasarian [1] proposed a generalized Newton method for solving AVEs (1) when it has a unique solution; then 100 AVEs (1) of 1000 dimensions generated randomly are used to test effectiveness of this method, and the accuracy is up to 10−6. On this basis, an improved generalized Newton algorithm is proposed by adding a dynamic step size [5], and the accuracy of the solution is of 10−9. Feng and Liu [6] presented a two-step iterative algorithm which decreases the probability of the occurrence of poor solutions in the first iteration, thus improving the global convergence of the whole algorithm. A new method for solving the system of absolute value equations is proposed [7] by the preconditioning technique and successive over-relaxation. It was inspired by the Picard-Hermitian and skew-Hermitian splitting iteration method to solve the system nonlinear equations. Salkuyeh [8] presented the Picard-HSS iteration method for solving the system of absolute value equations, and there are also two CSCS-based iteration methods [9] and other iterative algorithms [10–12]. In addition, some iterative algorithms for solving the system of nonlinear equations are also interesting, for example, many three-step higher-order iterative algorithms are designed to solve the system nonlinear equations [13], Cordero et al. proposed two iterative algorithms with fourth-order and fifth-order convergences to solve the system nonlinear equations in [14].Considering the nondifferentiation of absolute value equation, taking the advantages of the above algorithms and overcoming their disadvantages, a three-step iterative algorithm is designed for effectively solving AVEs (1) in this paper. Firstly, we give a three-step iterative formula, which absorbs the advantages of both the generalized classic Newton method and higher-order iterative algorithm; it has the advantages of small error and fast iteration speed. Then, we can prove that this method can linearly converge to the global optimal solution of AVEs (1) and possess locally quadratic convergence. Finally, some numerical experiments and comparison with both the classic generalized Newton method [1] and two-step iterative algorithm [6] show that our method has high accuracy and fast convergence speed.The rest of this article is arranged as follows. Section2 gives the preliminary basic knowledge about AVEs (1). We give a three-step iterative algorithm and prove the global convergence and local quadratic convergence of the proposed method in Section 3. In Section 4, we present some numerical experiments. Some concluding remarks to end the paper in Section 5.


## 2. Preliminaries

We are now describing some symbols and backgrounds. Lete and I be a unit vector and a unit matrix, respectively. x is the two-norm xTx1/2, and sign (x) is a vector with components equal to 1, 0, or −1 depending on whether the corresponding component of x is positive, zero, or negative. In addition, diag (sign (x)) is a diagonal matrix whose diagonal elements are the components of sign (x). The diagonal matrix Dx represents a generalized Jacobian matrix of x:(2)Dx=∂x=diagsignx.We define a nonlinear functionfx as follows:(3)fx=Ax−x−b.A generalized Jacobian offx at x is(4)∂fx=A−Dx,where Dx=diagsignx .For solving AVEs (1), a generalized Newton iteration algorithm was presented in [1] and the iteration formula is as follows:(5)xk+1=A−Dxk−1b,k=0,1,2,….Effectiveness of this method was tested by the 100 randomly generated 1,000-dimensional AVEs (1), when the singular values of A are not less than 1, and the accuracy is up to 10−6.A two-step iterative method for solving AVEs (1) is presented in [6] and the iterative formula is(6)yk=xk+A−Dxk−1fxk,xk+1=xk−A−Dxk−1fyk−fxk,k=0,1,2,….Example in [1] is used to verify the effectiveness of this algorithm. Compared with generalized Newton method, the convergence speed is faster and the solution accuracy is improved.For solving the system of nonlinear equationsgx=0, where g:D⊂R⟶R, many methods are given in [13–15], these methods also give us a lot of good ideas. Taking some of the advantages of the above approach, considering the particularity of the system of absolute value equations, this paper designed the following three-step iterative algorithm for AVEs (1).


## 3. Three-Step Iterative Algorithm

In this section, a three-step iterative algorithm is presented in the following form:(7)yk=xk−A−Dxk−1fxk,zk=yk−A−Dxk−1+A−Dyk−12fyk,xk+1=zk−A−Dzk−1fzk,k=0,1,2,….Based on this iterative formula (7), we design a new algorithm for solving AVEs (1).The algorithm steps and the specific process are shown as follows:Step 1. Randomly generated an initial vectorxk∈Rn to AVEs (1), set k=0;Step 2. Computexk+1 by the (7);Step 3. IfAxk+1−xk+1−b=0, stop, otherwise go to step 4;Step 4. Setk:=k+1, go to Step 2.The global linear convergence and the local quadratic convergence of the Algorithm1 are given below.Algorithm 1: Three-step iterative algorithm.
(1)
Initialization:An initial vector:xk∈Rn,k=0.(2)
whileAxk−xk−b≥εdo(3)
By (7), calculate xk+1.(4)
By (3), calculate fxk+1.(5)
k=k+1.(6)
end whileLemma 1.
(see [4]). The minimum singular value of the matrix A∈Rn×n is greater than 1 if and only if all the eigenvalues of A′A are greater than 1.Lemma 2.
(see [4]). If the minimum singular value of A∈Rn×n exceeds 1 for the algorithm (6), then for any diagonal matrix D whose diagonal elements Dii=+1,0,−1,i=1,2,…,n, A−D−1 exists.Lemma 3.
(see [1]). Lipschitz continuity of the absolute value. Let the vectors x,y∈Rn, then(8)x−y≤2x−y.Theorem 1.
If the minimum singular value of the matrixA is greater than 1 and Dxk+1=Dzk for some k for the three-step algorithm (6), then xk+1 is a solution to the AVEs (1).Proof.
Let’s first simplifyxk+1=zk−A−Dzk−1fzk in formula (7),(9)xk+1=zk−A−Dzk−1fzk=zk−A−Dzk−1Azk−zk−b=zk−A−Dzk−1Azk−Dzkzk−b=zk−A−Dzk−1A−Dzkzk−b=zk−A−Dzk−1A−Dzkzk+A−Dzk−1b=zk−zk+A−Dzk−1b=A−Dzk−1b.
Then,A−Dzkxk+1=b, so,(10)0=A−Dzkxk+1−b=A−Dzk+1xk+1−b=Axk+1−Dxk+1xk+1−b=Axk+1−xk+1−b.
Hence,xk+1 is the solution to the AVEs (1).Theorem 2.
(global linear Convergence). If∃K0 , make Dxk=Dyk,k>K0, and A−D−1<1/3 for any diagonal matrix D whose diagonal elements are ±1 or 0, then the three-step iterative algorithm (6) from any initial point x0 converges linearly to a solution x¯ for any solvable AVEs (1).Proof.
Suppose thatx¯ is a solution of the AVE (1), noting that Dx¯x¯=x¯ and Dxkxk=xk, for simplicity, let D¯=Dx¯, Dk=Dxk.
The proof of Theorem1 shows that the first one yk=xk−A−Dxk−1fxk in formula (7) can be reduced to yk=A−Dxk−1b=A−Dk−1b, that is, A−Dkyk=b.
BecauseA−D¯x¯=b, let us take A−D¯x¯=b minus A−Dkyk=b,(11)Ayk−x¯=Dkyk−D¯x¯=Dkyk−xk+xk−D¯x¯=Dkyk−xk+Dkxk−D¯x¯=xk−x¯+Dkyk−xk=xk−x¯+Dkyk−x¯+x¯−xk=xk−x¯+Dkyk−xk+Dkx¯−xk.
So,(12)A−Dkyk−x¯=xk−x¯+Dkx¯−xk.
Therefore,(13)yk−x¯=A−Dk−1xk−x¯+Dkx¯−xk.
According to Lemma3 and given conditions,(14)yk−x¯=A−Dk−1xk−x¯+Dkx¯−xk≤A−Dk−1xk−x¯+Dkx¯−xk≤A−Dk−12xk−x¯+x¯−xk≤A−Dk−13xk−x¯<xk−x¯.
Becausek>K0, Dxk=Dyk, the second one(15)zk=yk−A−Dxk−1+A−Dyk−12fyk,in formula (7) can be simplified to the following form:(16)zk=yk−A−Dyk−1fyk=A−Dyk−1b,
In the same way,(17)zk−x¯<yk−x¯.
Now letus simplify the third one xk+1=zk−A−Dzk−1fzk in formula (7) to(18)xk+1=A−Dzkb.
Also get,(19)xk+1−x¯<zk−x¯.
Hence,(20)xk+1−x¯<zk−x¯<yk−x¯<xk−x¯.
So thexk+1−x¯ converges to zero, the sequence iterated by formula (7) linearly converges to a solution x¯.Theorem 3.
(locally quadratic convergence). For any diagonal matrixD with diagonal elements being ±1 or 0, if A−D is nonsingular, then the sequence xk+1 from three-step iterative algorithm (6) converges to x¯ and xk+1−x¯=Oxk−x¯2.Proof (see [16]).
We omit it here.


## 4. Numerical Examples

In this section, six AVEs (1) examples are worked out to illustrate the feasibility and effectiveness of the proposed methods. All the numerical computations are performed in MATLAB R2017a. We compare the proposed method (Three-SIA) with the two-step iterative algorithm [6] (Two-SIA) and the generalized Newton’s method [1] (GNM).Example 1.
(21)A=502360,b=−49−56,
The initial value isx0=rand2,1, and the exact solution to this problem is x1=−1,x2=1.Example 2.
(22)A=4.32441.13020.93641.13024.61140.86430.93640.86433.8834,b=44.470361.543279.1937,
The initial value isx0=rand3,1, and the exact solution to this problem is x1=3.2697,x2=10.4486,x3=23.2716.Example 3.
(23)A=10120111310212117013,b=12151420,
The initial value isx0=rand4,1, and the exact solution to this problem is x1=x2=x3=x4=1.Example 4.
(24)n=5;rand′state′,0;R=10∗randn,n;A=R′∗R+n∗eyen;b=A−eyen,n∗onesn,1.
The initial value isx0=rand5,1, and the exact solution to this problem is x1=x2=x3=x4=x5=1.Example 5.
(25)n=1000;B=0.5∗onesn,n;C=4∗n−0.5∗eyen;D=n−0.5∗ones1,n−1;E=diagD,1+diagD,1′;A=B+C+E;b=A−eyen∗onesn,1.Example 6.
(26)n=1000;A=−10+randn,n∗20;x=−2+randn,1∗4;b=A∗x−absx.
For the Examples1–4, the numerical solutions and errors (Ax−x−b) generated by the three algorithms in the first three iterations are given. Let Xi,i=1,2,3,… represent the numerical solution after the i-th iteration, and Ri,i=1,2,3,… represent the error generated by the i-th iteration.
In Tables1–4, from the numerical solutions and errors obtained from the three algorithms in each iteration, it is clear that the Three-SIA method has a fast convergence speed and high solution accuracy, especially in Examples 1 and 3.
The convergence curves of the three algorithms for solving the high-dimensional system of absolute value equations Examples4 and 5 are shown in Figures 1 and 2. It can be seen from the figures that the Three-SIA method is the best in terms of convergence speed and accuracy. So the Algorithm 1 is superior in convergence and the quality of solution for solving AVEs (1). And this algorithm takes a short time to calculate the low-dimensional absolute value equations, about 2 seconds. When calculating high-dimensional absolute value equations, such as 1000-dimensional equations, it takes about 10 seconds. Overall, the efficiency is higher than other algorithms.Table 1
The comparison of three-SIA, two-SIA, and GNM for Example1.
AlgorithmX1X2X3R1;R2GNMx1=−1.040901213171577x1=−1.000000000000000x1=−12.081802426343145;x2=1.002079722703640x2=1.000000000000000x2=10Two-SIAx1=−1.002171578270887x1=−1x1=−11.267518301536992;x2=0.991745740048690x2=1x2=10Three-SIAx1=−1x1=−1x1=−10;x2=1x2=1x2=10Table 2
The comparison of three-SIA, two-SIA, and GNM for Example2.
AlgorithmX1X2X3R1;R2;R3GNMx1=3.269694330310371x1=3.269694330310371x1=3.2696943303103710.1588×10−13;x2=10.448630719160590x2=10.448630719160590x2=10.4486307191605900.1588×10−13;x3=23.271556738061619x3=23.271556738061619x3=23.2715567380616190.1588×10−13Two-SIAx1=3.269694330310371x1=3.269694330310371x1=3.2696943303103710.3256×10−13;x2=10.448630719160588x2=10.448630719160588x2=10.4486307191605880.3256×10−13;x3=23.271556738061616x3=23.271556738061616x3=23.2715567380616160.3256×10−13Three-SIAx1=3.269694330310369x1=3.269694330310369x1=3.2696943303103690.7105×10−14;x2=10.448630719160592x2=10.448630719160592x2=10.4486307191605920.7105×10−14;x3=23.271556738061626x3=23.271556738061626x3=23.2715567380616260.7105×10−14Table 3
The comparison of three-SIA, two-SIA, and GNM for Example3.
AlgorithmX1X2X3R1;R2;R3;R4GNMx1=1.000000000000000x1=1.000000000000000x1=1.0000000000000000.5329×10−14;x2=1.000000000000000x2=1.000000000000000x2=1.0000000000000000.5329×10−14;x3=1.000000000000000x3=1.000000000000000x3=1.0000000000000000.5329×10−14;x4=1.000000000000000x4=1.000000000000000x4=1.0000000000000000.5329×10−14Two-SIAx1=1.000000000000000x1=1.000000000000000x1=1.0000000000000000.6153×10−14;x2=1.000000000000000x2=1.000000000000000x2=1.0000000000000000.5329×10−14;x3=1.000000000000000x3=1.000000000000000x3=1.0000000000000000.4351×10−14;x4=1.000000000000000x4=1.000000000000000x4=1.0000000000000000.1776×10−14Three-SIAx1=1x1=1x1=10;x2=1x2=1x2=10;x3=1x3=1x3=10;x4=1x4=1x4=10Table 4
The comparison of three-SIA, two-SIA, and GNM for Example4.
AlgorithmX1X2X3R1;R2;R3;R4;R5GNMx1=1.000000000000002x1=1.000000000000002x1=1.0000000000000020.6126×10−11;x2=1.000000000000007x2=1.000000000000007x2=1.0000000000000070.6126×10−11;x3=1.000000000000004x3=1.000000000000004x3=1.0000000000000040.6126×10−11;x4=0.999999999999995x4=0.999999999999995x4=0.9999999999999950.6126×10−11;x5=1.000000000000021x5=1.000000000000021x5=1.0000000000000210.6126×10−11Two-SIAx1=1.000000000000001x1=1.000000000000012x1=1.0000000000000010.4781×10−11;x2=1.000000000000006x2=1.000000000000006x2=1.0000000000000060.4510×10−11;x3=1.000000000000003x3=1.000000000000003x3=1.0000000000000030.4118×10−11;x4=0.999999999999994x4=0.999999999999994x4=0.9999999999999940.3136×10−11;x5=1.000000000000021x5=1.000000000000020x5=1.0000000000000200.0873×10−11Three-SIAx1=0.999999999999998x1=1.000000000000012x1=1.0000000000000010.1607×10−12;x2=1.000000000000000x2=1.000000000000000x2=1.0000000000000000.1607×10−12;x3=1.000000000000003x3=1.000000000000003x3=1.0000000000000030.1607×10−12;x4=1.000000000000001x4=1.000000000000001x4=1.0000000000000010.1607×10−12;x5=0.999999999999997x5=0.999999999999997x5=0.9999999999999970.1607×10−12Figure 1
The convergence curve of three-SIA, two-SIA, and GNM for Example5.Figure 2
The convergence curve of three-SIA, two-SIA, and GNM for Example6.


## 5. Conclusions

In this paper, we proposed a three-step iterative algorithm for solving nondifferentiable and NP-hard AVEs (1), when the minimum singular value of A is greater than 1. Compared Two-SIA and GNM, our Three-SIA method has faster convergence speed fast and the solution accuracy is high. Next, we will consider solving the system of absolute value equations with smooth high-order algorithm.



---

*Source: 8531403-2020-07-25.xml*