Privacy-preserving distributed optimization algorithm for directed networks via state decomposition and external input

1.   Introduction

Distributed optimization, as a core technology for solving large-scale problems in networked systems, has received widespread attention in recent years. By decomposing the global problem into local sub-problems of each agent and achieving the overall optimal solution by coordination, its algorithm design includes gradient descent, dual decomposition technology, and the alternating direction multiplier method (ADMM). These methods have been successfully applied in fields such as smart grids, communication networks, and machine learning due to their excellent parallelism and convergence ^[1,2,3]. In addition, in order to adapt to dynamic environments, researchers have proposed dynamic consistency optimization methods to cope with changes in network topology and data distribution ^[4,5]. At the same time, the scalability and security issues of distributed optimization in large-scale computing have also become the focus of research ^[6,7].

Distributed optimization is widely applied, especially in fields such as energy, machine learning, healthcare, and communications. In smart grids, it optimizes energy management by distributed resource allocation and load scheduling, improving system's efficiency and resilience ^[8,9,10,11]. In machine learning, distributed optimization provides parallelization support for large-scale model training, significantly improves computing efficiency, and especially shows great potential in the field of federated learning ^[12,13,14]. In addition, medical imaging and diagnostics have also benefited from the introduction of distributed optimization technologies that not only improve data processing capabilities but also ensure the security of patients' data with privacy-preserving algorithms ^[15,16]. In the field of the Internet of Things (IoT), distributed optimization technology is widely used in resource allocation and dynamic routing decisions, providing strong support for efficient communication ^[17,18]. The study of ^[19] alleviates the network congestion and bandwidth utilization issues caused by the quality of service queuing mechanism and denial of service attacks by introducing new compression rules, and develops an intelligent trigger controller supervised by the mini-batch machine learning algorithm. These application examples fully demonstrate that distributed optimization has wide applicability and strong theoretical support.

However, the communication characteristics of distributed optimization bring significant privacy risks, especially in scenarios involving sensitive data such as medical, financial, and user behavior modeling. Differential privacy technology effectively improves the anonymity of data by injecting noise during the optimization process while minimizing the impact on the model's performance ^[20,21]. Existing research has proven that using differential privacy mechanisms in distributed optimization can significantly reduce the risk of data leakage while maintaining computational efficiency ^[22,23]. The authors of ^[24] designed a distributed algorithm based on the direction and state perturbation. This algorithm achieves differential privacy by perturbing the state variables and directions with attenuated Laplacian noise. The authors of ^[25] proposed a new algorithm for decentralized non-convex optimization. This algorithm can simultaneously achieve strict differential privacy and the avoidance of saddle points/maxima. Some studies also combine local differential privacy and global differential privacy methods to further optimize the privacy protection effect ^[26,27,28]. However, the added noise may prevent the agents from converging to an exact solution. Homomorphic encryption technology ensures the security of the entire optimization process by allowing calculations to be performed directly on encrypted data ^[29,30]. The authors of ^[31] proposed a privacy-preserving decentralized optimization method based on the alternating direction method of multipliers and partial homomorphic encryption technology. The authors of ^[32] proposed a new algorithm through homomorphic encryption technology. This algorithm can achieve secure multi-party computation with complete correctness. Compared with differential privacy, homomorphic encryption has unique advantages in high-security scenarios, but has the problem of higher computational cost.

In addition to the two methods above, ^[33] developed a new privacy protection method, namely state decomposition. The main idea of the state decomposition method is to decompose the state of each agent into an actual state and a virtual state. The actual state interacts with other agents normally to exchange information, while the virtual state is unknown to the outside world, thereby protecting the real data of the agent from being accessed. This method has been widely used in the field of privacy protection; for example, ^[34] proposed a state decomposition method that can privately achieve average consensus without any trustworthy neighbor agents. Moreover, ^[35] proposed a privacy-preserving push-sum method for directed networks. However, when using the push-sum algorithm, each agent needs to maintain two state values, which will increase the communication overhead. In this paper, on the basis of the state decomposition method, we study the privacy-preserving distributed optimization problem on a directed graph. The contributions of this paper are summarized as follows.

