Convergence of distributed approximate subgradient method for minimizing convex function with convex functional constraints

1.   Introduction

Let $\mathbb{R}^k$ be a Euclidean space with inner product $\langle\cdot, \cdot\rangle$ and its induced norm $\|\cdot\|$. Let $m$ be a fixed natural number. In this work, we focus on the convex optimization problem of the following form:

where $f:\mathbb{R}^k\rightarrow \mathbb{R}$ is a real-valued differentiable convex function, $h:\mathbb{R}^k\rightarrow \mathbb{R}$ is a real-valued (possibly) non-differentiable convex function, and the constrained set $X$ is the intersection of a simple closed convex set $X_0\subset\mathbb{R}^k$ and a finite number of a level set $\mathrm{Lev}(g_i, 0): = \{ \mathbf{x}\in\mathbb{R}^k:g_i(\mathbf{x})\leq0\}$ of a real-valued convex function $g_i:\mathbb{R}^k\rightarrow \mathbb{R}$ for all index $i = 1, \ldots, m$. Throughout this work, we denote by $X^*$ and $\phi^*$ the set of all minimizers and the optimal value of the problem (1.1), respectively. The problem in the form of problem (1.1) arises in some practical situations such as image processings ^[1,2,3], signal recovery ^[4,5], and statistics ^[6,7,8], to name but a few.

As the function $f$ is a differentiable convex function and the function $h$ is a convex function, it is well known that the objective function $f+h$ in the problem (1.1) is, of course, a non-differentiable convex function. Therefore, one might attempt to solve problem (1.1) by using existing methods for non-differentiable convex optimization problems, for instance, the subgradient methods or proximal methods. It has been suggested and discussed that the proximal algorithm is generally preferable to the subgradient algorithm since it can converge without any additional assumption on step-size sequence and can archive a convergence rate of order $\mathcal{O}(1/N)$ for the objective function values. Nevertheless, computing the proximal operator for the sum of functions can be challenging. In this situation, methods for solving problems with the additive structure of the objective function, like the problem (1.1), often utilize the specific structure of each function $f$ and $h$ when constructing the solution methods; see ^[9] for more information. Focusing on iterative methods for dealing with the objective function in the form of the sum of two convex functions, the well-known one is nothing else than the so-called proximal gradient method, which suggests constructing a sequence $\{ \mathbf{x}_n\}_{n = 0}^\infty$ as follows:

where $\alpha_n$ is a positive step size, and $\nabla f(\mathbf{x}_n)$ is a gradient of $f$ at $\mathbf{x}_n$.

Let us notice that the proximal gradient method given in (1.2) may not be appropriate for the problem (1.1) by virtue of the fact that the constraint set $X$ of the current form is the intersection of a finite number of closed convex sets. This is because, in updating the iterate $\mathbf{x}_{n+1}$ for every iteration $n\geq0$, one is required to solve a constrained optimization subproblem over the intersection of finitely many closed convex sets. To tackle this, Nedić and Necoara ^[10] proposed a subgradient type method [10, Methods (2a)–(2c)] for solving the problem (1.1) in the case when the objective function is only a function $h$ with a strong convexity assumption and the constrained set is an infinite number of constraint functions. The strategy is to separate the problem into two parts, namely the step for minimizing the objective function $\phi$ over the simple set $X_0$, and the second one is a parallel computation for the feasible intersection $\bigcap_{i = 1}^m \mathrm{Lev}(g_i, 0)$ via the classical subgradient scheme of each constraint function $g_i$ for all index $i = 1, \ldots, m$. They analyzed its convergence results and showed that the method had a sublinear convergence rate. Note that this strategy reduces the difficulty of dealing with the whole constrained set by minimizing the function over a simple set and then minimizing feasibility violations through parallel computation on each component of the functional constraints.

Since the calculation of the subgradient of each function $g_i$ is needed in the feasibility update, it may face time-consuming difficulty due to the complication structures of the functions $g_i$, $i = 1, \ldots, m$. To overcome this drawback, the concept of the approximate subgradient of the functions $g_i$ has been utilized. Apart from this mentioned issue, the concept of approximate subgradient also arises in the duality theorem ^[11] and network optimization ^[12]. Moreover, the notion of an approximate subgradient has been widely studied in various aspects when solving optimization problems, such as $\epsilon$-subgradient methods ^[13,14,15], projection $\epsilon$-subgradient methods ^[16,17], and its variant methods ^{[18,19,20,21]}. Even if the main contributions of the approximate subgradient type methods is to reduce the complication of the subgradient computation, it can be noted that within some acceptable error tolerance $\epsilon$, the method with an approximate subgradient can improve the efficiency of its non-error of tolerance type method, (see Table 1 below).

