Distributed Nonconvex Multiagent Optimization Over Time-Varying Networks

I Introduction

Distributed optimization has found wide range of applications in several areas, including machine learning, data analysis, signal processing, networking, and decentralized control. Common to these problems is a network of agents$-$processors, computers of a cluster, nodes of a sensor network, vehicles, or UAVs$-$that want to cooperatively minimize a global cost function by means of actions taken by each agent and local coordination between neighboring nodes. In this paper, we consider the following general class of (possibly) nonconvex multiagent problems:

Our goal is developing solution methods for the nonconvex problem (1) in the following distributed setting: i) Each agent $i$ knows only its own function $f_{i}$ (as well as $G$ and $\mathcal{K}$); and ii) the communication topology connecting the agents is time-varying and directed, and it is not known to the agents. Time-varying communication topologies arise, for instance, in mobile wireless networks, wherein the nodes are mobile and/or communicate throughout (fast-)fading channels. Directed communication links are also a natural assumption as in many cases there is no reason to expect different nodes to transmit at the same power level or that transmitter and receivers are geographically collocated (e.g., think of ad-hoc networks).

Distributed solution methods for convex instances of Problem (1) have been widely studied in the literature, under various assumptions on network topology; some recent contributions include . The majority of the aforementioned works assume either undirected graphs or static directed graphs. Moreover all the algorithms developed in the aforementioned papers along with their convergence analysis are not applicable to nonconvex problems, and thus to Problem (1). We are aware of only few works dealing with distributed algorithms for some nonconvex instances of (1), namely: . Among them, our previous work is to date the only method applicable to the general class of nonconvex constrained problems in the form (1). However, the implementability of algorithm relies on the possibility of building a sequence of double-stochastic consensus matrices that are commensurate with the sequence of underlying time-varying communication digraphs. This can limit the applicability of the method in practice, especially when the network topology is time-varying, for several reasons. First, not all digraphs are doubly-stochasticable (i.e., admit a doubly stochastic adjacency matrix); some form of balancedness in the graph is needed , which limits the class of network topologies over which algorithm can be applied. Moreover, necessary and sufficient conditions for a digraph to be doubly-stochasticable are not easy to be checked in practice. Second, constructing a doubly-stochastic weight matrix matching the graph, even when possible, calls for computationally intense, generally centralized, algorithms. Third, double stochasticity prevents one from using natural broadcast schemes, in which a given agent may transmit its local estimate to all its neighbors without expecting any immediate feedback.

The analysis of the literature shows that the design of distributed algorithms for the class of problems (1) over time-varying, arbitrary digraphs is up to date a challenging and open problem, even in the case of convex cost functions $f_{i}$. This paper introduces the first broadcast-based distributed algorithmic framework for the aforementioned class of problems. The crux of the framework is a general convexification-decomposition technique that hinges on our recent (primal) Successive Convex Approximation (SCA) methods , coupled with i) a tacking mechanism that allows every agent $i$ to estimate locally the gradients of other agents’ functions $\sum_{j\neq i}f_{j}$; and ii) a novel broadcast protocol instrumental to distribute the computation and propagate the needed information over the network. We term the new scheme “distributed Successive cONvex Approximation algorithm over Time-varying digrAphs (SONATA)”. Some key desirable features of SONATA are: i) It is applicable to arbitrary (possibly) time-varying network topologies; ii) it is fully distributed, requiring neither the knowledge of the graph sequence nor the use of a double-stochastic consensus matrix; in fact, each agent just needs to broadcast its local estimates to all its neighbors without expecting any feedback; iii) it deals with nonconvex and nonsmooth objectives as well as (convex) constraints; and iv) it is very flexible in the choice of the approximations of $f_{i}$’s, which need not be necessarily its first or second order approximation (like in all current distributed gradient schemes). Asymptotic convergence to stationary solutions of Problem (1) is proved. Numerical results show that SONATA, applied to a number of convex and nonconvex problems, outperforms state-of-the-art schemes, in terms of practical convergence while reaching the same (stationary) solutions. As a final remark, we point out that the proposed broadcast protocol is different from the renowned pushed-sum protocol , used in a number of papers to remove the double-stochastic requirement on the consensus matrix. The major difference is that the proposed method is the first one applicable to constrained (convex and nonconvex) optimization problems while push-sum-based schemes work only for unconstrained problems (this is because push-sum-based updates do not preserve feasibility of the iterates).

