Distributed Lagrangian Methods for Network Resource Allocation

arXiv:1609.06287v3 [math.OC] 24 Aug 2017

Thinh T. Doan1 and Carolyn L. Beck2

Abstract— Motivated by a variety of applications in control engineering and information sciences, we study network
resource allocation problems where the goal is to optimally
allocate a fixed amount of resource over a network of nodes.
In these problems, due to the large scale of the network with
complicated inter-connections between nodes, any solution must
be implemented parallel between nodes and based only on local
data resulting in the need of distributed algorithms. In this
paper, we propose a novel distributed Lagrangian methods,
which only requires local computation and communication. Our
focus is to understand the performance of this algorithm on the
underlying network topology. Specifically, we obtain an upper
bound on the rate of convergence of the algorithm as a function
of the size and the topology of the underlying network. Finally,
to illustrate the effectiveness of the proposed method we apply
it to solve the important economic dispatch problems in power
systems on the benchmark IEEE 14 and 118 bus systems.

I. I NTRODUCTION
We study network resource allocation problems, where the
goal is to optimally allocate a fixed portion of resources over
a network of nodes. Each node suffers a cost as a function
of the portion of resources allocated to it. The goal of this
problem is to seek an optimal allocation such that the total
cost incurred over the network is minimized, while satisfying
each node’s local constraints. This problem is sometimes
described in terms of utility functions, with the goal being to
maximize the total utility. In this problem, due to the large
scale and complex interconnection structure of the network,
central coordination is undesirable or even impossible, resulting in the necessity for distributed algorithms. Our focus,
therefore, is to study distributed algorithms which can be
implemented in parallel and require only local data.
Resource allocation is a fundamental and important problem that arises in a variety of application domains within
engineering. One standard example is the problem of congestion control where the global objective is to route and
schedule information in an internet network such that a fair
resource allocation between users is achieved [21]. Another
example is coverage control in wireless sensor networks,
where the goal is to optimally allocate a large number of
sensors in an unknown environment such that the coverage
area is maximized [7], [20]. A simplified version of the
important economic dispatch problem in power systems can
also be viewed as a resource allocation problem, wherein
1 Thinh
Computer

T. Doan is with the Deparment of Electrical and
Engineering, University of Illinois, Urbana, IL, USA

ttdoan2@illinois.edu
2 Carolyn Beck is with the Department of Industrial and Enterprise Systems Engineering, University of Illinois, Urbana, IL, USA

beck3@illinois.edu

geographically distributed generators of electricity must coordinate to meet fixed demand while maintaining the stability
of the systems [12], [25].
Given the large application domains of network resource
allocation problems, distributed algorithms for such problems
have received a surge of interest in recent years. The first
algorithm which could be implemented in a distributed way
was the “center-free” protocol introduced in [13] for a
relaxation of this problem, in which the authors consider the
case where local constraints are excluded. The term “centerfree” was originally meant to refer to the absence of any
central coordination. In this relaxed problem, the necessary
and suffcient optimality conditions are the consensus of the
nodes’ incremental costs and the feasibility constraint on the
total amount of resource available [22]. The work in [13]
has been followed by work in [9], [16], [17], [22], with the
main focus on analyzing the performance of the algorithm
and its variants for the relaxed problem.
Although the results of the relaxed problem are welldeveloped, they are impractical since the local constraints
of the nodes are critical in real applications. For example, in
economic dispatch problems these local constraints, which
represent the limited capacity of generators, are inevitable.
Recently, there has been a number of studies on resource
allocation problems which utilize the necessary and sufficient conditions of the relaxed problem. In particular, the
authors in [5], [10], [15], [23], [24] focus on studying
economic dispatch problems where the objective functions
are quadratic. Their methods are mainly based on utilizing
distributed consensus algorithms to achieve an agreement
on the incremental costs between generators while using
a proper projection for the generators’ local constraints.
The authors in [6], [16] relax the assumption on quadratic
cost functions to allow for any convex cost functions with
Lipschitz continuous gradients. These methods are based on
considering a relaxed problem that uses appropriate penalty
functions for the nodes’ local constraints. While the authors
in [16] only show a convergence to a near-optimal solution,
the authors in [6] show that the solutions of the relaxed
problem coincide with resource allocation problems with an
appropriate choice of the penalty level.
In this paper, we propose a fully distributed method for
resource allocation problems with general convex objective
functions. We focus on analyzing the performance of the
method to understand how fast the optimal value may be
obtained. In particular, we provide an upper bound for the
convergence rate of the method as a function of the size
and the topology of underlying networks. This fundamental
question, which is necessary to analyze distributed systems,

