Sage Journals: Discover world-class research

Abstract

This paper studies the distributed convex optimization problem, where the global utility function is the sum of local cost functions associated to the individual agents. Only using the local information, a novel continuous-time distributed algorithm based on proportional-integral-differential (PID) control strategy is proposed. Under the assumption that the global utility function is strictly convex and local utility functions have locally Lipschitz gradients, the exponential convergence of the proposed algorithm is established with undirected and connected graph among these agents. Finally, numerical simulations are presented to illustrate the effectiveness of theoretical results.

Keywords

Distributed convex optimization proportional-integral-differential exponential convergence

Introduction

Recent years have witnessed an increasing interest in distributed optimization and its widely applications in various fields, including energy internet, intelligent manufacturing and machine learning.^1–4 The aim of distributed optimization problem is to minimize global objective function with a sum of individual objective function, which computes and exchanges information among neighboring agents. The research on distributed optimization can be traced back to the pioneering work^5,6 and then many valuable algorithms for this topic have been proposed, which can mainly be classified as discrete-time algorithm and continuous-time algorithm.

The discrete-time algorithm has attracted much attention since the distributed gradient descent (DGD) algorithm was proposed by Nedić and Ozdaglar.⁷ But, due to the diminishing step-size, the convergence rate of DGD algorithm was slow. Then, Shi et al.⁸ proposed an exact first-order algorithm (EXTRA) with fixed step-size, which converges to the optimal solution precisely. In order to eliminate the requirement of the double random weight matrix, the push-sum algorithm under the directed graph was proposed by Nedić and Olshevsky.⁹ And then, the combination of push-sum protocol and distributed subgradient algorithm were proposed for unconstrained distributed optimization problem in the directed time-varying topology.^10–12 By introducing projection operator, various distributed projection algorithms for constrained distributed optimization problem were proposed in Lou et al.,¹³ Lin et al.,¹⁴ Liu et al.,^15,16 Wang et al.,¹⁷ and Liang et al.¹⁸ To deal with equality and inequality constraints, Chang et al.¹⁹ proposed the consensus-based distributed primal-dual perturbation (PDP) algorithm, which was applied to smooth inequality constraints and non-smooth constraints. For the case of non-smooth optimization problems, a smooth double proximal primal-dual algorithm was present in Wei et al.²⁰ Moreover, without convexity assumptions on the objectives, a chebyshev proxy and consensus-based algorithm (CPCA) was given in He et al.,²¹ which had low computational costs.

As a counterpart, much attention has also been paid to the continuous-time algorithm. Several distributed optimization algorithms with the single integrator dynamics were proposed in Lin et al.,²² which considered state-dependent gradient gains and nonuniform gradient gains. Considering second-order multi-agent networks, a double-integrator distributed optimization algorithm under the undirected graph was presented in Zhang and Hong.²³ Based on the Karush-Kuhn-Tucker condition and the saddle point property, a new distributed algorithm for constrained optimization was developed in Yi et al.²⁴ With impulsive communication framework, an average quasi-consensus algorithm for distributed constrained optimization was designed in He et al.²⁵ In order to reduce communication costs and energy consumption, the event-triggered control idea was introduced to design the distributed optimization algorithm. In Chen and Ren,²⁶ the event-triggered zero-gradient-sum algorithm was established. In Li et al.,²⁷ distributed optimization algorithm with event-triggered communication via input feedforward passivity was presented, and the event-triggered distributed fixed-time optimization algorithm over a directed network was developed in Yu et al.²⁸

Due to the progressive control techniques, various of algorithms based on proportional-integral (PI) control strategy for distributed optimization have attracted an increasing attention recently. Wang and Elia²⁹ proposed a distributed optimization algorithm based on PI control strategy, where each agent used an auxiliary state to correct the error caused by different local gradient. Based on PI control strategy, a continuous-time coordination algorithm with discrete-time communication was investigated in Kia et al.,³⁰ which can reduce communication costs and energy consumption. Combining projection output feedback with PI protocol, the distributed convex optimization subject to general constraints was studied in Yang et al.³¹ It is well known that proportional-integral-derivative (PID) control strategy is a classic control approach, which has simple structures, clear physical meaning of parameters, and strong robustness. Thus, it has been applied in various fields, such as, active disturbance rejection control (ADRC),³² formation control,³³ and so on. But, to the best knowledge of ours, the PID control strategy for distributed optimization problem has not been discussed.