The rest of the paper is organized as follows. In Section II we first introduce the general idea of SONATA, followed by its formal description along with its convergence properties. Section III sheds light on the connection between SONATA and some recent distributed algorithms proposed in the literature (mostly appeared after the submission of this work). Some applications of SONATA are discussed in Section IV along with some numerical results. Finally, Section V draws some conclusions.

II Algorithmic Design

We study Problem (1) under the following standard assumptions.

Assumption A (Problem Setup) {enumerate*}

The set $\mathcal{K}\neq\emptyset$ is closed and convex;

Each $f_{i}$ is a continuously differentiable function defined on an open set containing $\mathcal{K}$;

Each $\nabla f_{i}$ is Lipschitz continuous on $\mathcal{K}$;

$\nabla F$ is bounded on $\mathcal{K}$, with $F(\mathbf{x})=\sum_{i}f_{i}(\mathbf{x})$;

$G$ is convex with bounded subgradients on $\mathcal{K}$;

$U$ is coercive on $\mathcal{K}$, i.e., $\lim_{\mathbf{x}\in\mathcal{K},\,\|\mathbf{x}\|\to\infty}U\left(\mathbf{x}\right)=+\infty$.

Assumption A is standard and satisfied by many practical problems. For instance, A3-A5 hold automatically if $\mathcal{K}$ is bounded and $f_{i}$ is twice continuously differentiable, whereas A6 guarantees the existence of a solution. Note that each $f_{i}$ need not be convex and is known only by agent $i$.

In words, Assumption B says that the information sent by any agent $i$ at any time $n$ will reach any agent $j$ within the next $B$ time slots.

Our goal is to develop an algorithm that converges to stationary solutions of Problem (1) while being implementable in the above distributed setting (Assumptions A and B), and applicable to arbitrary network topologies without requiring any knowledge of the graph sequence $\mathcal{G}[n]$. To shed light on the core idea of the novel framework, we first introduce an informal and constructive description of the proposed algorithm, see Sec. II-A. Sec. II-B will formally introduce SONATA along with its convergence properties.

Designing distributed algorithms for Problem (1) faces two main challenges, namely: the nonconvexity of the objective function and the lack of global information on the optimization problem from the agents. To cope with these issues, SONATA combines SCA techniques (Step 1 below) with a consensus-like step implementing a novel broadcast protocol (Step 2), as described next.

Step 1: Local SCA. Each agent $i$ maintains a local copy of the common optimization variable $\mathbf{x}$, denoted by $\mathbf{x}_{i}$, which needs to be updated at each iteration; let $\mathbf{x}_{i}[n]$ be the value of $\mathbf{x}_{i}$ at iteration $n$. The nonconvexity of $f_{i}$ together with the lack of knowledge of $\sum_{j\neq i}f_{j}$, prevent agent $i$ to solve Problem (1) directly. To cope with this issues, we leverage SCA techniques: at each iteration $n$, agent $i$ solves instead a convexification of Problem (1), having the following form

where the nonconvex function $F$ is replaced with the strongly convex approximation $\widehat{F}_{i}\left(\mathbf{x}_{i};\mathbf{x}_{i}\left[n\right]\right)$ around $\mathbf{x}_{i}[n]$, defined as

Note that $\widehat{\mathbf{x}}_{i}\left(\mathbf{x}_{i}\left[n\right]\right)$ is well-defined, because (2) has a unique solution. The direct use of $\widehat{\mathbf{x}}_{i}$ as the new local estimate ${\mathbf{x}}_{i}[n+1]$ may affect convergence because it might be a too “aggressive” update. To cope with this issue we introduce a step-size in the update of ${\mathbf{x}}_{i}$:

where $\alpha[n]$ is a step-size (to be properly chosen, see Th. 1). The idea behind the iterates (2)-(5) is to compute stationary solutions of Problem (1) as fixed-points of the mappings $\widehat{\mathbf{x}}_{i}(\bullet)$. To this end, we require the following assumptions on the surrogate function $\widetilde{f}_{i}$.

