Linear convergence of a primal-dual algorithm for distributed interval optimization

1.   Introduction

Due to the theoretical significance and wide range of applications in areas such as machine learning, multi-agent system coordination, sensor networks, and smart grids, distributed optimization has received a lot of attention from researchers in recent years. Various distributed algorithms for solving distributed optimization problems have been introduced, and they involve agents collaborating with their neighboring agents in order to attain global minimization, see recent works ^{[1,2,3,4,5,6,7]}.

The aforementioned works' objective functions are scalar functions. In practice, however, scalar functions have been frequently incapable of expressing objective functions for distributed networks explicitly or precisely (see ^[8,9,10]). On the contrary, interval functions are employed to describe problems, as exemplified in the applications of smart grids and economic systems ^[11,12]. To address the challenges presented by interval functions, interval optimization problems (IOPs), have been proposed ^{[13,14,15,16,17,18,19]}. Initial studies on IOPs were conducted by the authors of ^[13], and subsequently investigated in ^[14,15]. Existence conditions have been presented in ^[11,20] to achieve Pareto solutions of IOPs. In addition, ^{[21,22,23,24]} detail algorithms that have been designed for centralized IOPs. Without conducting a theoretical analysis, ^[11,12] present distributed applications of IOPs in economic systems and smart infrastructures. For centralized IOPs ^{[21,22,23,24]} have presented algorithms. These line search algorithms, nevertheless, fail in distributed environments.

