On the Lie bracket approximation approach to distributed
optimization: Extensions and limitations ∗

arXiv:1802.10519v1 [math.OC] 28 Feb 2018

Simon Michalowsky1 , Bahman Gharesifard2 , and Christian Ebenbauer1
1 Institute

for Systems Theory and Automatic Control, University of Stuttgart, Germany
{michalowsky,ce}@ist.uni-stuttgart.de
2 Department of Mathematics and Statistics, Queen’s University, Canada
bahman@mast.queensu.ca

to relax these assumptions.
In the present work we want to extend these results
and show that the approach can be applied to a large
class of optimization problems under mild assumptions
on the communication network. While in [11], [12], [13]
only optimization problems with linear constraints and
objective functions in the form of a sum of separable functions were considered, in the present work we enhance
the methodology to general convex optimization problems. The main idea of the approach is to use Lie bracket
approximation techniques to find distributed approximations of non-distributed saddle-point dynamics. While in
the previous works only certain Lie bracket approximations were used, we further show here that a whole class
is applicable.

Abstract. We consider the problem of solving a smooth
convex optimization problem with equality and inequality constraints in a distributed fashion. Assuming that
we have a group of agents available capable of communicating over a communication network described by
a time-invariant directed graph, we derive distributed
continuous-time agent dynamics that ensure convergence
to a neighborhood of the optimal solution of the optimization problem. Following the ideas introduced in our
previous work, we combine saddle-point dynamics with
Lie bracket approximation techniques. While the methodology was previously limited to linear constraints and
objective functions given by a sum of strictly convex separable functions, we extend these result here and show that
it applies to a very general class of optimization problems
under mild assumptions on the communication topology.

1 INTRODUCTION

2 PRELIMINARIES

Over the last decades, distributed optimization has been
an active area of research with high practical relevance,
see, e.g., [2, 3, 4] for applications. In these type of problems, the goal is to cooperatively solve an optimization
problem using a group of agents communicating over a
network. While discrete-time algorithms for distributed
optimization constitute the majority in the existing literature, we focus on continuous-time algorithms which have
regained interest in the last decades, [5, 6, 7, 8, 9, 10]. These
algorithms require strong assumptions either on the structure of the optimization problem or on the communication
network. Recently, a novel approach to continuous-time
distributed optimization based on Lie bracket approximations has been proposed in [11], [12] that has the potential
*

2.1 Notation
We denote by Rn the set of n-dimensional real vectors and
further write C p , p ∈ N, for the set of p-times continuously
differentiable real-valued functions. The gradient of a
function f : Rn → R, f ∈ C 1 , with respect to its argument
x ∈ Rn , will be denoted by ∇ x f : Rn → Rn ; we often omit
the subscript, if it is clear from the context. We denote the
(i, j)th entry of a matrix A ∈ Rn×m by aij , and sometimes
denote A by A = [ aij ]. We use ei to denote the vector with
the ith entry equal to 1 and all other entries equal to 0. We
do not specify the dimension of ei but expect it to be clear
from the context. For a vector λ ∈ Rn we let diag(λ) ∈
Rn×n denote the diagonal matrix whose diagonal entries
are the entries of λ. Given two continuously differentiable
vector fields f 1 : Rn → Rn and f 2 : Rn → Rn , the Lie

This article is an extended version of [1] additionally including proofs
for all results, a discussion of the choice of vector fields after Remark 1
and the overview in Table 1.

1

bracket of f 1 and f 2 evaluated at x is defined to be

[ f 1 , f 2 ]( x ) :=

∂ f2
∂f
( x ) f 1 ( x ) − 1 ( x ) f 2 ( x ).
∂x
∂x

set of (4) is non-empty and that the problem has a unique
solution.
Our goal is to design continuous-time optimization algorithms that converge to an arbitrarily small neighborhood of the unique global optimizer of (4) and that can be
implemented in a distributed fashion. More precisely, we
assume that we have a group of n agents available, each capable of interchanging information over a communication
network described by a directed graph G = (V , E ) with
graph Laplacian G = [ gij ], where V = {v1 , v2 , . . . , vn } is
a set of n nodes and E ⊆ V × V is the edge set between
the nodes. In the present setup, each node vi represents
an agent and the edges define the existing communication links between the agents, i.e., if there is an edge from
node i to node j then agent i has access to the information
provided by agent j. We then say that an algorithm is
distributed if each agent only uses its own information as
well as that provided by its out-neighboring agents.
Let L : Rn × Rneq × Rnineq → R, neq = ∑i∈Ieq neq i ,
nineq = ∑i∈Iineq nineq i , denote the Lagrangian associated
to (4), i.e.,

(1)

With a slight abuse of notation we sometimes also write
[ f 1 ( x ), f 2 ( x )]. For a vector x = [ x1 , x2 , . . . , xn ]> ∈ Rn and
a finite set S ⊆ {1, 2, . . . , n}, we denote by xS ∈ R|S| the
ordered stacked vector of all xi with i ∈ S . For example, if
n = 5 and S = {2, 4}, then xS = [ x2 , x4 ]> .