Assumption C (On the surrogate function). Each function $\widetilde{f}_{i}$ satisfies the following properties: {enumerate*}

$\nabla\widetilde{f}_{i}\left(\mathbf{x};\mathbf{x}\right)=\nabla f_{i}\left(\mathbf{x}\right)$, for all $\mathbf{x}\in\mathcal{K}$;

$\widetilde{f}_{i}\left(\bullet;\mathbf{y}\right)$ is uniformly strongly convex on $\mathcal{K}$;

$\nabla\widetilde{f}_{i}\left(\mathbf{x};\bullet\right)$ is uniformly Lipschitz continuous on $\mathcal{K}$; Conditions C1-C3 are quite natural: $\widetilde{f}_{i}$ should be regarded as a (simple) convex, local, approximation of $f_{i}$ at the point $\mathbf{x}$ that preserves the first order properties of $f_{i}$. Several feasible choices are possible for a given $f_{i}$; we discuss alternative options in Sec. II-C. Here, we only remark that no extra conditions on $\widetilde{f}_{i}$ are required to guarantee convergence of the proposed algorithm.

The next proposition establishes the desired connection between the fixed points of $\widehat{\mathbf{x}}_{i}(\bullet)$ and the stationary solutions of (1); the proof follows from [15, Prop. 8(b)] and thus is omitted.

Consider Problem (1) under Assumptions A1-A6. If the surrogate functions $\widetilde{f}_{i}$’s are chosen according to Assumption C, then the set of fixed-points of $\widehat{\mathbf{x}}_{i}(\bullet)$ coincides with that of stationary solutions of Problem (1).

Step 2: Broadcasting local information. We have now to introduce a mechanism to ensure that the local estimates ${\mathbf{x}}_{i}$ eventually agree among all agents. To disseminate information over a time-varying digraph without requiring the knowledge of the sequence of digraphs and a double-stochastic weight matrix, we propose the following broadcasting protocol. Given $\mathbf{v}_{i}[n]$, each agent $i$ updates its own local estimate $\mathbf{x}_{i}$ together with one extra scalar variable $\phi_{i}\left[n\right]$ (initialized to $\phi_{i}\left[0\right]=1$), according to

where the $a_{ij}[n]$’s are some weighting coefficients (to be properly chosen) matching the graph $\mathcal{G}[n]$ in the following sense.

Assumption D (On the weighting matrix). Matrix $\mathbf{A}[n]\triangleq(a_{ij}[n])_{i,j}$ satisfies the following conditions: {enumerate*}

$a_{ij}[n]\geq\kappa>0$ if $\left(j,i\right)\in\mathcal{E}[n]$, and $a_{ij}=0$ otherwise;

$\mathbf{A}[n]$ is column stochastic, i.e., $\mathbf{1}^{T}\mathbf{A}[n]=\mathbf{1}^{T}$.

Steps (6)-(7) are interpreted as follows: All agents i) send their local variables $\phi_{j}[n]$ and $\phi_{j}[n]\mathbf{v}_{j}[n]$ to their out-neighbors; and ii) linearly combine with coefficients $a_{ij}[n]$ the information coming from their in-neighbors. The idea behind the use of the extra variable $\phi_{i}\left[n\right]$ is to dynamically construct a row stochastic weight matrix so that consensus among the $\mathbf{x}_{i}$’s can be asymptotically achieved; see Sec. II-C for more details.

On the local update of $\boldsymbol{\pi}_{i}\left[n\right]$. The algorithm developed so far is based on the computation of $\widehat{\mathbf{x}}_{i}\left(\mathbf{x}_{i}\left[n\right]\right)$ in (2). To do so, at each iteration, every agent $i$ needs to evaluate $\boldsymbol{\boldsymbol{\pi}}_{i}\left[n\right]$ and thus know locally all $\nabla f_{j}(\mathbf{x}_{i}\left[n\right])$, which is not feasible in a distributed time-varying setting. To cope with this issue, we replace $\boldsymbol{\pi}_{i}\left[n\right]$ in (2) with an estimate $\widetilde{\boldsymbol{\pi}}_{i}\left[n\right]$ and solve instead