Given this context, it is natural for us to consider the design of efficient algorithms to solve DIOPs over multi-agent networks. The DIOPs, nevertheless, remain a subject of ongoing research. This may be due to the ease with which line search algorithms (e.g., Wolfe or Lamke's algorithms ^{[21,22,23,24]}) can be applied in distributed settings, and very few papers ^[25] with related theoretical results have been published. In addition, algorithm designs are made difficult by the partial order of interval functions.

Furthermore, there is growing interest in the convergence rates of distributed algorithms for distributed optimization with scalar functions. In fact, when local objective functions were strongly convex, the algorithms of ^[2,26,27] achieved linear convergence rates for the centralized and distributed counterparts. Local scalar functions for distributed optimization are not strongly convex in a number of practical applications. Further investigation was undertaken by a group of scholars ^[1,28,29,30] regarding the substitution of strongly convex conditions that dictate linear convergence rates. For example, ^[1] analyzed four distinct categories of function conditions and deduced the linear convergence of numerous centralized algorithms. The authors of ^[28,29] respectively demonstrated the linear rates of their distributed algorithms under metrically sub-regular and Polyak-Lojasiewicz conditions.

In this paper, we investigate the Pareto solutions of a DIOP whose local functions are interval functions rather than scalar functions. The DIOP is given as follows:

where $G_{i} = [L_{i}, R_{i}]$ is a convex interval function for each agent $i$. $L_{i}(s)\leqslant R_{i}(s)$ holds for every given $s$. Still, each agent can only get the gradient information of interval function $G_{i}$. By means of neighborhood information communication, the global Pareto solution is obtained. The contributions of this paper are summarized as follows:

(a) We investigate the Pareto solution of a DIOP whose local functions are interval functions. By incorporating convexity and well-defined partial orderings of interval functions, we convert the DIOP ^[11,20,31] into a solvable distributed optimization problem scalarization (DSIOP) with convex global constraints.

(b) In this reformulation, the optimal solutions of the DSIOP correspond to the Pareto solutions of the DIOP. With this relationship, we propose a distributed primal-dual algorithm to find a Pareto solution of the DIOP.

(c) We discuss a crucial criterion that, when applied to Pareto solutions of a DIOP, weaken the strict or strong convexity required for linear convergence. Given that this paper investigates DIOPs, the supplied criterion differ from those delineated in ^[1,28,29]. In addition, the criterion is essential for evaluating the convergence of DIOP distributed algorithms.

The rest of the paper is organized as follows. The preliminaries of this paper are given in Section 2. In Section 3, the DIOP is analyzed. The primal-dual algorithm is further given to find a Pareto solution of the DIOP in Section 4 and a numerical example is given in Section 5. Finally, the conclusion of this paper is offered in Section 6.

Notations. Denote by $\mathcal{R}$ the set of real numbers, $I_n\in \mathcal{R}^{n\times n}$ as the identity matrix, and $\mathit{\boldsymbol{1}}_{n} = [1, 1, \ldots, 1]^{\top}\in \mathcal{R}^{n}$, respectively. Denote $\langle \cdot \, ,\, \cdot\rangle$ as the inner product and $\|\cdot\|$ as the Euclidean norm in $\mathcal{R}^n$.

2.   Preliminaries

In this section, we present an introduction to convex analysis for scalar functions ^[32], graph theory, and interval optimization ^[33].

2.1.   Graph theory

Define $\mathcal{N} = \{1, 2, ..., n\}$ as the agent set and $\mathcal{E}\subset \mathcal{N}\times \mathcal{N}$ as the set of edges between agents. The communication between $n$ agents is described by an undirected graph $\mathcal{G} = \big(\mathcal{N}, \mathcal{E}\big)$. If $(i, j)\in \mathcal{E}$, then the agent $i$ can communicate with the agent $j$. Therefore, each agent $i\in \mathcal{N}$ can communicate with agents in its neighborhood $N_{i} = \{j|(i, j)\in \mathcal{E}\}\cup\{i\}.$ Denote $\mathcal{A}\in \mathcal{R}^{n\times n}$ as the communication matrix between agents, whose elements $a_{ij}$ satisfy the following conditions:

Denote $d_{i}$ by the degree of agent $i$, i.e., $|d_{i}| = \sum_{j = 1}^{n}a_{ij}$. Further, denote $D$ by the $n\times n$ diagonal degree matrix such that $D = \mbox{diag}(\sum_{j = 1}^{n}a_{1j}, \ldots, \sum_{j = 1}^{n}a_{nj})$. Then, the associated Laplacian matrix $\mathcal{P}\in \mathcal{R}^{n\times n}$ is $\mathcal{P}: = D-\mathcal{A}$.

The following assumption forms the basis of the communication topology $\mathcal{G} = \big(\mathcal{N}, \mathcal{E}\big)$ between agents over the network:

Assumption 1. The undirected graph $\mathcal{G} = \big(\mathcal{N}, \mathcal{E}\big)$ is connected.

Assumption 1 is extensively employed in ^[28], this ensures the consensus of vectors for agents over the network.

2.2.   Convex analysis

Prior to proceeding with the discussion of interval functions, we define convexity and the Lipschitz continuity of scalar functions.

Definition 1 (a) A scalar function $f: \Omega\to \mathcal{R}$ is convex if for any $s_{1}, \; s_{2} \in \Omega$ and $z\in [0, \, 1]$, $f(\lambda s_{2} +(1-\lambda)s_{1}) \leq \lambda f(s_{2}) + (1-\lambda)f(s_{1})$ holds.

(b) A scalar function $f:\mathcal{R}^n \to \mathcal{R}$ is $\kappa$-Lipschitz continuous with respect to a constant $\kappa > 0$ if

The following lemma is crucial for the analysis of convergence in distributed optimization problems involving scalar functions and interval functions.

Lemma 1. ^[32,Lemma 11,Chapter 2.2] Define $\{v^{k}\}_{k\geqslant 1}$ and $\{w^{k}\}_{k\geqslant 1}$ as two nonnegative scalar sequences. Define $\{h^{k}\}_{k\geqslant 1}$ as a scalar sequence, which is bounded from below uniformly. If there exists a nonnegative constant sequence $\eta^{k} \geqslant 0$ with $\sum_{k = 1}^{\infty}\eta^{k} < \infty$ and

then $\{h^{k}\}_{k\geqslant 1}$ converges with $\sum_{k = 1}^{\infty} v^{k} < \infty$.

2.3.   Interval optimization problems

Let $G: \mathcal{R}^{p}\rightrightarrows\mathcal{R}$ be any interval map. Now, we consider the following IOP:

where $G(x) = [L(s), R(s)]$ is any non-empty compact interval in $\mathcal{R}$.

The Pareto optimal solution to an IOP is defined as follows:

Definition 2. ^[34] A point $s^{*} \in \Omega$ is said to be a Pareto optimal solution to an IOP iff it holds that for some $\bar{s}\in \Omega$, $L(\bar{s})\leqslant L(s^{*})$ and $R(\bar{s})\leqslant R(s^{*})$ both hold implying that $L(s^{*})\leqslant L(s)$ and $R(s^{*})\leqslant R(s)$.

The example of the DIOP is presented below. There is no solution other than the Pareto solution in the example that follows.

Example 1 The IOP illustrated in Figure 1 does not have a solution. However, the Pareto optimal solutions to the given problem are $[s_{1}, s_{2}]$.

(a) For $y\leqslant s_{1}$, we have that $R(y)\geqslant R(s_{1})$ and $L(y)\geqslant L(s_{1})$, and $s_{1}$ is a Pareto solution to the IOP.

(b)For $y\geqslant s_{2}$, we have that $R(y)\geqslant R(s_{2})$ and $L(y)\geqslant L(s_{2})$, and $s_{2}$ is a Pareto solution to the IOP.

(c) For $s_{1}\leqslant y\leqslant s_{2}$, we have that $R(y)\leqslant R(s_{1})$, $L(y)\geqslant L(s_{1})$, $R(y)\geqslant R(s_{2})$ and $L(y)\leqslant L(s_{2})$.

For $s_{1}\leqslant y\leqslant s_{2}$, $\bar{s}\in \Omega$, $L(\bar{s})\leqslant L(y)$ and $R(\bar{s})\leqslant R(y)$ could not hold concurrently.

According to Definition 2, $[s_{1}, s_{2}]$ are Pareto optimal solutions to this given problem.

To investigate the Pareto solutions of an IOP, let us consider the following IOP in conjunction with its scalarization (SIOP):

where $\lambda\in [0, 1]$. The following lemma holds for Pareto solutions of IOPs and solutions of SIOPs according to ^[34]. Furthermore, it remains valid in distributed settings.

Lemma 2. ^[34] We assume that $G$ is compact-valued and convex with respect to $x$:

(a) If there exists a real number $\lambda\in(0, 1)$ such that $s^{*}\in \Omega$ is a solution to the SIOP, then $s^{*}\in \Omega$ is a Pareto optimization of the IOP.

(b) If a point $s^{*}\in \Omega$ is a Pareto optimization of the IOP, then there exists a real number $\lambda\in [0, 1]$ such that $s^{*}\in \Omega$ is an optimal solution of the SIOP.

3.   Optimization model and algorithm

In this section, we consider a DIOP and introduce its distributed primal-dual algorithm.

3.1.   Optimization model

Consider the following DIOP:

where $\mathit{\boldsymbol{s}} = \big [s_{1}^{\top}, s_{2}^{\top}, \ldots, s_{n}^{\top}\big ]^{\top}\in \mathcal{R}^{np}$, $s_{i}\in \mathcal{R}^{p}$, and $G_{i} = [L_{i}, R_{i}]$. $L_{i}, R_{i}:\mathcal{R}^{p}\rightarrow \mathcal{R}$ are convex functions. For any given $s_{i}$, $L_{i}(s_{i})\leqslant R_{i}(s_{i})$ holds. Each agent $i$ knows its local interval function $G_{i}$.

Define $L(\mathit{\boldsymbol{s}})$ and $R(\mathit{\boldsymbol{s}})$ as

With (3.2), the definition of Pareto solutions is then given to the DIOP.

Definition 3. ^[34] $s^{*} \in \Omega$ is a Pareto solution of the DIOP, iff for some $\bar{\mathit{\boldsymbol{s}}}\in \Omega$, $L(\bar{\mathit{\boldsymbol{s}}})\leqslant L(\mathit{\boldsymbol{s}}^{*})$ and $R(\bar{\mathit{\boldsymbol{s}}})\leqslant R(\mathit{\boldsymbol{s}}^{*})$ both hold implying that $L(\mathit{\boldsymbol{s}}^{*})\leqslant L(\bar{\mathit{\boldsymbol{s}}})$ and $R(\mathit{\boldsymbol{s}}^{*})\leqslant R(\bar{\mathit{\boldsymbol{s}}})$.

The existence of Pareto solutions for the DIOP is guaranteed by Assumption 2 which is consistent with the centralized counterpart ^[35].

Assumption 2. (a) $L_{i}(s)$ and $R_{i}(s)$ are strongly convex, continuous functions.

(b) Problem (3.1) has at least one Pareto solution.

(c) Gradients of $L_{i}(s)$ and $R_{i}(s)$ are Lipschitz continuous.

Lemma 2 also establishes a theoretical framework for Pareto solutions for the DIOP. Consider the following scalarization of the DIOP as well. Define $f:\mathcal{R}^{np}\times \mathcal{R}^{n} \rightarrow \mathcal{R}$ and $f_{i}:\mathcal{R}^{p}\times [0, 1]\rightarrow \mathcal{R}$ as

where $\mathit{\boldsymbol{z}} = \big [z_{1}, z_{2}, \ldots, z_{n}\big ]^{\top}\in (0, 1)^{n}$ and $\mathit{\boldsymbol{s}} = \big [s_{1}^{\top}, s_{2}^{\top}, \ldots, s_{n}^{\top}\big ]^{\top}\in \mathcal{R}^{np}$. Let $\mathit{\boldsymbol{z}} = z_{0}\mathit{\boldsymbol{1}}_{n}$ with $z_{0}\in (0, 1)$. The DSIOP (3.1) can be rewritten as follows:

where each agent $i$ possesses the following information: $\nabla f_{i}$, $s_{i}$, $z_{i}\in (0, 1)$ and $s_{j}\in N_{i}$. The given problem (3.5) can be modeled as a distributed optimization problem ^[28,36,37] with scalars when $z$ represents a common vector to each agent $i$. Additionally, under Assumption 2, the following lemma remains valid:

Lemma 3. ^[34,35]

(a) $f_{i}\big (s, z\big)$ is linear with respect to $z$ and $f_{i}\big (s, z\big)$ is convex with respect to $s$.

(b) There are Lipschitz constants $k_{i1}$ and $K_{1}$ such that the partial derivative $\nabla f_{i_{x}}\big (s, z\big)$ is Lipschitz continuous with respect to $s$ with $k_{i1}$ and $\nabla F_{\mathit{\boldsymbol{s}}} \big (\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}}\big)$ is Lipschitz continuous with respect to $\mathit{\boldsymbol{s}}$ with $K_{1}$.