Motivated by the above discussions, we present in this work a distributed approximate subgradient method based on the ideas of the proximal gradient method and the approximate subgradient method. The main difference between the proposed method and the method proposed by Nedić and Necoara ^[10] is that we used the proximal gradient method for dealing with the objective function and the approximate subgradient method for the feasibility constrained set. The remainder of this work is organized as follows: In Section 2, we recall the notations and auxiliary results that are needed for our convergence work. In Section 3, we present an approximate subgradient method for solving the considered problems. Subsequently, after building all the needed tools, we investigate the convergence results and the convergence rate in Section 4. In Section 5, we present numerical experiments. Finally, in Section 6, we give a conclusion.

2.   Preliminaries

In this section, we recall some basic definitions and useful facts that will be used in the following sections; readers may consult the books ^[22,23,24].

Let $f:\mathbb{R}^k\rightarrow \mathbb{R}$ be a real-valued function. We call $f$ a convex function if

for all $\mathbf{x}, \mathbf{y}\in\mathbb{R}^k$ and $\alpha\in(0, 1)$. For each $\alpha\in\mathbb{R}$, an $\alpha$-level set (in short, level set) of $f$ at the level $\alpha$ is defined by

Note that, if $f$ is continuous, the $\alpha$-level set $\mathrm{Lev}(f, \alpha)$ is a closed set for all $\alpha\in\mathbb{R}$. Moreover, if $f$ is a convex function, then its $\alpha$-level set $\mathrm{Lev}(f, \alpha)$ is a convex set for all $\alpha\in\mathbb{R}$.

For a given $\mathbf{x}\in\mathbb{R}^k$ and $\epsilon\geq0$, we call a vector $s_f(\mathbf{x})\in\mathbb{R}^k$ an $\epsilon$-subgradient of $f$ at $\mathbf{x}$ if

holds for all $\mathbf{y}\in\mathbb{R}^k$. The set of all $\epsilon$-subgradients of $f$ at $\mathbf{x}$ is denoted by $\partial_{\epsilon}f(\mathbf{x})$ and is called the $\epsilon$-subdifferential of $f$ at $\mathbf{x}$. In the case of $\epsilon = 0$, we obtain a (usual) subgradient of $f$ at $\mathbf{x}$ and denoted the subdifferential set by $\partial f(\mathbf{x}): = \partial_0 f(\mathbf{x})$. For a convex function $f:\mathbb{R}^k\rightarrow \mathbb{R}$ and $\mathbf{x}\in\mathbb{R}^k$, we note that

for all $\epsilon_1, \epsilon_2 \geq 0$ with $\epsilon_1 < \epsilon_2$.

We note that convexity is a sufficient condition for approximate subdifferentiability. Namely, for a convex function $f:\mathbb{R}^k\rightarrow \mathbb{R}$, the $\epsilon$-subdifferential set $\partial_{\epsilon}f(\mathbf{x})$ is a nonempty set for all $\mathbf{x}\in\mathbb{R}^k$ and $\epsilon\geq0$, see [24, Theorem 2.4.9] for more details. Additionally, if $X_0\subset\mathbb{R}^k$ is a nonempty bounded set, then the set $\bigcup_{ \mathbf{x}\in X_0}\partial_{\epsilon}f(\mathbf{x})$ is a bounded set for all $\epsilon\geq0$, see [24, Theorem 2.4.13].

Let $X_0\subset\mathbb{R}^k$ be a nonempty closed convex set, and $\mathbf{x}\in\mathbb{R}^k$. The normal cone to $X_0$ at $x$ is given by

The indicator function of $X_0$, $\delta_{X_0} : \mathbb{R}^k\to(-\infty, \infty]$, is the function defined by

If the function $f:\mathbb{R}^k\rightarrow \mathbb{R}$ is convex and the set $X_0\subset\mathbb{R}^k$ is nonempty closed convex, then for every $\mathbf{x}\in X_0$, we have

Let $f:\mathbb{R}^k\rightarrow \mathbb{R}$ be a function, and $X_0\subset\mathbb{R}^k$ be a nonempty closed convex set. The set of all minimizers of $f$ over $X_0$ is denoted by

If the function $f:\mathbb{R}^k\rightarrow \mathbb{R}$ is convex and the set $X_0\subset\mathbb{R}^k$ is a nonempty closed convex, then $\mathbf{x}^*\in\mathrm{argmin}_{ \mathbf{x}\in X_0}f(\mathbf{x})$ if and only if,

that is, there exists $s_f(\mathbf{x})\in\partial f(\mathbf{x}^*)$ for which

for any $\mathbf{x}\in X_0$.