The question now becomes how to update each $\widetilde{\boldsymbol{\pi}}_{i}$ using only local information [in the form of (6)-(7)] while asymptotically converging to $\boldsymbol{\pi}_{i}\left[n\right]$. As in , rewriting first $\boldsymbol{\pi}_{i}\left[n\right]$ as

with $\overline{\nabla f}\left(\mathbf{x}_{i}\left[n\right]\right)\triangleq\frac{1}{I}\sum_{j=1}^{I}\nabla f_{j}\left(\mathbf{x}_{i}\left[n\right]\right)$, we propose to update $\widetilde{\boldsymbol{\pi}}_{i}$ mimicking (9):

where $\mathbf{y}_{i}\left[n\right]$ is a local variable (controlled by agent $i$) whose task is to asymptotically track $\overline{\nabla f}\left(\mathbf{x}_{i}\left[n\right]\right)$. Similar to (6)-(7), we propose the following new gradient tracking step:

where $\phi_{i}\left[n+1\right]$ is defined in (6). Note that the update of $\mathbf{y}_{i}$ and thus of $\boldsymbol{\pi}_{i}[n]$ can be now performed locally by agent $i$, with the same signaling as for (6)-(7).

II-B Successive Convex Approximation over Time-varying Digraphs

We are now in the position to formally introduce SONATA, as given in Algorithm 1, whose convergence is stated in Theorem 1.

Let $\left(\{\mathbf{x}_{i}\left[n\right]\}_{i=1}^{I}\right)_{n}$ be the sequence generated by Algorithm 1, and let $\{\bar{\mathbf{z}}[n]\triangleq\left(1/I\right)\sum_{i}\phi_{i}[n]\cdot\mathbf{x}_{i}\left[n\right]\}_{n}$. Suppose that i) Assumptions A-D hold; ii) the step-size sequences $\{\alpha[n]\}_{n}$ satisfying $\alpha\left[n\right]\in\left(0,1\right]$ and $\sum_{n=0}^{\infty}\alpha\left[n\right]=+\infty$. Then,

(1) [convergence]: $\bar{\mathbf{z}}\left[n\right]$ is bounded for all $n$, and every limit point of $\bar{\mathbf{z}}\left[n\right]$ is a stationary solution of Problem (1); (2) [consensus]: $\|\mathbf{x}_{i}\left[n\right]-\bar{\mathbf{z}}\left[n\right]\|\to 0$ as $n\to+\infty$, for all $i$.

We point out that convergence of SONATA (as stated in Th. 1) can also be established under weaker assumptions, namely: i) a constant step-size, (possibly) different for each agent, can be used; and ii) Assumption A4 is not needed. We refer the reader to for the proof.

II-C Discussion on Algorithm 1

ATC- versus CTA-based updates. To illustrate the algorithm dynamics, let us combine (5)-(7). Eliminating the auxiliary variable $\mathbf{v}_{i}[n]$, one can write

where $\mathbf{W}\left[n\right]\triangleq(w_{ij}[n])_{i,j}$ is a nonnegative matrix with elements

Eq. (12) follows an Adapt-Then-Combine-based (ATC) scheme, where each agent $i$ first updates its local copy $\mathbf{x}_{i}[n]$ along the “descent direction” $\widetilde{\mathbf{x}}_{i}\left(\mathbf{x}_{i}\left[n\right]\right)-{\bf x}_{i}\left[n\right]$, and then it combines its new update with that of its neighbors via consensus, using the weights $\left\{w_{ij}[n]\right\}_{j\in\mathcal{N}_{i}[n]}$.

As an alternative to Eq. (12), one can also follow a so-called Combine-Then-Adapt-based (CTA) approach: each agent $i$ first mixes its own local copy $\mathbf{x}_{i}[n]$ with that of its neighbors via consensus, and then it performs its local optimization-based update. The CTA scheme yields the following alternative:

We remark that SONATA based on CTA updates is proved to converge under the same conditions as in Theorem 1 (and Remark 1); see .

