Distributed and time-varying primal-dual dynamics via contraction analysis
Pedro Cisneros-Velarde Saber Jafarpour Francesco Bullo
eess.SY cs.MA cs.SY 34H05 (Primary), 34D23, 90C25, 93C95 (Secondary) G.1.7; G.1.6

[NO \title GIVEN]
    [NO \author GIVEN]
    December 30, 2023
======================




  In this note, we provide an overarching analysis of primal-dual dynamics associated to
  linear equality-constrained optimization problems 
   
   using contraction analysis.

  For the 

  well-known standard version of the problem: we establish
  convergence 
  under convexity 
  and 
  the contracting rate under strong convexity.



 Then, for a canonical 
 distributed optimization problem,
 we use partial contractivity to
 establish  

  global exponential
  convergence of its 
  primal-dual dynamics.

  As an application, 
  we propose a new distributed solver for the least-squares
  problem with the same convergence guarantees. 

  Finally, for 
  time-varying versions of both centralized and distributed
  
  primal-dual dynamics,
  
  we exploit their contractive
  nature to establish bounds on their tracking error.  To
  support our 
  analyses, we introduce novel results on
  contraction theory.
  
  



















§ INTRODUCTION




  
*Problem statement and motivation


Primal-dual (PD) dynamics are dynamical systems that solve 
constrained optimization problems. Their study can be traced back to many decades
ago <cit.> and has 
regained
interest since the last decade <cit.>. 





PD 
dynamics have been made popular due to their scalability and
simplicity.

 They have been widely adopted in engineering applications 
such as resource allocation problems
in power networks <cit.>, frequency control in
micro-grids <cit.>, solvers for linear
equations <cit.>, etc. 
In this note, we study optimization
problems with linear equality constraints. In general, PD 
dynamics
seek to find a saddle point of the associated Lagrangian function to the
constrained problem, which is characterized by the equilibria of the dynamics. 




For a general treatise of asymptotic stability of saddle points, 

we refer to
 <cit.> and references therein. However, despite the long history of study and application, there are very recent 
studies on PD 
dynamics related to linear equality constraints 
further 
studying 
different dynamic properties such as: exponential  convergence under different convexity assumptions

 <cit.> and contractivity properties <cit.>. 





We are particularly interested in studying primal-dual dynamics in distributed and time-varying optimization problems. We refer to the recent survey <cit.> 
for an  overview of the long-standing interest on distributed 
optimization. 
Of particular interest is to provide strong convergence guarantees such as global (and exponential)  convergence for the distributed solvers. We aim to provide them 
using contraction theory.



Time-varying optimization has 
found applications 
in system identification, signal detection, robotics, 
traffic management, etc. <cit.>. The goal is to employ a dynamical system 

able to track the time-varying optimal solution up to some bounded error in real time. Although different dynamics have been proposed to 
both time-varying centralized <cit.> and distributed 

problems <cit.>, to the best of our knowledge, there has not been a characterization of the PD 
dynamics in such application contexts. The importance of PD 
algorithms is their simplicity of implementation, i.e., they do not require more complex information structures like the inverse of the Hessian of the system at all times, as in <cit.> and <cit.> for the centralized and distributed cases respectively. 
However, 

simplicity may come with 

a possible trade-off in the tracking error.






Contraction is valuable in practice because it introduces strong stability and robustness guarantees. 
For example, it implies input-to-state stability for systems subject to state-independent disturbances. It also 

guarantees fast correction after transient perturbations to the trajectory of the solution, 
since initial conditions are forgotten. Moreover, a contractive system may be robust towards structural perturbations on the vector field, 
e.g., when a non-convex term is added to the objective function. Finally, 
contraction 
guarantees stable numerical discretizations with geometric convergence rates, an ideal situation for practical implementations. 



All these properties are transparent to whether the system is time-varying or not. 
All of this 
motivates a contraction analysis of PD 
algorithms 


in contrast to the prevalent Lyapunov or invariance analysis in the literature. 





  
*Literature review

The recent works <cit.> study convergence properties of 
PD 
dynamics under different assumptions on the objective function. 

In 
distributed optimization, solvers based on PD 
dynamics are fairly recent, e.g.,  <cit.>. 
An application of distributed optimization of current interest - as seen in the recent survey <cit.> - is the distributed least-squares problem for solving 
an over-determined system of linear equations. To the best of our knowledge, solvers for this problem (in continuous-time) with exponential global convergence 
are still missing in the literature.






Finally, this paper is related to contraction theory, a mathematical tool to analyze 
incremental stability
 <cit.>. An introduction and survey 
can be found in <cit.>. A variant of contraction theory, partial contraction <cit.>, analyzes the convergence to linear subspaces 
and 
has been used in the synchronization analysis of diffusively-coupled network systems <cit.>; however, its application to distributed algorithms is still missing, and our paper provides such contribution. 




  
*Contributions
In this paper we consider the PD dynamics associated to optimization problems with a 

twice differentiable and strongly convex
objective function 
and linear equality constraints. We use 
contraction theory to perform an overarching study of PD dynamics in a variety of implementations and applications; see Fig. <ref>. In particular: 



(i) We introduce new theoretical results 

of how 
non-expansiveness and partial contraction can imply exponential convergence 
to a 
point 
in a subspace of equilibria. 




(ii) For the standard and distributed PD dynamics, we prove: 1) convergence under 
non-expansiveness when the objective function is convex; 2) contraction for the standard problem and partial contraction for the distributed one 
in the 

strongly convex
case, with closed-form exponential global convergence rates. The analysis in result 1) is novel, since it uses the new results introduced in (i). 

Compared to the work <cit.> that also shows contraction for the standard PD, our proof method provides an explicit closed-form expression of the system's contraction rate. Our exponential convergence rate is different from the one by <cit.> via Lyapunov analysis, and 
both rates 


cannot be compared 
without extra 
assumptions on the numerical relationships among various parameters associated to the 
objective function or constraints. 
Moreover, we propose using the augmented Lagrangian 
in order to achieve contraction when the objective function is 
only 
convex. 


In the case of distributed optimization, 
there exist other 
solvers that show exponential convergence, e.g., as in <cit.>, but none of these have 
contractivity. 


























(iii) We propose a new solver for the distributed least-squares problem based on 
PD dynamics, and use our results in (ii) to prove its convergence. 

Compared to the recent work <cit.>, our new model exhibits global convergence; and compared to the recent work
 <cit.>, ours exhibits exponential convergence 
and has a simpler structure. 



(iv) 
We 
characterize the performance of PD dynamics associated to time-varying versions of both standard and distributed optimization problems in terms of the problems' parameters. In particular, we prove the tracking error to the time-varying solutions is uniformly ultimately bounded (UUB) in either case and that the 
bound decreases as the contraction rate increases — these results, to the best of our knowledge, are novel. Our analysis builds upon the contraction results in contribution (ii). 













  
*Paper organization 
Section <ref> has notation and preliminary concepts. Section <ref> has results on contraction theory. Section <ref> analyzes contractive properties of the standard PD dynamics. 
The contractive analysis of distributed (with the least-squares problem application) and time-varying versions of PD dynamics are in Sections V and VI respectively.