1) The privacy-preserving algorithm is proposed, which is based on state decomposition for the distributed optimization problem on a directed graph. In this algorithm, the initial state of each agent is decomposed into two sub-states: the actual state and the virtual state. The actual state is used for information exchange between agents, while the virtual state is only used for internal information exchange and is unknown to the outside world.

2) Many existing distributed optimization algorithms applied to directed graphs use the push-sum algorithm. They decompose the state of the agent into two states for iteration, and finally take the ratio of these two states as the true value. The problem with this is that it will increase the communication burden of the system, so we did not use the push-sum algorithm, but introduced external input during the iteration process.

3) We also demonstrate that the algorithm can protect the private information of agents from being obtained by malicious external eavesdroppers or honest but curious neighbors.

The remaining part of this paper is structured as follows. Section 2 presents some preliminaries. Section 3 is our main results, where the algorithm is proposed and the proof is given. In Section 4, a numerical example is illustrated. Finally, a brief conclusion is given in Section 5.

Notations: Let ${\bf 1}_d$ and ${\bf 0}_d$ be the $d$-dimensional all-one vector and all-zero vector, respectively. $\mathbb{R}^d$ is the set of $d$-dimensional real numbers. $I_d$ and $O_d$ denote the $d\times d$-demensional identity matrix and all-zero matrix, respectively. Given a matrix $X$, the element located at the $i$-th row and $j$-th column of the matrix is represented by $X_{ij}$. We use the notation $\rho(A)$ to stand for the spectral radius of matrix $A$. A matrix $A$ is referred to as row-stochastic or column-stochastic when the sum of all elements in each row or each column amounts to $1$, and all the entries of $A$ are non-negative. The symbol $\otimes$ represents the Kronecker product, while ${\left\| \cdot \right\|_2}$ represents the $\ell_2$-norm.

2.   Preliminaries

2.1.   Graphs

We consider a directed graph ${\cal G} = ({\cal V}, {\cal E}, A)$ which comprises $n$ agents. Here, ${\cal V} = \{1, 2, \ldots, n\}$ stands for the set of agents and ${\cal E}\subset{\cal V}\times{\cal V}$ represents the set of edges. The adjacency matrix $A = \left[{{a_{ij}}} \right]$ indicates the coupling weights, where ${a_{ij}} > 0$ if there is an edge from $i$ to $j$, that is, $(i, j) \in \mathcal{E}$, and ${a_{ij}} = 0$ otherwise. When we use $(j, i) \in {\cal E}$, it implies that there is a communication link enabling agent $i$ to transmit information to Agent $j$. The agents capable of directly sending information to Agent $i$ are referred to as the in-neighbors of Agent $i$, and the collection of such agents is denoted as ${\cal N}_i^ - = \{ j \in {\cal V}|(i, j) \in {\cal E}\}$. Likewise, the agents that can directly receive messages from agent $i$ are called the out-neighbors of Agent $i$, and the set of these agents is denoted as ${\cal N}_i^ + = \{ j \in {\cal V}|(i, j) \in {\cal E}\}$.

2.2.   Problem formulation

Consider an optimization issue within a multiagent system that consists of $n$ agents. Every single agent possesses a private cost function $f_i$, and this function is known solely to Agent $i$. The common objective of all the agents involved is to minimize a global objective function

where $x$ is the global decision variable.

The subsequent assumptions concerning the objective function and the graph are provided, which will be utilized for deriving the main results.

Assumption 1. (Connectivity): The directed graph ${\cal G}$ is strongly connected.

Assumption 2. (Strong convexity): The global objective function, f, is $\mu$-strongly convex, i.e.,

for any ${\bf x}$ and ${\bf y} \in {\mathbb{R}^d}$, where $\mu > 0$.

Given Assumption 2, Problem (2.1) possesses a sole optimal solution, ${x^*}\in {\mathbb{R}^d}$.

Assumption 3. (Smoothness): The gradient of each $f_i$ is $L$-Lipschitz continuous, i.e., for any ${\bf x}$ and ${\bf y} \in {\mathbb{R}^d}$,

2.3.   State decomposition method