Based on the above discussions, a new continuous-time algorithm with PID control strategy for distributed optimization under an undirected communication graph is studied in this paper. The main contributions of this paper are as follows. (I) The PID algorithm is firstly presented for distributed optimization, where each agent uses only local information, that is, the proposed algorithm is fully distributed. (II) Using the matrix transform and the inequality technique, the exponential convergence and the estimation for convergence rate of the proposed algorithm are established under the assumption that the global utility functions are strictly convex and local utility functions have locally Lipschitz gradients. (III) The constriction on the initial value is removed, which has less conservation than that in Zhang and Hong²³ and Kia et al.³⁰

The remainder of this paper is organized as follows. Section 2 is devoted to mathematical preliminaries on distributed optimization problem. The continuous-time distributed PID algorithm and its convergence are presented in Section 3. Numerical examples are given to illustrate the performance of the proposed algorithms in Section 4. Finally, conclusions are drawn in Section 5.

Notations: Let $R^{n}$ be the n-dimensional real vector space. ‖·‖ denotes the Euclidean norm or induced matrix norm for a vector or a matrix. ⊗ is the matrix Kronecker product. $I_{n}$ is the identity matrix in $R^{n \times n}$ . $0_{N}$ and $1_{N}$ represent the column vectors with $N$ zeros and ones, respectively. det(·) is the determinant of a matrix.

Preliminaries

Graph theory

A weighted undirected graph is a triplet $G = (V, E, A)$ , where $V = {v_{1}, \dots, v_{N}}$ is a vertex set, $E \in V \times V$ is an undirected edge set, and $A = {a_{ij}}_{N \times N}$ is an adjacency matrix with nonnegative elements $a_{ij}$ , where $a_{ij} > 0$ if and only if $(v_{i}, v_{j}) \in E$ , otherwise $a_{ij} = 0$ . We assume that there is no self-loops, that is, $a_{ii} = 0$ for all $i \in V$ . The degree of node $i$ is defined by $d_{i} = \sum_{j = 1}^{N} a_{ij}$ . The Laplacian of graph $G$ is defined as $L_{N} = D - A$ , where $D = diag {d_{1}, \dots, d_{N}}$ .

An undirected edge $e_{ij}$ in graph $G$ is denoted by the unordered pair of nodes $(v_{i}, v_{j})$ , which means that nodes $v_{i}$ and $v_{j}$ can exchange information with each other and $A$ is a symmetric matrix. A path between nodes $v_{i}$ and $v_{j}$ in graph $G$ is a sequence of edges $(v_{i}, v_{i 1}), (v_{i 1}, v_{i 2}), . . ., (v_{ik}, v_{j})$ in the graph with distinct nodes $v_{il} \in V$ . An undirected graph $G$ is connected if there exists a path between any pair of distinct nodes $v_{i}$ and $v_{j}$ $(i, j = 1, 2, . . ., N)$ . $L_{N}$ has a simple zero eigenvalue and all the other eigenvalues are positive if and only if the graph $G$ is connected, and the eigenvalues of $L_{N}$ can be ordered as $0 = λ_{1} < λ_{2} \leq \dots \leq λ_{N}$ .

Problem formulation

Consider a network of $N$ agents and each agent has a local private differentiable function $f^{i} (x) : R^{n} \to R$ . The communication topology among agents is described by an undirected graph $G$ . The following convex optimization problem will be studied.

\min_{x \in R^{n}} f (x) = \sum_{i = 1}^{N} f^{i} (x) .

(1)

The global utility function $f (x) = \sum_{i = 1}^{N} f^{i} (x)$ is assumed to be strictly convex, that is,

(x - y)^{T} (\nabla f (x) - \nabla f (y)) > 0, \forall x, y \in R^{n} and x \neq y .

(2)

Moreover, a function $f (x) : R^{n} \to R$ is Lipschitz with constant $m > 0$ if

‖ f (x) - f (y) ‖ \leq m ‖ x - y ‖, \forall x, y \in R^{n},

(3)

and for each $i \in V$ , the gradient of $f^{i} (x)$ is $l_{i}$ -Lipschitz if

‖ \nabla f^{i} (x) - \nabla f^{i} (y) ‖ \leq l_{i} ‖ x - y ‖, \forall x, y \in R^{n} .

(4)

In this paper, we focus on designing a distributed proportional-integral-differential (PID) algorithm such that each agent obtains the global minimizer $x^{*} \in (- \infty, \infty)$ of the feasible optimization problem

x^{*} = \arg min_{x \in R^{n}} f (x)

(5)

only using its own and its neighbors’ information.

Distributed PID algorithm