has not been considered explicitly in the literature. Moreover,
unlike the work previously cited where the authors consider
either a relaxation of the problem or specific quadratic
objective functions, our minimal assumption on the convexity
of the objective functions is general enough to cover a larger
class of problems.
Main Contributions The main contributions of the paper
are the following. We first propose a novel distributed
Lagrangian method for resource allocation problems on
undirected and connected networks. Second, we demonstrate
that under fairly standard assumptions on the convexity
of objective functions and network connectivity, the distributed Lagrangian√method achieves a convergence rate
O(n ln(k)/(1 − σ2 ) k) to the optimal value, where σ2 is
a parameter representing the spectral properties of network
connectivity of the nodes, n is the number of nodes, and k
is the number of iterations. Unlike the work in [6] and [16],
we assume neither any relaxation nor Lipschitz continuity of
the gradient of objective functions in our problem, meaning
that our method is general enough to cover a larger class
of problems. As one illustration of the effectiveness of the
proposed method for control and optimization applications,
we apply it to solve the important economic dispatch problem
in power systems, and specifically consider the benchmark
IEEE-14 and IEEE-118 bus test systems. Simulations show
that our method outperforms the method proposed in [15].
The remainder of this paper is organized as follows.
We give a formal statement of the problem in Section II.
Our proposed method is described in Section III and its
convergence analysis is given in Section IV. In Section V,
we discuss the results of applying our method to specific
economic dispatch problems via simulations. We conclude
the paper with some potential future directions in Section
VI.
Notation 1: We use boldface to distinguish between vectors x in Rn and scalars x in R. Given a vector x, we
write x = (x1 , x2 , . . . , xn ) and denote by kxk2 its Euclidean
norm. Finally, let 1 ∈ Rn be the vector whose entries are 1.
II. P ROBLEM F ORMULATION
In this paper we consider resource allocation problems
over a network of n nodes. The goal of this problem is
to seek an optimal allocation for a prespecified portion or
quantity of a given resource such that the total cost incurred
over the network is minimized while satisfying the nodes’
local constraints. In general, this problem can be formulated
as the following optimization problem:

Pn

 minx∈Rn i=1 fi (xi )
Pn
P :
(1)
s.t.
i=1 xi = b,


xi ∈ Xi , ∀i = 1, . . . , n.
where fi : R → R is a cost function known only by node i
and the constant b is the total portion of resources shared by
the nodes. Moreover, the sets Xi are assumed to be convex
and compact. We note that the formulation of P is general
enough to cover the models studied in [6], [9], [10], [15],
[16].

In the sequel, will use X to denote the Cartesian product
of Xi , i.e., X = X1 × X2 ×P
. . . × Xn . The feasible set S of
n
P is given as S = {x ∈ X | i=1 xi = b} and it is assumed
to be nonempty. For short, we denote f : Rn → R as the
sum of the functions fi , i.e.,
f (x) =

n
X

fi (xi ).

(2)

i=1

We will make the following assumptions on the objective
functions fi throughout the paper:
Assumption 1: For each i = 1, . . . , n the function fi :
R → R is proper, closed, and convex.
Assumption 2 (Slater’s condition [4]): There exists a
point
Pn x̃ that belongs to the relative interior of X and satisfies
i=1 x̃i = b.
We note that since the constraint set in P is compact and
the objective function f is continuous, there exists a vector
x∗ = (x∗1 , x∗2 , . . . , x∗n ) ∈ S which achieves the minimum
of this problem. However, this solution may not be unique.
We denote the set of solutions of P as S ∗ . Moreover, under
the Slater’s condtion strong duality holds and the set of dual
optimal solutions is nonempty.
Our focus is on designing a distributed method to solve P
in a network, which means that each node is only allowed to
interact with nodes, referred to as their local neighbors, that
are connected to it in a graph. Specifically, we assume we
are given a graph G = (V, E) with V = {1, . . . , n}; nodes i
and j can exchange messages if and only if (i, j) ∈ E. We
denote by Ni the set of neighbors of node i. We make the
following fairly standard assumption regarding connectivity
of graph G.
Assumption 3: The graph G is undirected and connected.
III. M AIN A LGORITHM
In this section, we propose a novel distributed method,
namely, a distributed Lagrangian method, for P. Our method
can be presented as a distributed version of well-known
classical Lagrangian methods [3]. We start this section by
giving a brief motivation for our method.
Without loss of generality, we
Pnassume that each node i
knows the constant bi such that i=1 bi = b. Here bi can be
interpreted as the initial resource allocation at node i. One
specific choice is to initially distribute b equally to all nodes,
i.e., bi = b/n for all i = 1, . . . , n. We note that the design
of our algorithm as well as our analysis given later does not
depend on the choice of these bi since they are only used
for notational convenience.
We now explain the mechanics of our approach. Consider
the following Lagrangian function L : X × R → R of P
!
n
n
X
X
L(x, λ) :=
fi (xi ) + λ
x i − bi ,
(3)
i=1