Let $X_0\subset\mathbb{R}^k$ be a nonempty closed convex set, and $\mathbf{x}\in\mathbb{R}^k$. We call a point $\mathbf{y}\in X_0$ the projection of $\mathbf{x}$ onto $X_0$ if

for all $\mathbf{z}\in X_0$ and denoted by $\mathbf{y} = :P_{X_0}(\mathbf{x})$. It is well known that the projection onto $X_0$ is uniquely determined. Actually, we denote the distance from $\mathbf{x}$ to $X_0$ by $\mathrm{dist}(\mathbf{x}, X_0): = \|P_{X_0}(\mathbf{x})- \mathbf{x}\|$.

3.   Algorithm and assumptions

In this section, we start our investigation by proposing a distributed approximate subgradient method for solving the considered constrained convex optimization problem (1.1). We subsequently discuss the important assumptions for analyzing the convergence behaviors of the proposed method.

Some important comments relating to Algorithm 1 are in order.

Remark 3.1. (i) Since the objective function $h(\cdot)+\dfrac{1}{2\alpha_{n-1}}\|\cdot- \mathbf{x}_{n-1}\|^2+\langle\nabla f(\mathbf{x}_{n-1}), \cdot- \mathbf{x}_{n-1}\rangle$ is a strongly convex function and the constrained set $X_0\subset\mathbb{R}^k$ is a nonempty closed convex set, we can ensure the existence and uniqueness of its minimizer, namely the iterate $\mathbf{v}_n$ for all $n\geq1$. This means that the iterate $\mathbf{v}_n$ is well-defined for all $n\geq1$.

(ii) Since the function $g_i$ is a real-valued convex function, we note that the function $g_i^{+} = \max\{g_i, 0 \}$ is also a convex function. This implies that the $\epsilon_{n, i}$-subdifferential set $\partial _{\epsilon_{n, i}}g^{+}_i(\mathbf{v}_n)$ is nonempty for all $n\geq1$. Moreover, if $g_i^{+}(\mathbf{v}_n) > 0$, it follows that $0\notin\partial g_i^{+}(\mathbf{v}_n)$. Indeed, since $Y_i\neq\emptyset$ and $Y_i = \{ \mathbf{x}\in\mathbb{R}^k:g_i^{+}(\mathbf{x})\leq 0\}$, there exists a point $\mathbf{x}\in\mathbb{R}^k$ such that $g_i^{+}(\mathbf{x})\leq0$ and hence $\min_{ \mathbf{x}\in\mathbb{R}^k}g_i^{+}(\mathbf{x})\leq0 < g_i^{+}(\mathbf{v}_n)$ which implies that $\mathbf{v}_n$ is not a minimizer of the function $g_i^{+}$, and hence $0\notin\partial g_i^{+}(\mathbf{v}_n)$. Also, it follows from the properties of the $\epsilon_{n, i}$-subdifferential set that $\partial g_i^{+}(\mathbf{v}_n)\subset\partial _{\epsilon_{n, i}}g^{+}_i(\mathbf{v}_n)$ which implies that the well-definiteness choice of a nonzero vector $\mathbf{d}_{n, i}$ is guaranteed.

The following assumption will play an important role throughout the convergence results of this work:

Assumption 3.2. The constrained set $X_0$ is bounded.

As a consequence of Assumption 3.2, we state here the boundedness properties of some related sequences and subdifferential sets as the following proposition.

Proposition 3.3. The following statements hold true:

(i) There exists a positive constant $M$ such that for all $i = 1, \ldots, m$, we have

for all $\mathbf{x}\in X_0$.

(ii) There exists a positive constant $B$ such that

for all $\mathbf{x}\in X_0$.

(iii) There exists a positive constant $D$ such that for all $n\geq1$ and for all $i = 1, \ldots, m$, we have

(iv) The sequences $\{ \mathbf{x}_n\}_{n = 0}^\infty$, $\{ \mathbf{v}_n\}_{n = 1}^\infty$, $\{\bar{ \mathbf{z}}_n\}_{n = 1}^\infty$, $\{ \mathbf{d}_{n, i}\}_{n = 1}^\infty$ and $\{ \mathbf{z}_{n, i}\}_{n = 1}^\infty$, $i = 1, \ldots, m$, are bounded.

Proof. (ⅰ) For each $i = 1, 2, \ldots, m$, since the function $g_i^+$ is continuous and the set $X_0$ is compact, we obtain that the image of $g_i^+$ is also bounded over the set $X_0$. Hence, such an $M > 0$ exists.

(ⅱ) Since the $\epsilon$-subdifferential set is bounded on a bounded set $X_0$, for each $\epsilon\geq0$, we get that the vectors $\nabla f(\mathbf{x}), s_h(\mathbf{x})$, and $s_{\phi}(\mathbf{x})$ are bounded for all $\mathbf{x}\in X_0$, which implies (ⅱ).

