{'fraction_non_alphanumeric': 0.05084953689504999, 'fraction_numerical': 0.009139422192234558, 'mean_word_length': 4.364703301524624, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Duality and Network Theory in Passivity-based Cooperative Control

This paper presents a class of passivity-based cooperative control problems that have an explicit connection to convex network optimization problems. The new notion of maximal equilibrium independent passivity is introduced and it is shown that networks of systems possessing this property asymptotically approach the solutions of a dual pair of network optimization problems, namely an optimal potential and an optimal flow problem. This connection leads to an interpretation of the dynamic variables, such as system inputs and outputs, to variables in a network optimization framework, such as divergences and potentials, and reveals that several duality relations known in convex network optimization theory translate directly to passivity-based cooperative control problems. The presented results establish a strong and explicit connection between passivity-based cooperative control theory on the one side and network optimization theory on the other, and they provide a unifying framework for network analysis and optimal design. The results are illustrated on a nonlinear traffic dynamics model that is shown to be asymptotically clustering.

derive performance bounds on the input/output behavior of consensus-type networks. Passivity is also widely used in coordinated control of robotic systems [10] and the teleoperation of UAV swarms [11]. Passivity-based cooperative control with quantized measurements is, for example, studied in [12]. The related concepts of incremental passivity or relaxed co-coercivity have been used to study various synchronization problems, see [13] or [14], respectively. Passivity was also used in the context of Port-Hamiltonian systems on graphs in [15]. A passivity framework was used to study clustering in networks of scalar dynamical systems with saturated couplings [16], [17], [18].
In [19], a new definition of passivity was introduced that serves the needs of networked systems. In particular, equilibrium independent passivity was introduced to characterize dynamical systems that are passive with respect to an arbitrary equilibrium point that can be generated by a constant input signal. Equilibrium independent passivity enables a convergence analysis of dynamical networks without computing the convergence point a priori. A similar passivity concept can be found in [20].
The passivity-based cooperative control framework and the network optimization framework have many modeling similarities, as both rely on a certain matrix description of the underlying network (i.e., the incidence matrix). However, to the best of our knowledge, an explicit connection between these two research areas has not yet been established, and this motivates the main thesis of this work: Does the cooperative control framework inherit any of the duality results found in network optimization?
We present in this paper a class of networks consisting of dynamical systems with certain passivity properties that are intimately related to the network optimization theory of [2] and admit similar duality interpretations. Our results build an analytic bridge between cooperative control theory and network optimization theory.
The contributions are as follows. Building upon the existing work on passivity-based cooperative control and in particular on [19], we introduce a refined version of equilibrium independent passivity, named maximal equilibrium independent passivity. The new definition is motivated by the fact that the original definition excludes some important systems, such as integrators. Maximal equilibrium independent passive systems are passive for different steady-state input-output configurations and the equilibrium input-output maps are allowed to be maximal monotone relations. A cooperative control framework involving maximal equilibrium independent passive systems that aim to reach output agreement is considered. First, necessary conditions for an output agreement solution to exist are derived, considering only the systems dynamics and the network topology. It it then shown that any steadystate configuration that satisfies these necessary conditions is inverse optimal, in the sense that the corresponding steady-state input solves a certain optimal flow problem and the steady-state output solves the corresponding dual optimal potential problem. Exploiting this connection, certain results on the existence and uniqueness of output agreement solutions are derived using tools from convex optimization theory. Following this, conditions on the couplings are derived that ensure the output agreement steady-state is realized. Maximal equilibrium independent passivity turns out to be again the central concept, and by using convex analysis, conditions are derived that ensure that the desired steady-state input can be generated for all possible network configurations. The dynamic state and the output variable of the couplings are also shown to be inverse optimal with respect to a dual pair of network optimization problems.
Following the discussion on output agreement problems, the inverse optimality and duality results are generalized to a broader class of networks of maximal equilibrium independent passive systems. The general results are used to analyze a nonlinear traffic dynamic model, that is shown to exhibit asymptotically a clustering behavior.
The reminder of the paper is organized as follows. The network optimization framework of [2] is reviewed in Section 2. In Section 3 the dynamical network model is introduced, some results on passivity-based cooperative control are reviewed and the new notion of maximal equilibrium independent passivity is introduced. The connection to network optimization theory is established in Section 4. First, necessary conditions for the existence of an output agreement solution are derived and inverse optimality and duality results for those solutions are presented. The inverse optimality results are then generalized to networks of maximal equilibrium independent passive systems in Section 5. The theoretical results are illustrated on a nonlinear traffic dynamics model in Section 6. 2 for all η, ξ ∈ D, see, e.g., [21]. A function Φ : R q → R is said to be convex on a convex set D if for any two points η, ξ ∈ D and for all λ ∈ [0, 1], Φ(λη + (1 − λ)ξ) ≤ λΦ(η) + (1 − λ)Φ(ξ). It is said to be strictly convex if the inequality holds strictly and strongly convex on D if there exists α > 0 such that for any two points η, ξ ∈ D, with η = ξ, and for all λ ∈ [0, 1]

Preliminaries
The convex conjugate of a convex function Φ, denoted Φ , is defined as [22]: The definition of a convex conjugate implies that for all η and ξ it holds that Φ(η) The set of all subgradients of Φ at η is called the subdifferential of Φ at η and is denoted by ∂Φ(η). The multivalued mapping ∂Φ : η → ∂Φ(η) is called the subdifferential of Φ, see [22]. A special convex function we employ is the indicator function. Let C be a closed, convex set, the indicator function is defined as We will also use the indicator function for points, e.g., I 0 (η) as the indicator function for η = 0. Given a control systemẋ = f (x, u), with state x ∈ R p and input u ∈ R q , and a function S(x) mapping R p to R, the directional derivative of S is denoted byṠ = ∂S ∂x f (x, u).

Network Optimization Theory
The objective of this paper is to study passivity-based cooperative control in the context of network optimization theory [2]. A network is described by a graph G = (V, E), consisting of a finite set of nodes, V = {v 1 , . . . , v |V| } and a finite set of edges, E = {e 1 , . . . , e |E| }, describing the incidence relation between pairs of nodes. Although we consider G in the cooperative control problem as an undirected graph, we assign to each edge an arbitrary orientation. The notation e k = (v i , v j ) ∈ E ⊂ V × V indicates that v i is the initial node of edge e k and v j is the terminal node. For simplicity, we will abbreviate this with k = (i, j), and write k ∈ E and i, j ∈ V. The incidence matrix E ∈ R |V|×|E| of the graph G with arbitrary orientation, is a {0, ±1} matrix with the rows and columns indexed by the nodes and edges of G such that [E] ik has value '+1' if node i is the initial node of edge k, '-1' if it is the terminal node, and '0' otherwise. This definition implies that for any graph, 1 E = 0, where 1 ∈ R |V| is the vector of all ones. We refer to the circulation space of G as the null space N (E), and the differential space of G as the range space R(E ); see [2]. Additionally, we call N (E ) the agreement space. Note that N (E ) ⊥ R(E) and N (E) ⊥ R(E ).
We call a vector µ = [µ 1 , . . . , µ |E| ] ∈ R |E| a flow of the network G. An element of this vector, µ k , is the flux of the edge k ∈ E. The incidence matrix can be used to describe a type of conservation relationship between the flow of the network along the edges and the net in-flow (or out-flow) at each node in the network, termed the divergence of the network G. The net flux entering a node must be equal to the net flux leaving the node. The divergence associated with the flow µ is denoted by the vector u = [u 1 , . . . , u |V| ] ∈ R |V| and can be represented as 1 Borrowing from electrical circuit theory, we call the vector y ∈ R |V| a potential of the network G. To any edge k = (i, j), one can associate the potential difference as ζ k = y j − y i ; we also call this the tension of the edge k. The tension vector ζ = [ζ 1 , . . . , ζ |E| ] , can be expressed as 2 Flows and tensions are related to potentials and divergences by the conversion formula µ ζ = −y u. Network theory broadly connects elements of graph theory to a family of convex optimization problems. The beauty of this theory is that it admits elegant and simple duality relations.
The optimal flow problem attempts to optimize the flow and divergence in a network subject to the conservation constraint (2). Each edge is assigned a flux cost, C f lux k (µ k ), and each node is assigned a divergence cost C div i (u i ), i.e., The problem (4) admits a dual problem with a very characteristic structure. To form the dual problem, one can replace the divergence u i and flow µ k variables in the objective functions with artificial variablesũ i andμ k , respectively, and introduce the artificial constraints u i =ũ i , µ k =μ k . These artificial constraints can be dualized with Lagrange multipliers y i and ζ k , respectively. The objective functions of the dual problem turn out to be the convex conjugates of the original cost functions, i.e., In the dual, the linear constraint ζ = E y must hold, such that is becomes an optimal potential problem We provide in the sequel an interpretation of cooperative control problems for a certain class of passive systems in the context of the network optimization theory.

Passivity-based Cooperative Control
The basic model involving networks of passive dynamical systems with diffusive couplings is now introduced. A new notion of passivity, called maximal equilibrium independent passivity, is presented and we demonstrate it to be a well-suited concept for cooperative control.

A Canonical Dynamic Network Model
Networks of dynamical systems defined on an undirected graph G = (V, E) are considered where each node represents a single-input single-output (SISO) system with state x i (t) ∈ R pi , input u i (t) ∈ R, output y i (t) ∈ R and constant external signal w i . In the following, we adopt the notation y(t) = [y 1 (t), . . . , y |V| (t)] and u(t) = [u 1 (t), . . . , u |V| (t)] for the stacked output and input vectors. Similarly, we use x(t) ∈ R |V| i=1 pi for the stacked state vector, w for the external signals and writė x = f (x, u, w), y = h(x, u, w) for the complete stacked dynamical system. To each edge k ∈ E, connecting two nodes i, j ∈ V, we associate the relative output ζ k (t) = y i (t) − y j (t). The relative outputs can be defined with the incidence matrix as The relative outputs ζ(t) drive dynamical systems placed on the edges of G that are of the form Figure 1: Block-diagram of the canonical passivity-based cooperative control structure.
The nonlinear output functions ψ k will be specified later on. The systems (8) will in the following be called controllers. The output of a controller Π k influences the two incident systems as The complete dynamical network (6), (7), (8), (9) is illustrated in Figure 1.
where χ i ∈ R is a dynamical state and N i is the set of neighbors of node i in G. If the nonlinear diffusive couplings ψ ij (χ j − χ i ) are realized by odd functions and ψ ij = ψ ji , then the system can be represented in the form (6), (7), (8), (9), with x i =χ. This model has evolved as a standard model, e.g., studied in [8], where passivity was identified as a central concept for convergence analysis.

Passivity as a Sufficient Condition for Convergence
A common theme in the existing literature is to exploit passivity properties of the dynamical systems for a convergence analysis. The convergence results can be traced back to well-known feedback theorems [23], and we review a basic convergence result here. From here on we use the notational convention that italic letters denote dynamic variables, e.g., y(t), and letters in normal font denote constant signals, e.g., y.
Assumption 3.3 There exist constant signals u, y, µ, ζ such that u = −Eµ, ζ = E y and i) each dynamic system (6) is output strictly passive with respect to u i and y i , i.e., there exists a positive semidefinite storage function S i (x i (t)) and a constant ρ i > 0 such thaṫ ii) each controller (8) is passive with respect to ζ k and µ k , i.e., there exists a positive semi-definite storage function W k (η k (t)) such thatẆ Now, the basic convergence result follows directly.
Proof: The passivity condition implies that One can bring |E| k=1Ẇ k to the left of the inequality and invoking Barbalat's lemma [23] to conclude convergence, i.e., lim t→∞ y(t) − y → 0.
The appeal of this convergence result is that it decouples the dynamical systems layer and the network layer. Only the input-output behavior must be shown to be passive to conclude convergence of the overall network.

