Distributed Optimization with Projection-free Dynamics

Inspired by the historical literature [27], we design a novel FW-based distributed dynamics for agents to solve the constrained optimization. Compared to the dynamics in [6, 7], a feasible descent direction is derived by solving optimization with a linear objective. Hence, the dynamics avoids solving complicated quadratic subproblems due to projection operations on set constraints, which actually leads to a projection-free dynamics. Our distributed projection-free dynamics accordingly induces a novel discrete-time format, where averaging consensus is employed both to ensure the consensus of local decision variables and to help auxiliary variables track the global gradient. This differs from the mechanism in the decentralized discrete-time FW algorithm of [28]. Hence, we develop a novel convergence analysis with the Lyapunov theory and comparison theorems, and provide the analysis on the convergence rate. Moreover, compared with the projected dynamics given in [6, 7] and the discrete-time FW algorithm in [28], the distributed projection-free dynamics is applied over the communication networks described by weight-balanced digraphs.

The organization of this paper is given as follows. Section II formulates the distributed constrained optimization with basic assumptions, and presents a projection-free algorithm with the corresponding discretization. Then Section III reports the main results, including the consensus of decision variables, global gradient tracking and convergence of the continuous-time algorithm, as well as the convergence rate of the induced discrete scheme. Finally, Section IV shows numerical examples with a comparison to the existing algorithms, while Section V provides some concluding remarks and discussions on future work.

Here we give some necessary notations in this paper. Denote $\mathbb{R}^{n}$ ( $\mathbb{R}^{m\times n}$) as the set of $n$-dimension ($m$-by-$n$) real column vectors (real matrices), $1_{n}$ (or $0_{n}$) as the $n$-dimensional column vectors with all elements of one (or zero), and $col\{x_{1},\dots,x_{n}\}=(x_{1}^{\rm T},\dots,x_{n}^{\rm T})^{\rm T}.$ Let $A\otimes B$ as the Kronecker product of matrices $A$ and $B$. In addition, take $\|\cdot\|$ as the Euclidean norm of vectors, and $\|\|_{F}$ as the Frobenius norm of real matrices defined by $\|Q\|_{F}=\sqrt{tr(Q^{T}Q)}.$

Consider $N$ agents indexed by $\mathcal{V}=\{1,2\dots,N\}$. For agent $i\in\mathcal{V}$, there is a local cost function $f_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ on the feasible set $\Omega\subseteq\mathbb{R}^{n}$. The global cost function is

All agents aim to solve the constrained optimization:

In a multi-agent network, the $i$th agent controls a local decision variable $x_{i}\in\Omega$ to search the optimal $x^{*}\in\arg\min F(x)\quad\text{s.t.},\;x\in\Omega.$ Also, the information of local cost functions are regarded as private knowledge. The agents communicate with their neighbors through a network described by a digraph $\mathcal{G}(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of nodes (regarded as agents here) and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges. $\mathcal{A}=[a_{ij}]\in\mathbb{R}^{N\times N}$ is the adjacency matrix subject to $a_{ij}>0$ if and only if $(i,j)\in\mathcal{E}$, which means that agent $j$ can send information to agent $i$, and $a_{ij}=0$, otherwise. The Laplacian matrix $\mathcal{L}=\mathcal{D}-\mathcal{A}$, where $\mathcal{D}\in\mathbb{R}^{N\times N}$ is diagonal with $\mathcal{D}_{i,i}=\sum_{j=1}^{N}a_{ij}$, for any $i\in\mathcal{V}$. A digraph $\mathcal{G}$ is strongly connected if there exists at least one directed path between any pair of vertices, and $\mathcal{G}$ is weight-balanced if $\sum_{j=1}^{N}a_{ij}=\sum_{j=1}^{N}a_{ji}$ for $i\in\mathcal{V}$.

In addition, the gradient of a differentiable function $f$ is $\kappa$-Lipschitz on convex set $C\subseteq\mathbb{R}^{n}$ with a constant $\kappa>0$, if

Also, the above is equivalent to the following:

Then we consider solving distributed optimization (1) under the following assumptions.

The differentiable cost functions enable us to use the gradient information as in [24, 28, 25]. Additionally, the strongly connected and weight-balanced digraph, as a generalization of connected undirected graphs, was studied in other continuous-time distributed algorithms [29, 16].

To solve the distributed optimization (1), we intend to explore a projection-free approach following the FW method. In fact, continuous-time algorithms provide evolved dynamics, which help reveal how each variable achieves the optimal solution with given directions. Also, the analysis techniques in modern calculus and nonlinear systems may lead to comprehensive results with mild assumptions in continuous-time schemes. Hence, we firstly propose a novel projection-free dynamics with the FW method in the following Algorithm 1, which differs from the projection-based continuous-time algorithms in [6, 7].

Algorithm 1 is distributed since the dynamics of the $i$th agent is only influenced by local values of $x_{i}$, $y_{i}$, $z_{i}$, $v_{i}$ and $\nabla f_{i}(x_{i})$. Specifically, the $i$th agent uses local decision variable $x_{i}$ to estimate the optimal solution $x^{*}\in\Omega$ and local optimal solution $v_{i}$ as a conditional gradient. Since each agent is merely capable to calculate its own gradient $\nabla f_{i}(x)$, rather than the global gradient $\frac{1}{N}\sum_{i=1}^{N}\nabla f_{i}(x)$, thus, $z_{i}$ serves as the variable that simultaneously operates two processes — one is to compute agent $i$’s local gradient, the other is to achieve consensus with neighbors’ local gradients, in order to estimate the global gradient. In fact, the gradient tracking method in [30, 31] motivates our algorithm design. Although the time-varying $\beta(t)$ seems to be a global parameter, it is easy to determine its value for all agents, by merely selecting some general decreasing functions like $\beta(t)=1/t$. That is analogous to other FW-based works dealing with parameters [28, 25].

So far, we have devoted to proposing distributed projection-free dynamics to avoid solving complex subproblems owing to projections. Following these instructive ideas in designing the above distributed continuous-time Algorithm 1, we consider deriving its implementable discretization. We notice the decentralized discrete-time FW algorithm in [28]. To make a comparison, we present the discretization of Algorithm 1 by adopting the notations in [28] in the following. To remain consistent with [28], set the network $\mathcal{G}$ undirected and connected, and adjacency matrix $\mathcal{A}$ as symmetric and doubly stochastic. Let $0<\delta<1$ be a fixed step-size in discretization, and denote $\eta^{k}=\delta\beta^{k}$. Take the weighted average of agent $i$’s neighbors $\mathcal{N}_{i}$ in the network $\mathcal{G}$ by

and similarly,

Then, consider the ODE in Algorithm 1

The corresponding difference equation is

Therefore, the discretization of Algorithm 1 gives

For clarification, the discrete-time FW in [28] is given as

The discretization above reveals that the major difference between (2) and (3) refers to the update protocol of $z_{i}^{k+1}$. In (2), agent $i$ uses both its neighbors’ gradient values and its own gradient renewal to track the global gradient. In (3), agent $i$ gathers the average value of neighbors’ decision variables to compute local gradient at first. Then agent $i$ makes again the neighbors’ average gradient value to estimate the global gradient. In other words, the consensus format in (3) requires agents to sequentially collect its neighbors’ decision variables $x_{j\in\mathcal{N}_{i}}^{k}$ and auxiliary variables $z_{j\in\mathcal{N}_{i}}^{k}$, which results in more communication burden and data storage. Consider that constructing a reliable communication link is time-consuming and energy-consuming in practice. Therefore, (2) overcomes this weak point by requiring agents to simultaneously collect the both variables. Since the mechanism of Algorithm 1 differs from what in [28], we need to explore new tools for analysis. In addition, we apply Algorithm 1 over weight-balanced digraphs as the generalization of undirected connected graphs in [28], which brings more technical challenges correspondingly.

For convenience of statements in the following, we first provide some compact notations here. Take

and $\bm{L}=\mathcal{L}\otimes I_{n}$. Also, define the profile of gradients

Equivalently, Algorithm 1 can be expressed in the following compact form

where $\bm{v}\triangleq col\{v_{1},\dots,v_{N}\}$ with

Hereupon, we can derive the following results for the convergence guarantees of Algorithm 1.

The following two lemmas are necessary for the analysis of Algorithm 1, whose proofs can be found in the appendix.

In this way, we give the proof of Theorem 1.

i). It follows from Lemma 1 that $x_{i}(t)\in{{\Omega}}$. Moreover, since $v_{i}(t)$ is chosen from $\Omega$, it implies that $v_{i}(t)-x_{i}(t)$ is bounded. Because $\beta(t)\rightarrow 0$ as $t\rightarrow\infty$, we have

Thus, the dynamics for decision variables in Algorithm 1 can be written as

where $\lim_{t\rightarrow\infty}u_{i}(t)=\bm{0}$. According to the existing results in [32, Section 4.3], all decision variables in (5) reach consensus, i.e.,

which yields the result.

Futhermore, let us invetigate the function

and consider its derivative along Algorithm 1 in the following.

where $\bm{I}=I_{nN}$. By Assumption 1, the digraph is strongly connected and weight-balanced, which yields

Hence,

where $\lambda_{2}$ is the smallest positive eigenvalue of $\frac{1}{2}(\bm{L}+\bm{L}^{T})$, and the last inequality follows from the fact $W(t)=W_{\perp}(t)$ and Rayleigh quotient theorem [33, Page 234]. Moreover,

It follows from Assumption 1 that $\nabla f_{i}$ is $\kappa$-Lipschitz on $\Omega$, which leads to the $\frac{k}{2}$ boundedness of $\|\nabla G(x)\|$. Thus,

So far, since $x_{i}(t)$ achieves consensus and $\beta(t)\rightarrow 0$ as $t\rightarrow\infty$, we have

which indicates that

Recall the properties that $\lambda_{2}>0$ and $\|\bm{I}-\frac{1}{N}\hat{\bm{1}}\hat{\bm{1}}^{T}\|_{F}>0$. Therefore, we learn from Lemma 2 that (III-A) yields

which implies that all variables $z_{i}$ track the dynamical global gradient.

Therefore,

Recall that we have already proved

as well as

Moreover, the positive parameter $\beta(t)$ satisfies

Hence, by Lemma 2 again, we have

Take $X^{*}\subseteq\Omega$ as the set of optimal solutions to problem (1), and

Since $\Omega$ is compact, there exists a point $x_{\infty}\in\Omega$ and a sequence $\{\overline{x}(t_{k}),k\in\mathbb{N}\}$ such that

and

Since $f_{i}$ is differentiable and $\rho$ is lower semicontinuous,

Thus,

which implies $x_{\infty}\in X^{*}$, i.e., the decision variable $x_{i}$ converges to an optimal solution to problem (1). $\square$