(c) There are Lipschitz constants $k_{i2}$ and $K_{2}$ such that $f_{i}\big (s, z\big)$ is Lipschitz continuous with respect to $z$ with constant $k_{i2}$ and $F\big (\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}}\big)$ is Lipschitz continuous with respect to $\mathit{\boldsymbol{z}}$ with constant $K_{2}$.

(d) There are Lipschitz constants $k_{i3}$ and $K_{3}$ such that the partial derivative $\nabla f_{i_{x}}\big (s, z\big)$ is Lipschitz continuous with respect to $z$ with constant $k_{i3}$ and $\nabla F_{\mathit{\boldsymbol{s}}} \big (\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}}\big)$ is Lipschitz continuous with respect to $\mathit{\boldsymbol{z}}$ with constant $K_{3}$.

It should be noted that although $f_i(s_i, z_i)$ is convex with respect to $s$ and $z$, $f_i(s_i, z_i)$ is not a convex function. Owing to the non-convexity of $f_i(s_i, z_i)$, the criteria for linear convergence rates of algorithms are no longer applicable to the DIOP.

3.2.   Algorithm

During distributed optimization processes, $s_{1}, \ldots, s_{n}$, ${z}_{1}, \ldots, z_{n}$ are not necessarily equal all of the time. Therefore, it is natural to treat those variables separately and impose the soft constraints $s_{1} = \ldots = s_{n}$, ${z}_{1} = \ldots = z_{n}$. By using the Laplacian matrix $\mathcal{P}$, these constraints are equivalent to $\mathbf{P}\mathit{\boldsymbol{s}} = 0$ and $\mathcal{P}\mathit{\boldsymbol{z}} = 0$, where $\mathit{\boldsymbol{z}} = \big [z_{1}, z_{2}, \ldots, z_{n}\big ]^{\top} \in (0, 1)^{n}$, $\mathit{\boldsymbol{s}} = \big [s_{1}^{\top}, s_{2}^{\top}, \ldots, s_{n}^{\top}\big ]^{\top}\in \mathcal{R}^{np}$, and $\mathbf{P} = \mathcal{P}\otimes I_{p}$. Consequently, problem (3.5) is reformulated as follows:

Let $\mathit{\boldsymbol{t}} = \big [t_{1}, t_{2}, \ldots, t_{n}\big ]^{\top}$. Recall that the dual problem of (3.6) is

and the augmented Lagrangian function of (3.7) with respect to $\mathit{\boldsymbol{s}}$ is

Define by $\bar{z}^{0} = \frac{1}{n}\sum_{i = 1}^{n}z_{i}^{0}$, $\mathit{\boldsymbol{\bar{z}^{0}}} = [(\bar{z}^{0})^{\top}, (\bar{z}^{0})^{\top}, \ldots, (\bar{z}^{0})^{\top}]\in\mathcal{R}^{np}$, where $z_{i}^{0}\in (0, 1)$ is an initial value for any agent $i$. For the vector $\mathit{\boldsymbol{\bar{z}^{0}}}$, denote $S^*$ as the optimal solution set of problem (3.6) and $T^{*}$ as the saddle point set of problem (3.7), respectively. According to Assumption 2, for a proper given $\mathit{\boldsymbol{z}}^{0}$, there exists $\mathit{\boldsymbol{t}}^*$ such that $(\mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{t}}^*) \in S^* \times T^{*}$. $(\mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{t}}^*) \in S^* \times T^{*}$ also satisfies the following lemma, which is also a basis for the analysis of convergence:

Lemma 4. (Karush-Kuhn-Tucker condition, ^[38,Theorems 3.25–3.27]) With Assumption 2, for a particular given $\mathit{\boldsymbol{\bar{z}^{0}}} = \bar{z}^{0}\otimes \mathit{\boldsymbol{1}}_{n}\in (0, 1)^{n}$, $(\mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{t}}^*)$ is a solution to (3.7) if

With Lemma 4, we introduce a distributed primal-dual algorithm as follows:

where the step-size $h$ satisfies that $0 < h < \frac{2}{L+4\sigma}$, $\sigma$ is the largest eigenvalue of the Laplacian matrix $\mathcal{P}$. At the $k$-th iteration, for all $i \in \mathcal{V} = \{1, 2, \dots, n\}$, each agent $i$ only obtains a partial gradient in the form of $\nabla f_{i_{s_{i}^{k}}}(s_{i}^{k}, z_{i}^{k})$ for its local function $f_{i}(s_{i}^{k}, z_{i}^{k})$, and it is cooperative with neighbors to achieve a Pareto solution of problem (3.1).

