# Symmetric SOR Method for Absolute Complementarity Problems

Authors: Javed Iqbal; Muhammad Arif
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We study symmetric successive overrelaxation (SSOR) method for absolute complementarity problems. Solving this problem is equivalent to solving the absolute value equations. Some examples are given to show the implementation and efficiency of the method.


---

## Body

## 1. Introduction

Absolute complementarity problem seeks real vectorsx≥0 and Ax-|x|-b≥0, such that
(1)〈x,Ax-|x|-b〉=0,
where A∈Rn×n and b∈Rn. The complementarity theory was introduced and studied by Lemke [1] and Cottle and Dantzig [2]. The complementarity problems have been generalized and extended to study a wide class of problems, which arise in pure and applied sciences; see [1–9] and the references therein. Equally important is the variational inequality problem, which was introduced and studied in the early sixties.In this paper, we suggest and analyze SSOR [5] method for absolute complementarity problem which was introduced by Noor et al. [10]. The convergence analysis of the proposed method is considered under some suitable conditions. We show that the absolute complementarity problems are equivalent to variational inequalities. Results are very encouraging. The ideas and the technique of this paper may stimulate further research in these areas.LetRn be the finite dimension Euclidean space, whose the inner product and norm are denoted by 〈·,·〉 and ∥·∥, respectively. For a given matrix A∈Rn×n, a vector b∈Rn, we consider the problem of finding x∈K*, such that
(2)x∈K*,Ax-|x|-b∈K*,〈Ax-|x|-b,x〉=0,
where K*={x∈Rn:〈x,y〉≥0,y∈K} is the polar cone of a closed convex cone K in Rn and |x| will denote the vector in Rn with absolute values of components of x∈Rn. We remark that the absolute value complementarity problem (2) can be viewed as an extension of the complementarity problem considered by Karamardian [6].LetK be a closed and convex set in the inner product space Rn. We consider the problem of finding x∈K such that
(3)〈Ax-|x|-b,y-x〉≥0,∀y∈K.
The problem (3) is called the absolute value variational inequality, which is a special form of the mildly nonlinear variational inequalities [11]. If K=Rn, then the problem (3) is equivalent to find x∈Rn such that
(4)Ax-|x|-b=0.
To propose and analyze algorithms for absolute complementarity problems, we need the following definitions.Definition 1.
B
∈
R
n
×
n is called an L-matrix if bii>0 for i=1,2,…,n, and bij≤0 for i≠j, i,j=1,2,…,n.Definition 2.
IfA∈Rn×n is positive definite, then(i)
there exists a constantγ>0, such that
(5)〈Ax,x〉≥γ∥x∥2,∀x∈Rn;(ii)
there exists a constantβ>0 such that
(6)∥Ax∥≤β∥x∥,∀x∈Rn.


## 2. Absolute Complementarity Problems

