Distributed Optimization Method Based On Optimal Control

The communication graph is denoted by a directed graph $\mathcal{G=(V,E,A)}$, where $\mathcal{V}=\{1,2,\ldots,n\}$ is a set of vertices(nodes), $n$ is the number of agents satisfying $n\geq 2$, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges, and the weighted matrix $\mathcal{A}=(a_{ij})_{n\times n}$ is a non-negative matrix for adjacency weights of edges, $a_{ij}\neq 0$ if and only if $(i,j)\in\mathcal{E}$. The graph $\mathcal{G}$ is said to be balanced if the sum of the interaction weights from agent $j$ to agent $i$ are equal, i.e., $\sum\limits_{j=1}^{n}a_{ij}=\sum\limits_{j=1}^{n}a_{ji},\forall i\in\mathcal{V}$. Moreover, $\mathcal{N}_{i}=\{j\in\mathcal{V}|{(i,j)}\in\mathcal{E}\}$ is used to represent the neighbor set of agent $i$. For the topology $\mathcal{G=(V,E,A)}$, a path of length $r$ from node $i_{1}$ to node $i_{r}+1$ is a sequence of $r+1$ distinct nodes ${\{i_{1}\ldots,i_{r}+1\}}$ such that $(i_{q},i_{q}+1)\in\mathcal{E}$ for $q=1,\ldots,r$. If there exists a path between any two nodes, then $\mathcal{G}$ is said to be strongly connected. Here we make the following assumptions for the communication graph.

Noting that in the distributed coordination control, conditions in Assumption 1 play important roles in ensuring multi-agent systems (MAS) to reach consensus [7] [15].

Consider an MAS consisting of $n$ agents with optimization problem, labeled by set $\mathcal{V}=\{1,\dots,n\}$ where agents communicate the local state information with their neighbors via directed graph $\mathcal{G}$. Only agent $i\in\mathcal{V}$ knows the function $f_{i}:{\mathbb{R}^{n}}\to\mathbb{R}$, which is twice continuously differentiable, possibly non-convex. The traditional unconstrained optimization problem is given by

Different from the traditional distributed optimization method, we transform the task of finding solutions to problem (1) into updating of the state sequence within an optimal control problem. To be specific, consider the following discrete-time linear time-invariant system for each agent

where $x_{i}(k)\in R^{n}$ is state with the initial value $x(0)$, $u_{i}(k)\in R^{n}$ is the control input which needs to be further specified later. The $i$ represents the $i$th agent, $i\in{\{1,2,\dots n\}}$.

Correspondingly, the cost function of each agent satisfies

with $e_{ij}(k)=x_{i}(k)-x_{j}(k)$ where $Q_{i}\geq 0$, $H_{i}\geq 0$ and $R_{i}>0$.

Based on the discussion above, we are in position to derive the distributed optimization algorithm from the viewpoint of the optimal control. For convenience of future discussion, some symbols are denoted below.

Let $\delta_{i}(k)$ be the errors set of the $i$th agent, then $e(k)=[\delta^{T}_{1}(k),...,\delta^{T}_{n}(k)]$. In this way, we have

where $B_{i}$ is the column vector composed by $0,1,-1$, satisfying $B=[B_{1},...,B_{n}]$ and $B^{T}B=L$ is a Laplacian matrix. To this end, (2) and (3) can be written with expanded forms as

and

respectively. The optimal control problem to be solved in this section is given.

Problem: Find the optimal control $u(k)$ minimizing the long-term cost $J_{N}$ and subject to (7).

Following from [18], applying Pontryagins maximum principle to the system (7) with the cost function (8), the following costate equation and equilibrium condition are obtained:

with the terminal value ${\lambda(N)}=B^{T}He(N+1)+\nabla f(N+1)$, where $\nabla f(k)=[\nabla f_{1}(x_{1}(k),...,\nabla f_{n}(x_{n}(k)))]^{T}$.

To derive the analytical solution from the FBDEs (7), (9)- (10), define the Riccati equation

with the terminal value ${P(N+1)}=H$, where ${\Gamma(k)}=R+B^{T}P(k+1)B$.

The analytical expression to the controller is given.