Equilibrium Independent Passivity
A critical aspect of the previous result relates to the assumption on the existence of the constant signals u, y, µ, ζ that satisfy Assumption 3.3. The equilibrium configuration depends on the properties of all systems in the network and the desired passivity property cannot be verified locally. To overcome this issue, the concept of equilibrium independent passivity was introduced in [19]. Equilibrium independent passivity requires a system to be passive independent of the equilibrium point to which it is regulated.

Definition 3.5 ([19])
The system (6) is said to be (output strictly) equilibrium independent passive if there exists a set U i ⊂ R and a continuous function k x,i (u), defined on U i , such that i) for any constant signal u i ∈ U i the constant signal x i = k x,i (u i ) is an equilibrium point of (6), i.e., 0 = f i (x i , u i , w i ), and ii) the system is passive with respect to u i and y i = h i (k x,i (u), u i , w i ); that is, for each u i ∈ U i there exists a storage function such that the inequality (11) holds (with ρ i ≥ 0 for equilibrium independent passivity and ρ i > 0 for output-strictly equilibrium independent passivity).
The relevance of equilibrium independent passivity for the analysis of dynamical networks can be readily seen. If the systems (6) and (8) are output-strictly equilibrium independent passive and equilibrium independent passive, respectively, one has to verify only that an equilibrium trajectory exists in the respective sets to make the basic convergence proof of Theorem 3.4 applicable. The exact equilibrium point need not be known.
One important implication of equilibrium independent passivity is that the equilibrium input-output map must be monotone, and even co-coercive, if the system is output-strictly equilibrium independent passive, see [19].