i=1

where λ ∈ R is the Lagrangian multiplier associated with
the coupling equality constraint in (1). The dual function

d : R → R of problem P for some λ value is then defined
as
!!
n
n
X
X
d(λ) := minn
fi (xi ) + λ
(xi − bi )
x∈R

=

n
X

i=1

i=1

{−fi∗ (−λ) − λbi },

q : Rn → R as
q(λ) =

n
X

qi (λi ).

i=1

The updates (6)–(8) then can be written compactly in vector
form as,
v(k + 1) = Aλ(k)

i=1

x(k + 1) ∈ arg min

where fi∗ is the Fenchel conjugate of fi , defined by

x∈X

fi∗ (u) = sup {ux − fi (x)}.

X

fi (xi ) + vi (k + 1)(xi − bi )

i∈V

λ(k + 1) = v(k + 1) − α(k)∇q(v(k + 1)),

x∈Xi

where ∇q(·), with some abuse of notation, is the subgradient
of the dual function q, i.e.,

The dual problem of P, denoted by DP, is given by
DP : max
λ∈R

n
X
{−fi∗ (−λ) − λbi },

∇q(λ) = [∂q1 (λ1 ), . . . , ∂qn (λn )]T .

i=1

which is then equivalent to solving
min
λ∈R

n
X
i=1

f ∗ (−λ) + λbi ,
{z
}
|i

(4)

=qi (λ)

where qi : R → R is a convex function since fi∗ is a convex
function [3].
A common approach to solve problem (1) is Lagrangian
methods [3], which require a central coordinator to update
and distribute the multiplier λ to the nodes. The key idea of
our approach is to eliminate this requirement by utilizing the
distributed subgradient method presented in [19] to compute
the solution of (4). In particular, we have that each node i
stores a local copy λi of the Lagrange multiplier λ, and
then iteratively updates λi upon communicating with its
neighbors. The update of λi is comprised of two steps,
namely, a consensus step and a so-called “local gradient
descent” step. These two steps, coupled with the primal
update in the Lagrangian approach, results in our distributed
Lagrangian algorithm, presented in Algorithm 1.
The updates in Algorithm 1 have a simple implementation:
first, at time k ≥ 0, each node i in step (6) broadcasts the
current value of λi (k) to its neighbors. Node i computes
vi , as given by the weighted average of the current local
values of its neighbors and its own value. The updates of
xi (k + 1) and λi (k + 1) then do not require any additional
communications among the nodes at step k. In particular,
the update of the primal variables xi is executed in step (7).
Finally, in step (8) λi is updated by moving a distance of
α(k) along a subgradient of qi at vi (k + 1), given by
bi − xi (k + 1) ∈ ∂qi (vi (k + 1)),

(5)

where ∂qi (vi (k + 1)) is the sub-differential set of qi at
vi (k + 1). We note that our method maintains the feasibility
of the nodes’ local constraints at every iteration, i.e., xi (k) ∈
Xi for all k ≥ 0. Furthermore, the nodes do not need to
store the variables vi in step (6) since these are used only
for notational convenience.
Let A be the communication matrix whose the (i, j)−th
entries are aij . Moreover, for short we denote the function

Throughout the remainder of this paper, we assume that
A satisfies the following assumption.
4: A is a doubly stochastic matrix, i.e.,
PAssumption
P
n
n
a
=
ij
i=1
j=1 aij = 1 with aii > 0. Moreover, the
weights aij > 0 if and only if (i, j) ∈ E otherwise aij = 0.
In the sequel, let σ2 be the second largest singular value
of A. By the Courant-Fisher theorem [14], since A is doubly
stochastic and the graph is connected, we have σ2 ∈ (0, 1).
Algorithm 1: A Distributed Lagrangian Method (DLM)
1. Initialize: Each node i initializes its variables as
xi (0) ∈ R, λi (0) ∈ R.
2. Iteration: For k ≥ 0 each node i implements the
following steps
X
vi (k + 1) =
aij λj (k)
(6)
j∈Ni

xi (k + 1) ∈ arg min fi (xi )+vi (k + 1)(xi − bi )

(7)

λi (k + 1) = vi (k + 1) − α(k)(xi (k + 1) − bi )

(8)

xi ∈Xi