In this section, we propose a distributed PID algorithm and obtain the convergence result.

For each agent $i \in {1, \dots, N}$ , the distributed PID algorithm for the problem (1) is described as follows.

\begin{matrix} {\overset{\cdot}{x}}^{i} = v^{i} \\ {\overset{\cdot}{v}}^{i} = - a \sum_{j = 1}^{N} a_{ij} (x^{i} - x^{j}) - b \sum_{j = 1}^{N} a_{ij} (v^{i} - v^{j}) \\ - c \sum_{j = 1}^{N} a_{ij} (y^{i} - y^{j}) - k \nabla f^{i} (x^{i}) \\ {\overset{\cdot}{y}}^{i} = a^{2} k \sum_{j = 1}^{N} a_{ij} (x^{i} - x^{j}), \end{matrix}

(6)

where $x^{i}, v^{i}, y^{i} \in R^{n}$ represent position, velocity, and the auxiliary state of the $i$ th agent, respectively, $x^{i}$ is a solution to problem (1) for agent $i$ . Positive constants $a, b, c > 0$ are the proportional parameter, differential parameter, integral parameter, respectively. $k > 0$ is the constant stepsize.

Denote $\tilde{f} (x) = \sum_{i = 1}^{N} f^{i} (x^{i})$ , $x = ((x^{1})^{T}, \dots, (x^{N})^{T})^{T} \in R^{Nn}$ , $v = ((v^{1})^{T}, \dots, (v^{N})^{T})^{T} \in R^{Nn}$ , $y = ((y^{1})^{T}, \dots, (y^{N})^{T})^{T} \in R^{Nn}$ , $\nabla \tilde{f} (x) = {(\nabla f^{1} {(x^{1})}^{T}, \dots, \nabla f^{N} {(x^{N})}^{T})}^{T} \in R^{N n} .$ Then, the algorithm (6) can be rewritten as the following compact form

\begin{matrix} \overset{\cdot}{x} = v \\ \overset{\cdot}{v} = - aL x - bL v - cL y - k \nabla \tilde{f} (x) \\ \overset{\cdot}{y} = a^{2} kL x \end{matrix},

(7)

where $L = L_{N} \otimes I_{n}$ .

Lemma 1. Suppose the communication topology $G$ is undirected and connected, the equilibrium point of system (7) is the optimal solution of problem (1).

Proof. Since the communication graph is undirected and connected, we have $1_{N}^{T} L_{N} = 0$ .

Assume that $(x^{*}, v^{*}, y^{*})$ is the equilibrium point of system (7), we have

\begin{matrix} v^{*} = 0_{Nn} \\ - aL x^{*} - bL v^{*} - cL y^{*} - k \nabla \tilde{f} (x^{*}) = 0_{Nn} \\ a^{2} kL x^{*} = 0_{Nn} \end{matrix}

(8)

Since $G$ is connected, there is a $x^{*} \in R^{n}$ such that

x^{*} = 1_{N} \otimes x^{*} .

Next, it will be shown that $x^{*}$ is the optimal solution of problem (1). Multiply $(1_{N} \otimes I_{n})^{T}$ on the both sides of the second equation in (8), one can derive that

(1_{N} \otimes I_{N})^{T} \nabla \tilde{f} (x^{*}) = 0,

and then

\sum_{i = 1}^{N} \nabla f^{i} (x^{*}) = 0,

which implies $x^{*}$ is the optimal solution of problem (1).

The proof is completed.

Theorem 1. Assume that the communication topology $G$ is connected and the global utility function $f (x)$ is strictly convex. The local utility function is continuously differentiable and its gradient is $l_{i}$ -Lipschitz on $R^{n}$ . Then, with the PID algorithm (6), where $a, c > 0$ , $b > ack$ , and $k > 0$ is bounded, $x^{i} (t)$ exponentially converges to the global minimizer $x^{*}$ for each $i \in V$ with any initial values.

Proof. Without loss of generality, for simplicity, let $n = 1$ . The case for $n > 1$ can also be proved by the property of Kronecker product only with complex computation.

Let $\tilde{x} = x - x^{*}, \tilde{v} = v - v^{*}, \tilde{y} = y - y^{*}$ . Then, (7) can be rewritten in the following matrix form

\overset{\cdot}{X} (t) = AX (t) - G_{1} (t),

(9)

