Primal-dual $\varepsilon$-Subgradient Method for Distributed Optimization ^††thanks: This work was supported by National Natural Science Foundation of China under Grants 61973043.

The last decade has witnessed considerable interests in distributed optimization problems due to the numerous applications in signal processing, control, and machine learning. To solve this problem, subgradient information of the objective functions has been widely used due to the cheap iteration cost and well-established convergence properties [1, 2].

Note that most of these subgradient-based results assume the availability of local cost function’s exact subgradients. In many circumstances, the function subgradient is computed by solving another auxiliary optimization problem as shown in [3, 5, 4]. In practice, we are often only able to solve these subproblems approximately. Hence, in that context, numerical methods solving the original optimization problem are provided with only inexact subgradient information. This leads us to investigate the solvability of distributed optimization problem using inexact subgradient information.

A close topic is the inexact augmented Lagrangian method. As surveyed in [6], this method has been extensively extended to distributed settings in various ways assuming the primal variables are only obtained in an approximate sense. Nevertheless, most of these results still require the exact gradient or subgradient information of the local objective functions at each given estimate. It is interesting to ask whether the primal-dual method is still effective when only inexact gradient/subgradient information is available.

In this paper, we focus on a typical distributed consensus optimization problem for a sum of convex objective functions subject to heterogeneous set constraints. Although this problem has been partially studied by gradient/subgradient methods in [7, 8, 9, 10, 11, 12, 13, 14], its solvability using only inexact subgradient information has not yet been addressed and is still unclear at present.

To solve this problem, we first convert it into a distributed saddle point seeking problem and present a projected primal-dual $\varepsilon$-subgradient dynamics to handle both the distributedness and constraints. When the objective functions are smooth with exact gradients, the proposed algorithms reduce to the primal-dual dynamics considering in [10, 8]. Then, we discuss the convergent property with diminishing step sizes and suboptimality of the proposed algorithm depending on the accuracy of available subgradients. In particular, we show that if the accumulated error resulting from the subgradient inexactness is not too large, the proposed algorithm under certain diminishing step size will drive all the estimates of agents to reach a consensus about an optimal solution to the global optimization problem. To our knowledge, this might be the first attempt to solve the formulated distributed optimization problem using only inexact subgradients of the local objective functions. To improve the transient performance of our preceding designs, we further propose a novel componentwise normalized step size as that in [14]. As a byproduct, this normalized step size removes the widely used subgradient boundedness assumption in the literature [7, 8].

The rest of this paper is organized as follows. We first give some preliminaries in Section 2 and then introduce the formulation of our problem in Section 3. Main results are presented in Section 4. After that, we give a numerical example in Section 5 to show the effectiveness of our design. Finally, some concluding remarks are given in Section 6.

In this section, we first give some preliminaries about graph theory and convex analysis.

In this paper, we focus on solving the following constrained optimization problem by a network of $N$ agents:

$\displaystyle\begin{split}\min&\quad f(x)=\sum_{i=1}^{N}f_{i}(x)\\ \mbox{s.t.}&\quad x\in X\triangleq\bigcap_{i=1}^{N}X_{i}\end{split}$

(1)

Here function $f_{i}\colon\mathbb{R}\to\mathbb{R}$ and set $X_{i}$ are private to agent $i$ for each $i\in\mathcal{N}\triangleq\{1,\,2,\,\dots,\,N\}$ and can not be shared with others.

To ensure its solvability, the following assumption is made.

Note that $f_{i}$ might be nondifferentiable under this assumption. Denote the minimal value of problem (1) by $f^{*}$ and the optimal solution set by $\cal{X}^{*}$, i.e., $f^{*}=\min_{x\in X}f(x)$ and $\mathcal{X}^{*}=\{x\in X\mid f(x)=f^{*}\}$. As usual, we assume $f^{*}$ is finite and set $\mathcal{X}^{*}$ is nonempty. To cooperatively address the optimization problem (1) in a distributed manner, we use a weighted undirected graph $\mathcal{G}=\{\mathcal{N},\,\,\mathcal{E},\,\mathcal{A}\}$ to describe the information sharing relationships with node set $\mathcal{N}$, edge set $\mathcal{E}\subset\mathcal{N}\times\mathcal{N}$, and weight matrix $\mathcal{A}=[a_{ij}]_{N\times N}$. Here $a_{ij}=a_{ji}>0$ means agents $i$ and $j$ can communicate with each other.