The state decomposition method was initially proposed in ^[33]. The core concept of this method is to decompose the initial state $x_{i, 0}$ of each agent into two sub-states, denoted $x_{i, 0}^\alpha$ and $x_{i, 0}^\beta$ respectively, as shown in Figure 1. The values of the sub-states $x_{i, 0}^\alpha$ and $x_{i, 0}^\beta$ can be any real numbers, yet they must satisfy the equation $x_{i, 0}^\alpha + x_{i, 0}^\beta = 2 x_{i, 0}$. After decomposition, the sub-state $x_{i, 0}^\alpha$ assumes the role that the original state $x_{i, 0}$ played in the interactions among agents. The other sub-state $x_{i, 0}^\beta$ does not engage in the information exchange among neighboring agents. Instead, it only communicates with $x_{i, 0}^\alpha$. For instance, consider Agent $i$ in Figure 1(b). In the interactions between agents, $x_i^\alpha$ behaves exactly like $x_i$, while $x_i^\beta$ is hidden from all agents except Agent $i$, even though it has an impact on the evolution of $x_i^\alpha$.

3.   Main results

Within this part, we put forward a privacy-preserving algorithm for directed graphs via state decomposition and external input. In addition, we also provide the convergence analysis and privacy analysis.

3.1.   Privacy-preserving algorithm

After the state decomposition, the update equation becomes

The coupling weights between the two substates $x_{i, k}^\alpha$ and $x_{i, k}^\beta$ are not symmetric. They are denoted $\alpha_i$ and $\beta_i$ respectively. The update weight for the substate $x_{i, k}^\beta$ is designated as $p_{ii}$. The weight of the outgoing link from Agent $j$ to Agent $i$ is represented by $a_{ij}$.

Definition 1. ^[36] (Minimal polynomial of a matrix): For matrix $P$, its minimal polynomial is denoted as $Q(t)$, which is expressed as $Q(t) = t^{D + 1} + \sum_{i = 0}^D \omega_i t^i$. Here, $Q(t)$ is a monic polynomial. It has the minimum degree of $D + 1$ and satisfies the condition that when we substitute the matrix $P$ into $Q(t)$, we get $Q(P) = 0_n$. In this polynomial, $\omega_i$ represents the coefficients.

Definition 2. ^[36] (Minimal polynomial of a matrix pair): For the object $[P, e_i^T]$, there is an associated minimal polynomial, which we denote as $Q_i(t)$. It is given by the expression $Q_i(t) = t^{D_i + 1} + \sum_{i = 0}^{D_i} \omega_{i, j}t^i = 0$, where the coefficients $\omega_{i, j}$ belong to the set of real numbers $\mathbb{R}$. This $Q_i(t)$ is a monic polynomial. It has the minimum degree of $D_i + 1$ and fulfills the condition that when we perform the operation $e_i^T Q_i(P)$, the result is 0.

On the basis of the analysis of ^[36], we let ${x_{2k}^\alpha } = \left[{x_{i, 1}^\alpha, x_{i, 2}^\alpha, \ldots, x_{i, 2k + 1}^\alpha } \right]^T$. In addition, we define the Hankel matrix and the difference vectors as follows:

In ^[36], a distributed termination mechanism was put forward. This mechanism enables all agents to reach an agreement on when to end their iterations, provided that they have all finished computing the average. The specific steps are as follows.

1) When start the iteration (3.1), each Agent $i$ simultaneously starts two counters, namely $c_i$ and $r_i$, both initialized to 0. The counter $c_i$ increases by one with each passing time step, which can be expressed as $c_{i, k + 1} = c_{i, k} + 1$. The subsequent text will elaborate on how the counter $c_i$ is updated.

2) Simultaneously with the iteration (3.1), a max-consensus algorithm is also launched, which is expressed as

with $\theta _{i, 0} = 0$. After that, the update rule for $r_i$ is as follows:

3) Once the Hankel matrix $\Gamma \left\{ {{{\left({\bar x_{{D_i}}^\alpha } \right)}^T}} \right\}$ loses rank, Agent $i$ records the value of counter $c_i$ at that particular time step, which we denote as $k_i^0$, and names it $c_i^0$. In other words, $c_i^0$ is defined as $c_i[k_i^0]$. Subsequently, Agent $i$ halts the increment of the counter, i.e., for all $k' \geqslant k_i^0$, we have $c[k'] = {c_i}[k_i^0] = c_i^0$. It should be noted that $c_i^0 = 2(D_i + 1) + 1$.