Maximal Equilibrium Independent Passivity
While equilibrium independent passivity turns out to be an useful concept for network analysis, the given definition excludes some important systems. Consider for example a simple integrator, i.e.,ẋ It is well known that the integrator is passive with respect to U i = {0} and any output value y i ∈ R. 4 However, the equilibrium input-output map is not a (single-valued) function such that the integrator is not equilibrium independent passive, as defined in [19].
Motivated by this example, we propose here a refinement of equilibrium independent passivity. In particular, we do not require the equilibrium input-output maps k y,i to be functions, but instead allow them to be relations (or curves in R 2 ). That is, k y,i is the set of all pairs (u i , y i ) ∈ R 2 that are equilibrium input-output relations. The domain of the relation is the set U i , i.e., dom k y,i := U i . We will sometimes write k y,i (u i ) to denote the set of all y i such that (u i , y i ) ∈ k y,i . This gives an interpretation of k y,i (u i ) as set-valued map. For the integrator example described above, the equilibrium input output relation is the vertical line through the origin, i.e., k y,i = {(u i , y i ) : u i = 0, y i ∈ R}. For relations in R 2 we review the concept of maximal monotonicity.
Definition 3.6 ([2]) A relation k y,i is said to be maximally monotone if it cannot be embedded into a larger monotone relation. Equivalently, the relation k y,i is a maximal monotone relation if and only if We refer to [2] for a detailed treatment of maximal monotone relations. It is not difficult to see that the equilibrium input-output relation of the integrator system discussed above is maximally monotone. Based on this definition, a refined version of equilibrium independent passivity can be introduced. Please note that only SISO systems are considered in this paper and therefore the following definition applies only to SISO systems.
Definition 3.7 (Maximal equilibrium independent passivity) A dynamical SISO system (6) is said to be maximal equilibrium independent passive if there exists a maximal monotone relation k y,i ⊂ R 2 such that for all Furthermore, it is output-strictly maximal equilibrium independent passive if additionally there is a constant The new notion of maximal equilibrium independent passivity is closely related to the definition of [19]. In fact, any equilibrium independent system with U i = R is also maximal equilibrium independent passive. This includes in particular affine dynamical systemṡ that were shown in [19] to be output strictly equilibrium independent passive if they are output-strictly passive in the classical sense for w = 0 and if A is invertible. The equilibrium input-output relation is then the (single-valued) affine function (and thus a maximal monotone relation) k y (u) = −CA −1 B + D u + −CA −1 P + G w. Note that this is the dc-gain of the linear system plus the constant value determined by the exogenous inputs. The two definitions also both include scalar nonlinear systems of the forṁ However, the integrator is the central example of a system that is included in the new definition of maximal equilibrium independent passivity, but not in the original definition of [19].
In the following section, networks of the structure (6), (7), (8), (9) consisting of maximal equilibrium independent passive systems will be considered. It will be shown that these networks admit a certain inverse optimality, in the sense that they converge to the solutions of several dual pairs of network optimization problems of the form (4) and (5). This result establishes a connection between the new definition of passivity and convex network optimization theory.