The constraint $\mathcal{P}\lim_{k\rightarrow \infty}\mathit{\boldsymbol{z(k)}} = 0, z_{i}\in (0, 1)$ in (3.6), is satisfied through (3.9b) and the initialization of $z_{i}(0)\in(0, 1)$ in (3.9), while the constraint $\mathcal{P}\lim_{k\rightarrow \infty}\mathit{\boldsymbol{x(k)}} = 0$ and the minimization of $F\big (\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{z}}\big)$ are satisfied through (3.9a) and (3.9c) in (3.9). Define $\mathit{\boldsymbol{s^{k}}} = col\{s_1^{k}, \ldots, s_n^{k}\}$, $\mathit{\boldsymbol{t^{k}}} = col\{t_1^{k}, \ldots, t_n^{k}\}$ and $\mathit{\boldsymbol{z^{k}}} = col\{z_1^{k}, \ldots, z_{n}^{k} \}$. Then, with $\mathit{\boldsymbol{w}}\triangleq col\{\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{t}}\} \in \mathcal{R}^{2qn}$, $\mathit{\boldsymbol{w^{*}}} \triangleq col\{\mathit{\boldsymbol{s^{*}}}, \mathit{\boldsymbol{t^{*}}}\}\in W^* \subset S^* \times T^{*}$ for a proper given $\mathit{\boldsymbol{\bar{z}^{0}}}$, where $W^*$ is the primal-dual solution set of problem (3.7). Algorithm (3.9) can be rewritten in a compact form in terms of $\{\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}}\}$:

where

We have the following basic result, whose proof is in the Appendix.

Theorem 1. Under Assumptions 1 and 2, $\{\mathit{\boldsymbol{s}}^{k}, \mathit{\boldsymbol{t^{k}}}\}$ converges to the Pareto solution set $W^{*}$.

Consider a Lyapunov function

where $V_a(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}}) = \sigma d^2(\mathit{\boldsymbol{w}}, W^*)$, $V_b(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}}) = F(\mathit{\boldsymbol{s, z}})- F(\mathit{\boldsymbol{s^*, \bar{z}^{0}}}) + \frac{1}{2}\langle\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{P}}\mathit{\boldsymbol{s}}\rangle+ \langle\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{P}}\mathit{\boldsymbol{t}}\rangle$, $V_c(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}}) = K_{2}\|\mathit{\boldsymbol{z}}-\mathit{\boldsymbol{\bar{z}^{0}}}\big\|$ and $K_{2}$ is a Lipschitz constant given in Lemma 3. Theorem 1 is based on Lemmas 5 and 6, whose proof are also given in Appendix.

Lemma 5. With Assumption 1, $\big\{\mathit{\boldsymbol{z^{k}}}\big\}$ converges to $\mathit{\boldsymbol{\bar{z}^{0}}}$ with a linear convergence rate $\gamma_{1}$ whose elements belong to $(0, 1)$: $\lim_{k\rightarrow \infty}\mathit{\boldsymbol{z^{k}}} = \mathit{\boldsymbol{\bar{z}^{0}}}, \quad \big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\big\|\leqslant \gamma_{1}\big\|\mathit{\boldsymbol{z^{k-1}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\big\|$. $\big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\big\|$ is also summable with respect to $k$: $\sum_{k = 1}^{\infty}\big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\big\| < \infty$.

Lemma 6 is additionally presented to illustrate the minimum and maximum values of $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$.

Lemma 6. With Assumptions 1 and 2, the following inequality holds for the Lyapunov function $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$:

where $K_{1}, K_{2}$ are Lipschitz constants given in Lemma 1, and $\sigma$ is the largest eigenvalue of the Laplacian matrix $\mathcal{P}$.

The asymptotic convergence of (3.9) is demonstrated by Theorem 1, which is consistent with that of ^[28] for distributed optimization. It should be noted that the inclusion of the partial gradient term $\nabla F_{\mathit{\boldsymbol{s}}}(\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}})$ renders inapplicable the contraction mapping principle. In contrast to numerous distributed algorithms that rely on the contraction mapping principle for their proofs ^{[26,28,37,39]}, this awork involves employing the martingale convergence theorem (Lemma 1) in Theorem 1.

4.   Main results

In this section, we present our main results. A criterion without strong convexity is first introduced for the DIOP, which, together with (3.9) will imply linear convergence. Our criterion for (3.9) to achieve exponential convergence is as follows.

Criterion. The continuously differentiable function $\tilde{\mathcal{L}} > 0$ has a restricted quadratic gradient growth. That is, if there exists a constant $\kappa_{L}$ such that for any $\mathit{\boldsymbol{w}}$, $\mathit{\boldsymbol{w^{*}}} = P_{W^{*}}(\mathit{\boldsymbol{w}})$, we have

where $\tilde{\mathcal{L}}$ is the augmented Lagrangian function defined in (3.8).

The criterion given in this paper differs from the quadratic convex condition given in ^[1] and the metrically irregular condition discussed in ^[28] for distributed optimization problems with scalar functions. This criterion is given for DIOPs. On the other hand, regarding the dynamics given by (3.9), we will show that (4.1) is sufficient to achieve linear convergence.

Theorem 2. Under Assumptions 1 and 2 and (4.1), $\{\mathit{\boldsymbol{s}}^{k}, \mathit{\boldsymbol{t^{k}}}\}$ converges linearly to the optimal set $W^{*}$.

