2018 International Symposium on Nonlinear Theory and Its Applications,
NOLTA2018, Tarragona, Spain, September 2-6, 2018

A Distributed Algorithm for Solving Sandberg-Willson Equations
Masaaki Takeuchi and Norikazu Takahashi
Graduate School of Natural Science and Technology, Okayama University
3–1–1 Tsushima-naka, Kita-ku, Okayama 700–8530, Japan
Email: takeuchi@momo.cs.okayama-u.ac.jp, takahashi@cs.okayama-u.ac.jp
Abstract—A distributed algorithm for solving
Sandberg-Willson equations, which are well-known
nonlinear equations in the field of circuit theory, is proposed in this paper. It is shown numerically that, by using
this algorithm, all agents in a network can find the uniquesolution. It is also shown theoretically that the sequence ofsolutions of every agent converges to the unique solution
under some assumptions on the nonlinear function and thecoeﬃcient matrix in the equation.
1. Introduction
Distributed computations by multi-agent networks haverecently attracted a great deal of attention [1–5]. One of
the most well-known distributed computations is the average consensus [1]; the state value of each agent is updated based on the state values of agents in its neighborhood, and converges to the average of the initial values of
all agents. Other examples are the computation of the algebraic connectivity of the network [4, 5], the constrained
consensus [2, 3], and the constrained optimization [2].
In this paper, we consider the distributed computation ofa class of nonlinear algebraic equations studied by Sandberg and Willson Jr. [6]. An important property of theseequations is that the existence and the uniqueness of the solution is guaranteed. However, the problems are neither linear nor convex, conventional approach [2, 3] based on projection cannot be directly applied. We propose a new distributed algorithm for solving the above-mentioned equations. This algorithm is based on a consensus algorithm
and numerical techniques such as the Newton method [7]for solving nonlinear equations. It is shown numericallythat, by using this algorithm, all agents in a network canfind the unique solution. It is also shown theoretically thatthe sequence of solutions of every agent converges to theunique solution under some assumptions on the nonlinear
function and the coeﬃcient matrix in the equation.

f (x) = ( f1 (x1 ), f2 (x2 ), . . . , fn (xn ))T is a given nonlinear
function from Rn to Rn . Throughout this paper, we assume
that (1) satisfies the following two assumptions.
Assumption 1 A is a P0 matrix.
Assumption 2 For all i ∈ {1, 2, . . . , n}, the function fi :R → R is continuous, strictly monotone increasing, andsurjective.
Sandberg and Willson, Jr. [6] proved that (1) has aunique solution if Assumptions 1 and 2 are valid. Hence
we hereafter call equations of the form (1) that satisfy Assumptions 1 and 2 Sandberg-Willson equations.
We want to let a network of n agents solve SandbergWillson equations under the following situation: i) agent i
only knows the i-th equation, that is,fi (xi ) + ai x = bi(2)where ai is the i-th row of the matrix A, ii) each agent canfind a solution of its own equation, iii) each agent can send
its solution to some other agents and receive their solutions
through communication channels (see Fig. 1). The objective of this paper is to design a distributed algorithm for themulti-agent network so that every agent can find the uniquesolution of (1) under the above-mentioned situation.
The communication among agents can be represented
by a simple and undirected graph G = (V, E) where V ={1, 2, . . . , n} is the vertex set and E is the edge set. Vertex i corresponds to agent i. Each edge is an unorderedpair of distinct vertices. Edge {i, j} is contained in E if
and only if agents i and j can directly communicate witheach other. The neighborhood Ni of vertex i is defined as
Ni = { j | {i, j} ∈ E} ∪ {i}.
3. Proposed Algorithm
Let us define n functions g1 , g2 , . . . , gn by

2. Problem Statement
We consider nonlinear algebraic equations for x =(x1 , x2 , . . . , xn )T ∈ Rn of the following form:f (x) + Ax = b(1)

where A = (ai j ) ∈ Rn×n is a given constant matrix,b = (b1 , b2 , . . . , bn )T ∈ Rn is a given constant vector, andgi (xi ) ≜ fi (xi ) + aii xi ,i = 1, 2, . . . , n.