Suppose agent $i$ maintains an estimate $x_{i}$ of the optimal solution to (1) with other (possible) auxiliary variables. Agents exchange these variables through the communication network described by $\mathcal{G}$ and perform some updates at given discrete-time instants $k=1,\,2,\,\dots$. Then, the distributed optimization problem in this paper is formulated to find an update rule of $x_{i}(k)$ for agent $i$ using only its own and neighboring information such that $\lim_{k\to\infty}[x_{i}(k)-x_{j}(k)]=0$ for any $i,\,j\in\mathcal{N}$ and $\lim_{k\to\infty}\sum_{i=1}^{N}f_{i}(x_{i}(k))=f^{*}$. If possible, we expect that all the estimates will converge to an optimal solution to problem (1).

As stated above, this problem has been intensively studied in literature [1, 2]. However, most existing designs require the exact subgradients of the local objective functions in constructing effective distributed algorithms. In this paper, we are interested in the solvability of the formulated distributed constrained optimization problem (1) working with inexact subgradients of the local objective functions. For this purpose, we adopt the notion of $\varepsilon$-subgradient to describe such inexactness as in [15] and assume the $\varepsilon$-subgradient of $f_{i}$ can be easily computed for any given $\varepsilon\geq 0$.

Denote by $\partial_{\varepsilon}f(x)$ the $\varepsilon$-subdifferential of $f$ at $x\in\mathbb{R}^{m}$, which is the set of all $\varepsilon$-subgradients of $f$ at $x$. $\partial_{\varepsilon}f(x)$ is nonempty and convex for any $x\in\mathbb{R}^{m}$ due to the convexity of $f$. Moreover, $\partial_{0}f(x)$ coincides with the subdifferential of $f$ at $x\in\mathbb{R}^{m}$.

In next section, we will convert our problem into a saddle-point seeking problem and develop a projected primal-dual $\varepsilon$-subgradient method with rigorous solvability analysis.

To begin with, we rewrite problem (1) into an alternative form as that in [10, 16]:

	$\displaystyle\min~{}~{}$	$\displaystyle\tilde{f}({\bf x})=\sum_{i=1}^{N}f_{i}(x_{i})$
	s.t.	$\displaystyle L{\bf x}={\bf 0}_{N}$		(2)
		$\displaystyle{\bf x}\in\tilde{X}\triangleq X_{1}\times\dots\times X_{N}$

where ${\bf x}=\mathrm{col}(x_{1},\,\dots,\,x_{N})$ and $L$ is the Laplacian of graph $\mathcal{G}$. Note that $L$ is symmetric and positive semi-definite with its ordered eigenvalues as $0=\lambda_{1}<\lambda_{2}\leq\dots\lambda_{N}$ under Assumption 2 by Theorem 2.8 in [17].

Consider the augmented Lagrangian function of problem (4):

$\displaystyle\Phi({\bf x},\,{\bf v})=\tilde{f}({\bf x})+{\bf v}^{\intercal}L{\bf x}+\frac{1}{2}{\bf x}^{\intercal}L{\bf x}$

(3)

with ${\bf v}=\mbox{col}(v_{1},\,\dots,\,v_{N})\in\mathbb{R}^{N}$. By Proposition 3.4.1 in [3], if $\Phi$ has a saddle point $({\bf x}^{*},\,{\bf v}^{*})$ in $\tilde{X}\times\mathbb{R}^{N}$, then ${\bf x}^{*}$ must be an optimal solution to problem (4), which in turn provides an optimal solution to (1). Since the Slater’s condition holds under Assumption 1, such saddle points indeed exist by virtue of Theorems 3.34 and 4.7 in [18]. Thus, it suffices for us to seek a saddle point of $\Phi$ in $\tilde{X}\times\mathbb{R}^{N}$.