Proof. If $\mathit{\boldsymbol{w}} = \mathit{\boldsymbol{w^{*}}}$, we have that $\big\|\mathit{\boldsymbol{I}}(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})\big\|\geqslant 0$. Further, consider the case when $\mathit{\boldsymbol{w}}\neq\mathit{\boldsymbol{w^{*}}}$. With Lemma 5, we obtain

where the last inequality holds by $\langle \mathit{\boldsymbol{a}}, \mathit{\boldsymbol{b}} \rangle \leqslant { \|\mathit{\boldsymbol{a}}\|^2+ \|\mathit{\boldsymbol{b}}\|^2 \over 2}.$ Still,

Equations (4.2) and (4.3) indicate that $\big\|\mathit{\boldsymbol{I}}(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})\big\|\geqslant \kappa_{L}\big\|\mathit{\boldsymbol{w}} - \mathit{\boldsymbol{w^*}}\big\|-K_{3}\big\|\mathit{\boldsymbol{z}}- \mathit{\boldsymbol{\bar{z}^{0}}}\big\|$. Therefore, if Assumption 2 holds, $\big\|\mathit{\boldsymbol{I}}(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})\big\|\geqslant \kappa_{L}\big\|\mathit{\boldsymbol{w}} - \mathit{\boldsymbol{w^*}}\big\| -K_{3}\big\|\mathit{\boldsymbol{z}}-\mathit{\boldsymbol{z^{0}}}\big\|$. By Lemma 6,

Substituting (4.4) into (A12) yields

where $T_{1}^{k} = \bigg(1 - \frac{h(2-\nu_0h) \kappa_L^{2}}{K_1 + 4\sigma}\bigg)V\big(\mathit{\boldsymbol{w}}^{k}, \mathit{\boldsymbol{z^{k}}}\big)$, $T_{2}^{k} = 2hK_{3}\sigma\Big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|\cdot \big\|\mathit{\boldsymbol{s^{k}}} - \mathit{\boldsymbol{s^{*}}}$, $T_{3}^{k} = K_{2}\bigg(\Big\|\mathit{\boldsymbol{z^{k+1}}}-\mathit{\boldsymbol{z^{k}}}\Big\|+(1-\gamma_{1})\Big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|\bigg)$, $T_{4}^{k} = \frac{2hK_{2}(2-\nu_0h) \kappa_L^{2}}{K_1 + 4\sigma}\Big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|$ and $T_{5}^{k} = -\dfrac{h(2-\nu_{o}h)K_{3}^{2}}{2}\Big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|^{2}.$

Still, according to Lemma 5, $\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|$ converges linearly at a rate $\gamma_{1}$. Therefore, residue terms $T_{2}^{k}$, $T_{3}^{k}$, $T_{4}^{k}$ and $T_{5}^{k}$ diminish with linear rates. Since $\nu_{0} \leqslant K_{1} + 4\sigma$, the main term $T_{1}^{k}$ converges with a linear rate, which is no less than $\bigg(1 - \frac{h\big(2-(K_{1} + 4\sigma)h\big)\kappa_L^{2}}{2(K_1 + 4\sigma)}\bigg)$. With Lemma 6, we obtain that $\Big[\|\mathit{\boldsymbol{s^{k+1}}} - \mathit{\boldsymbol{s}}^*\|^2 + \|\mathit{\boldsymbol{y^{k+1}}} - \mathit{\boldsymbol{t}}^*\|^2\Big]\leqslant \dfrac{2}{\sigma}V\big(\mathit{\boldsymbol{w^{k+1}}}, \mathit{\boldsymbol{z^{k+1}}}\big)$, which completes the proof. □

As shown in Theorem 1, (4.1) plays an important role in achieving linear convergence even in the absence of strong convexity of $f_i(s_i, z_i)$. In this paper, we extend the quadratic convex condition given in ^[1] to (4.1) for interval functions. Criterion (4.1) also describes another linear growth condition of gradients for distributed optimization problems.

5.   Simulation

In this section, we demonstrate the following simulation:

where $\upsilon_{1i}$, $\upsilon_{1i}\in \mathcal{R}$ and $\rho_{i}\in \mathcal{R}^{p}$. The problem is motivated from both a centralized IOP ^[35] and the distributed optimization ^[40]. The communication topology between agents is described by Figure 2.