2.2 Basics on graph theory
We recall some basic notions on graph theory, and refer
the reader to [14] or other standard references for more
information. A directed graph (or simply digraph) is an
ordered pair G = (V , E ), where V = {v1 , v2 , . . . , vn } is
the set of nodes and E ⊆ V × V is the set of edges, i.e.
(vi , v j ) ∈ E if there is an edge from node vi to v j . In our
setup the edges encode to which other agents some agent
has access to, i.e. (vi , v j ) ∈ E means that node vi receives
information from node v j . We say that node v j is an outneighbor of node vi if there is an edge from node vi to node
v j . The adjacency matrix A = [aij ] ∈ Rn×n associated to
G is defined as
(
1 if i 6= j and (vi , v j ) ∈ E ,
(2)
aij =
0 otherwise.

L( x, ν, λ) = F ( x ) + ν> a( x ) + λ> c( x ),

where a = [ ai ]i∈Ieq , c = [ci ]i∈Iineq are the stacked vectors of
all ai and ci , respectively, and ν ∈ Rneq , λ ∈ Rnineq are the
associated Lagrange multipliers. In the sequel, we assume
that the state of the ith agent comprises of xi as well as
the dual variables associated to the constraints ai , ci , given
they exist. Without loss of generality we then put the
following assumption on the indexing of the constraints:

We also define the out-degree matrix D = [dij ] associated
to G as
(
if i = j
∑nk=1 aik
dij =
(3)
0
otherwise.

Assumption 1. For any i ∈ Ieq and any j ∈ Iineq , there
exists an x = [ x1 , x2 , . . . , xn ]> ∈ Rn such that
and

Finally, we call G = D − A = [ gij ] ∈ Rn×n the Laplacian of
G . A directed path in G is a sequence of nodes connected
by edges and we write pi1 ir = hvi1 |vi2 | . . . |vir i for a path
from node vi1 to node vir . We say that a path is simple if
the sequence contains no node more than once.

i ∈ Ieq ⊆ {1, 2, . . . , n},

ci ( x ) ≤ 0,

i ∈ Iineq ⊆ {1, 2, . . . , n},

(6)

The following saddle-point dynamics adapted from [15]
is known to converge to a saddle point of the Lagrangian
(see [13] for a proof), thus providing a solution to (4)

F(x)
ai ( x ) = 0,

6= 0

6= 0.

L( x ? , ν, λ) ≤ L( x ? , ν? , λ? ) ≤ L( x, ν? , λ? ).

Consider the following convex optimization problem

s.t.

∂c j
∂x j ( x )

∂ai
∂xi ( x )

In a nutshell, this assumption Newguarantees that the
ith constraints ai , ci are both functions of xi .
It is well-known that if the Lagrangian has Newa saddle
point ( x ? , ν? , λ? ), then x ? is an optimizer of (4). We say
that a point ( x ? , ν? , λ? ) is a saddle point if for all x ∈ Rn ,
nineq
ν ∈ Rneq , λ ∈ R+ , we have

3 PROBLEM SETUP
min

(5)

ẋ = −∇ x L( x, ν, λ)

(4)

= −∇ F ( x ) −

>
>
∂a
∂c
∂x ( x ) ν − ∂x ( x ) λ

(7a)

ν̇ = ∇ν L( x, ν, λ)

where F : Rn → R, ai : Rn → Rneq i , ci : Rn → Rnineq i ,
neq i , nineq i ≥ 1, F ∈ C 2 is strictly convex, the functions
ai , i ∈ Ieq , are affine and the ci ∈ C 2 , i ∈ Iineq , are convex.
We assume further that F, ai , ci are such that the feasible

= a( x )

(7b)

λ̇ = diag(λ)∇λ L( x, ν, λ)

= diag(λ)c( x ).

2

(7c)

notation, for each i = 1, 2, . . . , n, we define the index set

However, (7) is in general not distributed in the aforementioned sense, since the right-hand side of (7) is not
composed only of admissible vector fields, i.e., vector fields
that can be computed locally by the nodes. For example,
if g12 6= 0 and g13 = 0, then the vector field [ e1> x2 , 0, 0]> is
admissible for (7), while [ e1> x3 , 0, 0]> is not.
Recently, a novel approach to distributed optimization
has been proposed that employs Lie bracket approximation techniques to derive distributed approximations
of (7). The idea is to write the right-hand side of (7) by
means of Lie brackets of admissible vector fields. If we
have achieved to rewrite (7) in this form, i.e., we have
ż =

∑

v B B ( z ),

i −1

Ī(i ) := {i } ∪ { j = n +

∑ neq k + `, ` = 1, 2, . . . , neq i }

k =1
i −1

∪ { j = n + neq +

∑ nineq k + `, ` = 1, 2, . . . , nineq i }

(11)

k =1

associating the components of the complete state z to the
ith agent meaning that z j is part of the state of agent i for
all j ∈ Ī(i ). Hence, the state vector of the ith agent is given
by zĪ(i) . Based on this, for all j = 1, 2, . . . , N, we define

I( j) = Ī(i )

(8)

B∈B

(12)

for some i such that j ∈ Ī(i ), i.e., I( j) is the set of all
indices which are associated to the same agent as the jth
index. Note that Ī( j) = I( j), for all j = 1, 2, . . . , n.

[ x > , ν> , λ> ]> ,

where z =
v B ∈ R and B is a set of
Lie brackets of admissible vector fields {φ1 , φ2 , . . . , φ M },
φi : Rn+neq +nineq → Rn+neq +nineq , then we can employ Lie
bracket approximation techniques from [16], [17] to derive
distributed approximations of (8). More precisely, we can
find a family of functions uiσ : R → R parametrized by
σ > 0 such that the trajectories of

4.1 Lie brackets of admissible vector fields
In the following, we first want to discuss which kind of
vector fields can be written in terms of Lie brackets of
admissible vector fields. For i, j = 1, 2, . . . , N, define

M

żσ =

∑ φi (z)uiσ (t)

hi,j (z) = e j f j (zI( j) , zI(i) ),

(9)

(13)

i =1

where f j : R|I( j)| × R|I(i)| → R, f j ∈ C 1 . Observe that hi,j
is admissible if and only if there exist `, k ∈ {1, 2, . . . , n}
such that i ∈ I(`), j ∈ I(k) and gk` 6= 0. In the next
Newresult we consider Lie brackets of admissible vector
fields of the form (13).

uniformly converge to those of (8) as σ increases, given (8)
and (9) are initialized equally. A general algorithm to
compute suitable functions uiσ is presented in [16] and
we will present a modified version thereof tailored to the
problem at hand in [13]. In the present paper we do not
discuss the second step of how to design these functions
uiσ but focus on rewriting the right-hand side of (7) in
terms of Lie brackets of admissible vector fields.

Lemma 1. Consider a graph G of n nodes and let
pi1 ir = hvi1 |vi2 | . . . |vir i denote a simple path in G from
vi1 to vir . Then, for any jk ∈ I(ik ), k = 1, 2, . . . , r, we have


4 MAIN RESULTS

r −2 ∂ f
jk
∂z j
k +1
k =1

= e j1 f jr−1 (zI( jr−1 ) , zI( jr ) ) ∏

Consider the saddle-point dynamics (7) and observe
that the right-hand side is a sum of vector fields of the
form ei ψ( x ) and ei z j ψ( x ), i, j = 1, 2, . . . , n + neq + nineq ,
ψ : Rn → R, where
z = [ x > , ν> , λ> ]> ∈ R N ,

N = n + neq + nineq ,


h

i
h jr ,jr−1 , h jr−1 ,jr−2 , . . . , [h j3 ,j2 , h j2 ,j1 ] . . .
(z)

(14)

(zI( jk ) , zI( jk+1 ) )

and the left-hand side is a Lie bracket of admissible vector
fields.
•
A proof is given in Section 7.1. By the above Lemma,
each non-admissible vector field that takes the same form
as the right-hand side of (14) can be written in terms of a
Lie bracket of admissible vector fields. It is worth mentioning that this does not classify the whole set of vector fields
that can be written as a Lie bracket of admissible vector
fields since we limited ourselves to a single path. We next
discuss a special case that is of particular importance for
the application at hand.

(10)

is the complete state and ei ∈ R N is the ith unit vector. These vector fields might either be admissible or not,
depending on the communication graph as well as the
problem structure. In the following, we wish to discuss
how to write vector fields of this form by means of Lie
brackets of admissible vector fields. For the purpose of

3

Proposition 1. Consider a graph G of n nodes and let pi1 ir =
hvi1 |vi2 | . . . |vir i denote a simple path in G from vi1 to vir . Let
jk ∈ I(ik ), k = 1, 2, . . . , r, be any set of indices and suppose
that
(1)

(2)

k

k

f jk (zI( jk ) , zI( jk+1 ) ) = f j (zI( jk ) ) f j (zI( jk+1 ) )

for k = 2, . . . , r − 1; hence

(1)
k

(2)
k −1
∂z j
k

∂ fj

(zI( jk ) ) = 1

(15)

|

=

(2)

f j (zI( jk+1 ) ) = z jk+1 ,
k

(17)

k = 2, 3, . . . , r − 1,

(18a)

k = 1, 2, . . . , r − 2;

(18b)

As we see from the proof, each bounded vector field
in (17) leads to another unbounded vector field. Hence,
at most half of the vector fields h jk ,jk−1 in (17) can be
bounded. In particular, we can choose the functions f jk ,
k = 1, 2, . . . , r − 1, as follows to guarantee that (16) holds:
(
(1)
f j (x)
k

1



1
cos(α( x −d))

if k is even,
if k is odd, k 6= 1,


sin α( x − d) if k is even, k 6= r − 1,
∫ cos(α(1x−d)) dx if k is odd, k 6= r − 1,

(21a)
(21b)

Example 1. Consider the graph shown in Fig. 1 and assume for the sake of simplicity that I( j) = j for j = 1, . . . , 5
and z ∈ R5 . By (14) we can write non-admissible vector
fields of the form e1 ϕ1 (z2 ) ϕ2 (z3 ) as well as e1 ϕ3 (z4 ) ϕ4 (z5 )
and sums thereof in terms of Lie brackets of admissible
vector fields as long as ϕ1 , ϕ3 admit an analytic expression
of their antiderivatives ∫ ϕ1 (z2 )dz2 , ∫ ϕ3 (z4 )dz4 . In fact,
with

(1)

(1)
(zI( j ) )
k
k

=

cos(α x − d)

where α 6= 0, d ∈ R. However, this choice will lead to
functions f jk that are not globally continuous but only
π
π
); hence we
well-defined in the interval (d − 2α
, d + 2α
need to choose d appropriately and α sufficiently small.
By that choice, all functions f jk with even k are bounded
while all functions f jk with odd k are unbounded.
We next discuss how we can make use of the previous results to rewrite more general vector fields. While
Lemma 1 enables us to write products of functions of variables of nodes which lie on the same path as Lie brackets
of admissible vector fields, we cannot directly use this result to rewrite functions which do not fulfill this property.
To make this clearer, consider the following example:

all k = 1, 2, . . . , r. By (15), f j is also bounded for all
k
k = 1, 2, . . . , r since I( jk ) and I( jk+1 ) are disjunct. However, by (16),

fj

=
(

(2)
f j (x)
k

Proof. Suppose there exists a set of bounded vector fields
such that (17) holds. Then f jk is a bounded function for

(zI( jk ) ) =

∈ C 1.

Remark 1. The same holds true if we do not assume the
structure (15). In fact, the structure is required for all other
variables except of zI( j1 ) , zI( jr ) to cancel out in (17).
•

Lemma 2. Suppose that all assumptions from Proposition 1 are fulfilled. Then there exists no set of bounded
vector fields h jk ,jk−1 ∈ C 1 such that (17) holds.
•

(2)
k −1
∂z j
k

k −1

(2)

hence leading to h jk+1 ,jk (zI( jk ) , zI( jk+1 ) ) = e jk z jk+1 . However, in view of (9) where the φi are given by admissible
vector fields of the form (13), it is often desired that the
admissible vector fields have certain properties such as
boundedness in order to simplify the calculation of the approximating inputs uiσ and improve the transient behavior
of (9). However, as we see next, it is not possible to render
all vector fields bounded.

∂ fj

(2)

, fj

Thus, f j is strictly monotone in z jk which contradicts the
k −1
boundedness assumption, thus concluding the proof.

A proof is given in Section 7.2. In view of (14), the
constraint (16) ensures that all terms depending on zI( jk ) ,
k = 2, 3, . . . , r − 1, cancel out. Equation (17) is of particular
interest since the non-admissible vector fields often take
the form as its right-hand side. According to (16), there
exists a whole class of vector fields h jk ,jk−1 , or equivalently,
functions f jk , such that (17) holds. A particularly simple
choice that has been utilized in the previous works [11],
[12] is to take
k

(20)

k −1

for all z ∈ R N and the left-hand side is a Lie bracket of admissible vector fields.
•

(1)

(zI( jk ) )| ≥ β.
(1)

(1)
(2)
e j1 f j (zI( j1 ) ) f j (zI( jr ) )
1
r −1

f j (zI( jk ) ) = 1,

(2)
k −1
∂z j
k

∂ fj

Note that h jk ,jk−1 ∈ C 1 if and only if f j

(16)

R|I( jk )| ,

for all zI( jk ) ∈
k = 2, 3, . . . , r − 1. Then


h

i
(z)
h jr ,jr−1 , h jr−1 ,jr−2 , . . . , [h j3 ,j2 , h j2 ,j1 ] . . .

is bounded away from

zero, i.e., there exists some constant β > 0 such that for all
zI( jk ) ∈ R|I( jk )| we have

with
f j (zI( jk ) )

(2)
k −1
∂z j
k

∂ fj

(19)

4

h2,1 (z) = e1 ∫ ϕ1 (z2 )dz2 ,

h3,2 (z) = e2 ϕ2 (z3 ),

(22a)

h4,3 (z) = e1 ∫ ϕ3 (z4 )dz4 ,

h5,4 (z) = e4 ϕ4 (z5 ),

(22b)

z2

z3

2

3

and observe that for all z ∈ R N we have

[ψ2 , ψ1 ](z) = e1 ϕ2 (z3 ) ϕ4 (z5 ).

z1 1

(27)

Further, following Proposition 1 and choosing
5
z5

4
z4

h2,1 (z) = e1 z1 ,

h3,2 (z) = e2 ϕ2 (z3 ),

(28a)

h4,3 (z) = e1 ,

h5,4 (z) = e4 ϕ4 (z5 ),

(28b)

we have for all z ∈ R N

Figure 1. The graph considered in Example 1 where the ith agent
has an associated state zi .

ψ1 (z) = [h3,2 , h2,1 ](z),

ψ2 (z) = [h5,4 , h4,3 ](z).

(29)

Using this in (27) we finally managed to rewrite
e1 ϕ2 (z3 ) ϕ4 (z5 ) in terms of admissible vector fields.
•

we have for all z ∈ R5
e1 ϕ1 (z2 ) ϕ2 (z3 ) = [h3,2 , h2,1 ](z)

(23a)

e1 ϕ3 (z4 ) ϕ4 (z5 ) = [h5,4 , h3,2 ](z).

(23b)

Remark 2. Instead of realizing the multiplication by
means of Lie brackets another way is to augment the agent
state by estimates of the respective state of the other agent.
More precisely, in Example 1, we augment the state of
agent 1 by ξ 3 and ξ 5 that are estimates of z3 and z5 , respectively, and let
  

ż1
w ( z1 , z2 , z4 , ξ 3 , ξ 5 )
 + e2 z 5 + e3 z 5 ,
ξ̇ 3  = 
−µξ 3
(30)
−µξ 5
ξ̇ 5

However, we cannot directly use (14) to rewrite a nonadmissible vector field of the form e1 ϕ2 (z3 ) ϕ4 (z5 ).
•
In the next result, we wish to overcome this limitation
and show how to not only write sums of the vector fields
in the form of the right-hand side of (14) in terms of Lie
brackets of admissible vector fields, but also products
thereof.

where w : R5 → R and µ > 0 is sufficiently large, hence
ξ 3 (t) ≈ z3 (t), ξ 5 (t) ≈ z5 (t). The resulting non-admissible
vector fields in the complete augmented system can then
be written in terms of Lie brackets of admissible vector
fields using Proposition 1. However, in the application
at hand this alters the saddle-point dynamics (7) which
necessitates a stability analysis of the augmented system.

Proposition 2. Let ηk : R → R, ηk ∈ C 1 , k = 1, 2, . . . , m,
m ≥ 2, and define
ψ1 (z) = ei η1 (z j1 ) ∫ η0 (zi )dzi ,
ψk (z) = ei zi ηk (z jk ),

(24a)

k = 2, . . . , m − 1,

ψm (z) = ei ηm (z jm ),

(24b)
(24c)

i, jk ∈ N, ψk : R N → R N . Then, for any jk 6= i,
k = 1, . . . , m, we have for all z ∈ R N
h

i


. . . [ψm , ψm−1 ], ψm−2 , . . . , ψ1 (z)
m

= ei η0 (zi ) ∏ ηk (z jk ).
k =1

Hence, under suitable assumptions on the communication graph, this allows us to write vector fields whose
components are sums of products of arbitrary functions
in terms of Lie brackets of admissible vector fields. This
observation gives rise to the next Lemma.

(25)

Lemma 3. Consider a strongly connected graph G of n
nodes and let ϕ : R N → R be an analytic function. Then
any vector field ψ(z) = ei ϕ(z), ei ∈ R N , i = 1, 2, . . . , N,
can be written as a possibly infinite sum of Lie brackets of
admissible vector fields.
•

•

A proof is given in Section 7.3. The vector fields ψk
defined by (24) are in general non-admissible; thus, the
left-hand side of (25) is not a Lie bracket of admissible
vector fields. However, observing that the vector fields
ψk take the same form as the right-hand side of (17), we
can make use of Proposition 1 to write the left-hand side
of (25) as a Lie bracket of admissible vector fields as long
as, for any k ∈ {1, . . . , m}, there exists a path from the ith
node to the node that is associated to state z jk . We illustrate
that by means of Example 1.

Proof. Since ϕ is analytic, by a series expansion it can be
written as a possibly infinite sum of monomials of the
components z j of z, j = 1, 2, . . . , N. Using Proposition 2,
all these monomials can be written in terms of Lie brackets
of vector fields of the form (24). By strong connectivity
of G , all these vector fields can be written in terms of Lie
brackets of admissible vector fields, thus concluding the
proof.

Example 1. [continued] Reconsider Example 1 and suppose we want to rewrite the non-admissible vector field
e1 ϕ2 (z3 ) ϕ4 (z5 ). Following Proposition 2 we let
ψ1 (z) = e1 z1 ϕ2 (z3 ),

ψ2 (z) = e1 ϕ3 (z5 ),

While the result might be more of a theoretical nature
for the application at hand, it nevertheless shows that the
proposed approach in principle applies to a large class of
problems.

(26)

5

Vector field

Admissible if...

(`)