Following this conversion, many solvability results on problem (1) have been presented when the exact gradient or subgradient of $f_{i}$ is available, e.g., [19, 20, 16, 10, 21, 14]. However, whether and how $\varepsilon$-subgradient algorithms can be derived has not been discussed yet. To this end, we are motivated by aforementioned saddle-point seeking designs and present the following dynamics:

$\displaystyle\begin{split}x_{i}(k+1)&=P_{X_{i}}[x_{i}(k)-\alpha_{k}(g_{i}(k)+\hat{x}_{i}(k)+\hat{v}_{i}(k))]\\ v_{i}(k+1)&=v_{i}(k)+\alpha_{k}\hat{x}_{i}(k)\end{split}$

(4)

where $\hat{x}_{i}(k)\triangleq\sum_{j=1}^{N}a_{ij}(x_{i}(k)-x_{j}(k))$, $\hat{v}_{i}(k)\triangleq\sum_{j=1}^{N}a_{ij}(v_{i}(k)-v_{j}(k))$, and $g_{i}(k)\in\partial_{\varepsilon_{k}}f_{i}(x_{i}(k))$ with parameters $\varepsilon_{k},\,\alpha_{k}>0$ to be specified later. It can be taken as a constrained version of algorithms in [19, 20]. Different from similar primal-dual designs in [10, 16], we do not require the differentiability of these objective functions or their exact gradients.

Letting ${\bf x}(k)=\mathrm{col}(x_{1}(k),\dots,x_{N}(k))$ and ${\bf v}(k)=\mathrm{col}(v_{1}(k),\dots,v_{N}(k))$, we can put (4) into a compact form:

$\displaystyle\begin{split}{\bf x}(k+1)&=P_{\tilde{X}}[{\bf x}(k)-\alpha_{k}({\bf g}(k)+L{\bf v}(k)+L{\bf x}(k))]\\ {\bf v}(k+1)&={\bf v}(k)+\alpha_{k}L{\bf x}(k)\end{split}$

(5)

with ${\bf g}(k)=\mathrm{col}(g_{1}(k),\,\dots,\,g_{N}(k))\in\partial_{N\varepsilon_{k}}\tilde{f}({\bf x}(k))\in\mathbb{R}^{N}$. It can be further rewritten as follows.

$\displaystyle{\bf z}(k+1)=P_{\overline{X}}[{\bf z}(k)-\alpha_{k}T_{\varepsilon_{k}}({\bf z}(k))]$

(6)

where ${\bf z}(k)=\mathrm{col}({\bf x}(k),\,{\bf v}(k))$, $\overline{X}=\tilde{X}\times\mathbb{R}^{N}$, and

$\displaystyle T_{\varepsilon_{k}}({\bf z}(k))=\begin{bmatrix}{\bf g}(k)+L{\bf v}(k)+L{\bf x}(k)\\ -L{\bf x}(k)\end{bmatrix}$

To establish the effectiveness of this algorithm, another assumption is made as follows.

This assumption is temporally made for simplicity as in [22, 8] and will be further removed later by some novel step sizes later. Suppose ${\bf z}^{*}=\mathrm{col}({\bf x}^{*},\,{\bf v}^{*})$ is a saddle point of $\Phi$ in $\tilde{X}\times\mathbb{R}^{N}$. Here is a key lemma under Assumption 3.

Next, we consider the evolution of $||{\bf z}(k)-{\bf z}^{*}||^{2}$ with respect to $k$. Under the iteration (4), it follows then

		$\displaystyle||{\bf z}(k+1)-{\bf z}^{*}||^{2}$
		$\displaystyle\qquad=||P_{\overline{X}}[{\bf z}(k)-\alpha_{k}T_{\varepsilon_{k}}({\bf z}(k))]-{\bf z}^{*}||^{2}$
		$\displaystyle\qquad\leq||{\bf z}(k)-\alpha_{k}T_{\varepsilon_{k}}({\bf z}(k))-{\bf z}^{*}||^{2}-||{\bf z}(k)-\alpha_{k}T_{\varepsilon_{k}}({\bf z}(k))-P_{\overline{X}}[{\bf z}(k)-\alpha_{k}T_{\varepsilon_{k}}({\bf z}(k))]||^{2}$
		$\displaystyle\qquad\leq||{\bf z}(k)-{\bf z}^{*}||^{2}-2\alpha_{k}({\bf z}(k)-{\bf z}^{*})^{\intercal}T_{\varepsilon_{k}}({\bf z}(k))+\alpha_{k}^{2}||T_{\varepsilon_{k}}({\bf z}(k))||^{2}$		(8)