IV. C ONVERGENCE A NALYSIS
The goal of this section is to provide an analysis for
the convergence of the distributed Lagrangian method proposed in the previous section. Specifically, we will show
that the method achieves an asymptotic convergence to the
optimal value of P. In addition, to understand how fast the
algorithm obtains the optimal objective value we utilize the
standard technique from centralized subgradient methods.
Specifically, the method achieves an asymptotic convergence
√
to the optimal value at the rate O(n ln(k)/(1−σ2 ) k). Here
the parameter σ2 represents the spectral properties of network
connectivity. We note that such an explicit upper bound on
the convergence rate for distributed resource allocation is not
available in the literature. More detail will be given shortly.
We start our analysis by introducing more notation. Given
an optimal solution x∗ ∈ S ∗ of P, let λ∗ be a dual optimal
of DP, i.e., (x∗ , λ∗ ) is a saddle point of L(x, λ)
L(x∗ , λ) ≤ L(x∗ , λ∗ ) ≤ L(x, λ∗ ) ∀x ∈ Rn , λ ∈ R.

Moreover, let λ∗ be a vector such that
λ = (λ∗ , . . . , λ∗ )T ∈ Rn . Denote by Li : Xi × R → R the
local Lagrangian function at node i
∗

and with some abuse of notation, the global Lagrangian
function L : X × Rn → R is defined as
X
L(x, v) =
Li (xi , vi ).
(9)
i∈V

Our first result is the Lipschitz continuity of the functions qi
given in the following proposition.
Proposition 1: Let the sequences {xi (k)} and {λi (k)} for
all i ∈ V be generated by the DLM algorithm. Then there
exists a positive constant C such that for all k ≥ 0,
for all i ∈ V.

(10)

Proof: Since Xi is a compact set and xi (k) ∈ Xi
∀k ≥ 0, by (5) there exists a positive constant Ci such that
|∂qi (vi (k))| ≤ Ci ∀k. Letting C = maxi Ci gives (10).
Recall that the updates (6) and (8) are the distributed subgradient methods, studied in [19] for problem (4). Moreover,
since the subgradient of qi is bounded, we can now apply
the result in [19, Proposition 4] to show the convergence of
λi to λ∗ , a dual optimal. Due to the limited space, we skip
the proof here and refer the readers to [19].
Lemma 1 ( [19]): Let Assumptions 1–4 hold. Let the
sequences {xi (k)} and {λi (k)} for all i ∈ V be generated
by the DLM algorithm. Assume that the step size α(k)
is positive, nonincreasing with α(0) = 1, and satisfies the
following conditions,
∞
X

∞
X

α(k) = ∞,

k=0

α2 (k) < ∞.

(11)

k=0

Then, given a dual optimal λ∗ of (4), we have
lim λi (k) = λ∗ ,

k→∞

for all i ∈ V.

X

vi (k + 1)(x∗i − bi ).

(12)

We note that by Lemma 1, we have limk→∞ λi (k) = λ∗
∀i ∈ P
V, implying limk→∞ vi (k + 1) = λ∗ since vi (k +
1) = j∈Ni aij λj (k) and A isPa doubly stochastic
matrix.
P
In addition, since x∗i satisfies i∈V x∗i = i∈V bi = b we
have
lim kv(k + 1) − λ∗ k1 = 0,
X
lim
vi (k + 1)(x∗i − bi ) = 0.

k→∞

k→∞

i∈V

Thus, we obtain
X
0 ≤ lim
Li (x∗i , vi (k + 1)) − Li (xi (k + 1), vi (k + 1))
k→∞

i∈V

X

= lim

k→∞

Li (x∗i , λ∗ ) − Li (xi (k + 1), vi (k + 1)) = 0,

i∈V

which implies that
0 ≤ L(x∗ , λ∗ ) − lim sup L(x(k + 1), λ(k))
k→∞

= f (x∗ ) − lim sup L(x(k + 1), λ(k)) = 0,

(15)

k→∞

where we use the fact that L(x∗ , λ∗ ) = f (x∗ ) and
limk→∞ λ(k) = limk→∞ v(k) = λ∗ .
We are now proceeding to show (14). Since xi (k + 1)
satisfies (7) and by the definition of Li in (9) we have for
∀i ∈ V and k ≥ 0,
0 ≤ Li (x∗i , vi (k + 1)) − Li (xi (k + 1), vi (k + 1)),
which when summing for all i ∈ V implies that
X
0≤
Li (x∗i , vi (k + 1)) − Li (xi (k + 1), vi (k + 1))
=

X

−

X

fi (x∗i ) + vi (k + 1)(x∗i − bi )

i∈V

k→∞

∗

∗

Proof: We first have (x , λ ) is a saddle point of the
Lagrangian (3) where λ∗ satisfies (12). Recall from (9) that
X
X
L(x, v) =
Li (xi , vi ) =
fi (xi ) + vi (xi − bi ).
i∈V

fi (xi (k + 1)) + vi (k + 1)(xi (k + 1) − bi ). (16)

i∈V

By Assumption 1 the zero duality gap holds, i.e.,
X
X
X
(4)
fi (x∗i ) =
di (λ∗ ) = −
qi (λ∗ ).
i∈V

i∈V

i∈V