$-$Linearization: When there is no convex structure to exploit, one can simply linearize $f_{i}$, which leads to

In this case, SONATA becomes a distributed proximal gradient algorithm for constrained optimization.

$-$Partial Linearization: Consider the case that $f_{i}$ can be decomposed as $f_{i}\left(\mathbf{x}_{i}\right)=f_{i}^{\left(1\right)}\left(\mathbf{x}_{i}\right)+f_{i}^{\left(2\right)}\left(\mathbf{x}_{i}\right)$, where $f_{i}^{\left(1\right)}$ is convex and $f_{i}^{\left(2\right)}$ is nonconvex with Lipschitz continuous gradient. Preserving the convex part of $f_{i}$ while linearizing $f_{i}^{\left(2\right)}$ leads to the following valid surrogate

$-$Convexification: If variable $\mathbf{x}_{i}$ can be partitioned as $(\mathbf{x}_{i}^{(1)},\mathbf{x}_{i}^{(2)})$, and $f_{i}$ is convex with respect to $\mathbf{x}_{i}^{(1)}$ while nonconvex with respect to $\mathbf{x}_{i}^{(2)}$, then $\widetilde{f}_{i}$ can be constructed by convexifying only the nonconvex part of $f_{i}$, i.e.,

where $\nabla^{(2)}f_{i}\left(\bullet\right)$ is the gradient of $f_{i}$ with respect to $\mathbf{x}_{i}^{(2)}$.

On the choice of the step-size. Th. 1 offers some flexibility in the choice of the step-size $\alpha\left[n\right]$ sequence; the conditions therein ensure that the sequence decays to zero, but not too fast. There are many diminishing step-size rules in the literature satisfying the aforementioned conditions; see, e.g., . We found the following two choices effective in our experiments:

On the choice of matrix $\mathbf{A}[n]$. The key requirement of Assumption D is that each $\mathbf{A}[n]$ is column stochastic. To the best of our knowledge, this is the weakest condition on the weighting matrix to solve optimization problems over arbitrary time-varying digraphs. We remark that our protocol contains push-sum as a special case if $\mathbf{A}[n]$ is chosen as

Note that the message passing protocol based on (21) can be easily implemented, since each agent only needs the know its out-degree and broadcast the information evenly to all its out-neighbors.

III SONATA and Special Cases

In this section we contrast SONATA with related algorithms proposed in the literature (including very recent proposals , appeared online after the submission of this work) for special instances of Problem (1). Specifically, we show next that all these schemes are special cases of SONATA. To this end, we first rewrite SONATA in an equivalent more convenient form and provide some specific instances of the main algorithm.

where $\mathbf{W}[n]$ is given in (13), and $\textrm{Diag}\left(\boldsymbol{\phi}[n]\right)$ denotes a diagonal matrix whose diagonal entries are the components of the vector $\boldsymbol{\phi}[n]$. Furthermore, let us concatenate all the local copies $\mathbf{x}_{i}[n]$s in the $m\,I$-length column vector $\mathbf{x}[n]\triangleq\left[\mathbf{x}_{1}[n]^{T},\ldots,\mathbf{x}_{I}[n]^{T}\right]^{T}$; the vector $\mathbf{y}[n]$ is similarly defined. Finally, let $\mathbf{g}_{i}[n]\triangleq\nabla f_{i}\left(\mathbf{x}_{i}[n]\right)$ and $\Delta\mathbf{x}[n]\triangleq\widetilde{\mathbf{x}}[n]-\mathbf{x}[n]$. Using the above notation, the (ATC- and CTA-based) updates of SONATA [cf. Algorithm 1 and Eq. (14)] can be rewritten in compact form as

When the digraphs $\mathcal{G}[n]$ admit a double-stochastic matrix $\mathbf{A}[n]$, and $\mathbf{A}[n]$ in (22a) is chosen so, the iterates (22) can be further simplified. Indeed, it follows from (22a) and (22b) that $\boldsymbol{\phi}[n]=\mathbf{1}$ and $\mathbf{A}[n]=\mathbf{W}[n]$, for all $n$; and then SONATA in (22) reduces to