By the proprieties of saddle point and $\varepsilon_{k}$-subgradient, we have

	$\displaystyle({\bf z}(k)-{\bf z}^{*})^{\intercal}T_{\varepsilon_{k}}({\bf z}(k))$	$\displaystyle=({\bf x}(k)-{\bf x}^{*})^{\intercal}({\bf g}(k)+L{\bf v}(k)+L{\bf x}(k))-({\bf v}(k)-{\bf v}^{*})^{\intercal}L{\bf x}(k)$
		$\displaystyle\geq\tilde{f}({\bf x}^{k})-\tilde{f}({\bf x}^{*})-N\varepsilon_{k}+{{\bf v}^{*}}^{\intercal}L{\bf x}(k)+{\bf x}(k)^{\intercal}L{\bf x}(k)$
		$\displaystyle=\Phi({\bf x}(k),\,{\bf v}^{*})-\Phi({\bf x}^{*},\,{\bf v}^{*})+\frac{1}{2}{\bf x}(k)^{\intercal}L{\bf x}(k)-N\varepsilon_{k}$		(9)
		$\displaystyle=\Delta({\bf x}(k))-N\varepsilon_{k}$

Since $L{\bf x}^{*}={\bf 0}$, $T_{\varepsilon_{k}}({\bf z}(k))$ can be rewritten as

$\displaystyle T_{\varepsilon_{k}}({\bf z}(k))=\begin{bmatrix}{\bf g}(k)+L({\bf x}(k)-{\bf x}^{*})+L({\bf v}(k)-{\bf v}^{*})+L{\bf v}^{*}\\ -L({\bf x}(k)-{\bf x}^{*})\end{bmatrix}$

Under Assumption 3, there must be constant $C_{1}>0$ such that

$\displaystyle||T_{\varepsilon_{k}}({\bf z}(k))||^{2}\leq C_{1}(1+||{\bf z}(k)-{\bf z}^{*}||^{2})$

(10)

Putting all inequalities (4)–(10) together, we have

$\displaystyle||{\bf z}(k+1)-{\bf z}^{*}||^{2}$

$\displaystyle\leq(1+C_{1}\alpha_{k}^{2})||{\bf z}(k)-{\bf z}^{*}||^{2}-2\alpha_{k}\Delta({\bf x}(k))+2N\alpha_{k}\varepsilon_{k}+C_{1}\alpha_{k}^{2}$

which is exactly the expected inequality (7).  

When the exact subgradient is available (i.e., $\varepsilon_{k}=0$), the inequality (7) can be simplified into the well-known supermartingale inequality ensuring the convergence of ${\bf z}(k)$ towards ${\bf z}^{*}$ as shown in [3] if $\{\alpha_{k}\}$ is chosen to satisfy

$\displaystyle\sum_{k=1}^{\infty}\alpha_{k}=\infty,\quad\sum_{k=1}^{\infty}\alpha_{k}^{2}<\infty$

(11)

However, the inexactness of available subgradients deteriorates this property and the expected convergence might fail when we use only $\varepsilon$-subgradients in the iteration (4).

Let us denote $\overline{\Delta}=\liminf_{k\to\infty}\Delta({\bf x}(k))$ and take a closer look at the inequality (7). Note that $\overline{\Delta}$ consists of two parts, i.e., the discrepancy of function values and violation of constraints (in term of consensus error) of the iterative sequence. It can be taken as a measure of suboptimality of the iterative sequence. In other words, we can determine the upper bound for $\overline{\Delta}$ to evaluate the effectiveness of algorithm (4).

We first consider the case when $\varepsilon_{k}$ is a constant.