Section <ref> is the conclusion.



§ PRELIMINARIES AND NOTATION





 §.§ Notation, definitions and useful results

Consider A∈^n×n, 
then σ_min(A) denote its minimum
singular value and σ_max(A) its maximum one. 




If A has only
real eigenvalues, let λ_max(A) be its 
maximum eigenvalue. A
  is an orthogonal projection if it is symmetric
  and A^2 = A. Let · denote any norm, and ·_p denote the ℓ_p-norm. When the argument of a norm is a matrix, we refer to its respective induced norm. 
The matrix measure associated 
to 

· is μ(A) = lim_h→ 0^+I+hA-1/h; e.g., 
the one 
associated to the ℓ_2-norm is 
μ_2(A)=λ_max((A+A^⊤)/2) <cit.>. 
Given invertible Q∈^n× n, let ·_2,Q be the weighted ℓ_2-norm x_2,Q=Qx_2
, x∈^n, and whose associated matrix measure is 
μ_2,Q(A)=μ_2(QAQ^-1) <cit.>. 
  
Let I_n be the n× n identity matrix, 1_n and
0_n be the all-ones and all-zeros column vector with n
entries respectively. Let (X_1,…,X_N)∈^∑^N_i=1n_i×∑^N_i=1n_i be the 
block-diagonal matrix with elements 

X_i∈^n_i× n_i. 
Let _≥ 0 be the set of non-negative real numbers. Given x_i∈^k_i, 
let (x_1,…,x_N)=[ x_1^⊤     … x_N^⊤ ].

Consider a differentiable function f:^n→^n. We say f is Lipschitz smooth with constant K_1>0 if ∇ f(x)-∇ f(y)_2≤ K_1x-y_2 for any x,y∈^n; and strongly convex with constant K_2>0 if K_2x-y_2^2≤ (∇ f(x)-∇ f(y))^⊤(x-y) for any x,y∈^n. Assuming f is twice differentiable, these two conditions are equivalent to ∇^2 f(x)≼ K_1I_n and K_2I_n≼∇^2 f(x) for any x∈ R^n, respectively.





















The proof of the next proposition is found in the Appendix.


   For a full-row rank matrix A∈^m×n,
  B=B^⊤∈ R^n× n, and b_2≥b_1>0 such that b_2
  I_n≽ B ≽ b_1 I_n≻0, the matrix [     -B   -A^⊤;      A 0_m× m ] is Hurwitz.




 §.§ Review of basic concepts on contraction theory







Consider the dynamical system 

 ẋ=f(x,t)

with x∈^n. 
Let t↦ϕ(t,t_0,x_0) be the trajectory of
  the system 
  starting from x_0∈^n at time t_0≥ 0.






Consider the system satisfies ϕ(t,t_0,x_0)-ϕ(t,t_0,y_0)≤x_0-y_0e^-c(t-t_0), for any x_0,y_0∈^n and any t_0∈_≥ 0. 
We say it is contractive with
respect to · when c>0, and non-expansive 
when c=0.










A time-invariant contractive system has a unique
equilibrium point.











Now, assume the Jacobian of the system, 

i.e., Df(x,t), satisfies:
μ(Df(x,t))≤ -c for any (x,t)∈^n×_≥ 0, with μ being the matrix measure associated to · and constant c≥ 0. 
Then, 
this system 
has contraction rate c with respect to
·. 
Now, assume the
system 
has a flow-invariant linear subspace
ℳ=x∈^nVx=0_k with
V∈^k×n being 
full-row rank 
with orthonormal
rows. Then the system is partially contractive with respect to
· and 
ℳ if there exists
c>0 such that, for any x_0∈^n and t_0∈_≥ 0, the 
system 
satisfies
Vϕ(t,t_0,x_0)≤Vx_0e^-c(t-t_0). When
c=0, 
the system is partially non-expansive with
respect to ℳ <cit.>. Consequently, a partially
contractive system has any of its trajectories approaching ℳ
with exponential rate; 











and a partially non-expansive one has any of its trajectories at a
non-increasing distance from ℳ. 


Pick a symmetric positive-definite P∈^n×n and a scalar c>0, then 
μ_2,P^1/2(Df(x,t))≤ -c for all (x,t)∈^n×_≥ 0 is equivalent to f satisfying the integral contractivity condition, i.e., for every x,y∈^n and t≥ 0,
(y-x)^⊤ P(f(x,t)-f(y,t))≤ -cx-y_2,P^1/2^2.



  
  
















    


§ THEORETICAL CONTRACTION RESULTS


The next 
result 
will be used throughout the paper.











Consider the system ẋ=f(x,t), x∈^n, 
with a flow-invariant ℳ=x∈^nVx=0_k with V∈^k×n being a full-row rank matrix with orthonormal rows. Assume μ(VDf(x,t)V^⊤)≤ -c for any (x,t)∈^n×_≥ 0, some constant c≥ 0 and some matrix measure μ.


  * If c>0, then the system is partially contractive with
  respect to ℳ and every trajectory exponentially converges to
  the subspace ℳ with rate c.

  * If c=0 and μ(VDf((I_n-V^⊤ V)x,t)V^⊤)<0 for
  any (x,t)∈^n×_≥ 0, then the system is partially
  non-expansive with respect to ℳ and every trajectory
  converges to the subspace ℳ.
  

Moreover, assume that one of the conditions in parts <ref> and <ref> holds and ℳ is a set of equilibrium points. If the system is non-expansive, then 


  * every trajectory of the system converges to an equilibrium point, and if c>0, then it does it with exponential rate c. 









 

  Statement <ref> in Theorem <ref> was proved
  in <cit.>.  To the best of our knowledge,
  statements <ref> and <ref> are novel.




It is easy to check that V^⊤ V is an orthogonal projection matrix onto ℳ^⊥; and that U:=I_n-V^⊤ V is also an orthogonal projection matrix onto ℳ. 


Using these results, we can express the given system as ẋ=f(Ux+V^⊤ Vx,t). Now, we set z:=Vx, and observe that x(t) converges to ℳ if and only if z(t) converges 0_k. Then, using this change of coordinates, we obtain the system:

    ż=Vf(Ux+V^⊤ z,t).

It has been proved in <cit.> that 

z^*=0_k is an equilibrium point for the
system (<ref>). 
















To prove <ref>, assume that
μ(VDf(x,t)V^⊤)=0 for any (x,t)∈^n×_≥ 0; i.e.,
that the system (<ref>) is non-expansive. Now, if we
assume that μ(VDf(Ux,t)V^⊤)<0 for any (x,t)∈^n×_≥ 0, then by the Coppel's inequality <cit.>, the
fixed point z^*=0_k is locally exponentially stable. Now, we can use 
a generalization of <cit.>, namely Lemma <ref> (proof found in the Appendix),  

to establish the convergence of z(t) to z^*. This finishes the proof for <ref>.

Now, we prove statement <ref>. 
  Let t↦ x(t) be a trajectory of the dynamical system. For
  every t∈_≥ 0, (I_n - V^⊤V)x(t) is the orthogonal projection
  of x(t) onto the subspace ℳ and it is an equilibrium
  point. Since the dynamical system is non-expansive, we have