(ⅲ) By the same reasoning in (ⅱ) and the definition of $\mathbf{v}_n$ and $\mathbf{d}_{n, i}$ that $\mathbf{d}_{n, i}$ is bounded for all $n\geq1$ and for all $i = 1, 2, \ldots, m$.

(ⅳ) The boundedness of $X_0$ implies that the sequences $\{ \mathbf{x}_n\}_{n = 0}^\infty$ and $\{ \mathbf{v}_n\}_{n = 1}^\infty$ are bounded, while the boundedness of $\mathbf{d}_{n, i}$ and $\mathbf{v}_n$ and the definition of $\bar{ \mathbf{z}_n}$ and $\mathbf{z}_{n, i}$ implies that $\{\bar{ \mathbf{z}}_n\}_{n = 1}^\infty$ and $\{ \mathbf{z}_{n, i}\}_{n = 1}^\infty, i = 1, 2, \ldots, m,$ are bounded. □

The following conditions on parameters are needed to guarantee the convergence result of Algorithm 1.

Assumption 3.4. The sequence $\{\alpha_n\}_{n = 0}^{\infty}$ and $\{\epsilon_{n, i}\}_{n = 1}^{\infty}, i = 1, \ldots, m$, satisfy the following properties:

(i) $\sum_{n = 0}^\infty\alpha_n = \infty$ and $\sum_{n = 0}^\infty\alpha^2_n < \infty$.

(ii) $\sum_{n = 1}^\infty\epsilon_{n, i} < \infty$ for all $i = 1, 2, \ldots, m$.

Remark 3.5. One may choose sequences $\alpha_n: = \frac{\alpha}{(n+1)^a}$ and $\epsilon_{n, i}: = \frac{\epsilon}{(n+1)^b}$, where $a, b, \alpha, \epsilon > 0$ such that $a\in\left(\frac{1}{2}, 1\right]$ and $b > 1$, for particular examples of the sequences $\{\alpha_n\}_{n = 0}^{\infty}$ and $\{\epsilon_{n, i}\}_{n = 1}^{\infty}$, $i = 1, 2, \ldots, m$, satisfy Assumption 3.4.

The following assumption forms a key tool in proving the convergence result.

Assumption 3.6. There exists a real number $c > 0$ such that

Remark 3.7. Assumption 3.6 can be seen as a deterministic version of the assumptions proposed in [25, Assumption 2] and [10, Assumption 2]. The condition given in Assumption 3.6 is also related to the notion of linear regularity of a finite collection of sets; see [25, pages 231–232] for further details. A simple example of the constraint set $X$ that satisfies Assumption 3.6 is, for instance, $X: = X_0\cap Y_1\cap Y_2$ where $X_0: = [0, 1]\times[0, 1]$, $Y_1 = \{ \mathbf{x}: = (x_1, x_2)\in\mathbb{R}^2:g_1(\mathbf{x}): = x_1-x_2\leq0\}$ and $Y_2 = \{ \mathbf{x}: = (x_1, x_2)\in\mathbb{R}^2:g_2(\mathbf{x}): = -2x_1+x_2\leq0\}$. It can be seen that for all $c\geq1$, we have $\mathrm{dist}^2(\mathbf{x}, X)\leq\frac{c}{2}\left((g_1^{+}(\mathbf{x}))^2+(g_2^{+}(\mathbf{x}))^2\right)$ for all $\mathbf{x}\in X_0$.

4.   Convergence results

In this section, we will consider the convergence properties of the generated sequences. We divide this section into three parts. Namely, we start with the first subsection by providing some useful technical relations for the generated sequences. We subsequently prove the convergence of the generated sequences to an optimal solution in the second subsection. We close this section by deriving the rate of convergence of the function values of iterate to the optimal value of the considered problem.

4.1.   Technical lemmas

The following lemma provides an essential relation between the iterates $\mathbf{v}_{n+1}$ and $\mathbf{x}_n$ which are used to derive some consequence relations for the generated iterates.

Lemma 4.1. Let $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ and $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ be the sequences generated by Algorithm 1. Then, for every $n\geq0$, $\eta > 0$ and $\mathbf{x}\in X_0$, we have

Proof. Let $n\geq0$, $\eta > 0$, and $\mathbf{x}\in X_0$ be given. We first note that

Now, it follows from the definition of $\mathbf{v}_{n+1}$ and the optimality condition for constrained optimization that

which is the same as

This, along with the facts that $\mathbf{x}\in X_0$ and $\mathbf{v}_{n+1}\in X_0$, yield

or, equivalently, that

Thus, we employ the relation (4.2) in (4.1) and obtain the following:

We note from the first-order characterization of the convex function that

Now, for the upper bound of the term $2\alpha_{n}\langle\nabla f(\mathbf{x}_n), \mathbf{x}_n- \mathbf{v}_{n+1}\rangle$, we note from the well known Young's inequality that

Moreover, for a given subgradient $\mathbf{s}_h(\mathbf{x}_n)\in\partial h(\mathbf{x}_n)$, we note that

By using the obtained relations (4.4)–(4.6) in the inequality (4.3), we derive that

which is nothing else than the required inequality. □

Lemma 4.2. Let $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ and $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ be the sequences generated by Algorithm 1. Then, for every $n\geq0$, $\eta > 0$ and $\mathbf{x}^*\in X^*$, we have

Proof. Let $n\geq0$, $\eta > 0$, and $\mathbf{x}^*\in X^*$ be given. For a given $\mathbf{s}_{\phi}(\mathbf{x}^*)\in\partial\phi(\mathbf{x}^*)$, we note from the definition of subgradient that

where the second inequality holds true by the necessary and sufficient optimality conditions for convex constrained optimization. Similarly, for a given $\mathbf{s}_{\phi}(P_X(\mathbf{x}_n))\in\partial\phi(P_X(\mathbf{x}_n))$, we have

By adding these two obtained relations (4.7) and (4.8) and subsequently multiplying by $\frac{1}{2}$, we obtain

Applying this together with the inequality in Lemma 4.1, we obtain that

as desired. □

We now derive a relation between the iterates $\mathbf{v}_n$ and $\mathbf{z}_{n, i}$.

Lemma 4.3. Let $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ and $\{ \mathbf{z}_{n, i}\}_{n = 1}^{\infty}$, $i = 1, \ldots, m$, be the sequences generated by Algorithm 1. Then, for every $n\geq1$, $i = 1, 2, \ldots, m$ and $\mathbf{x}\in X$, we have

Proof. Let $n\geq1$, $i = 1, 2, \ldots, m$ and $\mathbf{x}\in X$ be given. We note from the definition of $\mathbf{z}_{n, i}$ that

If $g_i^{+}(\mathbf{v}_n) = 0$, then it is clearly that

We now consider the case $g_i^{+}(\mathbf{v}_n) > 0$ as follows: Since $\mathbf{d}_{n, i}\in\partial_{\epsilon_{n, i}} g_i^{+}(\mathbf{v}_n)\backslash\{\mathbf{0}\}$, we note that

which is

We also note that

and

Applying these obtained relations in (4.9), we get

as desired. □

In order to derive the relation between $\mathrm{dist}^2(\mathbf{x}_n, X)$ and $\mathrm{dist}^2(\mathbf{v}_n, X)$, we need the following fact:

Proposition 4.4. Let $\mathbf{z}_1, \mathbf{z}_2, \ldots, \mathbf{z}_m\in\mathbb{R}^k$ and $\bar{ \mathbf{z}} = \frac{1}{m}\sum_{i = 1}^{m} \mathbf{z}_i$ be given. Then, for every $\mathbf{x}\in\mathbb{R}^k$

Proof. It is straightforward based on the properties of the inner product and norm. □

We are now considering the relation between $\mathrm{dist}^2(\mathbf{x}_n, X)$ and $\mathrm{dist}^2(\mathbf{v}_n, X)$ in the following lemma.

Lemma 4.5. Let $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ and $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ be the sequences generated by Algorithm 1. Then, for every $n\geq1$, we have

where $\overline{D} = \max\{D, 1\}$.

Proof. Let $n\geq1$ be given. Since $\mathbf{x}_n = P_{X_0}(\bar{ \mathbf{z}}_n)$, it is noted, for all $\mathbf{x}\in X\subset X_0$, that

Since $\bar{ \mathbf{z}}_n = \frac{1}{m}\sum\limits_{i = 1}^{m} \mathbf{z}_{n, i}$, we note from Proposition 4.4 that for all $\mathbf{x}\in X$,

which implies that the inequality (4.10) becomes

for all $\mathbf{x}\in X$. By summing up the inequality obtained in Lemma 4.3 for $i = 1$ to $m$, and, subsequently, dividing by $m$ for both sides of the inequality, we have

This, together with inequality (4.11), means that for all $\mathbf{x}\in X$,

Invoking the bounds given in Proposition 3.3, we have for every $\mathbf{x}\in X$ that

Putting $\mathbf{x} = P_X(\mathbf{v}_n)\in X$ in the inequality (4.12), we obtain

and hence

□

As a consequence of the preceding lemmas, we obtain the following relation that is used to prove the convergence of the sequence $\{\| \mathbf{v}_n- \mathbf{x}^*\|^2\}_{n = 1}^{\infty}$ for all $\mathbf{x}^*\in X^*$.