To propose and analyze algorithm for absolute complementarity problems, we need the following results.Lemma 3 (see [12]).
LetK be a nonempty closed convex set in Rn. For a given z∈Rn,u∈K satisfies the inequality
(7)〈u-z,u-v〉≥0,v∈K,
if and only if
(8)u=PKz,
where PK is the projection of Rn onto the closed convex set K.Lemma 4 (see [10]).
IfK is the positive cone in Rn, then x∈K is a solution of absolute variational inequality (3) if and only if x∈K is the solution of the complementarity problem (2).The next result proves the equivalence between variational inequality (3) and the fixed point.Lemma 5 (see [10]).
IfK is closed convex set in Rn, then ρ>0; x∈K satisfies (3) if and only if x∈K satisfies the relation
(9)x=PK(x-ρ[Ax-|x|-b]),
where PK is the projection of Rn onto the closed convex set K.Now using Lemmas4 and 5, the absolute complementarity problem (2) can be transformed to fixed-point problem as
(10)x=PK(x-ρ[Ax-|x|-b]).Theorem 6 (see [10]).
LetA∈Rn×n be a positive definite matrix with constant α>0 and continuous with constant β>0. If  0<ρ<2(γ-1)/(β2-1), β>1, γ>1, then there exists a unique solution x∈K, such that
(11)〈Ax-|x|-b,y-x〉≥0∀y∈K,
where K is a closed convex set in Rn.To define the projection operatorPK, we consider the special case when K=[0,c] is a closed convex set in Rn, as follows.Definition 7 (see [3]).
LetK=[0,c] is a closed convex set in Rn. Then, the projection operator PKx is defined as
(12)(PKx)i=min{max(0,xi),ci},i=1,2,…,n.Lemma 8 (see [3]).
For anyx and y in Rn, the following facts hold:(i)
PK(x+y)≤PKx+PKy;(ii)
PKx-PKy≤PK(x-y);(iii)
x≤y⇒PKx≤PKy;(iv)
PKx+PK(-x)≤|x|, with equality, if and only if -c≤x≤c.
Now one splits the matrixA as
(13)A=D-L-U,
where D is the diagonal matrix and L and U are strictly lower and strictly upper triangular matrices, respectively. Let 0<ω<2; using (13), one suggests the SSOR method for solving (3) as follows.Algorithm 9.
Consider the following.Step  1. Choose an initial vector x0∈Rn and a parameter ω∈R+. Set k=0.Step  2. Calculate
(14)xk+1=PK(xk-D-1222×[-ωLxk+1+(ω(2-ω)A+ωL)xk222222-ω(2-ω)(|xk|+b)-ωLxk+1]D-1).Step  3. If xk+1=xk, then stop; else, setk=k+1 and go to step  2.Algorithm 10.
Consider the following.Step  1. Choose an initial vector x0∈Rn and a parameter ω∈R+. Set k=0.Step  2. Calculate
(15)xk+1=PK(xk-D-1222×[-ωUxk+1+(ω(2-ω)A+ωU)xk222222-ω(2-ω)(|xk|+b)-ωUxk+1]D-1).Step  3. If xk+1=xk, then stop; else, set k=k+1 and go to step  2.Now we define an operatorg:Rn→Rn such that g(x)=ξ, where ξ is the fixed point of the system
(16)ξ=PK(x-D-1222×[-ωLξ+(ω(2-ω)A+ωL)x222222-ω(2-ω)(|x|+b)-ωLξ+(ω(2-ω)A+ωL)]D-1).
We also assume that the set
(17)φ={x∈Rn:x≥0,Ax-|x|-b≥0}
of the absolute complementarity problem is nonempty. To prove the convergence of Algorithm 9, we need the following result.Theorem 11.
Consider the operatorg:Rn→Rn as defined in (16). Assume that A∈Rn×n is an L-matrix. Also assume that 0<ω≤1. Then for any x∈φ, it holds that.(i)
g(x)≤x;(ii)
x≤y⇒g(x)≤g(y);(iii)
ξ=g(x)∈φ.Proof.
To prove(i), we need to prove that
(18)ξi≤xi,i=1,2,…,n
with ξi satisfying
(19)ξi=PK(∑j=1i-1Lij(ξj-xj)+ω(2-ω)xi-aii-12222×[-ω∑j=1i-1Lij(ξj-xj)+ω(2-ω)2222222222222×(Ax-|x|-b)i∑j=1i-1Lij(ξj-xj)+ω(2-ω)]).
To prove the required result, we use mathematical induction. For this, let i=1:
(20)ξ1=PK(x1-a11-1ω(2-ω)(Ax-|x|-b)1).
SinceAx-|x|-b≥0, 0<ω≤1; therefore, ξ1≤x1.
Fori=2, we have
(21)ξ2=PK(x2-a22-1222×[-ωL21(ξ1-x1)+ω(2-ω)222222×(Ax-|x|-b)2]a22-1).
Here, Ax-|x|-b≥0, 0<ω≤2, L21≥0 and ξ1-x1≤0. This implies that ξ2≤x2.
Suppose that(22)ξi≤xifori=1,2,…,k-1,
we have to prove that the statement is true for i=k; that is,
(23)ξk≤xk.
Consider
(24)ξk=PK(∑j=1k-1Lkj(ξj-xj)+ω(2-ω)xk-akk-1222222×[-ω∑j=1k-1Lkj(ξj-xj)+ω(2-ω)222222222222222×(Ax-|x|-b)k∑j=1k-1Lkj(ξj-xj)+ω(2-ω)])=PK(xk-akk-122222×[-ω(Lk1(ξ1-x1)+Lk2(ξ2-x2)222222222222+⋯+Lkk-1(ξk-1-xk-1))22222221+ω(2-ω)(Ax-|x|-b)k]akk-1).
Since Ax-|x|-b≥0, 0<ωk≤2, Lk1,Lk2,…,Lkk-1≥0 and ξi≤xi for i=1,2,…,k-1; from (24), we can write
(25)ξk≤xk.
Hence, (i) is proved.
Now we prove(ii), for this let us suppose that ξ=g(x) and ϕ=g(y). We will prove that
(26)x≤y⟹ξ≤ϕ.
As(27)ξ=PK(x-D-1222×[-ωLξ+(ω(2-ω)A+ωL)x222222-ω(2-ω)(|x|+b)-ωUxk+1]D-1),
so ξi can be written as
(28)ξi=PK(∑j=1j≠inUijxj-aii-12222222×[-ω∑j=1i-1Lijξj+ωaiixi+(ω-ω(2-ω))22222222222222222×∑j=1i-1Lijxj-ω(2-ω)2222222222222222222222×∑j=1j≠inUijxj-ω(2-ω)|xi|22222222222222222222222222222-ω(2-ω)bi∑j=1j≠inUijxj])=PK(∑j=1i-1Lijξj+(ω-ω(2-ω))(1-ω)xi-aii-1222222×[-ω∑j=1i-1Lijξj+(ω-ω(2-ω))2222222222222222×∑j=1i-1Lijxj-ω(2-ω)222222222222222222222×∑j=1j≠inUijxj-ω(2-ω)|xi|2222222222222222222222222222-ω(2-ω)bi∑j=1i-1Lijξj+(ω-ω(2-ω))]).
Similarly, for ϕi we have
(29)ϕi=PK(∑j=1j≠inUijyj(1-ω)yi-aii-1222222×[∑j=1j≠inUijyj-ω∑j=1i-1Lijϕj+(ω-ω(2-ω))2222222222222222×∑j=1i-1Lijyj-ω(2-ω)2222222222222222222222×∑j=1j≠inUijyj-ω(2-ω)|yi|22222222222222222222222222222-ω(2-ω)bi∑j=1j≠inUijyj]).
For i=1, we have
(30)ϕ1=PK(∑j=1j≠inU1jyj(1-ω)y1-a11-1ω(2-ω)2222222×[-∑j=1j≠inU1jyj-|y1|-b1])≥PK(∑j=1j≠inU1jyj(1-ω)x1-a11-1ω(2-ω)222222×[-∑j=1j≠inU1jxj-|x1|-b1])=ξ1.
Since y1≥x1, therefore -|y1|≤-|x1|. Hence, it is true for i=1. Suppose it is true for i=1,2,…,k-1; we will prove it for i=k; for this consider
(31)ϕk=PK(∑j=1k-1Lkjϕj+(ω-ω(2-ω))(1-ω)yk-akk-122222222×[∑j=1k-1Lkjϕj+(ω-ω(2-ω))22222222222222×∑j=1k-1Lkjyj-ω(2-ω)2222222222222222222×∑j=1j≠inUkjyj-ω(2-ω)|yk|22222222222222222222222222-ω(2-ω)bk∑j=1k-1Lkjϕj+(ω-ω(2-ω))])≥PK(∑j=1k-1Lkjξj+(ω-ω(2-ω))(1-ω)xk-akk-12222222×[∑j=1k-1Lkjξj+(ω-ω(2-ω))2222222222222×∑j=1k-1Lkjxj-ω(2-ω)222222222222222222×∑j=1j≠inUkjxj-ω(2-ω)|xk|22222222222222222222222222-ω(2-ω)bk∑j=1k-1Lkjξj+(ω-ω(2-ω))])=ξk.
Since x≤y and ξi≤ϕi for i=1,2,…,k-1, hence it is true for k and (ii) is verified.
Next we prove (iii); that is,(32)ξ=g(x)∈φ.
Letλ=g(ξ)=PK(ξ-D-1[ωL(λ-ξ)+ω(2-ω)(Aξ-|ξ|-b)]) from (i) g(ξ)=λ≤ξ. Also by definition of g,ξ=g(x)≥0 and λ=g(ξ)≥0.
Now(33)λi=PK(∑j=1i-1Lij(λj-ξj)ξi-aii-12222×[-ω∑j=1i-1Lij(λj-ξj)+ω(2-ω)2222222222222×(Aξ-|ξ|-b)i∑j=1i-1Lij(λj-ξj)])
For i=1,ξ1≥0 by definition of g. Suppose that (Aξ-|ξ|-b)i<0, so
(34)λ1=PK(ξ1-a11-1ω(2-ω)(Aξ-|ξ|-b)1)>PK(ξ1)=ξ1,
which contradicts the fact that λ≤ξ. Therefore, (Aξ-|ξ|-b)i≥0.
Now we prove it for anyk in i=1,2,…,n. Suppose the contrary (Aξ-|ξ|-b)i<0; then
(35)λk=PK(∑j=1k-1Lkj(λj-ξj)ξk-akk-12222×[-ω∑j=1k-1Lkj(λj-ξj)+ω(2-ω)222222222222×(Aξ-|ξ|-b)k∑j=1k-1Lkj(λj-ξj)]).
As it is true for all α∈[0,1], it should be true for α=0. That is,
(36)λk=PK(ξk-akk-1ω(2-ω)(Aξ-|ξ|-b)k)>PK(ξk)=ξk,
which contradicts the fact that λ≤ξ. So, (Aξ-|ξ|-b)k≥0, for any k in i=1,2,…,n.
Hence,ξ=f(x)∈φ.Now we prove the convergence criteria of Algorithm9 when the matrix A is an L-matrix as stated in the next result.Theorem 12.
Assume thatA∈Rn×n is an L-matrix and 0<ω≤1. Then for any initial vector x0∈φ, the sequence {xk},k=0,1,2,…, defined by Algorithm 9 has the following properties:(i)
0≤xk+1≤xk≤x0; k=0,1,2,…;(ii)
limk→∞xk=x* is the unique solution of the absolute complementarity problem.Proof.
Sincex0∈φ, by (i) of Theorem 11, we have x1≤x0 and x1∈φ. Recursively using Theorem 11, we obtain
(37)0≤xk+1≤xk≤x0;k=0,1,2,…..
From (i), we observe that the sequence {xk} is monotone bounded; therefore, it converges to some x*∈R+n satisfying
(38)x*=PK(x*-D-122222×[-ωLx*+ω(2-ω)(A+ωL)x*22222222-ω(2-ω)(|x*|+b)]D-1)=PK(x*-D-1ω(2-ω)2222222×[Ax*-|x*|-b]D-1).
Hence, x* is the solution of the absolute complementarity problem (2).Note. The convergence of Algorithm 10 has the same steps as given in Theorems 11 and 12.