Moreover by (4) and (7) we have
qi (vi (k + 1))= −fi (xi (k + 1))− vi (k + 1)(xi (k + 1) − bi ).
Substitute the previous two preceding relations into (16) we
obtain
X
0≤
Li (x∗i , vi (k + 1)) − Li (xi (k + 1), vi (k + 1))
i∈V

=

X

≤

X

qi (vi (k + 1)) − qi (λ∗ ) + vi (k + 1)(x∗i − bi )

i∈V
1 There

(14)

i∈V

i∈V

A specific choice of the squence of stepsize is α(k) = 1/k,
which obviously satisfies (11). We are now ready to state our
first main result, that is the distributed Lagrangian method
achieves an asymptotic convergence to the optimal value of
problem P1 .
Theorem 1: Let all assumptions given in Lemma 1 hold.
Let {xi (k)} and {λi (k)} for all i ∈ V be generated by
Algorithm 1. Then, for all integers k ≥ 0 we have,
lim L(x(k + 1), λ(k)) = f (x∗ ).
(13)

i∈V

i∈V

≤ Ckv(k + 1) − λ∗ k1 +

Li (xi , vi ) = fi (xi ) + vi (xi − bi ),

|∂qi (vi (k + 1))| ≤ C,

To show our main result, we will show the following relation,
X
0≤
Li (x∗i , vi (k + 1)) − Li (xi (k + 1), vi (k + 1))

is an error in Theorem 1 in the version appeared on IEEE
Conference on Control and Technology Applications 2017 [8], which is
corrected by Theorem 1 given here

i∈V

C|λ∗ − vi (k + 1)| + vi (k + 1)(x∗i − bi ),

where the last inequality is due to (10). This concludes our
proof.
To show the convergence rate of the distributed Lagrangian
method, we need the following properties of (8) studied in
[18], for the case of undirected connected graph.
Lemma 2 (Lemma 3 [18]): Let Assumptions 3–4 hold.
Let the sequence {λi (k)} for all i ∈ V be generated by
Algorithm 1. Assume that the step size α(k) is nonincreasing
with α(0) = 1. Then the following statements hold,
1) For all i = 1, . . . , n, and k ≥ 0

√

nC

k−1
X

α(t)σ2k−1−t ,

(17)

where σ2 ∈ (0, 1) is the second largest singular value
of A.
√
2) If in addition α(k) = 1/ k for k ≥ 1 and α(0) = 1,
then for all i = 1, . . . , n, and an integer K ≥ 1

≤

kλ(0)k1
+
1 − σ2

nC(2 + ln(K))
·
1 − σ2

X
(vi (k + 1) − α(k)∂qi (vi (k + 1)) − λ∗ )2
i∈V

X
X
=
(vi (k + 1) − λ∗ )2 +
α2 (k)[∂qi (vi (k + 1))]2
− 2α(k)

i∈V

X

∂qi (vi (k + 1))(vi (k + 1) − λ∗ )

i∈V