Output Agreement Analysis
We now investigate the steady-state behavior of the dynamical network (6), (7), (8), (9) and characterize an associated inverse optimality for these systems. To prepare the following discussion, we introduce some additional notation. We will write k y (u) for the stacked input-output relations, that is y ∈ k y (u) means y i ∈ k y,i (u i ) for all i ∈ V. Similarly we will write U = U 1 × · · · × U |V| and Y = Y 1 × · · · × Y |V| to indicate the domain and range of k y (u).

The Plant Level
The first observation we make is that a steady-state of the network (6), (7), (8), (9) requires all systems to be in output agreement. Suppose that x and η are steady-state solutions of the network (6), (7), (8), (9), and let y be the corresponding steady-state output, then y = β1, for some β ∈ R, called the agreement value. Output agreement follows from the steady-state conditionη = 0, that requires y ∈ N (E ). As G is connected, y ∈ N (E ) is equivalent to y = β1 for some β.
The existence of an output agreement solution depends on properties of the nodes (6) and the network topology. In particular, the existence of an output agreement solution is related to the network equilibrium feasibility problem: A necessary condition for the existence of an output agreement solution is now the following.
Proof: The steady state condition for the plant and for the controller require y ∈ k y (u) and y ∈ N (E ), respectively. Additionally, the interconnection (9) implies that u(t) ∈ R(E), and consequently that u ∈ R(E).
To obtain further insights into the properties of an output agreement solution, we will next establish a connection to network optimization problems and show that certain duality relations hold. Therefore, some results relating maximal monotone relations and convex functions are recalled from [2]. A first observation is that one can extend any maximal monotone relation k y,i ⊂ R 2 with domain U i to a maximal monotone relation on R by setting it to −∞ for all u i 'left' of U i and +∞ for all u i 'right' of U i . 5 Now, we recall the following result of [22,Thm. 24.9] that holds for R: The subdifferential for the closed proper convex functions on R are the maximal monotone relations from R to R.
Thus, one can associate to any maximal monotone relation, and consequently to any maximal equilibrium independent passive system, a closed proper convex function K i : R → R that is unique up to an additive constant, such that If U i is not the complete R and the maximal monotone relation has been extended as described above, then K i (u i ) = +∞ for all u i / ∈ U i . If the equilibrium input-output relation is a continuous single-valued function from R to R then K i (u i ) is differentiable and ∇K i (u i ) = k y,i (u i ).
We will call K i (u i ) the cost function of the maximal equilibrium independent passive system i. Its convex conjugate, defined as in (1), i.e., K i (y i ) = sup ui {y i u i − K i (u i )}, is called the potential function of system i.
The steady-states of the dynamical network of maximal equilibrium independent passive systems are intimately related to the following pair of dual network optimization problems.
Optimal Flow Problem: Consider the the following optimal flow problem This problem is of the form of an optimal flow problem (4). The cost on the divergences (in/out-flows) u ∈ R |V| are the integral functions of the equilibrium input-output relations, i.e., C div i = K i , and the flows µ ∈ R |E| on the edges are not penalized, i.e., C f lux k = 0. Optimal Potential Problem: Dual to the optimal flow problem, we define the following optimal potential problem This problem is in the form (5). The convex conjugates of the integral functions of the equilibrium input-to-output maps are the costs for the potential variables y ∈ R |V| of the nodes, i.e., C pot i = K i . The constraint E y = 0 enforces a balancing of the potentials over the complete network. The problem can be written in the standard form (5), by choosing C ten k = I 0 , i.e., the indicator function for the point zero. To simplify the presentation, we will use the short-hand notation K(u) : The main result of this paper is that the the output agreement steady-states in a network of maximal equilibrium independent passive systems admit an inverse optimality.  7), (8), (9) has a steady-state solution u, y, then (i) u is an optimal solution to (OFP1), (ii) y is an optimal solution to (OPP1), and (iii) in the steady-state (OFP1) and (OPP1) have same value with negative sign, i.e., Proof: It is sufficient to show that the conclusions hold if the equilibrium problem (16) has a solution. If there is a solution u, y to (16), then u ∈ R(E) ∩ U, while y ∈ N (E ) ∪ Y. Thus, both optimization problem have a feasible solution and are finite. Consider now the Lagrangian function of (OFP1) with multiplierỹ, i.e., For u to be the a solution to (OFP1), it is necessary and sufficient that y ∈ ∂K(u) for the optimal multiplierỹ. Thus, since ∂K(u) = k y (u), the multiplier satisfiesỹ ∈ k y (u).
To conclude that u is an optimal solution, it remains to show that the equilibrium trajectory y is an optimal multiplier, i.e., y =ỹ. As y satisfies the equilibrium condition, it only remains to show thatỹ = N (E ). Let s(ỹ) = inf u,µ L(u, µ,ỹ). Now, ifỹ / ∈ N (E ) then s(ỹ) is unbounded below. Forỹ ∈ N (E ) it follows that s(ỹ) = −K (ỹ). Thus, the supremum problem is identical to (OPP1) with the negative objective function and both problems will have the same solution. Now, if the network equilibrium problem has a solution, than there must exists u and y satisfying the optimality conditions for the dual pair of optimization problems (OFP1) and (OPP1). Finally, as the steady-state solution is an optimal to both problems (OFP1) and (OPP1), it must be a saddle-point for the Lagrangian function, i.e., it must hold that Let now r(u, µ) = sup y L(u, µ, y). It follows that r(u, µ) = K(u) if u + Eµ = 0 and r(u, µ) = +∞ otherwise. Additionally, we have already seen that s(y) = inf u,µ L(u, µ, y) is s(y) = −K (y) if y ∈ N (E ) and s(y) = −∞ otherwise. For (19) to hold, the optimal solution u ∈ R(E) and y ∈ N (E ) must be such that K(u) + K (y) = 0. As shown before, the steady-states of the dynamic network are optimal solutions to (OFP1) and (OPP1) and must therefore satisfy the previous equality. The connection between the necessary condition for the existence of an agreement steady-state of the dynamical network and the dual pair of network optimization problems opens the way to use well-known tools form convex analysis for investigating the properties of output agreement steady-states in dynamic networks.
Corollary 4.4 (Existence) Suppose all node dynamics are maximal equilibrium independent passive with U i = R and Y i = R, then an output agreement steady-state exists.
Proof: Under the given assumption both optimization problems have a feasible solution and strong duality holds. The optimal primal-dual solution pair solves the equilibrium problem (16) and thus corresponds to a possible output agreement steady state.