Lemma 4.6. Let $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ and $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ be the sequences generated by Algorithm 1. Then, for every $n\geq0$, $\eta > 0$ and $\mathbf{x}^*\in X^*$, we have

where $\overline{D} = \max\{D, 1\}$.

Proof. Let $n\geq1$, $\eta > 0$, and $\mathbf{x}^*\in X^*$ be given. By using the inequality (4.12) and replacing $\mathbf{x}\in X$ by $\mathbf{x}^*$, which also belongs to $X$, we note that

Furthermore, by applying Young's inequality, we note that

Invoking these two relations in the inequality obtained in Lemma 4.2, we get that

which is the required inequality. □

4.2.   Convergence of iterates

In order to obtain the existence of the limit of the sequence $\{\| \mathbf{v}_n - \mathbf{x}^*\|\}_{n = 1}^{\infty}$, we need the following proposition:

Proposition 4.7. ^[26] Let $\{a_n\}_{n = 1}^{\infty}$, $\{b_n\}_{n = 1}^{\infty}$ and $\{c_n\}_{n = 1}^{\infty}$ be sequences of nonnegative real numbers. If it holds that $a_{n+1}\leq a_{n}+b_n-c_n$ for all $n\geq1$, and $\sum_{n = 1}^{\infty}b_n < \infty$, then $\lim_{n\rightarrow \infty}a_n$ exists and $\sum_{n = 1}^{\infty}c_n < \infty$.

Now, we are in a position to prove the main convergence theorem. The theorem guarantees that both generated sequences $\{ \mathbf{v}_n\}_{n = 1}^{\infty}$ and $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ converge to a point in the solution set $X^*$.

Theorem 4.8. The sequences $\{ \mathbf{v}_n\}_{n = 1}^{\infty}$ and $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ generated by Algorithm 1 converge to an optimal solution in $X^*$.

Proof. Let $n\geq1$ be given. Since $\mathbf{v}_n\in X_0$, it follows from Assumption 3.5 that there exists a constant $c > 0$ such that

Now, putting $\overline{c} > 0$ such that

we have

This, together with (4.13) and Lemma 4.5, imply that

and then

By applying this obtained relation together with the inequality in Lemma 4.6, we have for all $\eta > 0$

Now, by putting $\eta: = \frac{q}{(1-q)} > 0$ in the above inequality, we can neglect the non-negative term $\left(\frac{q}{(1-q)}-\eta\right)\mathrm{dist}^2(\mathbf{x}_n, X)$ so that the above inequality can be written as

which implies that

Invoking Assumption 3.4 (ⅱ) together with Proposition 4.7 in (4.17), we conclude that the limit

and, as well as,

On the other hand, by applying the inequality (4.12) in the relation obtained in Lemma 4.1 by replacing $\mathbf{x}$ by $\mathbf{x}^*$, we note that

and then

Now, let us fix a positive integer $N\geq 1$. Summing up the above relation for $n = 1$ to $N$, we have

By approaching $N\to\infty$, we obtain that

Next, we show that $\liminf\limits_{n\rightarrow \infty}(\phi(\mathbf{x}_n)-\phi^*)\leq0.$ Suppose, to the contrary, that there exists $N'\in\mathbb{N}$ and $\beta > 0$ such that $\phi(\mathbf{x}_n)-\phi^*\geq\beta$ for all $n\geq N'$. Since

we also have $\liminf\limits_{n\rightarrow \infty}(\phi(\mathbf{x}_n)-\phi^*)\leq0,$ that is, $\liminf\limits_{n\rightarrow \infty}\phi(\mathbf{x}_n)\leq\phi^*.$

Now, since the sequence $\{ \mathbf{x}_n\}_{n = 1}^{\infty}$ is bounded, there exists a subsequence $\{ \mathbf{x}_{n_l}\}_{l = 1}^{\infty}$ of $\{ \mathbf{x}_n\}_{n = 1}^{\infty}$ such that $\lim\limits_{l\rightarrow \infty}\phi(\mathbf{x}_{n_l}) = \liminf\limits_{n\rightarrow \infty}\phi(\mathbf{x}_n)\leq \phi^*$. Moreover, since $\{ \mathbf{x}_{n_l}\}_{l = 1}^{\infty}$ is also a bounded sequence, there exists a subsequence $\{ \mathbf{x}_{n_{l_j}}\}_{i = 1}^{\infty}$ of $\{ \mathbf{x}_{n_l}\}_{l = 1}^{\infty}$ and a point $\hat{ \mathbf{x}}\in\mathbb{R}^k$ in which $\mathbf{x}_{n_{l_j}}\rightarrow \hat{ \mathbf{x}}$. Thus, by using (4.18), we have $\mathbf{v}_{n_{l_j}}\rightarrow \hat{ \mathbf{x}}$.