x(s) - (I_n - V^⊤V)x(t)≤x(t) -
    (I_n - V^⊤V)x(t)=V^⊤Vx(t), for all s≥ t. 
  This implies that, for every t∈_≥ 0 and every s≥ t, the point x(s) remains
  inside the closed ball B(x(t),
  V^⊤Vx(t)). Therefore, for every t≥ 0, the point
  x(t) is inside the set C_t defined by 
  C_t = cl(⋂_τ∈ [0,t]B(x(τ),
  V^⊤Vx(τ))). 




It is easy to see that, for s≥ t, we have C_s⊆
C_t. This implies that the family {C_t}_t∈ [0,∞) is a
nested family of closed subsets of ^n. 
Moreover, by parts <ref> and <ref>, we have that lim_t→∞V^⊤Vx(t)→ 0 as t→∞, which in turn results in lim_t→∞diam(C_t) = 0, with convergence rate c for the case c>0 because of diam(C_t)=V^⊤Vx(t)≤
2e^-ctV^⊤Vx(0).










Thus, by the Cantor
Intersection Theorem <cit.>, there exists x^*∈^n such that
⋂_t∈ [0,∞) C_t = {x^*}. We first show that
lim_t→∞ x(t) = x^*. Note that x^*,x(t)∈ C_t, for every
t∈_≥ 0. This implies that 
x(t) - x^*≤diam(C_t). 
This in turn
means that lim_t→∞x(t) - x^*=0 and t↦ x(t)
converges to x^*, with convergence rate c for the case c>0. On the other hand, by part <ref>, the
trajectory t↦ x(t) converges to the subspace ℳ. Therefore, x^*∈ℳ and x^* is an
equilibrium point of the dynamical system. 














This completes the proof for statement <ref>.
























   



§ THE STANDARD 
OPTIMIZATION PROBLEM


We consider the constrained optimization problem:

    min_x∈^n  f(x)   subject to    Ax= b

with the following standing assumptions: 

A∈^k× n, k<n, b∈^k, A is full-row rank,
and f^n is convex and  twice differentiable.



Associated to the optimization problem (<ref>) is the
Lagrangian function 
ℒ(x,ν)=f(x)+ν^⊤(Ax-b) and the primal-dual dynamics



    [  ẋ; ν̇ ]=
      [ -∂ℒ(x,ν)/∂ x;   ∂ℒ(x,ν)/∂ν ]=
      [ -∇ f(x)-A^⊤ν;         Ax-b ].








We introduce two possible sets of
assumptions:


  *  the primal-dual dynamics (<ref>) have an
  equilibrium (x^*,ν^*) and ∇^2f(x^*)≻0_n×n;

  *  the function f is strongly convex with constant
  ℓ_inf>0 and Lipschitz smooth with constant ℓ_sup>0, and,
  for 0<ϵ<1, we define
  


    α_ϵ :=  ϵℓ_inf/σ^2_max(A)+3/4σ_max(A)σ^2_min(A)+ℓ_sup^2>0
              
    
              
    		   P := [                  I_n α_ϵ 
                A^⊤;               α_ϵ  A                  I_k ]∈^(n+k)×(n+k).



  Consider the constrained optimization problem (<ref>), its
  standing assumptions, and its associated primal-dual
  dynamics (<ref>).
  
  
  *  The primal-dual dynamics
    is non-expansive with respect to ·_2 and, if
    Assumption <ref> holds, then (x^*,ν^*) is globally asymptotically stable.
  
  *  Under Assumption <ref>,
  
  
  *  the primal-dual dynamics are contractive with respect
    to ·_2,P^1/2 with contraction rate
    
    α_ϵ3/4σ_max(A)σ^2_min(A)/σ_max(A)+1,
            and

  
  *  there exists a unique globally exponentially stable
    equilibrium point (x^*,ν^*), and x^*
    is the unique solution to the optimization
    problem (<ref>).
  
  




Let (ẋ,ν̇)^⊤:=(x,ν). 
Then, D(x,ν)=[ -∇^2f(x)     -A^⊤;        A        0 ], and so 



μ_2(D(x,ν))=λ_max((D(x,v)+D(x,v)^⊤)/2)
=λ_max((
-∇^2f(x),0_k× k))=0 
for any (x,ν)∈^n×^m, because of convexity ∇^2f(x)≽ 0, which implies 
the system is non-expansive.

For the second part of statement <ref>: Proposition <ref> implies D(x^*,ν^*) is Hurwitz since ∇^2f(x^*)≻ 0, and the proof follows from 
a simple generalization of <cit.> (its proof can be found in the Appendix).

Now, we prove statement <ref>. 











Define P=[   I_n α A^⊤;   α A   I_k ] which is a positive-definite matrix when 

    0<α<1/σ_max(A).

We plan to use the integral contractivity condition to show that system (<ref>) is contractive with respect to norm 
·_2,P^1/2. 

Thus, we need to show 

    η   :=[ x_1-x_2; ν_1-ν_2 ]^⊤ P((x_1,ν_1)-(x_2,ν_2))
       +c[ x_1-x_2; ν_1-ν_2 ]^⊤ P[ x_1-x_2; ν_1-ν_2 ]≤ 0

for any x_1,x_2∈^n and ν_1,ν_2∈^m, and some constant c>0 which will be the contraction rate. After completing squares, using the strong convexity and Lipschitz smoothness of f, along with σ^2_min(A)I_k≼ AA^⊤ and A^⊤ A≼σ^2_max(A)I_n, we obtain

    η   ≤ -((3α/4)σ^2_min(A)-c-cα)ν_1-ν_2_2^2-(ℓ_inf
        -ασ^2_max(A)-c-αℓ^2_sup-cασ^2_max(A))x_1-x_2_2^2
    
        -α c(ν_1-ν_2)-A(x_1-x_2)_2^2.

Set c=Dα for some D>0. Then, to ensure that η≤ 0, we need to ensure 

    3α/4σ^2_min(A)-Dα-Dα^2≥ 0,
       ℓ_inf-ασ^2_max(A)-Dα-αℓ^2_sup-Dα^2σ^2_max(A)≥
      0.

Now, to ensure inequality (<ref>) holds, using the inequalities (<ref>), 
it is easy to see that it suffices to ensure that 

    3σ_max(A)σ^2_min(A)/4(σ_max(A)+1)>D.

Now, using inequalities (<ref>) and (<ref>), we obtain: 

ℓ_inf-ασ^2_max(A)-Dα-αℓ^2_sup-Dα^2σ^2_max(A)>ℓ_inf-α(σ^2_max(A)+3/4σ_max(A)σ_min^2(A)+ℓ_sup^2) 
and so, to ensure inequality (<ref>) holds, it suffices that 

    ℓ_inf/σ^2_max(A)+3/4σ_max(A)σ^2_min(A)+ℓ_sup^2>α.

Now, the parameter α needs to satisfy inequalities (<ref>) and (<ref>); however, (<ref>) implies (<ref>) because the inequality π_1^2+π_2^2≥ 2π_1π_2 for π_1,π_2>0 let us conclude that ℓ_sup/σ^2_max(A)+ℓ^2_sup≤1/2σ_max(A). 