Corollary 4.5 (Uniqueness)
If the dynamical systems (6) are maximal equilibrium independent passive with a nonempty U i and a strongly monotone equilibrium input-output function k y,i satisfying lim →∞ |k y,i (u )| → ∞ whenever u 1 , u 2 , ... is a sequence in U i converging to a boundary point of U i , then there exists at most one pair (u, y) that can be a steady-state solution.
Proof: From the assumptions follow that K i (u i ) are differentiable and essentially smooth convex functions (see [22, p. 251]). Thus, (OFP1) can have at most one solution. If such a solution exists, then the dual problem also has a solution.

Remark 4.7
The above results apply to networks of homogeneous or heterogeneous maximally equilibrium independent systems. For homogeneous systems, or more generally, for systems where the intersection of the equilibrium input-output maps k y,i is a single point, the solution to (OPP1) is simply that intersection point. This set-up is considered in various passivity-based cooperative control approaches such as [8], [10]. Thus, it is precisely the heterogeneous case, i.e., when the equilibrium input-output maps do not all intersect at the same point, 6 where the presented analysis methods give new insights and turn out to be a powerful network analysis tool.

The Control Level
It remains to investigate when the controller dynamics (8) can realize an output agreement steady-state. In particular, in the steady-state configuration, the controller (8) must generate a signal µ that corresponds to the desired control input. Suppose a solution u to (16) is known, then the controller must be such that the following static network equilibrium feasibility problem has a solution: Proof: If the equilibrium problems have a solution u, y, η, then u, y, µ = ψ(η) and ζ = 0 are a steady-state solution to (6), (7), (8), (9). Any steady-state solution u, y, µ, ζ of (6), (7), (8), (9) solves the two equilibrium problems with µ = ψ(η). Please note that the two equilibrium problems (16) and (21) are not independent. However, if (16) has a unique solution, (21) has no influence on the solution of (16).
As the required steady-state input u is in general not known for the controller design, it seems appropriate to design the controller such that (21) is feasible for any u ∈ R(E). Again, it will turn out that the feasibility of the network equilibrium problem is intimately related to maximal monotonicity. In particular, we show that (21) has a solution for all u ∈ R(E) if ψ k are strongly monotone functions.
Following this observation, we now assume that all ψ k are strongly monotone functions. Then, one can associate to each edge k ∈ E a closed, proper strongly convex function P k : R → R such that Lemma 4.9 Suppose the functions ψ k are strongly monotone, than the controller dynamics (8) is maximal equilibrium independent passive.
Proof: The equilibrium input set for the controller dynamics is solely ζ k = 0. However, the dynamics (8) is passive with respect to the input ζ k = 0 and any output µ k ∈ R. To see this, consider the storage function where η k is such that µ k = ∇P k (η k ). From strict convexity of P k follows directly that W k is a positive definite function. 7 Now, maximal passivity follows immediately froṁ where we used that ζ k = 0.
It will be shown next that that strong monotonicity of ψ k ensures the existence of an output agreement steadystate solution and that the steady-state solution has additional inverse optimality properties. To see this, consider the following pair of dual network optimization problems.
Optimal Potential Problem: Let some u = [u 1 , . . . , u |V| ] ∈ R(E) be given. Consider the following optimal potential problem By its structure, (OPP2) is an optimal potential problem as defined in (5). The potential vector v is associated to the linear cost defined by u, while the tension variables η are associated to the integral functions of the coupling nonlinearities.
Optimal Flow Problem: The dual problem to (OPP2) is the following optimal flow problem where P k is the convex conjugates of P k , and u ∈ R(E) is a given constant vector. The problem is in compliance with the standard form of optimal flow problems (4), as one can introduce artificial divergence variables and add as a cost function the indicator function for the point u. Then the network (6), (7), (8), (9) has an output agreement steady-state solution. Furthermore, let η be the steadystate of the controller in output agreement, then (i) η is an optimal solution to (OPP2), (ii) µ = ψ(η) is an optimal solution to (OFP2), (iii) and |E| k=1 P k (µ k ) + |E| k=1 P k (η k ) = µ η. 7 Note that W k is the Bregman distance associated to P k between η k (t) and η k , see [24].
Proof: To prove the first claim, it is sufficient to show that for any u ∈ R(E) the equilibrium problem (21) has a solution η. At first we note that if ψ k are strongly monotone, then P k are strongly convex and are defined on R. Thus, (OPP2) has a unique solution for all u ∈ R(E). To prove the first claim, it remains to connect the solution of (OPP2) to the equilibrium condition (21). Any solution η = E v in (OPP2) must satisfy the first-order optimality condition where we use the short-hand notation P = |E| k=1 P k . Since ∇P = ψ, the optimal solution η = E v to (OPP2) solves explicitly the equilibrium condition (21), proving the first claim. Now, to prove the remaining statements of the theorem, we consider the Lagrangian of (OPP2), i.e., with multiplierμ. Define now the dual function as s(μ) = inf v,η L(v, η,μ). Clearly, s(μ) = −∞ if Eμ + u = 0, and otherwise s(μ) = −P k (μ). Thus, the dual problem sup s(μ) is equivalent to (OFP2) and the dual solutioñ µ is in fact the optimal solution to (OFP2). Together with the first order optimality condition this implies that µ =μ = ∇P(η) = ψ(η). The last statement, i.e., the strong duality, follows since it must hold that This implies that supμ s(μ) must take the same optimal value as (OPP2). The statement follows now immediately since supμ s(μ) has the same value as (OFP2) with negative sign, and u v = −µ η, where µ is the optimal solution to (OFP2).
The two optimization problems provide, on the one hand, explicit statements about the feasibility of the steadystate independent of the required u, and, on the other hand, additional duality relations. The internal state of the controller (8), η(t), can be understood as tensions, while the output of the controller, µ(t), can be understood as the corresponding dual flows.
Remark 4.11 (Sector Nonlinearities) An alternative assumption that is often imposed on the nonlinearities ψ k in the literature (as, e.g., in [10]) is that they are sector nonlinearities (see, e.g., [23,Def. 6.2]). The strong monontonicity condition is clearly a stronger assumption. 8 However, the dynamics (8) with a sector nonlinearity ψ k that is not strongly monotone is not necessarily maximally equilibrium independent passive and it cannot be guaranteed that for any required steady-state input u the controller dynamics (8) is passive with respect to the required steady-state. Thus, in order to ensure convergence of the network without knowing u in advance, the strong monotonicity assumption becomes a necessary requirement.