The ATC-based updates (23a) and (23) coincide with our previous algorithm NEXT, introduced in . We will refer to (23) as (ATC/CTA-)SONATA-NEXT.

and set $\tau_{i}=I$. Then, $\widetilde{\mathbf{x}}_{i}[n]$ can be computed in closed form [cf. (8)]:

which we will refer to as (ATC/CTA-)SONATA-L (L stands for “linearized”).

Similar to (23), if all $\mathbf{A}[n]$ are double stochastic martices, then (ATC/CTA-)SONATA-L reduces to

which is referred to as (ATC/CTA-)SONATA-NEXT-L.

III-B Connection with current algorithms

where $\widehat{\mathbf{W}}\triangleq\mathbf{W}\otimes\mathbf{I}_{m}$, $\mathbf{W}$ is a double stochastic matrix matching the graph (i.e., $w_{ij}>0$ if $(j,i)\in\mathcal{E}$ and $w_{ij}=0$ otherwise), and $\boldsymbol{\alpha}$ is the vector of agents’ step-sizes $\alpha_{i}$s. A similar algorithm was proposed in parallel in (in the same networking setting of ), which reads

While algorithm (28) is in principle more general than (29)–agents can use different step-sizes $\alpha_{i}$s–the assumptions in on $\boldsymbol{\alpha}$ to guarantee convergence are difficult to be enforced in practice, and in particular in a distributed setting.

Aug-DGM was shown to achieve convergence rate $O\left(1/n\right)$ for smooth convex functions $f_{i}$s, and linear convergence $O\left(\gamma^{n}\right)$ for some $\gamma\in\left(0,1\right)$, if $f_{i}$’s are strongly convex.

Clearly Aug-DGM in (28) and Algorithm in (29) are both special cases of (ATC-)SONATA-NEXT-L [cf. Eq. (27)].

(Push-)DIGing . Appeared in the technical report and applicable to $B$-strongly connected undirected graphs, the DIGing Algorithm reads

where $\mathbf{W}[n]$ is a double-stochastic matrix matching the graph. Clearly, DIGing is a special case of (CTA-)SONATA-NEXT-L [cf. (27)], proposed in the earlier works .

In the same technical report , the authors proposed push-DIGing, the extension of DIGing to $B$-strongly connected digraphs. It turns out that push-DIGing is a special case of (ATC-)SONATA-L [cf. Eq. (III-A)], when $a_{ij}[n]=1/d_{j}[n]$. Both DIGing and Push-DIGing are shown to have R-linear convergence rate, when agents’ objective functions are strongly convex. ADD-OPT . Finally, we mention the ADD-OPT Algorithm, proposed in for strongly connected static digraphs, which takes the following form:

Defining $\mathbf{y}[n]=\widehat{\boldsymbol{\Phi}}[n]^{-1}\widetilde{\mathbf{y}}[n]$, it can be verified that algorithm (31) can be rewritten as

Comparing Eq. (III-A) and (32), one can see that ADD-OPT is an instance of (CTA-)SONATA-L with the following particular choice of (uncoordinated) step-size: $\frac{\phi_{i}[n]\alpha}{\phi_{i}[n+1]}$ for agent $i$. We recall that (CTA-)SONATA-L is guaranteed to converge also with uncordinate step-sizes; see Remark 1. ADD-OPT is shown to have linear rate $O\left(\gamma^{n}\right)$ for strongly convex objective functions.

We summarize the connections between the different versions of SONATA(-NEXT) and its special cases in Table I.

IV Applications and Numerical Results

In this section, we test the performance of SONATA on both convex and nonconvex problems. For all applications, we simulate the following graph topology: at each iteration, each agent has two out-neighbors, with one belonging to a time-varying cycle and the other two randomly chosen. The step-size $\alpha\left[n\right]$ is chosen based on the rule (19), and matrix $\mathbf{A}[n]$ is chosen based on Eq. (21).

In the first simulation, we consider a robust linear regression problem. Each agent $i$ has $n_{i}$ measurements of parameter $\mathbf{x}$ as $b_{ij}=\mathbf{a}_{ij}^{T}\mathbf{x}$, which is corrupted by noise and outliers. To estimate $\mathbf{x}$, we solve the following problem