Finally, c must be less than the multiplication of the left-hand sides of the inequalities (<ref>) and (<ref>), which proves statement <ref>. 


Now, since the dynamics are contractive, there must exist a unique globally exponentially stable equilibrium point which also satisfies the (sufficient and necessary) KKT conditions of optimality for the optimization problem (<ref>), thus proving statement <ref>.




 



Theorem <ref> is a fundamental
  building block for the rest of results in this paper as seen in Fig. <ref> and therefore, it was necessary to provide a comprehensive proof
  using the integral contractivity condition that could provide an explicit estimate of the contraction rate (as opposed to the different proof in <cit.>).
  
    Throughout this note, 
  
  the Lipschitz smoothness and strong convexity of f 
  are used to prove contraction.  
  
  However, the latter is relaxed in Corollary <ref>.


For the case of convex f, Theorem <ref> does not state convergence - nor contraction - without additional assumptions; indeed, 
oscillations may appear 
and convergence to
the saddle points is not guaranteed <cit.>.























In order to still be able to use Theorem <ref> in this case, we 
consider
a modification to the
Lagrangian, 
known as the augmented
  Lagrangian <cit.>: 




ℒ_(x,ν)=ℒ(x,ν)+ρ/2Ax-b^2_2 
with gain ρ> 0. Its associated augmented primal-dual dynamics
become

    [  ẋ; ν̇ ]=
    [ -∇ f(x)-A^⊤ν-ρ A^⊤ A x+ρ A^⊤ b;                           Ax-b ]
 
and 
have the same equilibria as the original one
in (<ref>). 
We introduce two possible sets of assumptions:


  *  the primal-dual dynamics (<ref>) have an
  equilibrium (x^*,ν^*), ∇^2f(x^*)≽0_n×n, and (∇^2f(x^*))∩(A)={0_n};
  

  *  (∇^2f(x))∩(A)={0_n} for any
  x∈^n and f is Lipschitz smooth with constant ℓ_sup>0,
  and, for 0<ϵ<1, we define

  
    α̅_ϵ :=  ϵρσ_min^2(A)/(1+ρ)σ^2_max(A)+3/4σ_max(A)σ^2_min(A)+ℓ_sup^2
    
              
            P̅ := [                   I_n α̅_ϵ 
                A^⊤;               α̅_ϵ  A                   I_k ]∈^(n+k)×(n+k).


  
  Consider the constrained optimization problem (<ref>), its
  standing assumptions, and its associated augmented primal-dual
  dynamics (<ref>) with ρ>0.
  
  
  *  Under Assumption <ref>, the augmented primal-dual
    dynamics are non-expansive with respect to ·_2 and
    (x^*,ν^*) is globally asymptotically stable.
  
  *  Under Assumption <ref>,
    
    
  *  the augmented primal-dual dynamics are contractive
      with respect to ·_2,P̅^1/2 with contraction rate
      
    α̅_ϵ3/4σ_max(A)σ^2_min(A)/σ_max(A)+1,
            and

  
  *  there exists a unique globally exponentially stable
    equilibrium point (x^*,ν^*) for the augmented primal-dual dynamics
    and x^* is the unique solution to the constrained optimization
    problem (<ref>).
  
  













The proof follows directly from Theorem <ref>. For statement <ref>, note that (∇^2f(x^*))∩(A)={0_n} implies that ∇^2f(x^*)+ρ A^⊤ A≻0_n×n for the Jacobian of the system 
    [ -∇^2f(x)-ρ A^⊤ A             -A^⊤;                A                0 ].

For statement <ref>, note that (∇^2f(x))∩(A)={0_n} for any x∈^n implies that 
x↦ f(x)+ρ/2x^⊤ A^⊤ Ax is Lipschitz smooth with constant ℓ_sup^2+ρσ^2_max(A)>0 and strongly convex with constant ρσ_min^2(A)>0.


 The benefit of
    using the augmented Lagrangian is that, unlike the conditions in
    Theorem <ref>, the resulting primal-dual dynamics may be contractive despite
    f being only convex.








































§ DISTRIBUTED ALGORITHMS










We study a popular distributed implementation for solving an unconstrained optimization problem
 <cit.>. 


We want to solve the problem min_x∈^nf(x)=∑_i=1^Nf_i(x) with f_i:^n→ convex. 

Let 𝒢 be an undirected connected 



interaction graph between N distinct agents. 
Let 𝒩_i be the neighborhood of node i and L be the 
Laplacian matrix of 𝒢. Let x^i∈^n be the state 
associated to 
agent i, and let x=(x^1,…,x^N)^⊤. Then, 
the problem becomes: 

    min_x∈^nN     ∑_i=1^Nf_i(x^i)
       (L⊗ I_n)x= 0_nN
    .


The associated distributed primal-dual dynamics are 

    ẋ^i   
    	=-∇_x^if_i(x^i)-∑_j∈𝒩_i(ν^j-ν^i)
    
    	ν̇^i   =∑_j∈𝒩_i(x^j-x^i)






for i∈N. In system (<ref>), 
any agent only uses information from herself and the set of her neighbors.

To study this system, we introduce two possible sets of
assumptions:


  *  min_x∈^nf(x) has a solution x^* and ∇^2f_i(x^*)≻0_n×n for any i∈{1,…,N};

  *  min_x∈^nf(x) has a solution x^* and the function f_i is strongly convex with constant ℓ_inf,i>0 and Lipschitz smooth with constant ℓ_sup,i>0 for any i∈{1,…,N}, with 
ℓ_inf=(ℓ_inf,1,…,ℓ_inf,N) and ℓ_sup=(ℓ_sup,1,…,ℓ_sup,N).


With either assumption, note that we cannot apply Theorem <ref> directly since the linear equality constraint in (<ref>) is not full-row rank. However, if we instead consider partial contraction, then Theorem <ref> can be used to prove the next result.






Consider the distributed primal-dual dynamics (<ref>). 


  *  The distributed primal-dual dynamics are non-expansive with respect to ·_2, and 

  * under Assumption <ref>, for any
  (x^i(0),ν^i(0))∈^n×^n,
  lim_t→∞x^i(t)=x^* and
  lim_t→∞ν^i(t)=ν^*_i, for some ν_i^* such that ∑^N_k=1ν_k^*=∑^N_k=1ν^k(0).


  * Under Assumption <ref>, the convergence results in statement <ref> hold and, for 0<ϵ<1, the convergence of (x(t),ν(t))^⊤ has exponential rate 


    3ϵ/4λ_N λ^2_2/λ_N+1min_i∈Nℓ_inf,i/λ_N^2+3/4λ_N λ^2_2+ℓ_sup_∞^2,

where λ_2 and λ_N are the smallest non-zero
and the largest eigenvalues of L, respectively.















Set f(x)=∑_i=1^Nf_i(x^i) and ν=(ν^1,…,ν^N). Succinctly, the dynamics of the system are

    ẋ   =-∇ f(x)-(L⊗I_n)ν
    ν̇   =(L⊗I_n)x.