4) Agent $i$ is able to terminate the iteration (3.1) as soon as $r_i$ reaches the value of $c_i^0$.

We now design Algorithms 1 and 2.

3.2.   Convergence analysis

In this part, we present the proof regarding the convergence and accuracy of Algorithms 1 and 2.

Let ${x_k^\alpha } = [x_{1, k}^\alpha, x_{2, k}^\alpha, \ldots, x_{n, k}^\alpha]^T$ be the state vector of sub-agent $\alpha$, ${x_k^\beta } = [x_{1, k}^\beta, x_{2, k}^\beta, \ldots, x_{n, k}^\beta]^T$ be the state vector of sub-agent $\beta$, and ${\bf x'}_k = [x_{1, k}^\alpha, x_{2, k}^\alpha, \ldots, x_{n, k}^\alpha, x_{1, k}^\beta, x_{2, k}^\beta, \ldots, x_{n, k}^\beta]^T \in {\mathbb{R}^{2n}}$ be the overall state vector.

Then each Agent $i$ sets two new auxiliary vectors, $s_{i, k} = {[{s_{i1, k}}, {s_{i2, k}}, \ldots, {s_{i2n, k}}]^T} \in {\mathbb{R}^{2n}}$, ${s_{n + i, k}} = [{s_{n + i1, k}}, {s_{n + i2, k}}, \ldots, {s_{n + i2n, k}}]^T \in {\mathbb{R}^{2n}}$, with the initial state component ${s_{ij, 0}} = 1$ if $i = j$, $0$ otherwise. We choose the same evolution updating rule as Eq (3.1), in which case, the evolutions of these two variables can be represented as shown below.

The external input of Agent $i$ is calculated as

with:

and ${F_{i, -1}^\alpha} = 0, {F_{i, -1}^\beta} = 0$.

We now use a lemma to illustrate the convergence of ${{s_{i, k}}}$ and the specific convergence value.

Lemma 1. ^[37] Assume that the initial state variable $s_{i, 0} = {[{s_{i1, 0}}, {s_{i2, 0}}, \ldots, {s_{i2n, 0}}]^T} \in {\mathbb{R}^{2n}}$ with ${s_{ij, 0}} = 1$ if $i = j$; $0$ otherwise. After updating by Eq (3.6), $\mathop {\lim }\limits_{k \to \infty } {s_{i, k}} = \psi = {[{\psi _1}, {\psi _2}, \ldots, {\psi _{2n}}]^T}$, where $\psi$ is the normalized left eigenvector of the matrix $M = \left[{\begin{array}{*{20}{c}} {{M_1}} & {{M_2}} \\ {{M_3}} & {{M_4}} \end{array}} \right]$, with ${M_1} = \left[{{a_{ij}}} \right] \in {\mathbb{R}^{n \times n}}, {M_2} = diag({\alpha_1}, {\alpha_2}, \ldots, {\alpha_n}) \in {\mathbb{R}^{n \times n}}$, ${M_3} = diag({\beta_1}, {\beta_2}, \ldots, {\beta_n}) \in {\mathbb{R}^{n \times n}}, {M_4} = diag({p_{11}}, {p_{22}}, \ldots, {p_{nn}}) \in {\mathbb{R}^{n \times n}}.$ And we have $\mathop {\lim }\limits_{k \to \infty } { M ^k} = {(\rho (M))^k}{{\bf 1}_{2n}}{\psi ^T} = {{\bf 1}_{2N}}{\psi ^T}$.

We now use a lemma to illustrate the properties of $u_{i, k}^\alpha, u_{i, k}^\beta$.

Lemma 2. ^[37] For the external inputs $u_{i, k}^\alpha, u_{i, k}^\beta$ in the system, we have

We write the iteration (3.4) in the form of matrices and vectors:

where $u_k = [u_1^\alpha, u_2^\alpha, \ldots, u_N^\alpha, u_1^\beta, u_2^\beta, \ldots, u_n^\beta]^T$.

Moreover, Equation (3.5) can be rewritten as

where ${\textbf{x}_t} = {\left[{{x_{1, t}}, {x_{2, t}}, \ldots, {x_{n, t}}} \right]^T}$ and ${\textbf{y}_t} = {\left[{{y_{1, t}}, {y_{2, t}}, \ldots, {y_{n, t}}} \right]^T}$. Next, we give some necessary lemmas.

Lemma 3. ^[38] Given Assumption 1, the matrix $A$ possesses a sole non-negative left eigenvector $v$ (corresponding to the eigenvalue $1$) such that ${v^T}{{\bf 1}_n} = n$.

Lemma 4. ^[38] Given Assumptions 1–3, a matrix norm ${\left\| \cdot \right\|_A}$ exists such that ${\sigma _A} = {\left\| {A - \frac{{{\bf 1}_n{u^T}}}{n}} \right\|_A} < 1$, and $\sigma _A$ can be made arbitrarily close to the spectral radius $\rho (A - \frac{{{{\bf 1}_n}{\mu ^T}}}{n}) < 1$.

Now, we give Theorem 1.

Theorem 1. Given Assumptions 1–3, for each Agent $i \in \mathcal{V}$,

1) The output of Algorithm 1 is precisely the average of the initial values of all agents. That is, for every $i \in \mathcal{V}$, $\hat x_i^{ave} = \frac{1}{n}\sum\limits_{i = 1}^n {x_{i, 0}}$.