On the other hand, by utilizing the relation in (4.19), we note that for all $j\geq1$

Now, by using the fact that the sequence $\{|\phi(\mathbf{x}_n)-\phi^*|\}_{n = 1}^\infty$ is bounded, the continuity of each $g_i^{+}$, $i = 1, 2, \ldots, m$ and letting $j\rightarrow \infty$, we obtain

which implies that $\hat{ \mathbf{x}}\in\bigcap_{i = 1}^m \mathrm{Lev}(g_i, 0)$. Since the sequence $\{ \mathbf{x}_{n_{l_j}}\}_{j = 1}^{\infty}\subset X_0$, the closedness of $X_0$ yields that $\hat{ \mathbf{x}}\in X_0$, and hence $\hat{ \mathbf{x}}\in X: = X_0\cap\bigcap_{i = 1}^m \mathrm{Lev}(g_i, 0)$.

Finally, by using the continuity of $\phi$, we obtain that

which implies that $\hat{ \mathbf{x}}\in X^*$. Therefore, we conclude that the sequence $\{ \mathbf{v}_n\}_{n = 1}^{\infty}$ converges to the point $\hat{ \mathbf{x}}\in X^*$. This yields that the sequnce $\{ \mathbf{x}_n\}_{n = 1}^{\infty}$ also converges to the point $\hat{ \mathbf{x}}\in X^*$. This completes the proof. □

4.3.   Rate analysis

In this subsection, we consider the rate of convergence of the objective values $\{\phi(\mathbf{x}_n)\}_{n = 0}^{\infty}$ to the optimal value $\phi^*$.

Theorem 4.9. Let $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ and $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ be the sequences generated by Algorithm 1. Then, for a positive integer $N\geq1$, it holds that

where $\overline{c} > \max\left\{c, \frac{1}{\overline{D}^2}\right\}$ and $\overline{D} = \max\{D, 1\}$.

Proof. We note from the inequality (4.20) that for all positive integers $N\geq1$

which implies that

By using the property of $\overline{c}$ given in (4.14) that $\overline{c} > \max\left\{c, \frac{1}{\overline{D}^2}\right\}$, the definition of $q$ in (4.15) that $0 < q: = \frac{1}{\overline{c}\overline{D}^2} < 1$ and the definition of $\eta$ that $\eta: = \frac{q}{(1-q)} > 0$, we note that

This yields that

and hence

as required. □

To obtain the convergence rate of the objective function, we need the following proposition:

Proposition 4.10. [22, Lemma 8.26] Let $f:[a-1, b+1]\to \mathbb{R}$ be a continuous, nonincreasing real-valued function over $[a-1, b+1]$, where $a$ and $b$ are integers such that $a\leq b$. Then

We close this subsection by considering a particular stepsize sequence $\{\alpha_n\}_{n = 0}^\infty$ in Theorem 4.9 to obtain the $\mathcal{O}\left(\frac{1}{N^{1-a}}\right)$ rate of convergence of the function values of iterate to the optimal value of the considered problem, where $a\in (0.5, 1)$.

Corollary 4.11. Let $\{ \mathbf{x}_n\}_{n = 0}^{\infty}$ and $\{ \mathbf{v}_{n}\}_{n = 1}^{\infty}$ be the sequences generated by Algorithm 1. If the sequence $\{\alpha_n\}_{n = 0}^{\infty}$ is given by

for all $n\geq0$, where $a\in(0.5, 1)$, then for a positive integer $N\geq1$, it holds that

Proof. Let us note from Proposition 4.10 that

and

which implies that

Furthermore, we note that $\left(\frac{N+2}{N+3}\right)^{1-a}\geq\left(\frac{3}{4}\right)^{1-a}$ and $\left(\frac{2}{N+3}\right)^{1-a}\leq\left(\frac{1}{2}\right)^{1-a}$, we have

Hence, by putting $M_1: = \frac{2M}{m}\sum\limits_{i = 1}^m\sum\limits_{n = 1}^{\infty}\epsilon_{n, i}$ and applying the inequality derived in Theorem 4.9, we obtain that

and the proof is completed. □

5.   Numerical example

In this section, we consider the numerical behaviors of the proposed method (Algorithm 1) for solving the minimum-norm solution to the intersection of a finite number of closed balls and a box constraint of the following form. Let $\mathbf{c}_i\in \mathbb{R}^k$, $i = 1, \ldots, m$, be given vectors, and $a, b\in \mathbb{R}$. The problem is to find a vector $\mathbf{x}\in \mathbb{R}^k$ that solves the problem