where $h$ is the Huber loss function given by

Defining $f_{i}\left(\mathbf{x}\right)\triangleq\sum_{j=1}^{n_{i}}h\left(\mathbf{a}_{ij}^{T}\mathbf{x}-b_{ij}\right)$, Problem (33) is an instance of the general Problem (1) with $F=\sum_{i=1}^{I}f_{i}$. We provide two versions of surrogate function $\widetilde{f}_{i}$. In the first version, function $f_{i}$ is linearized at each iteration (cf. Eq. (15)). In the second version, we propose a SCA scheme that approximates $f_{i}$ at $\mathbf{x}\left[n\right]$ by a quadratic function $\widetilde{f}_{i}\left(\mathbf{x};\mathbf{x}\left[n\right]\right)=\sum_{j=1}^{n_{i}}\widetilde{h}_{ij}\left(\mathbf{x};\mathbf{x}\left[n\right]\right)+\frac{\tau}{2}\|\mathbf{x}-\mathbf{x}\left[n\right]\|^{2}$, where $\widetilde{h}_{ij}$ is defined as

with $r_{ij}\left[n\right]=\mathbf{a}_{ij}^{T}\mathbf{x}\left[n\right]-b_{ij}$. Consequently, the update $\widetilde{\mathbf{x}}_{i}\left[n\right]$ has a closed form solution given as $\widetilde{\mathbf{x}}_{i}\left[n\right]=\left(2\mathbf{A}_{i}^{T}\mathbf{D}_{i}\mathbf{A}_{i}+\tau\mathbf{I}\right)^{-1}\left(\tau\mathbf{x}\left[n\right]-\widetilde{\boldsymbol{\pi}}_{i}\left[n\right]+2\mathbf{A}_{i}^{T}\mathbf{D}_{i}\mathbf{b}_{i}\right),$ where the $j$th row of $\mathbf{A}_{i}$ is $\mathbf{a}_{ij}^{T}$, and the $j$th element of $\mathbf{b}_{i}$ is $b_{ij}$. Matrix $\mathbf{D}_{i}$ is diagonal with its $j$th diagonal being $\min\{c,c/r_{ij}\left[n\right]\}$.

We simulate $I=30$ agents collaboratively estimate $\mathbf{x}_{0}$ of dimension 200 with i.i.d. uniformly distributed entries in $\left[-1,1\right]$. Each agent only has $n_{i}=20$ measures. The elements of vector $\mathbf{a}_{ij}$ is generated following an i.i.d. Gaussian distribution, then normalized to be $\|\mathbf{a}_{ij}\|=1$. The measurements noise follows a Gaussian distribution with standard deviation $\sigma=0.1$, and each agent has one measurement corrupted by an outlier following a Gaussian distribution with standard deviation $5\sigma$. The cut-off parameter $c$ is set to be $c=3\sigma$.

Algorithm parameters are tuned as follows. The proximal parameter $\tau$ for our linearization scheme and SCA scheme are set to be $\tau_{L}=2$ and $\tau_{SCA}=1.5$, respectively. Step-size parameters are set to be $\alpha\left[0\right]=0.1$ and $\mu=0.01$ for both of them. We compare the performance with subgradient-push algorithm proposed in , for which the step-size parameter is set to be $\alpha\left[0\right]=0.5$, $\mu=0.01$. In addition, since SONATA has two consensus steps, we run subgradient-push twice in one iteration using the same graph for a fair comparison.

The performance is averaged over 100 Monte-Carlo simulations, where each time $\mathbf{x}_{0}$ is fixed while the noise and graph connectivity are randomly generated. Fig. 1 reports the progress of the algorithms towards optimality and consensus error, where measure $J\left[n\right]$ is defined as $J\left[n\right]\triangleq\|\nabla F\left(\bar{\mathbf{z}}\left[n\right]\right)\|_{\infty}$ and $D\left[n\right]\triangleq\frac{1}{I}\sum_{i=1}^{I}\|\mathbf{x}_{i}\left[n\right]-\bar{\mathbf{z}}\left[n\right]\|^{2}$. We can see that SONATA reaches consensus and convergence much faster than subgradient-push. In addition, SCA scheme outperforms plain linearization by exploiting the convexity of the objective function.