2) When $0 < \eta < \frac{1}{{\mu + L}}$, where $\mu$ and $L$ are as defined in Assumptions 2 and 3, respectively, Algorithm 2 converges linearly with respect to the number of optimization iterations to the global optimum, i.e., ${\left\| {{{\bf x}_t} - {\bf 1}_n \otimes {x^*}} \right\|_2}$ converges to $0$ in a linear fashion.

Proof. (1) Expanding Eq (3.7), we have

Let $F_k = [F_{1, k}^\alpha, F_{2, k}^\alpha, \ldots, F_{N, k}^\alpha, F_{1, k}^\beta, F_{2, k}^\beta, \ldots, F_{N, k}^\beta]^T$. According to Lemmas 1, 2, we have

and

On the basis of Eq (3.11), we can know that when $k \to \infty$, $\sum\limits_{t = 0}^k {M^{k + 1 - t}}u_t$ is a constant. We use $C$ to represent it, and thus we have

which can show that $\mathop {\lim }\limits_{k \to \infty } x_{i, k+1}^\alpha = \mathop {\lim }\limits_{k \to \infty } x_{i, k+1}^\beta$.

Therefore, we have

We thus have

(2) We write $\overline x_t = {v^T}{\bf x}_t/n$, $\overline y_t = \frac{1}{n}{\sum\nolimits_{i = 1}^n {\nabla f} _i}\left({x_{i, t} } \right)$ and $g_t = \frac{1}{n}{\sum\nolimits_{i = 1}^n {\nabla f} _i}({\overline x_t})$. From the analysis above, we know that at the time of iteration $t$, each agent can obtain the average gradient at time $k$ via Algorithm 1, i.e., $y_{i, t} = \bar{y}_t, {\bf y}_t = {\bf 1}_n\bar{y}_t.$ Hence, from the iteration (3.8), we can obtain

If $\eta < 1/(\mu+L)$, we have

Moreover, from the result of Lemma 4, we can obtain

Taking $V_t = [||\bar{x}_t-x^*||_2, ||{\bf x}_t-{\bf 1}_n\bar{x}_t||_A]^T$, we have

where the transition matrix $P = \left({\begin{array}{*{20}{c}} {1 - \eta \mu } & {\eta qL/\sqrt n }\\ 0 & {{\sigma _A}} \end{array}} \right)$.

Since $0 < 1- \eta \mu < 1$ and $0 < \sigma _A < 1$, we can see that the spectral radius of $P$ is strictly smaller than $1$ and therefore $||{\bf x}_t-{\bf 1}_n\otimes x^*||_2$ converges to zero linearly. □

Remark 1. The algorithm we proposed can achieve the optimal solution to the distributed optimization problem. It can be seen that, unlike the push-sum algorithm, where each agent needs to maintain two states and exchange more information during the process of information exchange with neighboring agents, our algorithm requires less information to be exchanged, which obviously reduces the communication cost.