where $X = (\begin{matrix} \tilde{x} \\ \tilde{v} \\ \tilde{y} \end{matrix}),$ $A = [\begin{matrix} 0_{N} & I_{N} & 0_{N} \\ - a L_{N} & - b L_{N} & - c L_{N} \\ a^{2} k L_{N} & 0_{N} & 0_{N} \end{matrix}]$ , $G_{1} (t) = [\begin{matrix} 0_{N} \\ k \cdot g (t) \\ 0_{N} \end{matrix}],$ $g (t) = \nabla \tilde{f} (\tilde{x} + x^{*}) - \nabla \tilde{f} (x^{*}) .$

Denote $E = [- 1_{N - 1} I_{N - 1}]$ and $M_{1} = diag {E E E}$ . Let $Y (t) = M_{1} X (t)$ , in term of (9), we have

\overset{\cdot}{Y} (t) = BY (t) - G_{2} (t),

(10)

where

\begin{matrix} B = [\begin{matrix} 0_{N - 1} & I_{N - 1} & 0_{N - 1} \\ - a {\tilde{L}}_{N - 1} & - b {\tilde{L}}_{N - 1} & - c {\tilde{L}}_{N - 1} \\ a^{2} k {\tilde{L}}_{N - 1} & 0_{N - 1} & 0_{N - 1} \end{matrix}], \\ {\tilde{L}}_{N - 1} = L_{22} - 1_{N - 1} \cdot η^{T}, \end{matrix}

\begin{matrix} L_{22} = [\begin{matrix} d_{2} & - a_{23} & \dots & - a_{2 N} \\ - a_{32} & d_{3} & \dots & - a_{3 N} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - a_{N 2} & - a_{N 3} & \dots & d_{N} \end{matrix}], η = [\begin{matrix} - a_{12} \\ ⋮ \\ - a_{1 N} \end{matrix}], \\ G_{2} (t) = [\begin{matrix} 0_{N - 1} \\ k \cdot E \cdot g (t) \\ 0_{N - 1} \end{matrix}] . \end{matrix}

Since the communication topology $G$ is connected, it is clear that all the eigenvalues of ${\tilde{L}}_{N - 1}$ , that is, $λ_{2}, λ_{3}, . . ., λ_{N}$ are positive. Moreover, there is an invertible matrix $S$ such that $S^{- 1} {\tilde{L}}_{N - 1} S = J$ . Thus, all the eigenvalues of $J$ are positive.

Let $M_{2} = diag {S^{- 1} S^{- 1} S^{- 1}}$ and $Z (t) = M_{2} Y (t)$ . Then, it follows from (10) that

\overset{\cdot}{Z} (t) = MZ (t) - G (t),

(11)

where

M = [\begin{matrix} 0_{N - 1} & I_{N - 1} & 0_{N - 1} \\ - aJ & - bJ & - cJ \\ a^{2} kJ & 0_{N - 1} & 0_{N - 1} \end{matrix}], G (t) = [\begin{matrix} 0_{N - 1} \\ k \cdot S^{- 1} \cdot E \cdot g (t) \\ 0_{N - 1} \end{matrix}] .

Assume $θ$ is an eigenvalue of $M$ . Then

\begin{matrix} \det (θ I_{3 (N - 1)} - M) = | \begin{matrix} θ I_{N - 1} & - I_{N - 1} & 0_{N - 1} \\ aJ & θ I_{N - 1} + bJ & cJ \\ - a^{2} kJ & 0_{N - 1} & θ I_{N - 1} \end{matrix} | \\ = | - I_{N - 1} | \cdot | \begin{matrix} θ^{2} I_{N - 1} + b θ J + aJ & cJ \\ - a^{2} kJ & θ I_{N - 1} \end{matrix} | \\ = 0 . \end{matrix}

(12)

If $θ = 0$ , that is, $0$ is one of the eigenvalues of $M$ . According to the Laplace theorem for a partitioned matrix, by (12), we have $\det (J) = 0$ , which contradicts with that all the eigenvalues of $J$ are positive. Thus, recall (12), we have

| θ^{2} I_{N - 1} + b θ J + aJ + \frac{a^{2} ck}{θ} J^{2} | . | θ I_{N - 1} | = 0 .

It follows that

| θ^{2} I_{N - 1} + b θ J + aJ + \frac{a^{2} ck}{θ} J^{2} | = 0,

that is

| \begin{matrix} θ^{3} + b θ^{2} λ_{2} + a θ λ_{2} + a^{2} ck λ_{2}^{2} & * & * & * \\ θ^{3} + b θ^{2} λ_{3} + a θ λ_{3} + a^{2} ck λ_{3}^{2} & * & * \\ ⋱ \\ θ^{3} + b θ^{2} λ_{N} + a θ λ_{N} + a^{2} ck λ_{N}^{2} \end{matrix} | = 0 .