Define $[\upsilon_{1i}, \upsilon_{2i}] = [0.5, 2]$. Take $\rho_{1} = 5$, $\rho_{2} = 4$, $\rho_{3} = 3$, $\rho_{4} = 2$, $\rho_{5} = 1$, $\rho_{6} = 0$, $\rho_{7} = -1$, $\rho_{8} = -2$, and $\rho_{9} = -3$. Next, initialize (3.9) by setting the step-size $h = 0.1$, $z_{i}^{0}$ as random numbers in $[0, 1]$, and $s_{i}^{0} = 0$. Then we investigate the convergence of (3.9). Also, Figures 3 and 4 show the consensus of $z_{i}^{k}$ and convergence of $s_{i}^{k}$ for the proposed algorithm. We get a Pareto solution as $(0.4695; 1.002)$ for $1000$ iterations. Figure 5 shows the convergence of $s_{i}^{k}$ for a centralized primal-dual algorithm (an algorithm generated according to the properties of solutions in ^[35]) for each agent $i$, where $z_{i}$ denotes random numbers in $[0, 1]$. In addition, we take a performance index $R$ as $R^{k} = \log \|\mathit{\boldsymbol{s^{k}}}-\mathit{\boldsymbol{s}}^{*}\|^{2}$. The performance of $R$ is shown in Figure 6, which implies the linear convergence of (3.9).

6.   Conclusions

We have investigated a DIOP in which the local functions are interval functions in this paper. With distributed interval optimization as its primary focus, this article introduces a distributed primal-dual algorithm. A criterion has been proposed that allows the linear convergence to the Pareto solution of a DIOP without strong convexity. Finally, a numerical simulation has been executed to demonstrate the linear convergence of the proposed algorithm. Given that the existing research on DIOPs primarily focuses on objective interval functions, the investigation of distributed problems involving interval constraints should be expanded in the future.

Use of AI tools declaration

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

Acknowledgments

This research was supported by the NSFC (72101026, 62203045) and Operation Expenses for Universities' Basic Scientific Research of Central Authorities (FRF-TP-22-141A1).

Conflict of interest

The authors declare that there is no conflict of interest.

Appendix

Proof of Lemma 5

Proof. According to Assumption 1(b), the adjacency matrix $\mathcal{A}$ is irreducible and aperiodic. With ^[33,Theorem 6.64], $\lim_{k\rightarrow \infty}\mathcal{A}^{k} = \mathcal{B}$ with a linear convergence rate $\gamma_{1}\in (0, 1)$, where $\mathcal{B} = \frac{1}{n} \mathit{\boldsymbol{1}}_{n}^{\top}\mathit{\boldsymbol{1}}_{n}$. With (3.9b), we have

According to ^[37,Lemma 3], $\sum_{k = 1}^{\infty}\big\|A^{k}-B\big\| < \infty$ holds, which completes the proof.

□

Proof of Lemma 6

Proof. $(a)$Lower bound of the Lyapunov function $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$: Let $\mathit{\boldsymbol{w}}^* = col\{\mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{t}}^{*}\}$ be the projection of $\mathit{\boldsymbol{w}}^{k}$ onto the optimal set $W^*$. Since the symmetry of $\mathit{\boldsymbol{P}}$ holds, given Lemma 4, $\nabla F_{\mathit{\boldsymbol{s^{*}}}}(\mathit{\boldsymbol{x^{*}, \bar{z}^{0}}}) = - \mathit{\boldsymbol{P}}\mathit{\boldsymbol{t}}^*$ and $\langle \mathit{\boldsymbol{s^{*}}}, \mathit{\boldsymbol{P}}\rangle = 0$. We further obtain that $\big\langle \mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*, \nabla F_{\mathit{\boldsymbol{s^{*}}}}(\mathit{\boldsymbol{x^{*}, \bar{z}^{0}}})\big\rangle = -\big\langle \mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{P}}\mathit{\boldsymbol{t}}^*\big\rangle$, and $\big\langle\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{P}}\mathit{\boldsymbol{t}}\big\rangle = \big\langle \mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{P}}\mathit{\boldsymbol{t}}\big\rangle$. $V_b(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$ can be further written as

According to Lemma 3, $F(\mathit{\boldsymbol{s, z}})$ is convex with respect to $\mathit{\boldsymbol{s}}$ and Lipschitz continuous with respect to $\mathit{\boldsymbol{z}}$. Therefore,

Since $\mathit{\boldsymbol{P}}$ is positive semidefinite,

Therefore, $\begin{aligned} V_b(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})\geqslant \big\langle \mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{P}} (\mathit{\boldsymbol{t}} - \mathit{\boldsymbol{t}}^*)\big\rangle \geqslant - \frac{\sigma}{2}\Big[\|\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*\|^2 + \|\mathit{\boldsymbol{t}} - \mathit{\boldsymbol{t}}^*\|^2\Big]-K_{2}\|\mathit{\boldsymbol{z}}-\mathit{\boldsymbol{\bar{z}^{0}}}\|, \end{aligned}$ which implies the lower bound of the Lyapunov function $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}}) \geqslant \frac{\sigma}{2}\Big[\|\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*\|^2 + \|\mathit{\boldsymbol{t}} - \mathit{\boldsymbol{t}}^*\|^2\Big].$