3.3.   Privacy analysis

In this part, we provide a detailed privacy analysis of Algorithm 1 in terms of how it can resist "attacks" from curious agents (in the network) and eavesdroppers (outside the network). First, we give detailed descriptions of curious and eavesdropping attack models^[25].

1) Honest-but-curious attacks refer to situations where one or more participating agents (whether they collude or not) accurately adhere to every step of the protocol. Nevertheless, they are inquisitive and gather all the received intermediate data with the intention of uncovering sensitive information about other participating agents.

2) Eavesdropping attacks are carried out by an adversary who manages to gain access to the information shared with other agents by infiltrating all the communication channels. Consequently, eavesdroppers are aware of the network's topology and all the data shared within the network. However, the state variables that are not shared will not become known to them.

Similar to the analysis in ^[36], we define $\Delta{\mathcal{I}_\mathcal{A}}(x_{p, i}) = \{\bar x_{p, i}|{\mathcal{I}_\mathcal{A}}(0:K)\}$; this set encompasses all the possible states associated with $x_{p, i}$ when the information set accessible to $\mathcal{A}$ is ${\mathcal{I}_\mathcal{A}}(0:K)$.

The diameter of $\Delta{\mathcal{I}_\mathcal{A}}(x_{p, i})$ is defined as

where $\bar{x}_{p, i}$ and $\bar{x}_{p, i}'$ are two disparate states which are part of the set $\Delta \mathcal{I}_\mathcal{A}(x_{p, i})$.

Now, we present Theorem 2 in the following paragraphs.

Theorem 2. Given Assumption 1, for every Agent $i \in \mathcal{V}$, the privacy of Agent $i$ can be preserved under Algorithm 1:

(1) For a set of honest-but-curious agents $\mathcal{N}$, as long as at least one neighbor of Agent $i$ is not in the set $\mathcal{N}$, the privacy information of Agent $i$ can be protected from being obtained by the set $\mathcal{N}$.

(2) For an eavesdropper $\mathcal{R}$, if there is an edge $\varepsilon _{mi}$ or $\varepsilon _{ji}$ that the eavesdropper $\mathcal{R}$ cannot eavesdrop on, then the privacy information of Agent $i$ can be protected from being obtained by the eavesdropper $\mathcal{R}$.

Proof. Since, under Algorithm 1, the maximum communication round equals $k_1$, the information set $\mathcal{I}_\mathcal{N}(0:k_1)$ and $\mathcal{I}_\mathcal{R}(0:$ $k_1)$ denote all the information accessible to the adversary. From Algorithm 2, it can be seen that the private information $\nabla f_i(x_{i, t}), \forall t\geq0$ is regarded as the input of Algorithm 1. Thus, it is enough to demonstrate that the privacy of the initial value $x_{i, 0}$ of Agent $i$ can be preserved under Algorithm 1.

(1) We use a method similar to that in ^[33] to prove that honest-but-curious neighbors cannot distinguish any changes in the neighbor's initial value. More specifically, under the following initial condition:

We set the following weights:

where $r\in \mathcal{V}\backslash\{i, m\}, q\in\mathcal{V}$, $\Delta$ is an arbitrary real number, and "$\backslash$" represents set subtraction. The external input $u_{i, k}^l, l = \alpha, \beta$ is invariant for $i \in \mathcal{V}$, it can be easily verified that $\hat x_{i, 1}^\alpha = x_{i, 1}^\alpha, \hat x_{m, 1}^\alpha = x_{m, 1}^\alpha$. Moreover, due to the weight values remaining identical for $k \geqslant 1$, it is easy to see that the updates of all agents are same, namely, $\hat x_{i, k}^\alpha = x_{i, k}^\alpha, i \in \mathcal{V}$. Thus, the information received by Agent $j$ remains consistent even when the real initial state of Agent $i$ changes. We now have

From the definition in ^[36], we have proved the first statement.