Thus, there is at least a $i \in {2, \dots, N}$ such that

θ^{3} + b θ^{2} λ_{i} + a θ λ_{i} + a^{2} ck λ_{i}^{2} = 0 .

(13)

Denote $θ = θ_{1} + \sqrt{- 1} θ_{2}$ , where $θ_{1}, θ_{2} \in R$ . Then

{\begin{matrix} θ_{1}^{3} - 3 θ_{1} θ_{2}^{2} + b λ_{i} (θ_{1}^{2} - θ_{2}^{2}) + a λ_{i} θ_{1} + a^{2} ck λ_{i}^{2} = 0 \\ - θ_{2}^{3} + (3 θ_{1}^{2} + 2 b λ_{i} θ_{1} + a λ_{i}) θ_{2} = 0 \end{matrix} .

(14)

Case 1: $θ_{2} = 0$ , which implies that

θ_{1}^{3} + b λ_{i} θ_{1}^{2} + a λ_{i} θ_{1} + a^{2} ck {λ_{i}}^{2} = 0 .

(15)

Thus, by the Routh-Hurwitz theorem, $θ_{1} < 0$ .

Case 2: $θ_{2} \neq 0$ . It follows from (14) that

8 θ_{1}^{3} + 8 b λ_{i} θ_{1}^{2} + (2 a λ_{i} + 2 b^{2} λ_{i}^{2}) θ_{1} + ab λ_{i}^{2} - a^{2} ck λ_{i}^{2} = 0 .

(16)

Since $b > ack$ , by the Routh-Hurwitz theorem, $θ_{1} < 0$ .

Thus, all the eigenvalues of $M$ are located at the open left half plane. Then, it is clear that there exist constants $μ > 0$ and $α > 0$ such that

‖ e^{M (t - t_{0})} ‖ \leq μ e^{- α (t - t_{0})}, t \geq t_{0} .

(17)

Noticing (11), by the variation of parameter formula, we have

Z (t) = e^{M (t - t_{0})} Z (t_{0}) + \int_{t_{0}}^{t} e^{M (t - s)} G (s) ds,

and then

‖ Z (t) ‖ \leq ‖ e^{M (t - t_{0})} ‖ \cdot ‖ Z (t_{0}) ‖ + \int_{t_{0}}^{t} ‖ e^{M (t - s)} ‖ ‖ G (s) ‖ ds .

(18)

According to (4), it can be obtained that

\begin{matrix} ‖ G (s) ‖ = ‖ - k \cdot S^{- 1} \cdot E \cdot ((\nabla \tilde{f} (\tilde{x} + x^{*}) - \nabla \tilde{f} (x^{*})) ‖ \\ \leq kl ‖ S^{- 1} \cdot E ‖ \cdot ‖ \tilde{x} (s) ‖, \end{matrix}

(19)

where $l$ is the maximum value of $l_{i} (i = 1, \dots, N)$ . By (17–19), it follows that

\begin{matrix} ‖ Z (t) ‖ \leq μ e^{- α (t - t_{0})} ‖ Z (t_{0}) ‖ + μ kl ‖ S^{- 1} \cdot E ‖ \\ \cdot \int_{t_{0}}^{t} e^{- α (t - s)} ‖ \tilde{x} (s) ‖ ds \\ \leq μ e^{- α (t - t_{0})} ‖ Z (t_{0}) ‖ + μ kl ‖ S^{- 1} \cdot E ‖ \\ \cdot ‖ E^{- 1} \cdot S ‖ \int_{t_{0}}^{t} e^{- α (t - s)} ‖ Z (s) ‖ ds \\ = μ e^{- α (t - t_{0})} ‖ Z (t_{0}) ‖ + μ klq \int_{t_{0}}^{t} e^{- α (t - s)} ‖ Z (s) ‖ ds, \end{matrix}

(20)

where $q = ‖ S^{- 1} \cdot E ‖ \cdot ‖ E^{- 1} \cdot S ‖$ .

Now, for any $m > 1$ and $γ \in (0, α)$ , it will be proved that

‖ Z (t) ‖ < m μ ‖ Z (t_{0}) ‖ e^{- γ (t - t_{0})} : = h (t), t \geq t_{0} .

(21)

If (21) does not hold, by continuity, there must exist a $t^{*} > t_{0}$ such that $‖ Z (t^{*}) ‖ = h (t^{*})$ and $‖ Z (t) ‖ < h (t)$ for $t \in [t_{0}, t^{*}) .$ Then, by (20), we can obtain

\begin{matrix} h (t^{*}) = ‖ Z (t^{*}) ‖ \leq μ ‖ Z (t_{0}) ‖ e^{- α (t^{*} - t_{0})} \\ + μ klq \int_{t_{0}}^{t^{*}} e^{- α (t^{*} - s)} ‖ Z (s) ‖ ds \\ < m μ ‖ Z (t_{0}) ‖ e^{- α (t^{*} - t_{0})} + μ klq \int_{t_{0}}^{t^{*}} e^{- α (t^{*} - s)} ‖ Z (s) ‖ ds \\ < m μ ‖ Z (t_{0}) ‖ e^{- α (t^{*} - t_{0})} + \frac{m μ klq}{α - γ} ‖ Z (t_{0}) ‖ ( \\ e^{- γ (t^{*} - t_{0})} - e^{- α (t^{*} - t_{0})}) \\ = m μ ‖ Z (t_{0}) ‖ \\ {e^{- α (t^{*} - t_{0})} + \frac{klq}{α - γ} (e^{- γ (t^{*} - t_{0})} - e^{- α (t^{*} - t_{0})})} . \end{matrix}

(22)

For $k \leq \frac{α - γ}{lq}$ , we have

h (t^{*}) = ‖ Z (t^{*}) ‖ < m μ ‖ Z (t_{0}) ‖ e^{- γ (t^{*} - t_{0})} \leq h (t^{*}) .

(23)

The contradiction in (23) shows that (21) is valid for any $m > 1$ . Let $m \to 1$ , one has

‖ Z (t) ‖ \leq μ ‖ Z (t_{0}) ‖ e^{- γ (t - t_{0})}, t > t_{0},

(24)

which implies that $Z (t)$ can exponentially converge to 0, that is, $x^{i} (t) \to x^{*}$ as $t \to \infty$ , for all $i \in {1, \dots, N}$ , and the convergence rate is estimated by $γ$ .

The proof is completed.

Numerical simulations

In the following, the proposed PID distributed algorithm is illustrated by some numerical simulations. We assume that there are six agents in the undirected and connected communication graph, which is described as Figure 1.

Case 1: All local cost functions are convex.

Figure 1.

Communication graph.

Assume that $f^{i} (x) = x^{T} P_{i} x + b_{i} x + c_{i}$ , $i = 1, 2, \dots, 6$ , $x \in R^{2}$ , where

\begin{matrix} P_{1} = [\begin{matrix} 0.2 & 0.1 \\ 0.1 & 20 \end{matrix}], P_{2} = [\begin{matrix} 4 & 0.2 \\ 0.2 & 0.4 \end{matrix}], P_{3} = [\begin{matrix} 0.3 & 1 \\ 1 & 2 \end{matrix}], \\ P_{4} = [\begin{matrix} 5 & 0.1 \\ 0.1 & 20 \end{matrix}], P_{5} = [\begin{matrix} 0.7 & 1 \\ 1 & 0.2 \end{matrix}], P_{6} = [\begin{matrix} 9 & 0.1 \\ 0.1 & 0.1 \end{matrix}], \end{matrix}

$b_{1} = [\begin{matrix} 1 & 8 \end{matrix}], b_{2} = [\begin{matrix} 10 & 1 \end{matrix}], b_{3} = [\begin{matrix} 3 & 1 \end{matrix}], b_{4} = [\begin{matrix} 50 & 12 \end{matrix}], b_{5} = [\begin{matrix} 4 & 2 \end{matrix}], b_{6} = [\begin{matrix} 70 & 13 \end{matrix}]$ , and $c_{1} = 1, c_{2} = 0.2, c_{3} = 3, c_{4} = 0.4, c_{5} = 5, c_{6} = 6$ . The optimal solution of $x^{*} = \arg min_{x \in R^{2}} f (x)$ , where $f (x) = \sum_{i = 1}^{6} f^{i} (x)$ can be given explicitly by $x^{*} = - \frac{1}{2} (\sum_{i = 1}^{6} P_{i})^{- 1} (\sum_{i = 1}^{6} b_{i})^{T} = [- 3.5645 - 0.2246]^{T}$ .

Let $a = 1, b = 15, c = 1, k = 1$ . Based on Theorem 1, the state $x^{i}$ of each agent $i (i = 1, \dots, 6)$ will converge to the global optimal solution of the objective function $f (x) = \sum_{i = 1}^{6} f^{i} (x)$ for any initial values. The numerical simulation results using distributed PID algorithm (6) are depicted in Figures 2 to 4, which show that $x^{i} \to [- 3.5645 - 0.2246]^{T}$ , ${\overset{\cdot}{x}}^{i} \to 0$ , and the global cost function converges to the optimal value $- 234.5056$ .

Figure 2.

The trajectory of state in Case 1 with algorithm (6).

Figure 3.

The trajectory of velocity in Case 1 with algorithm (6).

Figure 4.

The trajectory of cost function in Case 1 with algorithm (6).

In order to show the advantage of PID algorithm, the numerical simulation based on PI algorithm, that is, let $b = 0$ in (6), is shown in Figure 5, which shows that the state $x^{i}$ of each agent $i (i = 1, \dots, 6)$ can not converges to the global optimal solution.

Case 2: Some of the local cost functions are non-convex.

Figure 5.

The trajectory of state in Case 1 with PI algorithm.

Assume that $f^{1} (x) = \sin (x - \frac{π}{2})$ , $f^{2} (x) = - \cos (\ln (x^{2} + 2) - 0.2)$ , $f^{3} (x) = (x + 0.3)^{2} + e^{0.3 x}$ , $f^{4} (x) = 0.2 e^{- 0.2 x} + 0.4 e^{0.4 x}, f^{5} (x) = x^{2} (l n (x^{2} + 0.5)) + x^{2}, f^{6} (x) =$ $\frac{x^{2}}{\sqrt{x^{2} + 6}}$ , $x \in R$ , and $f (x) = \sum_{i = 1}^{6} f^{i} (x)$ , which was discussed in Wu et al.³⁴ Note that the local functions of agents 1 and 2 are non-convex. It can be verified the strict convexity of the global cost function, which ensures the uniqueness of the optimal solution. Assume that the initial values are randomly selected. Then, the simulation results are presented in Figures 6 to 8 with $a = 1, b = 15, c = 1, k = 1$ , which show that $x^{i} \to - 0.14272$ , ${\overset{\cdot}{x}}^{i} \to 0$ , and the global cost function converges to the optimal value $1.7159$ .

Figure 6.

The trajectory of state in Case 2 with algorithm (6).

Figure 7.

The trajectory of velocity in Case 2 with algorithm (6).

Figure 8.

The trajectory of cost function in Case 2 with algorithm (6).

Conclusions

In this paper, a continuous-time PID algorithm is proposed for solving the distributed optimization problem, where the global utility function is strictly convex and local utility functions have locally Lipschitz gradients. Using matrix transform and inequality technique, the exponential convergence of the proposed algorithm is established with undirected and connected graph. The estimation of the convergence rate is also given. It should be pointed out that this paper only consider the undirected communication graph and ideal communication. The directed communication graph andevent-triggered PID control for distributed convex optimization will be discussed in future study.

Footnotes

Acknowledgements

The authors would like to thank the Associate Editor and reviewers for their insightful comments and suggestions based on which the presentation of this paper has been greatly improved.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported partly by National Natural Science Foundation of China under Grant No. 61673080, 61876200 partly by the Science and Technology Research Program of Chongqing Municipal Education Commission under Grant KJZD-K202000601, partly by Natural Science Foundation of Chongqing under Grant cstc2019jcyj-msxmX0102, partly by Venture & Innovation Support Program for Chongqing Overseas Returnees under Grant cx2017099.

ORCID iD

Wei Zhu

References

Boyd

Parikh

Chu

, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 2010; 3(1): 1–122.

Huang

Wang

Yang

, et al. A neurodynamic-based distributed energy management approach for integrated local energy systems. Int J Electr Power Energy Syst 2021; 128: 106737.

Gao

, et al. Double-mode energy management for multi-energy system via distributed dynamic event-triggered Newton-Raphson algorithm. IEEE Trans Smart Grid 2020; 11(6): 5339–5356.

Huang

Liu

Zhang

, et al. Distributed optimal economic dispatch for microgrids considering communication delays. IEEE Trans Syst Man Cybern Syst 2019; 49(8): 1634–1642.

Tsitsiklis

. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.

Nagumey

. Book review: parallel and distributed computation: numerical methods. Int J Supercomput Appl 1989; 3(4): 73–74.

Nedić

Ozdaglar

. Distributed subgradient methods for multi-agent optimization. IEEE Trans Autom Control 2009; 54(1): 48–61.

Shi

Ling

, et al. Extra: an exact first-order a lgorithm for decentralized consensus optimization. SIAM J Optim 2015; 25(2): 944–966.

Nedić

Olshevsky

. Distributed optimization over time-varying directed graphs. IEEE Trans Autom Control 2015; 60(3): 601–615.

10.

Nedic

Olshevsky

. Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans Autom Control 2016; 61(12): 3936–3947.

11.

Nedić

Olshevsky

Shi

. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J Optim 2017; 27(4): 2597–2633.

12.

Nedic

Olshevsky

Shi

, et al. Uribe. Geometrically convergent distributed optimization with uncoordinated step-sizes. In: Proceedings of the American control conference, St. Louis, MO, USA, pp.3950–3955, 2017.

13.

Lou

Shi

Johansson

, et al. Approximate projected consensus for convex intersection computation: convergence analysis and critical error angle. IEEE Trans Autom Control 2014; 59(7): 1722–1736.

14.

Lin

Ren

Song

. Distributed multi-agent optimization subject to nonidentical constraints and communication delays. Automatica 2016; 65: 120–131.

15.

Liu

Qiu

Xie

. Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica 2017; 83: 162–169.

16.

Liu

Yang

Hong

. Constrained consensus algorithms with fixed step size for distributed convex optimization over multi-agent networks. IEEE Trans Autom Control 2017; 62(8): 4259–4265.

17.

Wang

Lin

Ren

, et al. Distributed subgradient-based multiagent optimization with more general step sizes. IEEE Trans Autom Control 2018; 63(7): 2295–2302.

18.

Liang

Wang

Yin

. Distributed smooth convex optimization with coupled constraints. IEEE Trans Autom Control 2020; 65(1): 347–353.

19.

Chang

Nedić

Scaglione

. Distributed constrained optimization by consensus-based primal-dual perturbation method. IEEE Trans Autom Control 2014; 59(6): 1524–1538.

20.

Wei

Fang

Zeng

, et al. A smooth double proximal primal-dual algorithm for a class of distributed nonsmooth optimization problem. IEEE Trans Autom Control 2018; 65(4): 1800–1806.

21.

Chen

, et al. CPCA: a chebyshev proxy and consensus based algorithm for general distributed optimization. In: 2020 American control conference (ACC), Denver, CO, USA, pp.94–99, 2020.

22.

Lin

Ren

Farrell

. Distributed continuous-time optimization: nonuniform gradient gains, finite-time convergence, and convex constraint set. IEEE Trans Autom Control 2017; 62(5): 2239–2253.

23.

Zhang

Hong

. Distributed optimization design for high-order multi-agent systems. In: Chinese control conference, CCC, Hangzhou, China, pp.7251–7256, 2015.

24.

Hong

Liu

. Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Syst Control Lett 2015; 83: 45–52.

25.

Huang

, et al. Average quasi-consensus algorithm for distributed constrained optimization: impulsive communication framework. IEEE Trans Cybern 2020; 50(1): 351–360.

26.

Chen

Ren

. Event-triggered zero-gradient-sum distributed consensus optimization over directed networks. Automatica 2016; 65: 90–97.

27.

Liu

. Distributed optimization with event-triggered communication via input feedforward passivity. IEEE Control Syst Lett 2021; 5(1): 283–288.

28.

Jiang

, et al. Distributed fixed-time optimization for multi-agent systems over a directed network. Nonlinear Dyn 2021; 103(1): 775–789.

29.

Wang

Elia

. Control approach to distributed optimization. In: 2010 48th annual allerton conference on communication, control, and computing, allerton 2010, Monticello, Va, USA, pp.557–561, 2010.

30.

Kia

Cortés

Martínez

. Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Automatica 2015; 55: 254–264.

31.

Yang

Liu

Wang

. A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Trans Autom Control 2017; 62(7): 3461–3467.

32.

Han

. From PID to active disturbance rejection control. IEEE Trans Ind Electron 2009; 56(3): 900–906.

33.

Qin

Zhou

. Distributed proportion-integration-derivation formation control for second-order multi-agent systems with communication time delays. Neurocomputing 2017; 267: 271–282.

34.

Ding

, et al. Distributed continuous-time optimization with scalable adaptive event-based mechanisms. IEEE Trans Syst Man Cybern Syst 2020; 50(9): 3252–3257.

Distributed convex optimization via proportional-integral-differential algorithm

Abstract

Keywords

Introduction

Preliminaries

Graph theory

Problem formulation

Distributed PID algorithm

Numerical simulations

Conclusions

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References