Now, let A̅:=(L⊗ I_n) and (ẋ,ν̇):=(x,ν), 
and so D(x,ν)=[ -∇^2f(x)    -A̅^⊤;       A̅   0_m× m ]. 
Since -∇^2f(x)≼ 0_nN×nN because of convex f_i, it follows that μ_2(D(x,ν))=0 for any x∈^nN,ν∈^nN, and the system is weakly contractive, which proves <ref>.

Consider the equilibrium equations of (<ref>), and let (x^*,ν^*) be a (candidate) fixed point of the system. From the second equation in (<ref>), x^*=1_N⊗ v with v∈^n. Now, from the first equation in (<ref>), we get 
0_nN=∇ f(x^*)+(L⊗I_n)ν^* and left multiplying by 1_N^⊤⊗ I_n, we obtain 0_n=∑_i=1^N∇ f_i(v). 
This is exactly the necessary and sufficient conditions of optimality for the problem min_x∈^nf(x)=∑_i=1^Nf_i(x), and so v=x^* is an optimal solution to this problem. Moreover, ν^* is just some Lagrange multiplier for the constraint in (<ref>). 
















Now, define the change of coordinates (x',ν')=(x-x^*,ν-ν^*), then we get 
(ẋ',ν̇')=(ẋ,ν̇)=(x'+x^*,ν'+ν^*), 
and whenever we refer to the word “system" for the rest of the proof, we refer to the dynamics after this coordinate change. Observe the system has an equilibrium point (0_nN,0_nN), but it is not unique; in fact, it is easy to verify that the following is a linear subspace of equilibria for the system: ℳ=(x',ν')∈^nN×^nNx'=0_nN,ν'=1_N⊗α with α∈^n. As a corollary, the subspace ℳ is flow-invariant for the distributed system.

Now, since L has N-1 strictly positive eigenvalues, we can write them as 
0=λ_1<λ_2≤…≤λ_N, and, by eigendecomposition, we can obtain an orthogonal matrix R'∈^N×N such that R'LR'^⊤=(0,λ_2,…,λ_N). From here, we obtain the matrix R∈^N-1×N as a submatrix of R' such that RLR^⊤=Λ with Λ=(λ_2,…,λ_N) with the properties: RL=Λ R, RR^⊤ = I_N-1 and R^⊤ R≠ I_N. Now, define V=(I_nN,(R⊗I_n)) 









which has orthonormal rows and expresses ℳ=(x',ν')∈^nN×^nNV(x',ν')^⊤=0_(2N-1)n. Then, 

we can use Theorem <ref> for stating the convergence of trajectories of the system to ℳ using partial contraction. 

First, note that 