The Closed-Loop Perspective
Having established conditions that ensure the existence and the optimality properties of an output agreement steady-state solution, it remains to prove convergence. 8 After shifting the origin appropriately, a strongly monotone nonlinearity is always a sector nonlinearity.

Dynamic Signal
Network Variable Relation Cost Function Optimization Problem y(t) system output y potential y = k y (u)
Proof: The assumptions ensure that the four network optimization problems (OFP1), (OPP1), (OPP2), and (OFP2) have an optimal solution. Thus, a steady-state solution exists. Output-strictly maximal equilibrium independent passivity of the node dynamics ensures that for all i ∈ V there exists a storage function S i such thaṫ Additionally, maximal equilibrium independent passivity of the controller dynamics ensures that for all k ∈ E there exists a storage function W k satisfyingẆ k ≤ (µ k (t) − µ k )(ζ k (t) − ζ k ). Thus, the basic convergence result of Theorem 3.4 applies directly, proving convergence of the output trajectories, i.e., lim t→∞ y(t) → y. Since y ∈ k y (u), it follows that u(t) must converge to u. The convergence of µ(t) and ζ(t) to µ and ζ, respectively, follows immediately.
We can summarize the results of this section as follows. All signals of the dynamical network (6), (7), (8), (9) have static counterparts in the network optimization theory framework. The static counterparts of the outputs y(t) are the solutions y of an optimal potential problem (OPP1). Equivalently, the corresponding dual variables, i.e., divergence variables in (OFP1), u, are the static counterparts to the control inputs u(t). The controller state η(t) and the output µ(t) have the tension and flow variables of (OPP2) and (OFP2), respectively, as their static counterparts. We visualize the connection between the dynamic variables of the closed-loop system and the static network variables in Figure 2. Note that the signals in the dynamical system influence each other in a closedloop structure, while there is no equivalent closed-loop relation for the network variables. In particular, the two tension variables ζ and η are not connected, while their dynamic counterparts ζ(t) and η(t) are connected by an integrator. Additionally, a summary of all variables involved in the output agreement problem together with their static counterparts is provided in Table 1. For the sake of completeness, we include also the dynamic variable v(t), which corresponds to the potential variables v of (OPP2). Although we did not consider v(t) explicitly in our discussion of the dynamical network, we can define it in accordance to (OPP2) as η(t) = Ev(t).