This problem can be written in another form as

which is clearly a particular situation of the problem (1.1) in the case when $f(\mathbf{x}) = 0.5\| \mathbf{x}\|^2$, $h(\mathbf{x}) = 0$, $g_i(\mathbf{x}) = \| \mathbf{x} - \mathbf{c}_i\|-1$ for all $i = 1, \ldots, m$, and $X_0 = [0, 1.5]^k$.

In the first experiment, we examine the influence of the step size $\alpha_n: = \frac{\alpha}{(n+1)}$. We perform Algorithm 1 for solving the problem (5.1) when the number of target sets $m = 1000$. We set $\epsilon_{n, i} = 0$ for all $n\geq0$ and $i = 1, \ldots, m$. We choose the vector $\mathbf{c}_i$ by randomly choosing its coordinates in the interval $(1, 1.5)$, and the initial vector $\mathbf{x}_0$ is the vector whose all coordinates are $0.1$. We consider the parameter $\alpha\in [0.1, 0.9]$ in the step size $\alpha_n$ and the dimensions $k = 2, 5$ and $10$. We perform $10$ independent random tests for each choice of $\alpha$ and $k$ and terminate Algorithm 1 when the relative error $\frac{\| \mathbf{v}_{n+1}- \mathbf{v}_n\|}{\| \mathbf{v}_n\|+1}$ reaches the optimal error tolerance of $10^{-5}$. The averaged results of computational runtimes in seconds and the number of iterations and computational runtimes in seconds for each choice of $\alpha$ and $k$ are plotted in Figure 1. As we can see from Figure 1, for each dimension $k$, the parameter $\alpha = 0.1$ gives the least number of iterations and computational runtimes.

In the following experiment, we examine the influence of the error tolerances $\{\epsilon_{n, i}\}_{n = 1}^{\infty}$ for all $i = 1, 2, \ldots, m$. We consider the parameter $\epsilon = 0, 0.1, 0.3, 0.5, 0.7$ and $0.9$ in the error tolerance $\epsilon_{n, i} = \frac{\epsilon}{(n+1)^2}$ with various dimensions $k$ and number of target sets $m$. It is noted that for this tested problem, Algorithm 1 with $\epsilon = 0$ is a particular case of the method proposed by Nedic and Necoara ^[10], where the batch size is $m$. We set the step size $\alpha_n: = \frac{0.1}{(n+1)}$ and performed the above experiment. The averaged results of computational runtimes in seconds are given in Table 1.

One can see from the results presented in Table 1 that the averaged runtime increases for all $k$ and $m$ increases. It can be seen that the proposed method with the error-tolerance parameter $\epsilon\neq0$ requires less averaged runtimes compared to the case when $\epsilon = 0$ for almost all the number of target sets $m$. Even if we can not point out which choice of error-tolerance parameters $\epsilon\neq0$ yields the best performance for all $k$ and $m$, the results show us that the averaged runtime can be improved by some suitable choices of error tolerances. This also underlines the benefit of the approximate subgradient-type method proposed in this work.

6.   Conclusions

We concentrated on addressing the convex minimization problem across the intersection of a finite number of convex level sets. Our approach centered on introducing the distributed approximate subgradient method tailored to tackle this particular problem. To guarantee the convergence of our proposed method, we provided a rigorous proof demonstrating that the sequences generated by the method converge to an optimal solution. Furthermore, the $\mathcal{O}\left(\frac{1}{N^{1-a}}\right)$ rate of convergence of the function values of iterate to the optimal value of the considered problem, where $a\in (0.5, 1)$. Additionally, we illustrated our findings through several numerical examples aimed at examining the impact of error tolerances. While identifying the optimal error tolerance remains a significant consideration, our experimental results indicate that the average runtime can be enhanced by selecting suitable nonzero error tolerances as opposed to omitting them altogether. This observation suggests an intriguing avenue for future research exploration.

Author contributions

Jedsadapong Pioon: Conceptualization, Methodology, Validation, Convergence analysis, Investigation, Writing-original draft preparation, Writing-review and editing; Narin Petrot: Conceptualization, Methodology, Software, Validation, Convergence analysis, Investigation, Writing-review and editing, Visualization; Nimit Nimana: Conceptualization, Methodology, Software, Validation, Convergence analysis, Investigation, Writing-original draft preparation, Writing-review and editing, Visualization, Supervision, Project administration, Funding acquisition. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

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

Acknowledgments

The authors would like to thank three anonymous referees for their useful suggestions and comments.

This work has received funding support from the NSRF via the Program Management Unit for Human Resources & Institutional Development, Research and Innovation [grant number B05F650018].

Conflict of interest

The authors declare that there is no conflict of interest regarding the publication of this article.