ei

(`)

∂Fi
∂xi

( xi ) ∏ Fj ( x j )
(`)
j∈J F

Rewritable if...

` = 1, 2, . . . , n F
i = 1, 2 . . . , n

gij 6= 0 for all j ∈ J F

∃ pij in G for all j ∈ J F

k ∈ Ieq
i = 1, 2 . . . , n

gik 6= 0 for all k : aki 6= 0

∃ pik in G for all k : aki 6= 0

k ∈ Iineq , ` = 1, 2, . . . , nck
i = 1, 2, . . . , n

gij 6= 0 for all j ∈ Jck

∃ pij in G for all j ∈ Jck

k ∈ Ieq
i = 1, 2 . . . , n

Assumption 2 holds

∃ pki in G for all aki 6= 0

k ∈ Iineq
` = 1, 2, . . . , nck

Assumption 2 holds

∃ pkj in G for all j ∈ Jck

(`)

(`)

j 6 =i

ei āki νk
(`)

ei

∂ck,k
∂xk

(`)

( xk ) ∏ ck,j ( x j )
(`)

j∈Jc
k
j6=k

en+k aki xi
(`)

en+neq +k λk ∏ ck,j ( x j )
(`)
k

j∈Jc

(`)

(`)

(`)

Table 1. An overview of all vector fields appearing in (31).

4.2 Distributed optimization via Lie brackets

functions, i.e.,
nF

F(x) =
In the sequel we apply the results from the last section
to the problem at hand and rewrite the saddle-point dynamics (7) by means of Lie brackets of admissible vector
fields. For the sake of a simpler notation we assume in the
following that neq i = 1 for all i ∈ Ieq and nineq i = 1
for all i ∈ Iineq . We further assume that each agent
has an associated equality and inequality constraint, i.e.,
Ieq = {1, 2, . . . , n}, Iineq = {1, 2, . . . , n}. This can
always be achieved by augmenting the optimization problem (4) by constraints that do not alter the feasible set. We
emphasize that this is not necessary for the methodology
to apply as we will illustrate in the example in Section 5.
We can then write the saddle-point dynamics (7) equivalently as

n

ẋ = − ∑ ei
i =1

ν̇ =

∑

∑

∑ āik νk + ∑

k ∈Ieq


∂ck
∂xk ( x ) λk

`=1

∑ āki xi + b̄k



(32)

(`)

(33)

ck,j ( x j ),

(`)
j∈Jc
k

(`)

(`)

where the Fj
: R → R, j ∈ J F ⊆ {1, 2, . . . , n},
` = 1, 2, . . . , n F , n F > 0, are strictly convex functions
(`)