VD(x',ν') V^⊤=
[    ∇^2f(x'+x^*)   -((R^⊤Λ)⊗I_n);     ((Λ R)⊗I_n) 0_n(N-1)×n(N-1) ],



where we have used the fact that (R⊗I_n)(L⊗
I_n)
=(Λ R)⊗I_n. Now, set
A̅^*:=(Λ R)⊗I_n and note that
σ_min(A̅^*) = λ_2 and σ_max(A̅^*) = λ_N. 

Since ∇^2f(x'+x^*)≼0_nN×nN, it follows that μ_2(VD(x'+x^*,ν'+ν^*)V^⊤)≤ 0. Now, since ∇^2f(x^*)≺0_nN×nN, Proposition <ref> implies that VD(x^*,ν^*)V^⊤ is a Hurwitz matrix, which implies that μ_2(VD(x'+x^*,ν'+ν^*)V^⊤)< 0 for any (x',ν')∈ℳ, and thus result <ref> of Theorem <ref> implies the convergence to the subspace ℳ (and this implies convergence of the trajectories of the original system to the set ℳ'=(x,ν)∈^nN×^nNx=x^*, ν=1_N⊗α with α∈^n, i.e., ℳ is simply the set ℳ' translated or anchored to the origin). Since ℳ is a set of equilibria for the system and the system is weakly contractive, result <ref> of Theorem <ref> concludes that any trajectory of the system converges to some equilibrium point in ℳ. 

Now, observe that (1_N^⊤⊗ I_n)ν̇=(1^⊤_N L⊗ I_n)x=0_n, and so the set (x,ν)∈^nN×^nN(1_N^⊤⊗ I_n)ν=(1_N^⊤⊗ I_n)ν(0) is positively-invariant for (<ref>). Then, it follows that ∑^N_k=1ν^k_i(t)=∑^N_k=1ν^k_i(0) for any i∈n and any t≥ 0. Then, since lim_t→∞ν^i(t)<∞, 

we conclude the proof for statement <ref>.

We prove statement <ref>. Observe that 

min_i∈Nℓ_inf,i I_nN×nN≼∇^2f(x'+x^*)≼max_i∈Nℓ_sup,i I_nN×nN and that A̅^* is full-row rank since it is easy to verify that (Λ R)=N-1 and so ((Λ R)⊗I_n)=n(N-1). Then, for 0<ϵ<1, defining P= [      I_nN α_ϵ A̅^*⊤;  α_ϵ A̅^*  I_n(N-1) ]∈^nN× nN and 
α_ϵ :=  ϵmin_i∈Nℓ_inf,i/σ^2_max(A̅^*)+3/4σ_max(A̅^*)σ^2_min(A̅^*)+ℓ_sup_∞^2>0, 
we can use Theorem <ref> to conclude that 



μ_2,P^1/2(VD(x'+x^*,ν'+ν^*)V^⊤)≤ -c with c as in equation (<ref>) 

for any positive ϵ<1.
































So then, any trajectory (x'(t),ν'(t)) exponentially
converges to the subspace ℳ with rate c, due to
statement <ref> from Theorem <ref>. 

Finally, the proof finishes by following a similar proof to statement <ref>.





For the case of convex f_i, Theorem <ref> does not state convergence - nor partial contraction - without additional assumptions. Similar to the analysis in Section <ref>, we present an example where augmenting the Lagrangian let us use Theorem <ref>.





We consider the popular 
distributed least-squares problem <cit.>. Given a full-column rank matrix H∈^N×n, n<N, it is known that x^*=(H^⊤ H)^-1H^⊤ z is the unique solution to the least-squares 
problem min_x∈^nz-Hx_2^2, for z∈^N. 
An equivalent distributed version 
is


    min_x∈^nN     ∑^N_i=1(h_i^⊤ x^i-z_i)^2
       (L⊗ I_n)x= 0_nN

with h_i^⊤∈^1×n being the ith row of the matrix H, x=(x^1,…,x^N)^⊤ and z=(z_1,…,z_N)^⊤. Notice that f(x)=∑^N_i=1|h_i^⊤ x^i-z_i|^2 is convex, since 
∇^2f(x)=(h_1h_1^⊤,…, h_Nh_N^⊤)≽0_nN×nN. 




We propose to 
augment the Lagrangian 
with the quadratic term ρ/2x^⊤(L⊗ I_n)x with ρ>0 (which does not alter the original saddle points) 
and obtain


    ẋ^i   
    	=-(h_i^⊤ x^i-z_i)h_i-ρ∑_j∈𝒩_i(x^j-x^i)
       -∑_j∈𝒩_i(ν^j-ν^i)
    ν̇^i   =∑_j∈𝒩_i(x^j-x^i)

for i∈N. The new algorithm is 
distributed.


Observe that ((h_1h_1^⊤,…, h_Nh_N^⊤))∩(L⊗ I_n)={0_nN} implies 
ℓ_inf^* I_nN≼(h_1h_1^⊤,…, h_Nh_N^⊤)+(L⊗ I_n) for some constant ℓ_inf^*>0. Then, the following follows from Theorem <ref>. 


Consider the system (<ref>), and let x^* be the unique solution to the least-squares problem. Then, 
for any (x^i(0),ν^i(0))∈^n×^n, lim_t→∞x^i(t)= x^* and lim_t→∞ν^i(t)=ν^*_i for some ν_i^* such that ∑^N_k=1ν_k^*=∑^N_k=1ν^k(0); and, for 0<ϵ<1, the convergence of (x(t),ν(t)) has exponential rate

    ϵ3/4λ_N λ^2_2/λ_N+1ℓ_inf^*/λ^2_N+3/4λ_Nλ^2_2+(λ_N+ρmax_ih_i^2_2)^2

where λ_2 and λ_N are the smallest non-zero and
the largest eigenvalues of L, respectively.


































§ TIME-VARYING OPTIMIZATION





 §.§ Time-varying standard optimization










Our results in Section <ref> 




can be used to prove analyze 




the case where the associated optimization problem is time-varying. 

Consider  

    min_x∈^n  f(x,t)   subject to    Ax= b(t)


with the following standing assumptions: 

A∈^k× n, k<n, b∈^k, A is full-row rank,
and, for every (x,t)∈^n×_≥ 0,




  *  x↦ f(x,t) is twice continuously differentiable, uniformly strongly convex 

with constant ℓ_inf>0, i.e., ∇^2f(x,t)≽ℓ_inf I_n; and uniformly Lipschitz smooth 
with constant ℓ_sup>0, i.e., ∇^2f(x,t)≼ℓ_sup I_n;

  *  t↦∇ f(x,t) and t↦ b(t) are continuously differentiable functions. 










The associated time-varying primal-dual dynamics are

    [  ẋ; ν̇ ]=
    [ -∇ f(x,t)-A^⊤ν;        Ax-b(t) ].


















Given a fixed time t, let x^*(t) be a solution to the program min_x:Ax=b(t)f(x,t) and ν^*(t) its associated Lagrange multiplier. From the standing assumptions and Theorem <ref>, for any fixed t, there exists a unique optimizer (x^*(t),ν^*(t)). Then, (x^*(t),ν^*(t))_t≥ 0 defines 
the optimizer trajectory 
of the optimization problem (<ref>). The following result establishes the performance of the primal-dual dynamics in tracking the optimizer trajectory. 




Consider the time-varying optimization problem (<ref>), its standing assumptions, and its associated primal-dual dynamics (<ref>). 


  *  The primal-dual dynamics are contractive with
  respect to ·_2,P^1/2 with contraction rate c,
  where P is the matrix defined in (<ref>) and c is the same
  contraction rate as in (<ref>) of
  Theorem <ref>. 


Assume that, for any t≥ 0, ḃ(t)_2≤β_1 and
∂/∂ t∇ f(x,t)_2≤β_2 for some positive constants
β_1,β_2, and let z(t):=(x(t),ν(t))^⊤ and
z^*(t):=(x^*(t),ν^*(t))^⊤.


  * Then,

    z(t)-z^*(t)_2,P^1/2
       ≤(z(0)-z^*(0)_2,P^1/2-ρ/c)e^-ct+ρ/c,

i.e., the tracking error is uniformly ultimately bounded by ρ/c with 

    ρ=
    λ_max(P)   (β_2/ℓ_inf+(σ_max(A)/ℓ_inf+1)
       ℓ_max/σ_min^2(A)(β_1+σ_max(A)/ℓ_infβ_2)
    ).






Let (ẋ,ν̇):=(x,ν,t), and so 
D(x,ν,t)=[ -∇^2f(x,t)       -A^⊤;          A     0_k× k ]. Since A is constant and considering item <ref> of the standing assumptions,   
we can finish the proof for statement <ref> by following the same proof as in Theorem <ref>.
Now we prove statement <ref>. Let us fix any t≥ 0. Then, the KKT conditions that the optimizers x^*(t) and ν^*(t) must satisfy (i.e., equivalent to the equilibrium equations of the system (<ref>)) are

    0_n   =-∇ f(x^*(t),t) - A^⊤ν^*(t)
    0_k   =Ax^*(t)-b(t),

We first show that the curves t↦ x^*(t) and t↦ν^*(t) are continuously differentiable. Define the function
g:^k+n+1→^k+n as 
g(t,x,ν) = [ -∇ f(x,t) - A^⊤ν;        Ax - b(t) ]. 







Since t↦ b(t) and t↦∇ f(x,t) are continuously
differentiable, the function g is continuously differentiable on
^n+k+1. Moreover, note that 
∇_(x,ν) g(t,x,ν) = D(x,ν,t). 






By item <ref> of the standing assumptions, we know that -∇^2f(x,t)≼-ℓ_inf
I_n and A is full row rank. From Proposition <ref>, this implies that ∇_(x,ν) g(t,x,ν) 
is Hurwitz and therefore, nonsingular. Finally, the Implicit Function
Theorem <cit.> implies the solutions t↦ x^*(t) and
t↦ν^*(t) of the algebraic equations (<ref>) and (<ref>)
are continuously differentiable for any t∈_≥ 0. 

Now, observe that equation (<ref>) implies 
Aẋ^̇*̇(t)_2≤β_1.




Then, from (<ref>)

    0_n=∇^2f(x^*(t),t)ẋ^̇*̇(t)+∇̇f(x^*(t),t)
            +A^⊤ν̇^̇*̇(t)
       0_m=Aẋ^̇*̇(t)+A(∇^2f(x^*(t),t))^-1∇̇f(x^*(t),t)
           +A(∇^2f(x^*(t),t))^-1A^⊤ν̇^̇*̇(t)
    
    
    
       ν̇^̇*̇(t)_2≤ℓ_max/σ_min^2(A)(β_1+σ_max(A)/ℓ_infβ_2),

where the first implication follows from differentiation, the second one follows from the Hessian being  invertible, and the third one is derived considering that A is full-row rank. Similarly, we  differentiate (<ref>) again and obtain 

    ẋ^̇*̇(t)_2≤β_2/ℓ_inf+σ_max(A)/ℓ_infν̇^̇*̇(t)_2.

Now, considering the contraction result on item <ref>, we set Δ(t):=[ x(t); ν(t) ]-[ x^*(t); ν^*(t) ]_2,P^1/2 and use <cit.> to obtain the following differential inequality Δ̇(t)≤ -cΔ(t)+[  ẋ^̇*̇(t); ν̇^̇*̇(t) ]_2,P^1/2. Then, Δ̇(t)≤ -cΔ(t)+λ_max(P)(ẋ^̇*̇(t)_2+ν̇^̇*̇(t)_2) 




and using our previous results, we immediately obtain Δ̇(t)≤ -cΔ(t)+ρ with 
ρ as in the theorem statement.




















Now, observe the function h(u)=-cu+ρ is Lipschitz (since it is a linear function), and we can use the Comparison Lemma <cit.> to 
upper bound Δ(t) by the solution to the differential equation u̇(t)=-cu(t)+ρ for all t≥ 0, from which <ref> follows. 























The bounds in the assumptions for statement <ref> in Theorem <ref> ensure that 

the rate at which the time-varying
optimization changes is bounded. Indeed, the right-hand side of equation (<ref>) is consistent: the larger (lower) these bounds, the larger (lower) the asymptotic tracking error. Moreover, the tracking is better the larger the contraction rate.







 §.§ Time-varying distributed optimization



Our partial contraction analysis of Section <ref> can be extended to 
obtain new results of performance guarantees 










for the following time-varying distributed optimization problem







    min_x∈^nN     ∑_i=1^Nf_i(x^i,t)
       (L⊗ I_n)x= 0_nN,

where we consider a time-invariant connected undirected graph whose Laplacian matrix is L, and set x=(x^i,…,x^N)^⊤ with x^i∈^n, 



with the following standing assumptions: 

for every (x,t)∈^n×_≥ 0, and for any i∈N


  *  x↦ f_i(x,t) is twice continuously differentiable, uniformly strongly convex with constant ℓ_inf,i>0, i.e., ∇^2f_i(x,t)≽ℓ_inf,i I_n; and uniformly Lipschitz smooth with constant ℓ_sup,i>0, i.e., ∇^2f_i(x,t)≼ℓ_sup,i I_n;

  *  t↦∇ f_i(x,t) is continuously differentiable.



Then, the associated primal-dual dynamics are

    ẋ^i   =-∇_x^if_i(x^i,t)-∑_j∈𝒩_i(ν^j-ν^i)
    ν̇^i   =∑_j∈𝒩_i(x^j-x^i)












for i∈N. Given a fixed time t, let x^*(t)=1_N⊗ x^*(t) with x^*(t) being the unique solution to the program min_x∑_i=1^Nf_i(x,t). Then, (x^*(t))_t is a unique trajectory; however, there may exist multiple trajectories of the dual variables associated to the  
constraint in (<ref>). Let ν^*(t)=(ν^1^*(t),…,ν^N^*(t))^⊤ be any dual variable obtained by solving the problem (<ref>) for a fixed t. 
Then, we define the time-varying set of optimizers as: 






    ℳ(t)={(x,ν)∈^nN×^nN|
       V(x-1_N⊗x^*(t),ν-ν^*(t))^⊤=(0_nN,0_n(N-1))^⊤}


where 
V=(I_nN,R⊗I_n) with R∈^N-1× N as in the proof of Theorem <ref>. 







For convenience, let
ℓ_inf=(ℓ_inf,1,…,ℓ_inf,N) and
ℓ_sup=(ℓ_sup,1,…,ℓ_sup,N); and for 0<ϵ<1, we define 


    α̃_ϵ :=  ϵmin_i∈Nℓ_inf,i/λ^2_N+3/4λ_Nλ_2^2+ℓ_sup_∞^2>0
    
           P̃ := [      I_nN α_ϵ A̅^*⊤;  α_ϵ A̅^*  I_n(N-1) ]∈^nN× nN

where A̅^*=(Λ R)⊗I_n, with Λ=(λ_2,…,λ_N) containing the nonzero eigenvalues of L in nondecreasing order. 


The following result establishes the performance of the primal-dual dynamics at tracking the time-varying set of optimizers.




































Consider the time-varying optimization problem (<ref>), its standing assumptions, and its associated primal-dual dynamics (<ref>).
Set z(t):=V(x(t),ν(t))^⊤ and z^*(t):=V(x^*(t),ν^*(t))^⊤.


  * 

The system associated to ż is contractive with respect to ·_2,P̃^1/2 with 
rate c:=α_ϵ3/4λ^2_2/λ_N+1. 




Moreover, for any t≥ 0, if ∂/∂ t∇ f_i(x,t)_2≤β_1,i for some positive constant β_1,i and any i∈N, then, 



  * 

    z(t)-z^*(t)_2,P̃^1/2
       ≤(z(0)-z^*(0)_2,P̃^1/2-ρ/c)e^-ct+ρ/c,

i.e., the tracking error is asymptotically bounded by ρ/c with 

    ρ   =λ_max(P)β_1_1/ℓ_inf_1
    N
       +λ_max(P)β_1_1/λ_2(ℓ_sup_∞/ℓ_inf_1+1).





 














Define f(x(t),t):=∑^N_i=1f_i(x^i(t),t); 
then 


    ż
    
    
    
    
    
    =[ -∇ f(x(t),t)-(L⊗ I_n)ν(t);            (Λ R⊗ I_n)x(t) ].

Then, decomposing (x(t),ν(t))^⊤=U(x(t),ν(t))^⊤+V^⊤ z where U=I_n(2N-1)-V^⊤ V is a projection matrix, 

we use the chain rule and obtain that the Jacobian for this system  is









    [  -∇^2 f(x(t),t)    -(R^⊤Λ⊗ I_n);      (Λ R⊗ I_n) 0_n(N-1)×n(N-1) ],

so then, based on our standing assumptions, using Proposition <ref> and following a similar proof to Theorem <ref>, we obtain that this system is contractive as in item <ref>.

Now we prove statement <ref>. The KKT conditions that the optimizers x^*(t) and ν^*(t) must satisfy (i.e., the equilibrium equation of the system (<ref>)), for any t, are

    0_nN   =-∇ f(x^*(t),t) - (L⊗ I_n)ν^*(t)
    0_nN   =(L⊗ I_n)x^*(t).

Now, observe that (<ref>) and (<ref>)x^*(t)=1_N⊗x^*(t) with x^*(t) being the first nN coordinates of any element of ℳ(t). Moreover, by left multiplying (<ref>) with 1_N^⊤⊗ I_n, we obtain that 0_n=∑_i=1^N∇_x^i f_i(x^*(t),t). Then, the Implicit Function Theorem <cit.> (akin to its use in the proof of Theorem <ref>) implies the curve t↦ x^*(t) is continuously differentiable for any t∈_≥ 0.






Now, from (<ref>) we obtain that 0_n(N-1)=(R⊗ I_n)∇ f(x^*(t),t) + (Λ⊗ I_n)(R⊗ I_n)ν^*(t). Defining y^*(t):=(R⊗ I_n)ν^*(t), we get 0_n(N-1)=(R⊗ I_n)∇ f(x^*(t),t) + (Λ⊗ I_n)y^*(t). 





Again, an application of the Implicit Function Theorem let us conclude that 

the solution (x^*,t)↦ y^*(x^*,t) is continuously differentiable for any (x^*,t)∈^nN×_≥ 0; however, since 
t↦x^*(t) is continuously differentiable for any t∈_≥ 0, then 

t↦ y^*(t) is continuously differentiable too. 






































Then, we can differentiate equation (<ref>) and left multiply it by (1_N^⊤⊗I_n) to obtain







    ẋ^̇*̇(t)=-g(x^*(t),t)∑_i=1^N∂/∂ t∇_x^if_i(x^*(t),t))

with g(x^*(t),t):=(∑_i=1^N∇^2_x_if_i(x^*(t),t))^-1.

Recall that RL=Λ R. 

Then, since y^* 
is continuously differentiable, we differentiate equation (<ref>) and left multiply it by (R⊗ I_n) to obtain








    ẏ^̇*̇(t)   =-(Λ^-1R⊗ I_n)(∇^2f(x^*(t),t)(1_N⊗ h_1(x^*(t))
       +∂/∂ t∇ f(x^*(t),t)).


Therefore, observe that 
ẋ^̇*̇(t)_2≤1/∑_i=1^Nℓ_inf,i∑_i=1^Nβ_1,i=β_1_1/ℓ_inf_1, and ẋ^̇*̇(t)=1_N⊗ẋ^̇*̇(t). Moreover,







ẏ^̇*̇(t)_2≤1/|λ_2|(ℓ_sup_∞ẋ^̇*̇(t)_2+β_1_1), 
where we used: 


∂/∂ t∇ f(x^*(t),t)_2≤∑_i=1^N∂/∂ t∇_x^if_i(x^*(t),t)_2, and (Λ^-1R)⊗ I_n_2=√(λ_max(Λ^-2⊗ I_n))
=1/λ_2.

Now, for any t, let (a_1(t),a_2(t))∈ℳ(t). Note that, no matter which element of ℳ we choose, a_1(t)=1_N⊗ x^*(t) and so it is uniquely defined for any t and we also know is differentiable. Now, note that a_2(t)=γ(t)+1_N⊗α, with α∈^n and some uniquely defined γ(t); and note that (R⊗ I_n)a_2(t)=(R⊗ I_n)γ(t) for any t. Therefore (R⊗ I_n)a_2(t) is uniquely defined for any t and we also know is differentiable. In conclusion, the trajectory ((a_1(t),(R⊗ I_n)a_2(t)))_t≥ 0=(V
(a_1(t),a_2(t))^⊤)_t≥ 0 is unique and 

t↦ V(a_1(t),a_2(t))^⊤ 
is a continuously differentiable curve. 





Since the system associated to 


ż 
is contractive and the curve, as we just proved above, 

t↦ z^*(t):=V(x^*(t),ν^*(t))^⊤ 
is unique and differentiable, 





we set



Δ(t):=z(t)-z^*(t)_2,P^1/2 
    and use the result in item <ref> and <cit.> to obtain the 

differential inequality 







    Δ̇(t)   ≤ -cΔ(t)+[             ẋ^̇*̇(t); d/dt((R⊗ I_n)ν^*(t)) ]_2,P^1/2
       ≤ -cΔ(t)+λ_max(P)(Nẋ^̇*̇(t)_2+ż^̇*̇(t)_2).











Finally, replacing our previous results and using the Comparison
Lemma <cit.> 



conclude the proof for <ref>.












As in Remark <ref>, there is consistency on the right-hand side of equation (<ref>). 




§ CONCLUSION



Primal-dual (PD) dynamics associated to linear equality constrained
optimization problems are studied in centralized, distributed and time-varying cases. Contraction theory provides an overarching analysis of the dynamical behavior and performance for all these cases of
PD 
dynamics.





As future work, we plan to design controllers that can improve the PD solver's tracking
properties in the time-varying 
setting. We also plan to study distributed PD solvers for globally coupled linear equation constraints and PD solvers in nonsmooth domains.








plainurl





§ APPENDIX




 §.§ Proof of Proposition <ref>


We remark that the proof of Proposition <ref> is complementary to the one given (for a slightly different case) in <cit.>).

Let P:=[     -B   -A^⊤;      A 0_m× m ] be the matrix in the proposition statement. First, note that (λ(P)) ≤μ_2(P)
= 0. Therefore, every eigenvalue of P has non-positive real part. 

We first show that P has
no eigenvalue equal to zero. Note that by the Schur complement
determinant identity, we have (P) = (-B))(-AB^-1A^⊤). 




Note that B ≽ b_1 I_n, therefore
(-B)  0. Also, note that B^-1≽ b^-1_2 I_n; and thus A B^-1A^⊤≽ A(b^-1_2I_n) A^⊤ =b^-1_2 AA^⊤≻ 0, 




where the last inequality follows from AA^⊤ being invertible. 
This implies that (-A B^-1A^⊤)  0. 



As a result, (P) 0 and P has no zero
eigenvalue. Now we show that P is Hurwitz. Assume that λ = iη
is an eigenvalue of P with zero real part. This means
that, there exists u∈ℂ^n and v∈ℂ^m such that 

    [     -B   -A^⊤;      A 0_m× m ][ u; v ] = iη[ u; v ].



Multiplying this equation from the left by [u^H , v^H],
we get 
([ u^H v^H ][     -B   -A^⊤;      A 0_m× m ][ u; v ]) = 0.  





This implies that (u^HBu) = 0. Assume
that u =θ_1 + iθ_2, where θ_1,θ_2∈^n. Then
(u^HBu) = 0  is equivalent to θ_1^T Bθ_1 + θ_2^⊤Bθ_2 = 0. 



Since B ≽ b_1 I_n, we get that u =
0_n. As a result, the equation (<ref>) can be written as the system 
A^⊤v = 0_n and v = 0_k. 




This implies that if [ u; v ]∈ℂ^n+m is an eigenvector associated to the eigenvalue
λ = iη, then [ u; v ] =
0_n+m. Thus, the matrix P has no eigenvalue
with zero real part. Therefore, the real part of every eigenvalue of
P is negative and the matrix P is Hurwitz.





 §.§ A simple generalization of <cit.>




Consider the dynamical system ẋ=f(x,t), x∈^n, where f is
continuously-differentiable with respect to x and weakly contractive respect to some norm ·, and let x^* be an equilibrium
for the system, i.e., f(x^*,t) =0_n, for every t≥ 0. Then x^* is locally asymptotically stable if and only if it is globally asymptotically stable.



We only prove the nontrivial implication: if x^* is locally asymptotically stable then it is globally asymptotically stable. Since x^* is a locally asymptotically stable equilibrium point for
the dynamical system, then there exists ϵ>0, such that, for every y∈B(x^*,ϵ) we have ϕ(t,0,y)→ x^* as t→∞. Note that,
for every z∈B(x^*,ϵ), there exists T_z such
that ϕ(T_z,0,z) ∈B(x^*,ϵ/2). Using the fact that the
closed ball B(x^*,ϵ) is compact, we get that,
there exists T such that, for every z∈B(x^*,ϵ), we have ϕ(T,0,z) ∈B(x^*,ϵ/2). Suppose that t↦ x(t) is a
trajectory of the dynamical system. Assume
that y∈∂ B(x^*,ϵ) is a point on the straight line
connecting x(0) to the unique equilibrium point
x^*. Then we have x(T) - x^*≤x(T) -
  ϕ(T,0,y) + ϕ(T,0,y)- x^*≤x(0)-y + ϵ/2 =x(0)- x^*-ϵ/2.






Therefore, after time T, t↦x(t) -
  x^* decreases by ϵ/2. As a result, there
    exists a finite time T_inf such that, for every t≥
    T_inf, we have x(t)∈B(x^*,ϵ). Since
    B(x^*,ϵ) is in the region of
    attraction of x^* the trajectory t↦ x(t)
    converges to x^*.