≤ kv(k + 1) − λ∗ k22 + nC 2 α2 (k)
+ 2α((k)q(λ∗ ) − q(v(k + 1)),

+ 2α(k)(q(λ∗ ) − q(λi (k)1))

where the last inequality is due to Jensen’s inequality and
the double stochasticity of A, i.e.,
kv(k + 1) − λ̄(k)k1 ≤ kλ(k) − λ̄(k)k1 .

(22)

Sum up both sides of (21) from k = 0, . . . , K for some
K ≥ 0, and use (18) we have

(20)

where the last inequality is due to (10), the convexity of each

K
X

α2 (k)

k=0

(18)

i∈V

i∈V

≤ kv(k + 1) − λ∗ k22 + nC 2 α2 (k)

≤ kλ(0) − λ∗ k22 + nC 2

We now ready to show that the distributed Lagrangian
method converges√ to the optimal value at a rate
O(n ln(k)/(1−σ2 ) k) on the dual function value estimated
at the time-weighted average of any dual estimate. The
following Theorem adopted from [18], is to show this result.
Theorem 2 ( [18]): Let Assumptions 1–4 hold. Let
{xi (k)} and {λi (k)}
√ for all i ∈ V be generated by Algorithm
1. Let α(k) = 1/ k for k ≥ 1 and α(0) = 1. Then we have
for all i = 1, . . . , n, and K ≥ 1
 PK

α(k)λi (k)
k=0
PK
q
1
− q(λ∗ )
k=0 α(k)
√
4 nCkλ(0)k1 + 5nC 2 (2 + ln(K))
kλ(0)−λ∗ k22
√
√
+
·
≤
4 K
4(1 − σ2 ) K
(19)
Proof: Let λ∗ be a dual optimal of (4). By (6) and (8)
we have for all λ ∈ R,
X
(λi (k + 1) − λ∗ )2
=

+ 2α(k)(q(λ∗ ) − q(λi (k)1))


+ 2α(k) q(λi (k)1) − q(λ̄(k)) + q(λ̄(k)) − q(v(k + 1))

kλ(K + 1) − λ∗ k22

K
X
α(k)|λi (k) − λ̄(k)|

√

≤ kv(k + 1) − λ∗ k22 + nC 2 α2 (k)

≤ kλ(k) − λ∗ k22 + nC 2 α2 (k) + 2α(k)(q(λ∗ ) − q(λi (k)1))
√
+ 2Cα(k)( n|λi (k) − λ̄(k)| + kλ̄(k) − λ(k)k1 ),
(21)

t=0

k=0

kλ(k + 1) − λ∗ k22

+ 2Cα(k)(kλi (k)1 − λ̄(k)k1 + kλ̄(k) − v(k + 1)k1 )

|λi (k) − λ̄(k)|
≤ σ2k kλ(0)k1 +

qi . By (10) and for some i ∈ V the preceding relation implies

+2

K
X

α(k)(q(λ∗ ) − q(λi (k)1))

k=0
K
X

+ 2C

√
α(k)( n|λi (k) − λ̄(k)| + kλ̄(k) − λ(k)k1 )

k=0

≤ kλ(0) − λ∗ k22 + nC 2

K
X

α2 (k)

k=0

+2

K
X

α(k)(q(λ∗ ) − q(λi (k)1))

k=0
√
4 nCkλ(0)k1
4nC 2 (2 + ln(K))
+
+
.
1 − σ2
1 − σ2

PK
Dividing both sides of the previous equation by 2 k=0 α(k)
and rearranging the terms we obtain
PK
k=0 α(k)q(λi (k)1)
− q(λ∗ )
PK
α(k)
k=0
PK
kλ(0) − λ∗ k22 + nC 2 k=0 α2 (k)
≤
PK
2 k=0 α(k)
√
2 nCkλ(0)k1 + 2nC 2 (2 + ln(K))
+
.
(23)
PK
(1 − σ2 ) k=0 α(k)
√
Since α(k) = 1/ k with α(0) = 1, we have
Z K
K
K
X
X
1
dk
2
α (k) = 2 +
≤2+
= 2 + ln(K).
k
ln(k)
1
k=0
k=2
Z K
K
K
X
X
√
1
dk
√ ≥
√ =2 K
α(k) =
k
k
0
k=0
k=0

TABLE I
G ENERATOR PARAMETERS (MU= M ONETARY UNITS )
Gen.
1
2
3
4
5

Bus
1
2
3
6
8

γi [M U/M W 2 ]
0.04
0.03
0.035
0.03
0.04

βi [M U/M W ]
2.0
3.0
4.0
4.0
2.5

Pimax [M W ]
80
90
70
70
80

power allo cation Pi′ s (M W)

Distributed Lagrangian Method
80

P1
P2

60

P3
P4

40

P5

20

0

0

10

20

30

40

50
iteration

60

70

80

90

100

Fig. 1.

IEEE 14 bus systems.

Substituting these two preceding relations into (23) and using
Jensen’s inequality for the left hand side we obtain
 PK

α(k)λi (k)
k=0
PK
q
1
− q(λ∗ )
α(k)

power allo cation Pi′ s (M W)

Consensus + Innovation Method [13]
80

P1
P2

60

P3
P4

40

P5

20

0

0

10

20

30

40

50
iteration

60

70

80

90

100

k=0

which concludes our proof.
V. P OWER A PPLICATION S TUDIES
Our main motivations for the studies in this paper are for
use in power systems applications [12], [25]. In this section,
we show the effectiveness of the Lagrangian distributed
method by applying it to the economic dispatch problem,
wherein geographically distributed generators of electricity
must coordinate to meet fixed demand. We first apply the
method to the IEEE-14 bus test system [2] and compare
the performance of our method with that in [15]. Then to
illustrate its performance on a larger scale system, we study
economic dispatch on the IEEE-118 bus test system [1].
Simulation results are given to demonstrate that our method
works very well in both systems.
A. Case study 1: Economic dispatch on IEEE-14 bus systems
We first study the economic dispatch problem on IEEE-14
bus systems, where generators are located at buses 1, 2, 3, 6,
and 8 as shown in Fig. 1. Each generator i suffers a quadratic
cost as a function of the amount of its generated power Pi ,
i.e., fi (Pi ) = γi Pi2 + βi Pi where γi , βi are cost coefficients
of generator i. We also assume that each generator i can only
generate a limited amount of power represented by [0, Pimax ].

Distributed Lagrangian Method
Lagrange m ultipliers λ′i s

8

λ

1

λ2

6

λ3
λ4

4

λ5

2

0

0

10

20

30

40

50
iteration

60

70

80

90

100

Consensus + Innovation Method [13]
8
Lagrange m ultipliers λ′i s

kλ(0) − λ∗ k22 + nC 2 (2 + ln(K))
√
≤
4 K
√
2 nCkλ(0)k1 + 2nC 2 (2 + ln(K))
√
+
2(1 − σ2 ) K
√
kλ(0) − λ∗ k22
nCkλ(0)k1
√
√
≤
+
4 K
(1 − σ2 ) K
5nC 2 (2 + ln(K))
√
,
+
4(1 − σ2 ) K

λ1
λ2

6

λ3
λ4

4

λ5

2

0

0

Fig. 2.

10

20

30

40

50
iteration

60

70

80

90

100

Economic dispatch problem on IEEE-14 bus systems.

The coefficients of each generator are listed in Table I which
are adopted from [15]. The total load demand required from
the system is P = 300M W , which is a typical load value
chosen for the purpose of this simulation. The goal now is
to meet the load demand while minimizing the total cost
incurred at the generators. Here we assume the connection
between generators is represented by an undirected circle
graph.
Since the local function at each generator is quadratic, the
updates in the DLM algorithm can be simplified as
i
h P
− j∈N aij λj (k)
βi
i
xi (k + 1) = P[0,Pimax ]
−
2γi
2γi
X
λi (k + 1) =
aij λj (k) − α(k)(xi (k + 1) − bi ),
j∈Ni

where P[0,Pimax ] [x] is the projection of x on to the interval
[0, Pimax ].

VI. C ONCLUDING R EMARKS

power a llo ca tio n Pi′ s (M W)

Power allocation at generators
500
400
300
200
100
0

0

100

200

300
iteration

400

500

600

500

600

Consensus of Lagrange multipliers
La gra ng e m ultipliers λ′i s

40
30
20
10
0
−10

0

Fig. 3.

100

200

300
iteration

400

Economic dispatch problem on IEEE-118 bus systems.

In this study, we compare the performance of our DLM
algorithm with the consensus + innovation method (CIM)
studied in [15]. We select the same step size as that used in
[15], i.e., α(k) = 0.08/k 0.85 , which also satisfies the conditions in Lemma 1. The simulations of these two methods
when solving the economic dispatch problem on the IEEE14 bus test system are shown in Figure 2. In each figure, our
method is shown on the top plot while the CIM algorithm
of [15] is shown in the bottom. The plots show that in this
study DLM outperforms CIM. In particular, DLM schedules
the power to the generators after 20 iterations while CMI
requires 40 iterations. Moreover, the Lagrange multipliers
λi in DLM converge after 60 iterations, while those in CIM
have not converged even after 100 iterations.

B. Case study 2: Economic dispatch on IEEE-118 bus systems
We now consider the economic dispatch problem on
a larger system, the IEEE-118 bus test system [1]. This
system has 54 generators connected by bus lines. Each
generator i suffers a quadratic cost as a function of the
amount of its generated power Pi , i.e., fi (Pi ) = µi +
βi Pi + γi Pi2 . The coefficients of functions fi belong to
the ranges µi ∈ [6.78, 74.33], βi ∈ [8.3391, 37.6968],
and γi ∈ [0.0024, 0.0697]. The units of µi , βi , γi are
M Btu, M Btu/M W and M Btu/M W 2 , respectively. Each
Pi is constrained on some interval [Pimin , Pimax ] where these
values vary as Pimin ∈ [5, 150] and Pimax ∈ [150, 400]. The
unit of power in this system is M W . The total load demand
required from the system is P = 6000(M W ), which again
is a typical load demand chosen for the purpose of this
simulation. In this study we select the step size α(k) = 1/k
for k ≥ 1 with α(0) = 1. Moreover, the connections between
generators are based on the physical connections given by
bus data [1]. The simulation results are given in Figure 3
which demonstrate the convergence of our method for this
system.

In this paper, we have proposed a distributed Lagrangian
method for network resource allocation problems. Under a
minimal assumption on the convexity of the nodes’ functions,
we show that our method achieves asymptotic convergence
√
to the optimal value with the rate, O(n ln(k)/(1 − σ2 ) k).
Finally, to show the effectiveness of our method, we applied
our method to solve the economic dispatch problem on the
benchmark IEEE-14 and IEEE-118 bus test systems.
Our main motivation comes from applications in power
systems, where our method provides a useful tool for determining near optimal power allocation in a distributed
power system. One direction following this work is to couple
our method with other control tasks in power systems, for
example, frequency control problems [11], [25]. A second
interesting open direction is to consider the case of unknown
or time-varying resources as is typically found in actual
power systems where the demand is changing over time and
the relevant data may be uncertain.
ACKNOWLEDGEMENT
The authors would like to thank Alex Olshevsky, Rafal
Goebel, and Daniel Liberzon for their insightful comments
which helped to improve the quality of this paper.
R EFERENCES
[1] IEEE 118 bus system [online]. http://motor.ece.iit.edu/
data/JEAS_IEEE118.doc.
[2] IEEE 14 bus system [online]. http://icseg.iti.illinois.
edu/ieee-14-bus-system/.
[3] D. Bertsekas. Nonlinear Programming: 2nd Edition. Cambridge, MA:
Athena Scientific, 1999.
[4] D. Bertsekas, A. Nedić, and A. Ozdaglar. Convex Analysis and
Optimization. Cambridge, MA: Athena Scientific, 2004.
[5] G. Binetti, A. Davoudi, F.L. Lewis, D. Naso, and B. Turchiano. Distributed consensus-based economic dispatch with transmission losses.
IEEE Transactions on Power Systems, 29(4):1711–1720, June 2014.
[6] A. Cherukuri and J. Cortes. Distributed generator coordination for
initialization and anytime optimization in economic dispatch. IEEE
Transactions on Control of Network Systems, 2(3):226 – 237, Sept.
2015.
[7] J. Cortes, S. Martinez, T. Karatas, and F. Bullo. Coverage control for
mobile sensing networks. IEEE Transactions on Automatic Control,
20(2):243 – 255, 2004.
[8] T. T. Doan and C. L. Beck. Distributed Lagrangian Methods for
Network Resource Allocation. To appear in 1st IEEE Conference
on Control Technology and Applications, 2017.
[9] T. T. Doan and A. Olshevsky. Distributed Resource Allocation on
Dynamic Networks in Quadratic Time. Systems & Control Letters,
99:5763, January 2017.
[10] A. Domı́nguez-Garcı́a, S.T. Cady, and C.N. Hadjicostis. Decentralized
optimal dispatch of distributed energy resources. In 51st IEEE
Conference on Decision and Control, pages 3688–3693, 2012.
[11] F. Dörfler and S. Grammatico. Amidst centralized and distributed
frequency control in power systems. In IEEE American Control
Conference (ACC), Boston, USA, July 2016.
[12] F. Dörfler, J.W. Simpson-Porco, and F. Bullo. Breaking the hierarchy:
Distributed control and economic optimality in microgrids. IEEE
Transactions on Automatic Control, 3(3):241 – 253, Sept. 2016.
[13] Y. C. Ho, L. D. Servi, and R. Suri. A class of center-free resource
allocation algorithms. Large Scale Systems, 1:51–62, 1980.
[14] R.A. Horn and C.R. Johnson. Matrix Analysis. Cambridge, U.K.:
Cambridge Univ. Press, 1985.
[15] Soummya Kar and Gabriela Hug. Distributed robust economic
dispatch in power systems: A consensus + innovations approach. In
2012 IEEE Power and Energy Society General Meeting, pages 1–8,
2012.

[16] H. Lakshmanan and D.P. de Farias. Decentralized resource allocation
in dynamic networks of agents. SIAM Journal on Optimization,
19(2):911–940, 2008.
[17] I. Necoara. Random coordinate descent algorithms for multi-agent
convex optimization over networks. IEEE Trans. on Automatic
Control, 58(8):2001–2012, 2013.
[18] A. Nedić and A. Olshevsky. Distributed optimization over timevarying directed graphs. IEEE Transactions on Automatic Control,
60(3):601–615, 2015.
[19] A. Nedić and A. Ozdaglar. Distributed subgradient methods for
multi-agent optimization. IEEE Transactions on Automatic Control,
54(1):48–61, 2009.
[20] P. Sharma, S. M. Salapaka, and C. L. Beck. Entropy-based framework
for dynamic coverage and clustering problems. IEEE Transactions on
Automatic Control, 57(1):135–150, Jan 2012.
[21] Rayadurgam Srikant. The Mathematics of Internet Congestion Control.
Birkhauser, 2004.
[22] L. Xiao and S. Boyd. Optimal scaling of a gradient method for
distributed resource allocation. J. of Optimization Theory and Appl.,
129(3):469–488, 2006.
[23] H. Xing, Y. Mou, M. Fu, and Z. Lin. Distributed bisection method for
economic power dispatch in smart grid. IEEE Transactions on Power
Systems, 30(6):3024–3035, Aug. 2015.
[24] S. Yang, S. Tan, and J.-X. Xu. Consensus based approach for economic
dispatch problem in a smart grid. IEEE Transactions on Power
Systems, 28(4):4416–4426, Oct. 2013.
[25] C. Zhao, U. Topcu, N. Li, and S.H. Low. Design and stability of loadside primary frequency control in power systems. IEEE Transactions
on Automatic Control, 59(5):1177–1189, April 2014.