(3)Note that aii is nonnegative for all i because A is P0 matrix. So gi (xi ) is continuously diﬀerentiable, strictly monotone increasing, surjective, and therefore has the inverse
function g−1: R → R which is also continuously diﬀerientiable, strictly monotone increasing and surjective. Let- 259 -

Figure 2: Communication graph G1 .
4. Numerical Experiments
In order to check the validity of the proposed algorithm,
we conducted some numerical experiments. In the first experiment, we set0.123
 0.810
 0.418
2.185

 −0.081 −0.392
 −0.133
0.147
A = 
 −0.064 −0.236
 0.392
0.186 −0.075
0.176

0.158
0.167

Figure 1: A multi-agent network for solving (1).
xi (t) = (x1i (t), x2i (t), . . . , xni (t))T be the solution estimatedby agent i at discrete time t ∈ Z+ where Z+ is the set of
nonnegative integers. Then the distributed algorithm we
propose in this paper is described as follows.
In the first step, each agent i randomly chooses xi (0),and then obtain xi (1) by


(

)

∑n
−1
i


gi bi − j=1, j,i ai j x j (0)xij (1) = i x (0),j,

if j = i,if j , i.

−0.005
0.426
0.202
0.300
0.261
0.047
−0.1820.193
0.450 −0.173
0.138
1.131
0.037 −0.014
0.261
0.096

(4)

Here we have assumed that each agent i can compute thevalue of g−1
i (y) for any y ∈ R. Taking (3) into account, we
see that xi (1) is a solution of (2). In the t-th step (t ≥ 2),each agent i computes the average of the solutions of agentsk ∈ Ni by−0.599−0.066−0.4141.038−0.154−0.5870.204−0.337−0.0730.363
0.121−0.0280.133−0.100
0.802
0.068


0.463 
−0.285 

0.164 
−0.328 

0.105 

0.573 

−0.174 
0.976

b = (1.902, 30.594, 31.889, 42.617,
22.120, 46.400, 609.255, 5.754)T ,1 ∑ kw (t − 1) =x (t − 1)|Ni | k∈N
i

(5)

i

and
fi (xi ) = ixi + e0.1ixi ,iand then obtain x (t) by

(
)
∑n
−1
i


gi bi − j=1, j,i ai j w j (t − 1) ,ix j (t) = wi (t − 1),j−0.139−0.3040.902−0.0570.031
0.086−0.0730.115

if j = i,if j , i.

(6)

We see that xi (t) is also a solution of (2).
It is impossible in general to express g−1
explicitly.
i
So each agent i has to solve the equation gi (xi ) = bi −∑nij=1, j,i ai j w j (t − 1) for xi numerically. There are many
good algorithms for solving such equations. For example,
the inexact Newton method for solving systems of monotone equations proposed by Solodov and Svaiter [7] has
an important property that the sequence generated by themethod always globally convergent to the unique solution.
We therefore use this method in the numerical experiments.

i = 1, 2, . . . , 8.

We also set the communication graph G of the multi-agent
network to G1 shown in Fig. 2.
We obtained A above in the following way. We first
generated a matrix B = (bi j ) ∈ Rn×n such that b j j >∑ni=1,i, j |bi j | for j = 1, 2, . . . , n. This is easily done bychoosing the values of oﬀ-diagonal entries randomly andthen setting the value of diagonal entries so that the above
inequalities hold. We next generated a matrix C = (ci j ) ∈∑Rn×n such that c j j ≥ ni=1,i, j |ci j | for j = 1, 2, . . . , n in a similar way as B. We finally set A = B −1 C because it is guaranteed that any A constructed in this way is a P0 matrix. As
for the vector b, we chose the values of its entries so that(1) has the unique solution x∗ = (2, 8, 5, 6, 3, 4, 9, 1)T .
Each agent i sets the initial solution xi (0) to 0, and thenupdates the solution by using (4) and (6). Computation- 260 -

10

8
7

i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8

16
14
12
ei(t)

6
ei(t)

18

i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8

9

5
4

10
8
6

3
2