## 3. Numerical Results

In this section, we consider several examples to show the efficiency of the proposed methods. The convergence of SSOR method is guaranteed forL-matrices only, but it is also possible to solve different type of systems. All the experiments are performed with Intel(R) Core 2 × 2.1 GHz, 1 GB RAM, and the codes are written in MATLAB 7.Example 13 (see [10]).
Consider the ordinary differential equation(39)d2xdt2-|x|=(1-t2),0≤x≤1,x(0)=0x(1)=1.
The exact solution is
(40)x(t)={0.7378827425sin(t)-3cos(t)+3-t2x<0,-0.7310585786e-t-0.2689414214et+1+t2x>0.
We taken=10; the matrix A is given by
(41)ai,j={-242,forj=i121for{j=i+1,i=1,2,…,n-1j=i-1,i=2,3,…,n0,otherwise.
The constant vectorb is given by
(42)b=(120121,117121,112121,105121,96121,85121,72121,57121,40121,-14620121)T.
Here, A is not an L-matrix. The comparison between the exact solution and the approximate solutions is given in Figure 1.
In Figure1, we see that the SSOR method converges rapidly to the approximate solution of absolute complementarity problem (2) as compared to GAOR method.
In the next example, we compare SSOR method with iterative method by Noor et al. [13].Figure 1
Comparison between GAOR method and SSOR method.Example 14 (see [13]).
Let the matrixA be given by
(43)ai,j={8,forj=i-1for{j=i+1,i=1,2,…,n-1j=i-1,i=2,3,…,n0,otherwise.
Let b=(6,5,5,…,5,6)T, the problem size n, ranging from 4 to 1024. The stopping criteria are ∥Ax-|x|-b∥<10-6. We choose initial guess x0 as x0=(0,0,…,0)T. The computational results are shown in Table 1.
In Table1, TOC denotes the total time taken by CPU. The rate of convergence of SSOR method is better than that of iterative method [13].Table 1
n
Iterative method
SSOR method
Number of iterations
TOC
Number of iterations
TOC
4
10
0.0168
8
0.001
8
11
0.018
8
0.001
16
11
0.143
9
0.001
32
12
3.319
9
0.001
64
12
7.145
9
0.015
128
12
11.342
9
0.020
256
12
25.014
10
1.051
512
12
98.317
10
6.130
1024
13
534.903
10
126.242


## 4. Conclusion

In this paper, we have discussed symmetric SOR method for solving absolute complementarity problem. The comparison with other methods showed the efficiency of the method. The results and ideas of this paper may be used to solve the variational inequalities and related optimization problems.



---

*Source: 172060-2013-09-29.xml*