(2) For the second statement, because of the topological limitations, the eavesdropper $\mathcal{R}$ is unable to eavesdrop on ${\varepsilon _{mi}}$ or ${\varepsilon _{im}}$, where $m \in \mathcal{N}^+_i$ or $m \in \mathcal{N}^-_i$, i.e., $a_{mi}$ or $a_{im}$, is inaccessible to $\mathcal{R}$. Moreover, since the self-weights $a_{ii}, a_{mm}$ are not transmitted over the communication network, the eavesdropper $\mathcal{R}$ can not obtain any information of $a_{im}, a_{mm}$ or $a_{mi}, a_{ii}$. Subsequently, in a similar vein to the proof of the first statement, we have $\mathrm{Diam}(\Delta_i(\mathcal{I}_\mathcal{N}(0:k_1))) = \infty$, i.e., the privacy of $x_{i, 0}$ is preserved.

□

Remark 2. The state decomposition method we proposed enhances the privacy protection ability of distributed optimization on directed graphs, but it may also fail under certain circumstances. One potential vulnerability arises when adversaries possess highly correlated auxiliary data, which could enable inference attacks. Additionally, if an attacker continuously observes multiple decomposed states over time, they may reconstruct sensitive information through statistical analysis. Of course, the probability of this situation occurring is extremely low. To mitigate these risks, incorporating differential privacy mechanisms or applying obfuscation techniques to the decomposed states could enhance robustness. Future research will explore these strategies to further strengthen privacy guarantees in adversarial environments.

4.   Numerical example

In this part, we validate the convergence and privacy of the proposed algorithm by exemplary simulations. Consider a directed graph consisting of five agents, that is, $n = 5$, as shown in Figure 2. The task of each agent is to find the nearest gathering point ${x^*}$ by cooperating with other agents without exposing her/his initial position $p_i, \forall i \in {\cal V}$. The objective function of Agent $i$ is described by ${f_i}(x) = \frac{1}{2}\left\| {x - {p_i}} \right\|_2^2$, i.e.,

We suppose that the initial state values of the agents are $x_{1, 0} = 10$, $x_{2, 0} = 20$, $x_{3, 0} = 30$, $x_{4, 0} = 40$, and $x_{5, 0} = 50$, and select the weight values between the agents reasonably.

The variation in the variable ${{\bf x}_k} = {\left[{{x_{1, k}}, {x_{2, k}}, \ldots, {x_{5, k}}} \right]^T}$ with respect to the iteration $k$ is shown in Figure 3. It is observable that, with regard to these five agents, by applying Algorithms 1 and 2, ${\bf x}_k$ is capable of converging to the optimal solution ${x^*}$ successfully.

In addition, we need to prove that our algorithm can successfully save communication resources compared with algorithms like the one using push-sum in ^[36]. We record the amount of data that Agent 1 needs to send to their neighbors throughout the iteration process. As shown in Figure 4, the amount of data our algorithm needs to send during the iteration is lower. The same applies to other agents. This fully demonstrates that our algorithm can successfully save communication resources.

In the end, we assume that there is an eavesdropper that wants to obtain the information of Agent 1, where $z_{1, k}$ represents the information of Agent 1 obtained by the eavesdropper. When the privacy-preserving algorithm is not used, the result is shown in Figure 5(a). Although the convergence effect can eventually be achieved, the eavesdropper can successfully obtain the information of Agent 1. After using Algorithm 1, the convergence situation is shown in Figure 5(b). It is observable that not only can it converge, but the eavesdropper cannot steal the initial value information of Agent 1, and thus the privacy of Agent 1 is protected.

5.   Conclusions

In this paper, we proposed a novel privacy-preserving distributed optimization algorithm for directed graphs. By leveraging a state decomposition method, our approach ensures the protection of sensitive information while enabling agents to collaboratively minimize the sum of cost functions. Unlike traditional methods, the introduction of external inputs effectively reduces the communication overhead, enhancing efficiency without compromising convergence to the optimal solution. Numerical simulations demonstrate the effectiveness and practicality of the proposed method, confirming its potential for addressing privacy concerns in distributed optimization problems on directed graphs. Future work involves enhancing the optimization accuracy and addressing constrained optimization problems.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The work was supported by the National Natural Science Foundation of China under Grants 62203045 and 62433020. The material in this paper was not presented at any conference.

Conflict of interest

The authors declare there are no conflicts of interest.