4

1

2

0

0
0

20

40

60

80

100

0

50

100

150

t

200

250

t

Figure 3: Behavior of the error ei (t) = ∥xi (t) − x∗ ∥ when
G = G1 .

Figure 5: Behavior of the error ei (t) = ∥xi (t) − x∗ ∥ when
G = G2 .
Theorem 1 Suppose that fi (xi ) is continuously diﬀerentiable for i = 1, 2, . . . , n and there exists a positive constantδ such thatfi′ (xi ) ≥ δ > 0,i = 1, 2, . . . , n.

(7)

If the communication graph G of the multi-agent network
is connected and the matrix A satisfies
Figure 4: Communication graph G2 .

δ + aii >n∑|ai j |,

i = 1, 2, . . . , n,(8)j=1, j,iof g−1i is done by the inexact Newton method proposed by
Solodov and Svaiter [7] under the following setting: β =0.5, λ = 0.01, Gk is a number randomly chosen from [0, 1],µk = 0.01, ρk = 0.01, the initial solution is set to xii (t − 1),and the stopping condition is set to dk ≤ 10−4 . For moredetails of the inexact Newton method, see [7].
Figure 3 shows how the error ei (t) = ∥xi (t)−x∗ ∥ between
the solution xi (t) of agent i at time t and the true solution x∗
varies with t for i = 1, 2, . . . , 8. It is clear from the figurethat ei (t) converges to zero for all i, which means that allagents successfully find the true solution x∗ .
In the second experiment, we used the same setting as in
the first experiment except the communication graph. We
set the communication graph G to G2 in Fig. 4, which isa path graph obtained by removing three edges from G1 .
Figure 5 shows how the error ei (t) = ∥xi (t) − x∗ ∥ between
the solution xi (t) of agent i at time t and the true solutionx∗ varies with t for i = 1, 2, . . . , 8. It is clear from the figurethat all agents successfully find the true solution x∗ .

then we have
lim xi (t) = x∗ ,t→∞i = 1, 2, . . . , n(9)where x∗ is the unique solution of (1).
Proof: Let ãi be the row vector obtained from ai by setting
the i-th entry aii to zero. It follows from (7) and (8) thati−1∗xii (t + 1) − xi∗ = g−1
i (bi − ãi w (t)) − gi (bi − ãi x )


∑


∗
bi − 1 ãixk (t) − g−1= g−1
i (bi − ãi x )
i 

|Ni |
k∈Ni

≤

∑
1
1
ãi
xk (t) − ãi x∗
δ + aii |Ni | k∈N
i

=

∑

1
ãi
(xk (t) − x∗ )(δ + aii )|Ni |k∈Ni1|ai j | xkj (t) − x∗j(δ + aii )|Ni | k∈N j=1, j,i
i
∑n
|a
|
j=1, j,i i j≤max
xk (t) − x∗jδ + aii k∈Ni , j∈{1,2,...,n}\{i} j

5. Convergence Analysis≤

In this section, we show theoretically that if the nonlinear function f (x) and the matrix A satisfies a few additional assumptions then, by using the proposed algorithm,
all agents can find the unique solution of (1).

≤

- 261 -

n
∑ ∑

max

k∈Ni , j∈{1,2,...,n}\{i}xkj (t) − x∗j(10)holds for i = 1, 2, . . . , n. Also, for any pair of i and j suchthat i , j, we havexij (t + 1) − x∗j = wij (t) − x∗j1 ∑ kx (t) − x∗j|Ni | k∈N j
i
1 ∑ k
≤
x (t) − x∗j|Ni | k∈N j=

6. Conclusion≤ max xkj (t) − x∗j .

We have proposed a distributed algorithm for solving Sandberg-Willson equations. The authors confirmed
through a large number of numerical experiments that theunique solution is always found by the proposed algorithm.
However, we have only proved the validity of the algorithm
in a special case. Further theoretical analysis is needed tounderstand the behavior of the proposed algorithm.

i

k∈Ni

(11)

Let us now define Z(t) as Z(t) = maxi, j∈{1,2,...,n} xij (t) − x∗j .
Then we haveZ(t + 1) ≤ Z(t),t = 1, 2, . . .