(b) Upper bound of the Lyapunov function $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$: According to Lemma 3 ($L$-Lipschitz continuity of $\nabla F_{\mathit{\boldsymbol{s}}}(\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}})$ with respect to $\mathit{\boldsymbol{s}}$ ) and Assumption 2, $F(\mathit{\boldsymbol{s, \bar{z}^{0}}})- F(\mathit{\boldsymbol{s^*, \bar{z}^{0}}}) - \big\langle \mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*, \nabla F_{\mathit{\boldsymbol{s^{*}}}}(\mathit{\boldsymbol{x^{*}, \bar{z}^{0}}})\big\rangle\leqslant \frac{L}{2}\|\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*\|^2$. According to Lemma 3, $F(\mathit{\boldsymbol{s, z}})$ is Lipschitz continuous with respect to $\mathit{\boldsymbol{z}}$, we have that $F(\mathit{\boldsymbol{s, z}})-F(\mathit{\boldsymbol{x, \bar{z}^{0}}})\leqslant K_{2}\|\mathit{\boldsymbol{z}}-\mathit{\boldsymbol{\bar{z}^{0}}}\|$. Note that

Moreover, $\big\langle\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*, \mathit{\boldsymbol{P}} (\mathit{\boldsymbol{t}} - \mathit{\boldsymbol{t}}^*)\big\rangle \leqslant \sigma\|\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*\|\cdot \|\mathit{\boldsymbol{t}}- \mathit{\boldsymbol{t}}^*\| \leqslant \frac{\sigma}{2}\Big[\varepsilon \|\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*\|^2 + \frac{1}{\varepsilon}\|\mathit{\boldsymbol{t}}- \mathit{\boldsymbol{t}}^*\|^2\Big]$ for any $\varepsilon > 0$. Through choosing $\varepsilon = \frac{\sigma}{K_{1}+ \sigma}$, we get

which implies that $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}}) \leqslant \frac{K_{1} + 4\sigma}{2}\Big[\|\mathit{\boldsymbol{s}}- \mathit{\boldsymbol{s}}^*\|^2 + \|\mathit{\boldsymbol{t}} - \mathit{\boldsymbol{t}}^*\|^2\Big]+2K_{2}\|\mathit{\boldsymbol{z}}-\mathit{\boldsymbol{\bar{z}^{0}}}\|$.

□

Proof. Proof of Theorem 1

It follows from the $K_{1}$-Lipschitz of $\nabla F(\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}})$ in Lemma 3 that

where the second inequality builds on the definition of $I_1(\mathit{\boldsymbol{w}})$. Since $\|\mathit{\boldsymbol{P}}\|\leqslant \sigma$, we have

and

Combine (A3)–(A5). Given the definition of $V_b(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$, we get

which is based on $\big\langle \mathit{\boldsymbol{Px}}, \mathit{\boldsymbol{t}} \big\rangle = \big\langle \mathit{\boldsymbol{Py}}, \mathit{\boldsymbol{s}}\big\rangle$.

With Lemma 5 and $\|\mathit{\boldsymbol{P}}\|\leqslant \sigma$, we obtain

Since $F(\cdot)$ is a convex function with respect to $\mathit{\boldsymbol{s}}$,

According to the $K_{3}$-Lipschitz continuity of $\nabla F_{\mathit{\boldsymbol{s}}}(\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{z}})$ in Lemma 3, we have

Combining (A8) and (A9) with (A7) yields

According to the $\sigma$-Lipschitz continuity of $V_a(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$with respect to $\mathit{\boldsymbol{z}}$ in (3.12), we have

Therefore, by using (A6)m (A11) and the definition of $V(\mathit{\boldsymbol{w}}, \mathit{\boldsymbol{z}})$ in (3.12), we have

where $\nu_{0} = 4\sigma+K_{1}$. and $M^{k} = \Big\|\mathit{\boldsymbol{z^{k+1}}}-\mathit{\boldsymbol{z^{k}}}\Big\|+\Big\|\mathit{\boldsymbol{z^{k+1}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|-\Big\|\mathit{\boldsymbol{z^{k}}}-\mathit{\boldsymbol{\bar{z}^{0}}}\Big\|$.

According to Lemma 5 and Assumption 2,

and

Consequently, with Lemma 1, $V(\mathit{\boldsymbol{w^{k}}}, \mathit{\boldsymbol{z^{k}}})$ converges with $\sum_{k = 0}^\infty \Big\|\mathit{\boldsymbol{I}}\big(\mathit{\boldsymbol{w}}^{k}, \mathit{\boldsymbol{z^{k}}}\big)\Big\|^2 < +\infty$, which implies that $\lim_{k\to \infty}\mathit{\boldsymbol{I}}\big(\mathit{\boldsymbol{w}}^{k}, \mathit{\boldsymbol{z^{k}}}\big) = 0$. By Lemma 4 and the continuity of $\mathit{\boldsymbol{I}}$, $\lim_{k\to \infty} \big\|\mathit{\boldsymbol{s^{k}}}-\mathit{\boldsymbol{s^{*}}}\big\| = 0$ and $\lim_{k\to \infty} \big\|\mathit{\boldsymbol{t^{k}}}-\mathit{\boldsymbol{t^{*}}}\big\| = 0$.

□