A General Dynamic Network Analysis Framework
The full potential of the established duality framework can be seen if more general networks of maximal equilibrium independent passive systems are considered. A key component in the analysis of the previous section was that the controller dynamics (8) were maximal equilibrium independent passive systems. We will generalize the previous results for controllers that are arbitrary maximal equilibrium independent passive systems. In particular, we assume now that the controllers (8) are replaced by dynamical systems of the form Assumption 5.1 The controllers (23) are maximal equilibrium independent passive with input set Z k , output set M k , and maximal monotone input-output relation γ k ⊂ R 2 .
To each of the dynamics (23) one can associate now a closed, proper, convex function Γ k : R → R such that Now, the formalism developed in the previous section can be generalized as the asymptotic behavior of the network (6), (7), (23), (9) can be related to the following pair of dual network optimization problems.
Generalized Optimal Flow Problem Consider the following optimal flow problem where Γ k denotes the convex conjugate of Γ k . This is a generalized version of (OFP1). Still the divergence u are associated to the cost functions defined by the integral of the nodes input-output relations. However, now the cost function Γ k is associated to the flow variables µ k . Generalized Optimal Potential Problem Dual to the generalized optimal flow problem, we also define the generalized optimal potential problem as In contrast to (OPP1), this problem does not necessarily force the potential differences, i.e., the tensions, to be zero, but penalizes them with the general cost functions Γ k .
The general network optimization problems (GOFP) and (GOPP) are related to the asymptotic behavior of the network of maximal equilibrium independent passive systems.
Proof: First, we show that if the two network optimization problems have a feasible solution, this solution represents an equilibrium for the dynamical network. Consider again the Lagrangian function of (GOFP) with Lagrange multiplierỹ, i.e., Define nowζ = E ỹ. If (GOFP) has an optimal solution, this solution satisfies the optimality conditions where we use the notation Γ (µ) = |E| k=1 Γ k (µ k ). Since Γ(ζ) = |E| k=1 Γ k (ζ k ) is a closed convex function it follows from the inversion of the subgradients (i.e., [22,Thm. 23.5]) that ∂Γ (µ) is equivalent to µ ∈ ∂Γ(ζ). Thus, if (GOFP) has an optimal primal solution and dual solution, then these solutions are an equilibrium configuration of the dynamical network. To complete this part of the proof, it remains to show thatỹ andζ are optimal solutions to (GOPP). Define s(ỹ,ζ) = inf u,µ L(u, µ,ỹ) withζ = E ỹ. Clearly, s(ỹ,ζ) Since Γ k = Γ k it can be readily seen that an optimal solution to infỹ ,ζ s(ỹζ) is an optimal solution to (GOPP). Thus, optimal solutions to (GOFP), (GOPP) are equilibrium configurations for the network. By the same argument follows that all possible network equilibrium configurations are solution to (GOFP), (GOPP).
It remains to prove convergence. Consider an network equilibrium configuration u, y, µ, and ζ. By assumption, the node dynamics are output strictly maximal equilibrium independent passive and since (GOFP), (GOPP) are feasibel u ∈ U and y ∈ Y. All controllers are maximal equilibrium independent passive and since (GOFP), (GOPP) are feasible, µ ∈ M, and ζ ∈ Z. Convergence of the trajectories follows now from the basic convergence result.

Remark 5.3 (Revisiting Output Agreement)
The general result includes the output agreement problem studied in the previous section. There, the equilibrium input-output relation γ k of the controller (8) is the vertical line through the origin, such that Γ k is the indicator function for the origin. Its convex conjugate is Γ k (µ) = 0. Now, (GOFP) and (GOPP) reduce to the original problems (OFP1) and (OPP1).