Before proposing an algorithm based on optimal control obtained in Lemma 1, we first show an interesting phenomenon: the controller (12) derived from optimal control theory utilizes the average value of the derivative of each agent’s local function, referred to as the “average gradient” hereafter. That is to say, the matrix $M(l)$ has the property of taking the average value, which is proved below. It should be noted that distributed optimization algorithms that employ the average gradient have been explored in [19]. Our derived results theoretically demonstrate the rationality and correctness of adopting average gradient. The property of $M(l)$ defined in Lemma 1 is given below.

Lemma 2 indicates that (12) utilizes the average gradient. For the sake of simplifying notation, we will denote the average gradient as $g(l)$, i.e., $g(l)=M(l)\nabla f(l)$.

In this subsection, we discuss the distributed optimization algorithm derived based on Lemma 1, which includes a centralized algorithm and a decentralized algorithm.

Based on optimal control theory, we have derived a distributed optimization algorithm (19) with a central computing node (in computer science, it is called as $parameter\ server$ [21] and we use this expression in Algorithm 1). The algorithm presented in Algorithm 1 is called the Distributed Optimal Control Method with a Central Computing Node (DOCMC). Now, we summarize the DOCMC algorithm from the perspective of each agent $i$.

Utilizing the state error $e_{ij}$ with neighbors can significantly enhance the computational stability of the server. In fact, if each agent adopts the same state, then (21) will be utilized in DOCMC. However, when the states of each agent cannot be guaranteed to be consistent due to communication processes or the influence of individual agents, relying solely on (21) may not be sufficient to achieve the optimization goals. The existence of $e_{ij}$ ensures that each agent can achieve the optimization goals even when their states are not consistent (whether due to initially different states or deviations during the optimization process), as the algorithm incorporates an optimal consensus feedback control form based on $e_{ij}$.

Next, we will focus on describing the distributed optimization algorithm. Firstly, reconsidering the DOCMC algorithm, the existence of $(\Gamma_{P}+h(k))^{-1}$ is a primary reason why the algorithm requires a server. Motivated by our recent work [22], which replaced the inverse matrix with an adjustable scalar $\eta>0$, in the DOCMC algorithm, $(\Gamma_{P}+h(k))^{-1}$ will be replaced by $\eta>0$ in the following discussion. Due to the relationship $(\Gamma_{P}+h(k))^{-1}\Gamma_{P}=I-(\Gamma_{P}+h(k))^{-1}h(k)$ based on (19), we propose the following algorithm

where the second-order information $h(k)$ is used in algorithm (22) on account of the optimization framework of optimal control. We refer to the above algorithm as the Distributed Optimization Algorithm based on Optimal Control (DOAOC).

Now, a distributed optimization algorithm for each agent $i$ to handling problem (1) from the DOAOC algorithm is given, referring to Algorithm 2 for details. In the proposed distributed algorithm, as described in Steps 3 and 4, each agent only communicates with its neighbors. Step 5 initializes the loop by computing the initial $\overline{d}^{0}_{i}(k)$. Different from [22], Step 7 only requires each agent to calculate $\overline{d}^{t+1}_{i}(k)$ independently.

In this subsection, we discuss the compelling characteristics of DOCMC and DOAOC and some simplification techniques in practical use , which are summarized as follows:

• •

  Many distributed optimization methods commonly used in machine learning, including frameworks like TensorFlow, employ distributed algorithms with a central computing node. When considering a star network (master-slave network) structure [21] in the DOCMC algorithm (where $e_{ij}$ does not occur as each agent independently exchanges information with the server), simplification can be achieved using (21), where $g(k)$ represents the average derivative and $h(k)$ directly represents $\frac{1}{n}\sum\limits_{i=1}^{n}\nabla^{2}f_{i}(x_{i}(k))$.

• •

  To obtain the average gradient, Step 3 in Algorithm 2 is necessary. In practical applications, after evaluating the performance of the agents, a suitable consensus protocol can be chosen: if agents have ample memory, memory-intensive consensus protocols like the DSF algorithm [24] can be employed; if agents have limited memory, a finite-time average consensus protocol [25] can be used; and in cases where agent performance is poor, traditional consensus protocols [7] [20] can still be applied. $h_{i}(k)$ in DOAOC algorithm can be obtained not only through the above consensus protocol but also can be approximated by first-order derivative difference. In fact, in our recent work [23], Algorithm III utilizes a first-order derivative difference method to obtain the Hessian matrix.