≤ Z(t)
holds for i = 1, 2, . . . , n. Suppose that i , j. If there
exists a k ∈ Ni such that xkj (t) − x∗j < Z(t) then it
follows from (11) that xij (t + 1) − x∗j < Z(t). For thesame reason, we have xij (t + 2) − x∗j < Z(t). Repeating
this argument, we finally havexij (t + n) − x∗j< Z(t). If

xkj (t) − x∗j = Z(t) holds for all k ∈ Ni then it follows
from (11) that xij (t + 1) − x∗j = Z(t). However, because
x jj (t + 1) − x∗j < Z(t), for all vertices j1 adjacent to vertex j, x jj1 (t + 2) − x∗j < Z(t) holds. This implies that for all
vertices j2 such that the shortest path length from vertex j istwo, x jj2 (t + 3) − x∗j < Z(t) holds. Repeating this argument
and making use of the assumption that G is connected, wefinally have xij (t + n) − x∗j < Z(t).
Let Ẑ(t) ≜ Z(nt) for all t ∈ Z+ . Then, we see from theabove discussion that the sequence {Ẑ(t)}∞t=1 is monotone
decreasing and Ẑ(t + 1) = Ẑ(t) if and only if Ẑ(t) = 0,
that is, xi (nt) = x∗ for i = 1, 2, . . . , n. Also, for alli, j ∈ {1, 2, . . . , n} and all t ∈ Z+ , we have |xij (nt) − x∗j | ≤Z(1), which means that (x1 (nt), x2 (nt), . . . , xn (nt)) is included in a bounded and closed subset in (Rn )n . Furthermore, (x1 ((n + 1)t), x2 ((n + 1)t), . . . , xn ((n + 1)t)) depends
continuously on (x1 (nt), x2 (nt), . . . , xn (nt)). Therefore, by
Zangwill’s global convergence theorem [8], we have
lim xi (nt) = x∗ ,References(12)

from (10) and (11).
Next we show that if Z(t) > 0 then Z(t + n) < Z(t). We
first see from (10) and (12) that∑nj=1, j,i |ai j |i∗xi (t + n) − xi ≤Z(t + n − 1)
δ + aii< Z(t + n − 1)t→∞which means that limt→∞ Ẑ(t) = 0. From this result and themonotonicity of the sequence {Z(t)}∞t=1 , we can conclude
that limt→∞ Z(t) = 0 which is equivalent to (9).
□[1] R. Olfati-Saber, J. A. Fax and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol. 95, no. 1,
pp. 215–233, January 2007.
[2] A. Nedić, A. Ozdaglar and P. A. Parrilo, “Constrained
consensus and optimization in multi-agent networks,”
IEEE Transactions on Automatic Control, vol. 55,
no. 4, pp. 922–938, 2010.
[3] S. Mou and A. S. Morse, “A fixed-neighbor, distributed algorithm for solving a linear algebraic equation,” Proceedings of 2013 European Control Conference, pp. 2269–2273, 2013.
[4] K. Yamane and N. Takahashi, “Proposal of a truly
decentralized algorithm for estimating algebraic connectivity of multi-agent networks,” Proceedings of2015 International Symposium on Nonlinear Theory
and its Applications, pp. 277–280, 2015.
[5] K. Endo and N. Takahashi, “A new decentralized
discrete-time algorithm for estimating algebraic connectivity of multiagent networks,” Proceedings of2016 Asia Pacific Conference on Circuits and Systems, pp. 232–235, 2016.
[6] I. W. Sandberg and A. N. Willson, Jr., “Some theorems on properties of dc equations of nonlinear networks,” Bell System Technical Journal, vol. 48, pp. 1–
34, January 1969.
[7] M. Solodov and B. F. Svaiter, “A globally convergent inexact Newton method for systems of monotone equations,” Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods,
pp. 355–369, 1998.
[8] W. I. Zangwill, Nonlinear Programming: A Unified
Approach, Prentice-Hall, 1969.

i = 1, 2, . . . , n- 262 -