Application: Analysis of a Traffic Dynamics Model
The potential of the proposed network optimization interpretation is now illustrated on the analysis of a nonlinear traffic dynamics models. The considered model is an optimal velocity model, as proposed in [25], [26], with the following assumtions: (i) the drivers are heterogeneous and have different "preferred" velocities, (ii) the influence between cars is bi-directional, and (iii) vehicles can overtake other vehicles. Each vehicle adjusts its velocity v i according tov where κ i > 0 is a constant and the adjustment V i (∆p) depends on the relative position to other vehicles, i.e., ∆p = p j − p i , as Here N (i) is used to denote the neighboring vehicles influencing vehicle i. Throughout this example we assume that the set of neighbors to a vehicle is not changing over time. The constants V 0 i > 0 are "preferred velocities" and V 1 i > 0 are "sensitivities" of the drivers. In the following we assume V 0 i = V 0 j (i.e., heterogeneity). The model can be represented in the form (6), (7), (9), (23). The node dynamics can be identified aṡ with the velocity v i (t) being the node state. The input to each vehicle computes as u i (t) := j∈N (i) tanh(p j (t)− p i (t)). The relative velocities of neighboring vehicles are ζ(t) = E y. Now, sinceṗ i = v i , we can define the relative positions of neighboring vehicles as η k (t) = p j (t) − p i (t), where edge k connects nodes i and j. In vector notation, the coupling can be represented asη and u = −Eµ, where tanh(·) is here the vector valued function with each entry being the tanh of the respective entry of η. The node dynamics are output strictly maximal equilibrium independent passive systems. The equilibrium input-output map is the affine function k y,i (u i ) = V 0 i + V 1 i u i and a corresponding storage function is where v i is the desired constant velocity. The objective functions associated to the node dynamics are the quadratic functions Next, we show that the controller dynamics (29) is maximal equilibrium independent passive. Note that the output functions of (29) are monotone but bounded. The dynamics (29) will only attain a steady state for ζ = 0. However, if ζ = 0, the outputs will not grow unbounded, but will approach the saturation bounds of the nonlinearity. Thus, each of the coupling dynamics has the equilibrium input-output relation It can be easily verified that γ k represents a maximal monotone relation in R 2 . To prove now maximal equilibrium independent passivity, we define the integral functions of the coupling nonlinearities, i.e., P k (η k ) = ln cosh(η k ).
Note that the functions P k are not strongly convex, as they asymptotically approach an affine function. The function P k , the coupling nonlinearity ψ k (η k ) = tanh(η k ), and the convex conjugate P k (µ k ) are illustrated in Figure 3. The function P k can now be used to prove maximal equilibrium independent passivity.
Proposition 6.1 Each of the dynamics (29) is maximal equilibrium independent passive with equilibrium input output relation (31).
In the network optimization interpretation are the potential variables the velocities, i.e., v i , and the divergence variables are the influence of the other vehicles. Furthermore, the tensions are the relative positions of the vehicles and the flows are their mapping through the coupling functions. To complete the network theoretic interpretation of the traffic dynamics model, we define the integral function of the input output relation γ k . The integral function of γ k (ζ k ) is the absolute value of ζ k and its convex conjugate is the indicator function for the set [−1, 1], i.e., Γ k (ζ k ) = |ζ k |, Γ k (µ k ) = I [−1,1] (µ k ).   Thus, for the traffic dynamics, the two network optimization problems (GOFP) and (GOPP) take a very characteristic structure. The optimal flow problem (GOFP) is almost identical to (OFP1), except that additionally constraints on the flow variables are imposed, i.e., the flows are constrained as −1 ≤ µ k ≤ 1. On the other hand, the optimal potential problem (GOPP) has a quadratic cost function for the potentials plus an additional absolute value of the potential differences, that can be understood as an 1 -penalty. Remark 6.2 (Network Clustering) The connection of the presented results to the network clustering analysis presented in [17] can be explained on the traffic dynamics. In [17] a saddle-point problem is proposed to analyze and predict an asymptotic clustering behavior. The saddle-point problem of [17] for the traffic dynamics studied here (using the notation of this paper) is Some straight forward manipulations reveal that the saddle-point problem results in fact from the Lagrange dual of (GOPP) for the traffic dynamics model. The saddle point problem involves variables from the two dual network optimization problems, i.e., the potential variables y i and the flow variables µ k . It has been shown in [17] that the solutions to the saddle-point problem eventually have a clustered structure. Thus, one might expect a clustering behavior to happen in the traffic dynamics model and this behavior can in fact be observed in the simulations. We refer to [17] for a detailed treatment of the clustering phenomenon.
We present a computational study with 100 vehicles placed on a line graph in Figure 4. The sensitivity parameter is κ = 0.6 for all vehicles, while the parameters V 0 i and V 1 i are chosen as a common nominal parameter plus a random component, i.e., V 0 i = V 0 nom + V 0 i,rand . The common off-set is V 0 nom = 25 m s and V 1 = 10 m s . The random component is chosen according to a zero mean normal distribution with different standard deviations. In Figure 4 (left), the time-trajectories of the velocities v i are shown with the random coefficients V 0 i,rand , V 1 i,rand chosen from a distribution with σ 0 = 2.5 and σ 1 = 1, respectively. Figure 4 (right) shows the asymptotic velocity distribution of the traffic for different choices of the standard deviation σ 0 . While for σ 0 = 1 the traffic agrees on a common velocity, already for σ 0 = 2.5 a clustering structure of the network can be seen. The clustering structure becomes more refined for σ 0 = 4. We have chosen for all studies σ 1 = 1. Please note that the novel network theoretic framework provides us with efficient tools to analyze and predict the non-trivial asymptotic behavior of the nonlinear traffic dynamics, without the need to simulate the system for different parameter configurations.

Conclusions
We have established in this paper an intimate connection between passivity-based cooperative control and the network optimization theory of Rockafellar [2]. To obtain this connection, we introduced the notion of maximal equilibrium independent passivity as a variation of the equilibrium independent passivity concept of [19]. It was shown that dynamical networks involving maximal equilibrium independent passive systems asymptotically approach the solutions of several network optimization problems. For output agreement problems we have shown that it is a necessary condition that the output agreement steady-state is optimal with respect to an optimal flow and an optimal potential problem. This connection provided also an interpretation of the system outputs as potential variables, and of the system inputs as node divergence. Similar inverse optimality and duality results are established for general networks of maximal equilibrium independent passive systems, that do not necessarily converge to output agreement. The general theory was illustrated on a nonlinear traffic dynamics model that shows asymptotically a clustering behavior. As maximal equilibrium independent passive systems admit a certain inverse optimality and a strong duality, the presented results suggest that networks consisting of those systems are "well-behaved" and "easy" to be analyzed. We believe that this result contributes to a unified understanding of networked dynamical systems and opens the way for further advanced analysis methods.