IV-B Target Localization

Target Localization problem considers a number of $I$ sensors in a network collaboratively locate the position of $T$ targets. Sensor $i$ has the knowledge of the coordinate of its own location $\mathbf{s}_{i}$, and the relative Euclidean distance between itself and target $t$, denoted $d_{it}$. The problem is formulated as:

where $\mathcal{K}$ is a compact set and variable $\mathbf{x}_{t}$ is an estimate of the location of target $t$, denoted $\mathbf{x}_{t}^{0}$. Parameter $p_{it}\in\{0,1\}$ takes value zero if the $i$th agent has no measurement about target $t$.

We apply SONATA to Problem (34) with $f_{i}\left(\mathbf{x}\right)=\sum_{t=1}^{T}p_{it}\left(d_{it}-\|\mathbf{x}_{t}-\mathbf{s}_{i}\|^{2}\right)^{2}$, where $\mathbf{x}$ is obtained by stacking the $\mathbf{x}_{t}$’s. The two SCA schemes proposed in are adopted, namely, linearization (cf. Eq. (15)) and partial linearization with surrogate function

where $\widetilde{f}_{it}\left(\mathbf{x};\mathbf{x}\left[n\right]\right)=\mathbf{x}_{t}^{T}\mathbf{A}_{i}\mathbf{x}_{t}-\mathbf{b}_{it}\left[n\right]^{T}\left(\mathbf{x}_{t}-\mathbf{x}_{t}\left[n\right]\right)$, with $\mathbf{A}_{i}=4\mathbf{s}_{i}\mathbf{s}_{i}^{T}+2\|\mathbf{s}_{i}\|^{2}\mathbf{I}$, and $\mathbf{b}_{it}\left[n\right]=4\|\mathbf{s}_{i}\|^{2}\mathbf{s}_{i}-4\left(\|\mathbf{x}_{t}\left[n\right]\|^{2}-d_{it}\right)\left(\mathbf{x}_{t}\left[n\right]-\mathbf{s}_{i}\right)+8\left(\mathbf{s}_{i}^{T}\mathbf{x}_{t}\left[n\right]\right)\mathbf{x}_{t}\left[n\right]$.

In the simulation, we set the number of sensors to be $I=30$, and the number of targets to be $t=5$. Parameter $p_{it}$ takes value zero and one with equal probability. The locations of the sensors and targets are uniformly randomly generated in $\left[0,1\right]^{2}$. We consider a noisy environment that the measured distances are corrupted by i.i.d. Gaussian noise. The noise standard deviation is set to be the minimum pairwise distance between sensors and targets.

We compare with the gradient algorithm proposed in for unconstrained optimization. Algorithm parameters are tuned as follows. For our algorithm, the step-size parameters are set to be $\alpha\left[0\right]=0.1$ and $\mu=10^{-4}$. The proximal parameter $\tau$ of $\widetilde{f}_{i}$ for the linearization scheme is selected to be $\tau_{L}=7$ and that for partial linearization is selected to be $\tau_{PL}=5$. For the benchmark algorithm, $\alpha\left[0\right]=0.05$ and $\mu=10^{-4}$.

A comparison of the algorithms is given in Fig. 2, which is averaged over 100 Monte-Carlo simulations. Fig. 2 shows that within 200 iteration, both consensus and convergence are achieved for all algorithms; and SONATA converges much faster than the benchmark gradient algorithm.

V Conclusion

In this paper we have proposed (ATC/CTA-)SONATA, a family of novel distributed algorithms for nonconvex constrained optimization over time-varying (directed) networks. The algorithm leverages the idea of SCA for local optimization, a tracking mechanism to locally estimate the gradients of agents’ functions, and a new in-network broadcast protocol to distribute the computation and sharing information among agents. SONATA is the first broadcast-based algorithm framework that can solve convex or nonconvex constrained optimization problems over arbitrary time-varying digraphs. SONATA was also shown to contain, as special cases, current algorithms proposed in simplified settings. Numerical result shows that our algorithm outperforms state-of-the-art schemes on considered convex and nonconvex applications.

References