(`)

and the ck,j : R → R, k ∈ Iineq , j ∈ Jck ⊆ {1, 2, . . . , n},
` = 1, 2, . . . , nci , nck > 0, are convex. Observe that,
(`)

(`)

if n F and nck are infinite and Fj , ck,j are monomials,
(`)

this includes all analytic functions F, ck . If J F

= {`},

(`)
Jck

= {`}, we obtain the particularly important special
case that both the objective function and the constraints
are a sum of separable functions; hence also the case of
linear constraints considered in [11], [12] is covered here.
Under this assumption the vector fields appearing in (31)
are summed up in Table 1. Depending on the communication graph as well as the structure of the constraints
and the objective function, these vector fields can either be
admissible or not. In particular, the vector fields in (31b),
(31c) are admissible if the constraints are compatible with
the communication topology defined by the graph G , i.e.,
if the following assumption holds:

(31a)

k ∈Iineq

(31b)

i =1

e k λ k c k ( x ),

∑ ∏

`=1

(`)

Fj ( x j ),

(`)
j∈J F

nck

ck ( x ) =

n

ek

k ∈Ieq

λ̇ =

∂F
∂xi ( x ) +

∑ ∏

(31c)

k ∈Iineq

Assumption 2. For all i, j = 1, 2, . . . , n with gij = 0 we

where ai ( x ) = āi x + b̄i , āi = [ āi1 , āi2 , . . . , āin ] ∈ R1×n ,
b̄i ∈ R. Motivated by our previous discussions, we assume
in the following that the objective function as well as the
inequality constraints are sums of products of separable

have

∂ai
∂x j ( x )

≡ 0 as well as

∂ci
∂x j ( x )

≡ 0.

•

We point out that all non-admissible vector fields in (31)
can be written in terms of Lie brackets of admissible vector

6

2

1

5

3
4

Figure 2. The communication
graph for the example considered in Section 5.

Vector field

Corresponding path

e5 ν2

p52 = hv5 |v1 |v2 i

e2 x 2 λ 1

p21 = hv2 |v5 |v1 i

e1 λ 3

p13 = hv1 |v2 |v3 i

e4 x 1 λ 4

p41 = hv4 |v5 |v1 i

e1 x 4 λ 4

p14 = hv1 |v2 |v3 |v4 i

e1 x 1 λ 4

p14 = hv1 |v2 |v3 |v4 i

e8 λ 3 x 1

p31 = hv3 |v4 |v5 |v1 i

e9 λ 4 x 4 x 1

p41 = hv4 |v5 |v1 i

e9 λ4 x12

p41 = hv4 |v5 |v1 i

Lie bracket representation


e j z 6 , e5 z j


e j z 7 , e2 z 2 z j


e j λ 3 , e1 z j


e j x 1 , e4 λ 4 z j


e j2 λ4 x4 , [ e j1 z j2 , e1 z j1 ]


e j λ4 , [ e j1 z j2 , e1 x1 z j1 ]
 2

e j2 x1 , [ e j1 z j2 , e8 λ2 z j1 ]


e j x 1 , e9 z j x 4 λ 4 ]
 2

e j x 1 , e9 λ 4 z j

j ∈ I(1)
j ∈ I(5)
j ∈ I(2)
j ∈ I(5)
j1 ∈ I(2), j2 ∈ I(3)
j1 ∈ I(2), j2 ∈ I(3)
j1 ∈ I(4), j2 ∈ I(5)
j ∈ I(5)
j ∈ I(5)

Table 2. An overview of the non-admissible vector fields in (35) and their Lie bracket representations. Here, the index sets are I(1) = {1, 7}, I(2) = {2, 6}, I(3) = {3, 8}, I(4) = {4, 9},
I(5) = {5}.

fields under appropriate assumptions on the communication graph, see also the last column of Table 1. Specifically,
if the graph is strongly connected, then all non-admissible
vector fields can be rewritten independent of the objective
function as well as the constraints, given that they admit
the structure (32), (33). In most cases, however, much less
restrictive requirements on the communication graph are
sufficient. We do not explicitly discuss how to rewrite
the non-admissible vector fields using Proposition 1 and
Proposition 2 in general but illustrate this by means of an
example in Section 5.

point dynamics (7) are then given by
ẋ = − ∇ F ( x ) − (2e2 − e5 )ν2 − 2( x1 e1 + x2 e2 )λ1

(35a)
− (2x4 − x1 ) e4 λ4 − (2x1 − x4 ) e1 λ4 − ( e1 + e3 )λ3
ν̇2 = 2x2 − x5
(35b)
λ̇ = λ1 e1 ( x12 + x22 − 4) + λ3 e2 ( x1 + x3 − 2)

+ λ4 e3 ( x42 − x4 x1 + x12 − 100),

(35c)

where x ∈ R5 , ν2 ∈ R, and λ = [λ1 , λ3 , λ4 ]> ∈ R3 .
We next rewrite all non-admissible vector fields in (35)
using Proposition 1. We will thereby follow the choice (18)
to make sure that (16) holds. We do not discuss how to
rewrite each non-admissible vector field in detail, but limit
ourselves to the vector field e1 x4 λ4 from (35a). Comparing

5 EXAMPLE

(1)

with (17), we have j1 = 1, jr = 4, and f j (zI( j1 ) ) = 1,
1

In this section we illustrate the previous results by means
of an example. Consider the following optimization problem

(2)

f j (zI( jr ) ) = x4 λ4 . Following Proposition 1, we require
r −1
a path from node 1 to node 4 that is here given by p14 =
hv1 |v2 |v3 |v4 i; thus r = 4. We then obtain

5

min

x ∈ R5

s.t.

F(x) =



e1 x4 λ4 = e j2 λ4 x4 , [ e j1 z j2 , e1 z j1 ] ,

∑ Fi (xi )

i =1

a2 ( x ) = 2x2 − x5 = 0
c1 ( x ) = x12 + x22 − 4 ≤ 0

(36)

where j1 ∈ I(2) = {2, 6}, j2 ∈ I(3) = {3, 8}, and the
right-hand side is a Lie bracket of admissible vector fields.
All other non-admissible vector fields in (35) can be treated
similarly and we sum up the resulting Lie brackets in Table 2. For the simulation we let each j, j1 , j2 be the largest
index in its respective index set. By that choice, we inject
less perturbation in the primal and more in the dual variables New which is also visible in the simulation results
depicted in Fig. 3. As to be seen, the distributed algorithm approximates the trajectories of the non-distributed
saddle-point dynamics (35) and converges to a neighborhood of the optimizer x ? = [0, 2, 2, 4, 4]> . NewWe also

(34)

c3 ( x ) = x1 + x3 − 2 ≤ 0
c4 ( x ) = x42 − x4 x1 + x12 − 100 ≤ 0,
where Fi ( xi ) = ( xi − i )2 , x = [ x1 , x2 , x3 , x4 , x5 ]> ∈ R5 .
We assume that the communication topology is described
by the graph in Fig. 2. Observe that the constraints c3
and c4 are not compatible with the graph topology, hence
Assumption 2 is not fulfilled. The corresponding saddle-

7

6

x(t)

bracket approximation approach to distributed optimization proposed in [11], [12] and discussed which kind of
vector fields can in principle be written in terms of Lie
brackets of admissible vector fields. We did not discuss
the construction of approximating inputs but postpone
this to [13] where we will present a modified version of
the general algorithm from [16] that exploits the structure
of the problem at hand.

x1
x2
x3
x4
x5

4
2
0
-2
0

5

10

15

1

References

ν(t)

0

-1

[1]

S. Michalowsky, B. Gharesifard, and C. Ebenbauer,
“On the Lie bracket approximation approach to distributed optimization: Extensions and limitations,”
in 2018 European Control Conference (ECC), accepted,
2018.

[2]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning,
vol. 3, no. 1, pp. 1–122, 2011.

[3]

F. Bullo, J. Cortés, and S. Martínez, Distributed Control
of Robotic Networks, ser. Applied Mathematics Series.
Princeton University Press, 2009.

[4]

J. Zhao and F. Dörfler, “Distributed control and optimization in DC microgrids,” Automatica, vol. 61, no.
Supplement C, pp. 18 – 26, 2015.

[5]

D. Feijer and F. Paganini, “Stability of primal–dual
gradient dynamics and applications to network optimization,” Automatica, vol. 46, no. 12, pp. 1974 – 1981,
2010.

[6]

J. Wang and N. Elia, “A control perspective for centralized and distributed convex optimization,” in
2011 IEEE 50th Conference on Decision and Control
and European Control Conference (CDC-ECC), 2011, pp.
3800–3805.

[7]

H.-B. Dürr, C. Zeng, and C. Ebenbauer, “Saddle point
seeking for convex optimization problems,” IFAC Proceedings Volumes, vol. 46, no. 23, pp. 540–545, 2013.

[8]

B. Gharesifard and J. Cortés, “Distributed
continuous-time convex optimization on weightbalanced digraphs,” IEEE Transactions on Automatic
Control, vol. 59, no. 3, pp. 781–786, 2014.

[9]

S. K. Niederländer and J. Cortés, “Distributed coordination for separable convex optimization with
coupling constraints,” in 2015 54th IEEE Conference
on Decision and Control (CDC), Dec 2015, pp. 694–699.

-2
0

5

10

15

2

λ(t)

1

0

-1
0

5

10

15

time t
Figure 3. Simulation results of the example from Section 5. The
upper plot shows the primal variable x (t), the lower left one
the dual variable ν2 (t) and the lower right one the dual variable λ(t). NewIn each plot, the dotted black lines marked with
squares depict the trajectories of the non-distributed saddlepoint dynamics (35) while the thinner oscillating ones depict the
trajectories of the distributed approximation. The corresponding
thick lines depict the distributed approximation with additional
low-pass filters. The dashed black lines indicate the desired
equilbrium of (35).

included simulation results with additional low-pass filters in the distributed x-, ν- and λ-dynamics. While the
effect on the primal variables is small since we already
reduced the oscillations by our design choice, the dual
variables show significantly less oscillations and better
approximate the non-distributed trajectories. A rigorous
stability analysis of the augmented distributed dynamics
and a performance-oriented design of the filters is up to
future work.

6 CONCLUSIONS AND OUTLOOK
We considered a convex optimization problem and
showed how distributed optimization algorithms can be
designed for a quite general class of problems with little
structural requirements under mild assumptions on the
communication network. We therefore extended the Lie

8

[10] B. Touri and B. Gharesifard, “Saddle-point dynamics for distributed convex optimization on general
directed graphs,” in 2016 IEEE 55th Conference on Decision and Control (CDC), 2016, pp. 862–866.

By the induction hypothesis we then have


h

h jr̄+1 ,jr̄ , h jr̄ ,jr̄−1 , [ . . . , [h j3 ,j2 , h j2 ,j1 ] . . . ]

i

(z)

= [h jr̄+1 ,jr̄ , e j1 f˜jr̄ ,j1 ](z)

[11] C. Ebenbauer, S. Michalowsky, V. Grushkovskaya,
and B. Gharesifard, “Distributed optimization over
directed graphs with the help of Lie brackets,” in Proc.
20th IFAC World Congress, 2017, pp. 15 908–15 913.

N

= e j1 ( ∑

i =1

− e jr̄ (

∂ f˜jr̄ ,j1
∂zi

∑

ei

i ∈I( jr̄ )
∪I( jr̄+1 )

[12] S. Michalowsky, B. Gharesifard, and C. Ebenbauer, “Distributed extremum seeking over directed
graphs,” in 2017 IEEE 56th Conference on Decision and
Control (CDC), 2017, pp. 2095–2101.

= e j1

∂ f˜jr̄ ,j1
∂z jr̄

(z)) e jr̄ f jr̄ (zI( jr̄ ) , zI( jr̄+1 ) )
∂ f jr̄
∂zi

(zI( jr̄ ) , zI( jr̄+1 ) )) e j1 f˜jr̄ ,j1 (z)

(z) f jr̄ (zI( jr̄ ) , zI( jr̄+1 ) ),

(38)

where e ji ∈ Rn+neq +nineq is the ji th unit vector. Here, we
used that pi1 ir̄+1 is a simple path; hence, since I(ik1 ) and
I(ik2 ) are disjunct for any k1 6= k2 , also jk1 6= jk2 for any
k1 , k2 = 1, 2, . . . , r̄ + 1, k1 6= k2 . Using definition (37), we
obtain (14). Finally, since jk ∈ I(ik ) and gik ik+1 6= 0 for
all k = 1, 2, . . . , r − 1, all h jk+1 ,jk are admissible; hence the
left-hand side of (14) is a Lie bracket of admissible vector
fields.

[13] ——, “A Lie bracket approximation approach to distributed optimization over directed graphs,” ArXiv
e-prints arXiv:1711.05486 [math.OC], 2017, https://
arxiv.org/abs/1711.05486.
[14] N. Biggs, Algebraic graph theory. Cambridge university press, 1993.
[15] H.-B. Dürr and C. Ebenbauer, “On a class of smooth
optimization algorithms with applications in control,” IFAC Proceedings Volumes, vol. 45, no. 17, pp.
291 – 298, 2012, 4th IFAC Conference on Nonlinear
Model Predictive Control.

7.2 Proof of Proposition 1
Proof. Observe first that
r −2 ∂ f
jk
∂z j
k +1
k =1

f jr−1 (zI( jr−1 ) , zI( jr ) ) ∏

[16] W. Liu, “An approximation algorithm for nonholonomic systems,” SIAM Journal on Control and Optimization, vol. 35, no. 4, pp. 1328–1365, 1997.

(2)

(zI( jk ) , zI( jk+1 ) )

(1)

= f jr−1 (zI( jr ) ) f jr−1 (zI( jr−1 ) )
r −2

[17] H. J. Sussmann and W. Liu, “Limits of highly oscillatory controls and the approximation of general
paths by admissible trajectories,” in 1991 IEEE 30th
Conference on Decision and Control (CDC), 1991, pp.
437–442.

r − 1 ∂ f (2)
j

× ∏ f j (zI( jk ) ) ∏
k =1

=

(1)
k

(1)
(2)
f j (zI( jr ) ) f j (zI( j1 ) )
r −1
1

k =2

r −1

∏

k =1

k −1

∂z j

k

(zI( jk ) )
(2)

∂ fj
(1)
f j (zI( jk ) ) ∂zk−1 (zI( jk ) ).
j
k
k

Then, using (16) and applying Lemma 1, the result immediately follows.

7 APPENDIX
7.1 Proof of Lemma 1

7.3 Proof of Proposition 2

Proof. We prove this result by induction. First, for r = 1,
(14) is trivially true by definition (13). Suppose now that
the claim holds for all r ≤ r̄, r̄ > 1 and consider r = r̄ + 1.
Define

Proof. We first show by induction that
h


i
. . . [[ψm , ψm−1 ], ψm−2 ], . . . , ψ2 (z) = ei

m

∏ ηk (z jk ).

k =2

f˜jr̄ ,j1 (z) =

(39)

r̄ −2 ∂ f
jk
f jr̄−1 (zI( jr̄−1 ) , zI( jr̄ ) )
∂z j
k +1
k =1

∏

(zI( jk ) , zI( jk+1 ) ).

(37)

For m = 2 it is clear that (39) holds. Suppose now that (39)
holds for all m ≤ m̄, m̄ ≥ 2. For m = m̄ + 1 we then have

9

with a slight abuse of notation
h

i
. . . [[ψm̄+1 , ψm̄ ], ψm̄−1 ], . . . , ψ2 (z)
m̄+1

= [ ei

∏ ηk (z jk ), ei zi η2 (z j2 )]

k =2

∂η2
(z j2 )) ei
= ei ( ei> η2 (z j2 ) + zi e j2 ∂z
j2

m̄+1

+ ei (

∑

k =2

m̄+1

∏ ηk (z jk )

k =2

e jk ∂z k (z jk ) ∏ η` (z j` )) ei zi η2 (z j2 )
∂η

jk

`=2
`6=k

m̄+1

= ei

∏ ηk (z jk ),

(40)

k =2

where we used that i 6= jk for any k = 1, . . . , m in the last
step. This proves (39). Finally, using (39), we obtain
h

i
. . . [[ψm , ψm−1 ], ψm−2 ], . . . , ψ1 (z)
m

= [ ei ∏ ηk (z jk ), ei η1 (z j1 ) ∫ η0 (zi )dzi ]
k =2

m

= ei η0 (zi ) ∏ ηk (z jk ).

(41)

k =1

This finishes the proof.

10