Note that $1+\theta\leq e^{\theta}$ for any $\theta>0$. Hence $\prod_{k=K}^{\overline{K}}(1+C_{1}\alpha_{k}^{2})\leq e^{C_{1}\sum_{k=K}^{\overline{K}}\alpha_{k}^{2}}\leq e^{C_{1}\sum_{k=1}^{\infty}\alpha_{k}^{2}}$. Under the condition (11), there must exist a positive scalar $\overline{C}>0$ such that

$\displaystyle||{\bf z}({\overline{K}}+1)-{\bf z}^{*}||^{2}$

$\displaystyle\leq\overline{C}||{\bf z}(K)-{\bf z}^{*}||^{2}-\delta\sum_{k=K}^{\overline{K}}\alpha_{k}$

which can not hold for a sufficiently large $\overline{K}$ since $\sum_{k=1}^{\infty}\alpha_{k}=\infty$. We obtain a contradiction and complete the proof.  

With Theorem 1, it is natural for us to enforce some stronger condition on the error $\varepsilon_{k}$ for a better convergence performance of the entire sequence $\{x_{i}(k)\}$. Along this line, we provide another theorem supposing the accumulated error of subgradient inexactness is not too large.

Due to the uniform boundedness of sequence $\{{\bf z}(k)\}$ by item 1), there must be a convergent subsequence $\{{\bf z}_{k_{m}}\}$ of $\{{\bf z}_{k}\}$. We denote its limit by $\overline{\bf z}=\mathrm{col}(\overline{\bf x},\,\overline{\bf v})$. Then, it should satisfy $L\overline{\bf x}=0$ and $\tilde{f}(\overline{\bf x})=\lim_{m\to\infty}\tilde{f}({\bf x}_{k_{m}})=f^{*}$ by item 2). In other words, $\overline{\bf x}$ is an optimal solution to (4). By Assumption 2, one can conclude that there exists some $\overline{x}\in\mathbb{R}$ such that $\overline{\bf x}={\bf 1}_{N}\overline{x}$. Note that $f(\overline{x})=\tilde{f}(\overline{\bf x})=f^{*}$, i.e., $\overline{x}$ is an exact optimal solution to problem (1).

If $\mathcal{X}^{*}=\{x^{*}\}$ holds, all convergent subsequences of $\{{\bf{\bf x}}(k)\}$ have the same limit $x^{*}$. This combined with the boundedness of $\{{\bf{\bf z}}(k)\}$ implies item 4) and completes the proof.  

It is known that normalization might improve the transient performance of the algorithms to avoid overshoots at the starting phase. However, conventional normalized techniques often involve some global information and can not be directly implemented in distributed settings. We here present a novel componentwise normalized version of algorithm (4) as follows.

	$\displaystyle x_{i}(k+1)$	$\displaystyle=P_{X_{i}}[x_{i}(k)-\frac{\alpha_{k}}{\max\{c,\,\delta_{ik,D}\}}(g_{i}(k)+\hat{x}_{i}(k)+\hat{v}_{i}(k))]$
	$\displaystyle v_{i}(k+1)$	$\displaystyle=v_{i}(k)+\frac{\alpha_{k}}{\max\{c,\,\delta_{ik,D}\}}\hat{x}_{i}(k)$		(16)
	$\displaystyle\delta_{ik,\,m}$	$\displaystyle=\begin{cases}\qquad||T^{i}_{\varepsilon_{k}}({\bf z}(k))||,&\,\mbox{when }m=1\\ \max_{j\in\mathcal{N}_{i}}\{\delta_{ik,\,m-1},\,\delta_{jk,\,m-1}\},&\,\mbox{when }2\leq m\leq D\end{cases}$

where integer $D\geq\mathrm{D}(\mathcal{G})+1$ with $\mathrm{D}(\mathcal{G})$ the diameter of graph $\mathcal{G}$ and $c>0$ is any given constant. Since $\mathrm{D}(\mathcal{G})$ or an upper bound can be computed by distributed rules [26], this normalized algorithm is implementable in a fully distributed manner by embedding a max-consensus subiteration.

Here is a corollary to state that the normalized algorithm (4) retains all the established properties in Theorem 2.