On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems

I Introduction

The last few decades’ increasingly rapid technological developments have resulted in vast amounts of dispersed data. Optimization techniques have played a central role in transforming the vast data sets into usable information. However, due to the increasing size of the related optimization problems, it is essential that these optimization techniques scale with data size. Fortunately, many large scale optimization problems in real world applications possess appealing structural properties, due to the networked nature of the problems. Thus, increasing research efforts have been devoted to the investigation of how these structural properties can be exploited in the algorithm design to achieve scalability. The focal point of these efforts has been on “well-behaved” convex problems, rather than more challenging nonconvex problems. Nevertheless, large scale nonconvex problems arise in many real world network applications. Examples of such nonconvex applications include matrix factorization techniques for recommender systems (the Netflix challenge) , localization in wireless sensor networks , optimal power flow in smart grids , and LDPC decoding . Interestingly, these large scale nonconvex applications tend to have the structural advantages that are commonly exploited to design scalable algorithms for their convex counterparts. This suggests that the algorithms used for large scale convex problems can potentially be applied to nonconvex problems as well. However, theoretical guarantees for these algorithms in the nonconvex regime have not yet been established. This paper investigates convergence properties of a class of scalable and distributed algorithms for nonconvex structured optimization problems. Here, (i) by distributed algorithms we mean any algorithm that can be executed by at least two entities where no single entity has access to the full problem data, and (ii) by structured optimization problems we mean any problem with structures in the problem data that can be exploited to achieve (i).

Many recent studies on large scale optimization have focused on distributed subgradient methods in the context of multi-agent networks . There, multiple agents, each with a private objective function, cooperatively minimize the aggregate objective function by communicating over the network. In contrast to , the papers and consider nonconvex multi-agent problems. Specifically, applies distributed subgradient methods to the (convex) dual problem and investigates sufficient conditions under which the approach converges to a pair of optimal primal/dual variables. On the other hand, studies the convergence of stochastic subgradient methods to a point satisfying the first order necessary conditions for local optimality with probability one. A main drawback of these gradient based approaches is that they can only converge to an exact optimal (or local optimal) solution when a diminishing step size is used, which results in poor convergence rate. The diminishing step size assumption is relaxed in the promising recent work while keeping the exact convergence by introducing a correction term, which significantly improves the convergence rate.

Another widely used approach for structured convex optimization is the Alternating Direction Method of Multipliers (ADMM) . ADMM is a variant of the classical method of multipliers (MM) [17, Chapter 2] [18, Chapter 4.2], where the primal variable update of the MM is split into subproblems, whenever the objective is separable. This structure is common in large scale optimization problems that arise in practice . Even problems that do not possess such a structure can often be posed equivalently in a form appropriate for ADMM by introducing auxiliary variables and linear constraints. These techniques have been employed in many recent works when designing distributed algorithms for convex, as well as nonconvex problems . A key property of ADMM compared with other existing scalable approaches, such as subgradient and dual descent methods (mentioned above) is its superior convergence behavior, see for empirical results. Characterizing the exact convergence rate of ADMM is still an ongoing research topic . Many recent papers have also numerically demonstrated the fast and appealing convergence behavior of ADMM even on nonconvex problems . Despite these encouraging observations, there are still no theoretical guarantees for ADMM’s convergence in the nonconvex regime. Therefore, investigating convergence properties of the ADMM and related algorithms in nonconvex settings is of great importance in theory as well as in practice, and is motivated by the many emerging large scale nonconvex applications.

I-B Notation and Definitions

II Problem Statement, Related Background, and Contribution of the Paper

This section is organized as follows. Section II-A introduces the class of nonconvex structured problems we study. We give the necessary background on centralized algorithms in Section II-B, before introducing distributed algorithms which exploit the special structures of the related problems in Section II-C. Then we state the contribution and organization of the paper in Section II-D.

We consider the following optimization problem

Next we discus centralized solution methods for Problem (2) which are the basis for the distributed methods we study.

II-B Penalty and Augmented Lagrangian Methods

Nonconvex problems of the form (2) can be gracefully handled by penalty and augmented Lagrangian methods, such as the quadratic penalty function method and method of multipliers, [17, Chapter 2] [18, Chapter 4.2]. The main ingredient of these methods is the augmented Lagrangian, given by

The penalty and augmented Lagrangian methods consist in iteratively updating the variables ${\bf{x}}$, ${\bf{z}}$, ${\bf{y}}$, and $\rho$. An update common to all the methods is the primal variable update, i.e.,

The motivation for (4) is that when $({\bf{x}}(t{+}1),{\bf{z}}(t{+}1))$ is locally optimal for Problem (3) and satisfies the FON conditions (Definition 1)We do not include the multipliers related to the constraint $\mathcal{X}{\times}\mathcal{Z}$ to simplify the presentation, but it is easily checked that the claim holds when they are included. then $({\bf{x}}(t{+}1),{\bf{z}}(t{+}1))$ and ${\bf{y}}(t{+}1)$ satisfy conditions 2), 3), and 4) of the FON conditions for the original Problem (2), all except 1) primal feasibility. Furthermore, under mild conditions, the method of multipliers converges to a local optimal point $({\bf{x}}^{\star},{\bf{z}}^{\star})$ and to a corresponding optimal Lagrangian multiplier ${\bf{y}}^{\star}$ [17, Proposition 2.4]. In addition to the local convergence, when $({\bf{x}}(t),{\bf{z}}(t))$ is a global optima of (3), then (4) is a gradient ascent step for the dual problem. However, due to non-zero duality gap in most nonconvex problems, the solution to (2) can not be recovered from the dual problem. Hence the method of multipliers can generally only be considered a local method.

In general, the penalty and augmented Lagrangian methods mentioned above are very reliable and effective for handling problems of the form (2). However, these methods entail centralized solvers, especially in the $({\bf{x}},{\bf{z}})$-update (3), even if the objective function of problem (2) has a desirable separable structure in ${\bf{x}}$ and ${\bf{z}}$. More specifically, these methods do not allow the possibility of performing the $({\bf{x}},{\bf{z}})$-update in two steps: first ${\bf{x}}$-update and then ${\bf{z}}$-update. Otherwise, the assertions on the convergence of the algorithms do not hold anymore. Therefore, the penalty and augmented Lagrangian methods are not applicable in distributed settings, whenever the problems possess decomposition structures. Such restrictions have motivated an adaptation of the classical penalty and augmented Lagrangian methods that has excellent potential for a parallel/distributed implementation which we discussed now.

II-C Alternating Direction Lagrangian Methods

Recall that problem (2) has a linear coupling constraint and an objective function that is separable in ${\bf{x}}$ and ${\bf{z}}$. This motivates potential solution approaches to Problem (2), where the optimization in (3) is performed in two steps, first in the ${\bf{x}}$ coordinate and then in the ${\bf{z}}$ coordinate, i.e.,

II-D Contribution and Structure of the Paper

Next we investigate the convergence behavior of the ADMM when (2) is nonconvex in Section IV. We assume that the penalty parameter is fixed, i.e., $\rho(t)=\rho$. We consider general assumptions on Problem (2) where the sets $\mathcal{X}$ and $\mathcal{Z}$ can even be nonconvex. We show that when ${\bf{y}}(t)$ converges then any limit point of ${\bf{x}}(t),{\bf{z}}(t))$ satisfies the FON conditions of Problem (2). We note that the condition can be checked a posteriori or at runtime, by inspecting some algorithm parameters as the algorithm proceeds (online). Moreover, we show how our results can be used to completely characterize the convergence of ADMM for a class of problems, i.e., to determine to which point ADMM converges given an initialization. In comparison to , we consider ADMM, whereas therein the standard Lagrangian dual function is maximized.

Finally, we illustrate how the considered methods can be applied to design distributed algorithms for cooperative localization in wireless sensor networks.

III Alternating Direction Penalty Method

The steps of ADPM are shown in Algorithm 1 Algorithm 1: The Alternating Direction Penalty Method (ADPM)

Initialization: Set $t=0$ and initialize ${\bf{z}}(0)$, ${\bf{y}}(0)$, and $\rho(0)$.

x-update: ${\bf{x}}(t+1){=}\underset{{\bf{x}}\in\mathcal{X}}{\text{argmin}}~{}L_{\rho(t)}({\bf{x}},{\bf{z}}(t),{\bf{y}}(t))$.

z-update: ${\bf{z}}(t+1){=}\underset{{\bf{z}}\in\mathcal{Z}}{\text{argmin}}~{}L_{\rho(t)}({\bf{x}}(t+1),{\bf{z}},{\bf{y}}(t))$.

$\rho/{\bf{y}}$-update: Update $\rho(t{+}1)$ and ${\bf{y}}(t{+}1)$.

Stopping criterion: If stopping criterion is met terminate, otherwise set $t=t+1$ and go to step 2.

Nonconvexities of $f$ and $g$ suggest potential difficulties in the implementation of the ${\bf{x}}$- and ${\bf{z}}$- updates (see steps 2 and 3). However, it is worth noting that problems encountered in practice often contain structure that can be exploited to successfully implement the ${\bf{x}}$- and ${\bf{z}}$- updates. Several examples are given next.

A potential feature of the multi-agent setting is that the ${\bf{x}}$- update is separable into low dimensional problems. More specifically, suppose the variable ${\bf{x}}$ is partitioned into low dimensional subvectors as ${\bf{x}}=({\bf{x}}_{1},\cdots,{\bf{x}}_{N})$, where there is no coupling between ${\bf{x}}_{i}$ and ${\bf{x}}_{j}$ in the constraints, for all $i,j=1,\cdots,N$ such that $i\neq j$. Suppose also that the objective function is separable with respect to the partition, i.e., $f({\bf{x}})=\sum_{i=1}^{N}f_{i}({\bf{x}}_{i})$. Then the objective function in the ${\bf{x}}$-update is also separable with respect to the partition. Thus, provided that each subvector ${\bf{x}}_{i}$ is of low dimension, global methods such as branch and bound can be efficiently used to optimally solve the optimization problem in the ${\bf{x}}$-update.

III-B Algorithm Properties: Unconstrained Case

$g({\bf{x}}){=}0$, ${\bf{A}}{=}{\bf{I}}$, ${\bf{c}}{=}{\bf{0}}$, ${\bf{B}}$ has full column rank.

At least one of the following conditions holds true:

$||{\bf{B}}||_{\infty}{\leq}1$ and $||({\bf{B}}^{\mbox{\scriptsize T}}{\bf{B}})^{-1}{\bf{B}}^{\mbox{\scriptsize T}}||_{\infty}{\leq}1$. Moreover, there exist a scalar $c{>}0$ such that: (b.i) $[\nabla f({\bf{x}})]_{i}<0$ if ${\bf{x}}_{i}<{-}c$, for component $i\in\{1,{\cdots},p_{1}\}$ and (b.ii) $[\nabla f({\bf{x}})]_{i}>0$ if ${\bf{x}}_{i}>c$, for $i\in\{1,\cdots,p_{1}\}$.

Assumption 1 naturally arises when designing distributed algorithm over networks, where ${\bf{x}}$ represents private variables of each node/agent and ${\bf{z}}$ represents the coupling between the nodes. Assumption 2.a is standard in the literature, e.g., in relation to (sub)gradient methods methods . In addition, Assumption 2.b ensures that our results hold for more general classes of practical problems than covered by Assumption 2.a, e.g., when $f$ is a polynomial of even degree with positive leading coefficient (see Problem (58) in Section V). We note that the $||{\bf{B}}||_{\infty}{\leq}1$ and $||({\bf{B}}^{\mbox{\scriptsize T}}{\bf{B}})^{-1}{\bf{B}}^{\mbox{\scriptsize T}}||_{\infty}{\leq}1$ naturally hold when ${\bf{x}}$ and ${\bf{z}}$ represent private and coupling variables of each node/agent in a connected network, e.g. see Section V. The main implication of Assumption 2.b is that it ensures that the sequence $({\bf{x}}(t),{\bf{z}}(t))$ is bounded as we show in the following lemma.

Suppose Assumption 2.b holds true and $||{\bf{z}}(t)||_{\infty}\leq c$, then $||{\bf{x}}(t{+}1)||_{\infty}\leq c$ and $||{\bf{z}}(t{+}1)||_{\infty}{\leq}c$.

Let us start by showing that $||{\bf{x}}(t{+}1)||_{\infty}\leq c$ by using contradiction. Without loss of generality, we assume that ${\bf{x}}_{i}(t{+}1)<-c$ for some $i=1,\cdots,p_{1}$ (the other cases follow symmetrical arguments). Then $[\nabla f({\bf{x}}(t))]_{i}<0$, from Assumption 2.b, which in turn implies that

However, using the FON conditions of the ${\bf{x}}$-update and that $||{\bf{B}}||_{\infty}\leq 1$ we also have

Clearly, (7) and (8) contradict each other. Hence, $||{\bf{x}}(t{+}1)||_{\infty}{\leq}c$.

Let us next show that $||{\bf{z}}(t{+}1)||\leq c$. From the FON conditions of the ${\bf{z}}$-update we get that ${\bf{z}}(t{+}1)=({\bf{B}}^{\mbox{\scriptsize T}}{\bf{B}})^{-1}{\bf{B}}^{\mbox{\scriptsize T}}{\bf{x}}(t{+}1)$, which together with $||({\bf{B}}^{\mbox{\scriptsize T}}{\bf{B}})^{-1}{\bf{B}}^{\mbox{\scriptsize T}}||_{\infty}\leq 1$ ensures that $||{\bf{z}}(t{+}1)||\leq||{\bf{x}}(t{+}1)||_{\infty}\leq c$. ∎

We are now ready to derive the main result of this subsection.

Suppose assumptions 1 and 2 hold. Let $r(t)$ be the residual at iteration $t$ of the ADPM defined as $r(t)=||{\bf{x}}(t)+{\bf{B}}{\bf{z}}(t)||$. Then

If in addition $\sum_{t=0}1/\rho(t)=\infty$ and $\lim_{t\rightarrow\infty}({\bf{x}}(t),{\bf{z}}(t))=({\bf{x}}^{\star},{\bf{z}}^{\star})$, then $({\bf{x}}^{\star},{\bf{z}}^{\star})$ satisfies the FON conditions of Problem (2).

Using the FON conditions of the ${\bf{x}}$- and ${\bf{y}}$- updates we get

Using (11), (12), and that $\nabla f({\bf{x}}(t))$ is bounded we get

Similarly, using (9) and that $\nabla f({\bf{x}}(t))$ is bounded we get

Finally, using (14), (15) and the triangle inequality gives

Since $\rho(t)$ diverges to $\infty$, (16) converges to zero, which concludes the proof.

The left hand side of (18) is a telescopic series, hence

which in turn ensures the convergence of both (19) and

where the right hand side diverges to $\infty$, since $\sum_{t=0}^{\infty}1/\rho(t)=\infty$, which implies that the left hand side also diverges to $\infty$. This contradicts that the series (20) converges and therefore we can conclude that $L=0$. ∎

In Proposition 1 we considered the case where ${\bf{y}}(t){=}{\bf{0}}$, which allowed us to derive the theoretical results. Still, our numerical results in Section V show that it can be beneficial to update ${\bf{y}}$ according to the recursion ${\bf{y}}(t{+}1){=}{\bf{y}}(t){+}\rho({\bf{x}}(t{+}1){-}{\bf{B}}{\bf{z}}(t{+}1))$.

III-C Algorithm properties: Constrained Case

The functions $f$ and $g$ of problem (2) are continuously differentiable.

The sets $\mathcal{X}$ and $\mathcal{Z}$ of problem (2) are convex and compact.

Slater’s condition holds individually for $\mathcal{X}$ and $\mathcal{Z}$. In particular, there exists a ${\bf{x}}\in\mathcal{X}$ (respectively, ${\bf{z}}\in\mathcal{Z}$) such that all the inequality constraints characterizing $\mathcal{X}$ (respectively, $\mathcal{Z}$) are inactive at ${\bf{x}}$ (respectively, ${\bf{z}}$).

The matrices ${{\bf{A}}}$ and ${\bf{B}}$ of problem (2) have full column rank.

Note that we make no convexity assumptions on $f$ and $g$. However, the convexity assumption on $\mathcal{X}$ and $\mathcal{Z}$ is essential. Otherwise, primal feasibility is not guaranteed in general, see Example 4 later in this section. Assumption 5 is an additional technical condition, similar to the constraint qualifications usually used in convex analysis. The last assumption is technically necessary to ensure that both ${{\bf{A}}}^{\mbox{\scriptsize T}}{{\bf{A}}}$ and ${{\bf{B}}}^{\mbox{\scriptsize T}}{{\bf{B}}}$ are positive definite. It is quite common in practice that this assumption holds, as desired, see Section V. The following proposition establishes the convergence of ADPM:

Since $f$ and $g$ are continuous and the sets $\mathcal{X}$ and $\mathcal{Z}$ are compact there exists a scalar $M_{1}>0$ such that

are well-defined continuous functions [compare with Assumption 6]. By definition, ${\bf{x}}(t+1)$ is a solution of the optimization problem in ${\bf{x}}$-update of the ADPM. This, together with (21) yields

where (27) follows similarly by rearranging the terms of (25) and by using that $|M_{1}-(f({\bf{x}})+g({\bf{z}})+{\bf{y}}^{\mbox{\scriptsize T}}({\bf{A}}{\bf{x}}{+}{\bf{B}}{\bf{z}}{-}{\bf{c}}))|\leq 2M_{1}$ for all $({\bf{x}},{\bf{z}},{\bf{y}}){\in}\mathcal{X}{\times}\mathcal{Z}{\times}\mathcal{Y}$, (28) follows from combining the inequalities (26) and (27), together with the definition of $\hat{{\bf{x}}}$ and $\hat{{\bf{z}}}$, and (29) follows by the definition of $\hat{{\bf{x}}}$.

From the definition of $\{\rho(t)\}_{t\in N}$, we get

where (31) follows because the sum on the right contains all the terms of the sum on the left (and possibly more) and all the terms are positive, (32) follows because $1/\rho(t+i\kappa+j)\leq 1/(\Delta^{i}\rho(t))$ for all $0\leq j\leq\kappa-1$, and (33) trivially follows from the nonnegativity of summands. Since $\Delta>1$, $\sum_{i=0}^{\infty}1/\Delta^{i}$ is a convergent geometric series, and thus let $\sum_{i=0}^{\infty}\kappa/\Delta^{i}=M_{2}$. This, together with (30)-(33) implies that for all integers $t,n\geq 0$,

Let us now consider the limits in the inequality (29) as $t\rightarrow\infty$. Since $\lim_{t\rightarrow\infty}r(t+1)=\lim_{t\rightarrow\infty}((8M_{1})/\rho(t)+r(t))=R$, from (27), (28), and the squeezing lemma, together with the continuity of functions $\hat{{\bf{x}}}$ and $\hat{{\bf{z}}}$ it follows that

By combining (35) and (36), together with the definitions (22) and (23), we get

Since Slater’s constraint qualifications condition is satisfied for both sets $\mathcal{X}$ and $\mathcal{Z}$ (Assumption 5), $\bar{{\bf{x}}}$ and $\bar{{\bf{z}}}$ satisfy the first order necessary conditions for problems (37) and (38), respectively. By combining these first order necessary conditions and (38), it follows that $(\bar{{\bf{x}}},\bar{{\bf{z}}})$ satisfies the first order necessary conditions for the problem

Since problem (39) is convex and the constraint sets satisfy Slater’s constraint qualifications condition, we conclude that $(\bar{{\bf{x}}},\bar{{\bf{z}}})$ is the solution to problem (39). Given that problem (2) is feasible, we must have $||{\bf{A}}\bar{{\bf{x}}}+{\bf{B}}\bar{{\bf{z}}}-{\bf{c}}||^{2}=0$, and therefore $\lim_{t\rightarrow\infty}||{\bf{A}}{\bf{x}}(t)+{\bf{B}}{\bf{z}}(t)-{\bf{c}}||^{2}=0$ [compare with (35)]. ∎

One natural question that arises immediately with the Assumption 4 is what if $\mathcal{X}$ and/or $\mathcal{Z}$ are nonconvex. The following example shows that the results of Proposition 2 do generally not hold when either $\mathcal{X}$ or $\mathcal{Z}$ are nonconvex.

Note that our Assumption 3 is a weaker condition than assuming that $f$ and/or $g$ are convex. As a result, characterizing generally the proprieties of the objective value of ADPM after the convergence is technically challenging. Nevertheless, ADPM appears to resemble a sequential optimization approach, which provides degrees of freedom to hover over the true objective function for locating a good objective value. In , we give some experiments to numerically show these appealing aspects of the ADPM, besides those ensured by Proposition 2.

IV Alternating Direction Method of Multipliers

In this section we investigate some new general properties of the ADMM in a nonconvex setting. We state the algorithm in section IV-A and study convergence properties in section IV-B.

The ADMM can explicitly be stated as follows.

Algorithm 2: The Alternating Direction Method of Multipliers (ADMM)

Initialization: Set $t=0$ and put initial values to ${\bf{z}}(t)$, ${\bf{y}}(t)$, and $\rho$.

x-update: ${\bf{x}}(t{+}1)=\underset{{\bf{x}}\in\mathcal{X}}{\text{argmin}}~{}L_{\rho}({\bf{x}},{\bf{z}}(t),{\bf{y}}(t))$.

z-update: ${\bf{z}}(t{+}1)=\underset{{\bf{z}}\in\mathcal{Z}}{\text{argmin}}~{}L_{\rho}({\bf{x}}(t{+}1),{\bf{z}},{\bf{y}}(t))$.

y-update: ${\bf{y}}(t{+}1)={\bf{y}}(t)+\rho({\bf{A}}{\bf{x}}(t{+}1){+}{\bf{B}}{\bf{z}}(t+1)-{\bf{c}})$.

Stopping criterion: If stopping criterion is met terminate, otherwise set $t=t+1$ and go to step 2.

Unlike in Algorithm 1 (ADPM), in Algorithm 2 (ADMM) the penalty parameter is fixed. The first step is the initialization (step 1). As presented above, the ${\bf{x}}$- and ${\bf{z}}$- updates require a solution of an optimization problem. This is not as restrictive as it may seem, since under mild conditions such requirements are accomplished, see Examples 1-3. However, we note that no such global optimality requirement of ${\bf{x}}(t+1)$ and ${\bf{z}}(t+1)$ is necessary in our convergence assertions, as we will show in subsequent sections. More specifically, our convergence results apply as long as ${\bf{x}}(t+1)$ [respectively, ${\bf{z}}(t+1)$] is a local minimum.

IV-B Algorithm Properties

Let us now scrutinize the above assertion precisely. The analysis is based on the following assumption which can be expected to hold for many problems of practical interest:

The sets $\mathcal{X}$ and $\mathcal{Z}$ of problem (2) are closed and can be expressed in terms of a finite number of equality and inequality constraints. In particular,

associated with the set $\mathcal{X}$ is linearly independent, where $\mathcal{A}_{\mathcal{X}}(\bar{{\bf{x}}})=\{i\ |\ \boldsymbol{\phi}_{i}(\bar{{\bf{x}}})=0\}$. Similarly, the corresponding set of constraint gradient vectors $\mathcal{C}_{\mathcal{Z}}$ associated with the set $\mathcal{Z}$ is linearly independent.

Assumption 7 is self-explanatory. Note that steps $2$ and $3$ of the algorithm involve nonconvex optimization problems, where the computational cost of finding the solutions ${\bf{x}}(t+1)$ and ${\bf{z}}(t+1)$, in general, can be entirely prohibitive. However, Assumption 8 indicates that the solution ${\bf{x}}(t+1)$ [respectively, ${\bf{z}}(t+1)$] of the optimization problem associated with the steps $2$ (respectively, $3$) of the ADMM should only be a local minimum and not necessarily a global minimum. Thus, Assumption 8 can usually be accomplished by employing efficient local optimization methods (see [33, Section 1.4.1]). In the literature, Assumption 9 is called the “regularity assumption” and is usually satisfied in practice. Moreover, any point that complies with the assumption is called regular, see [18, p. 269]. Let us next document two results that will be important later.

From Lemma 3, we have that ${\bf{x}}(t_{k})$ and ${\bf{z}}(t_{k})$ are regular for sufficiently large $k$. This combined with the assumptions yields the result, which is an immediate consequence of [18, Proposition 3.3.1] ∎

Lemmas 3 and 4 play a central role when deriving our convergence results, as we will show in the sequel. The following proposition establishes the convergence results of the ADMM algorithm:

In the sequel, we show that the four conditions of Definition 1 (First order necessary condition) are all satisfied.

1) Primal feasibility: Since $({\bf{x}}(t_{k}),{\bf{z}}(t_{k}))\in\mathcal{X}\times\mathcal{Z}$ and the set $\mathcal{X}\times\mathcal{Z}$ is closed it follows that $(\bar{{\bf{x}}},\bar{{\bf{z}}})\in\mathcal{X}\times\mathcal{Z}$. Since $\bar{{\bf{y}}}{=}{\bf{y}}(0)+\sum_{t=1}^{\infty}\rho({\bf{A}}{\bf{x}}(t)+{\bf{B}}{\bf{z}}(t)-{\bf{c}})$, we must have $\lim_{t\rightarrow\infty}||{\bf{A}}{\bf{x}}(t)+{\bf{B}}{\bf{z}}(t)-{\bf{c}}||^{2}=0$, or ${\bf{A}}\bar{{\bf{x}}}+{\bf{B}}\bar{{\bf{z}}}={\bf{c}}$.

2) Dual feasibility: It holds for $\boldsymbol{\gamma}(t_{k})$ and $\boldsymbol{\omega}(t_{k})$ from Lemma 4 that $\boldsymbol{\gamma}(t_{k})\geq{\bf{0}}$ and $\boldsymbol{\omega}(t_{k})\geq{\bf{0}}$ (compare with Definition 1). Hence, since the closed right half-plane is a closed set, it follows that $\boldsymbol{\gamma}\geq{\bf{0}}$ and $\boldsymbol{\omega}\geq{\bf{0}}$.

3) Complementary slackness: If $\boldsymbol{\phi}_{i}(\bar{{\bf{x}}})=0$ then $\boldsymbol{\gamma}_{i}\boldsymbol{\phi}_{i}(\bar{{\bf{x}}})=0$ trivially holds. On the other hand, if $\boldsymbol{\phi}_{i}(\bar{{\bf{x}}})<0$ then we showed in the proof of lemma 5 that $\boldsymbol{\gamma}_{i}=0$. Hence, it follows that $\boldsymbol{\gamma}_{i}\boldsymbol{\phi}_{i}(\bar{{\bf{x}}})=0$.

4) Lagrangian vanishes: We need to show that

Let us start by showing (44). From Lemma 4, we get for all sufficiently large $k$ that [compare with Definition 1]:

By using ${\bf{y}}(t_{k}-1)={\bf{y}}(t_{k})-\rho({\bf{A}}{\bf{x}}(t_{k})+{\bf{B}}{\bf{z}}(t_{k})-{\bf{c}})$ in equation (45) and rearranging the terms we get that

By using that $\lim_{k\rightarrow\infty}({\bf{x}}(t_{k}),{\bf{z}}(t_{k}),{\bf{y}}(t_{k}))=(\bar{{\bf{x}}},\bar{{\bf{z}}},\bar{{\bf{y}}})$ and $\lim_{k\rightarrow\infty}(\boldsymbol{\lambda}(t_{k}),\boldsymbol{\gamma}(t_{k}),\boldsymbol{\mu}(t_{k}),\boldsymbol{\omega}(t_{k}))=(\boldsymbol{\lambda},\boldsymbol{\gamma},\boldsymbol{\mu},\boldsymbol{\omega})$, we conclude that equation (44) holds. By using the same arguments as above we get for all sufficiently large $k$ that

Therefore, by the arguments above, if we can show that $\lim_{t\rightarrow\infty}\rho{\bf{A}}^{\mbox{\scriptsize T}}{\bf{B}}({\bf{z}}(t{+}1){-}{\bf{z}}(t))={\bf{0}}$, then equation (43) holds. The assumption $\bar{{\bf{y}}}=\lim_{t\rightarrow\infty}{\bf{y}}(t)$ together with the relation ${\bf{y}}(t+1)={\bf{y}}(0)+\rho\sum_{l=1}^{t+1}{\bf{A}}{\bf{x}}(l)+{\bf{B}}{\bf{z}}(l)-{\bf{c}}$ can be used to show that the series

are convergent. By taking the difference of the two series and using that the sum of convergent series is a convergent series, we get that $\sum_{t=1}^{\infty}{\bf{B}}({\bf{z}}(t{+}1)-{\bf{z}}(t))$ is a convergent series. Thus, implying that $\lim_{t\rightarrow\infty}{\bf{B}}({\bf{z}}(t{+}1)-{\bf{z}}(t))=0$. By multiplying $\rho{\bf{A}}^{\mbox{\scriptsize T}}$ from the left side we get that $\lim_{t\rightarrow\infty}\rho{\bf{A}}^{\mbox{\scriptsize T}}{\bf{B}}({\bf{z}}(t{+}1)-{\bf{z}}(t))=0$. ∎

We prove the existence of the first two limits. The proof of the existence of the latter two limits follows similarly.

Since $\nabla f$, $\nabla\boldsymbol{\psi}$, and $\nabla\boldsymbol{\phi}$ are continuous functions (see Assumption 3) we have

This, together with Lemma 3 implies that there exists $K$ such that ${\bf{D}}({\bf{x}}(t_{k}))^{\mbox{\scriptsize T}}{\bf{D}}({\bf{x}}(t_{k}))$ (see Eq. (42)) is invertible for all $k\geq K$. Hence, it follows that for all $k\geq K$, we have

Since ${\bf{D}}(t_{k})$ and $\nabla f({\bf{x}}(t_{k}))$ converge when $k\rightarrow\infty$ it follows that $\lim_{k\rightarrow\infty}(\boldsymbol{\lambda}(t_{k}),(\boldsymbol{\gamma}_{i}(t_{k}))_{i\in\mathcal{A}_{\mathcal{X}}(\bar{{\bf{x}}})})$ exists.

A stronger version of Proposition 3 is shown in the following corollary:

If $\lim_{t\rightarrow}({\bf{x}}(t),{\bf{z}}(t),{\bf{y}}(t))=(\bar{{\bf{x}}},\bar{{\bf{z}}},\bar{{\bf{y}}})$, then $\bar{{\bf{x}}}$ and $\bar{{\bf{z}}}$ satisfy the FON conditions of Problem (2).

The corollary follows immediately because the hypothesis implies that the set $\mathcal{L}$ defined in Assumption 9 is a singleton.

Technically, Proposition 3 characterizes the solution of the ADMM algorithm applied on the possibly nonconvex problem (2). More specifically, the proposition claims that under mild assumptions the solutions computed by ADMM satisfy the FON conditions for problem (2), if at every iteration, the subproblems are locally (or globally) solved and if the dual variables of ADMM converge.

Let us now show how Proposition 3 can be used to completely characterize the convergence of the ADMM for a class of problems identified by the following assumption.

The following corollary of Proposition 3 shows that under Assumption 10 the ADMM always either converges or diverges to $\pm\infty$ and characterizes the convergence in terms of $z(0)$.

Suppose Assumption 10 holds, $\rho>L$, and $y(0){=}g^{\prime}(z(0))$. Then

where $z^{\star}$ is determined as follows:

If $f^{\prime}(z(0))+g^{\prime}(z(0))=0$, then $z^{\star}=z(0)$.

If $f^{\prime}(z(0))+g^{\prime}(z(0))<0$, then

If $f^{\prime}(z(0))+g^{\prime}(z(0))>0$, then

We start by writing the steps of the ADMM in a more convenient form. Note that $g^{\prime}(z(t{+}1))+y(t)+\rho(x(t{+}1)-z(t{+}1))=0$, from the optimality conditions of $z(t{+}1)$ at the ${\bf{z}}$-update. This combined with the ${\bf{y}}$-update yields (i) $y(t)=g^{\prime}(z(t))$. Moreover, because $f^{\prime}$ and $g^{\prime}$ are L-Lipschitz continuous, we have that (ii) the functions $L_{\rho}(\cdot,z(t),y(t))$ and $L_{\rho}(x(t),\cdot,y(t))$, associated with the ${\bf{x}}$- and ${\bf{z}}$- updates are strongly convex for all $\rho>L$.

From (i) and (ii), we get that $x(t{+}1)$ is the unique solution to

In the sequel, we show each case a), b), and c) separately.

a) If $f^{\prime}(z(0))+g(z(0))=0$ then $x(t)=z(0)$ and $z(t)=z(0)$ are clearly the unique solutions to (48) and (49), respectively, for all $t\geq 1$. The result follows.

We show that $z(t{+}1){>}z(t)$ and $z(t{+}1)<z^{\star}$ for all $z(t)\in[z(0),z^{\star}[$, but as an intermediary step we first show that $x(t{+}1){>}z(k)$ and $x(t{+}1)<z^{\star}$ for all $z(t)\in[z(0),z^{\star}[$. To see that $x(t{+}1){>}z(k)$, we note that $x(t{+}1)\leq z(k)$ contradicts the $L$-Lipschitz continuity of $f^{\prime}$. In particular, $x(t{+}1)\leq z(t)$ implies that $\rho|x(t{+}1)-z(t)|<|f^{\prime}(x(t{+}1))-f^{\prime}(z(t))|$, which is seen by the following inequality

which is obtained by combining (48) and ${-}f^{\prime}(z(t)){>}g^{\prime}(x(t))$ and rearranging. To see that $x(t{+}1)<z^{\star}$ we note that

where (51) comes from that $x(t{+}1)$ is the unique solution of (48) and $f^{\prime}(z(t)){<}{-}g^{\prime}(z(t)){-}\rho(z(t){-}z(t))$ and (52) comes from that $\rho{>}L$ and $g^{\prime}$ is $L$-Lipschitz continuous. Summing (51) and (52) and using the continuity of $f^{\prime}$ and $g^{\prime}$ shows that $f^{\prime}(x)+g^{\prime}(x)<0$ for all $x{\in}[z(t),x(t{+}1)]$ and hence $x(t{+}1){<}z^{\star}$.

We now show that $z(t{+}1){>}z(t)$ and $z(t){<}z^{\star}$. To see that $z(t{+}1){>}z(t)$, we note that $z(t{+}1){\leq}z(t)$ contradicts the $L$-Lipschitz continuity of $g^{\prime}$. In particular, $z(t{+}1){\leq}z(t)$ implies that $\rho|z(t{+}1){-}z(t)|<|g^{\prime}(x(t{+}1)){-}g^{\prime}(z(t))|$, which is seen by that if $z(t{+}1){\leq}z(t)$ then

where (53) comes by rearranging (49) and (54) comes by assuming that $z(t{+}1)\leq z(t)$ and using that $x(t{+}1)>z(t)$. Hence, we can conclude that $z(t{+}1)>z(t)$. To see that $z(t{+}1)<z^{\star}$ we note that if $z(t{+}1)\leq x(t{+}1)$ then we are done since $x(t{+}1)<z^{\star}$, otherwise we have that

where (55) comes from using that $\rho>L$ and $f^{\prime}$ is $L$-Lipschitz continuous together with the inequalities $z\geq x(t{+}1)$ and $f^{\prime}(x(t{+}1))<-g^{\prime}(z(t))$ which follows from (48) and (56) comes by that $z(t{+}1)$ is the unique solution of (49) together with that $g^{\prime}(z(t))<g^{\prime}(z(t))+\rho(x(t{+}1)-z(t)$ and $z(t)<z(t{+}1)$. Summing (55) and (56) and using the continuity of $f^{\prime}$ and $g^{\prime}$ shows that $f^{\prime}(z)+g^{\prime}(z)<0$ for all $z\in[x(t{+}1),z(t{+}1)]$, implying that $z(t{+}1)<z^{\star}$.

c) Follows from symmetric arguments as those used for showing b) and is thus omitted. ∎

The challenge in multidimensional case is that we need to know the direction towards the stationary point. Such a direction is easily obtained in the monodimensional, as suppose to the multidimensional case.

The next section demonstrates the potential of the proposed ADLM approaches (see Sections III and IV) in a problem of great practical relevance.

V Application: Cooperative Localization in Wireless Sensor Networks

In this section, we use the ADLM methods to design distributed algorithms for Cooperative Localization (CL) in wireless sensor networks.

Suppose the measurements of the squaredUsing the square ensures that the objective function of (57) is continuously differentiable (compare with Assumption 3). distance between two nodes $n,m\in\mathcal{N}$, denoted by $d_{n,m}^{2}$, are available if and only if $(n,m)\in\mathcal{E}$. The additive measurement errors are assumed to be independent and Gaussian distributed with zeros mean and variance $\sigma^{2}$. Then the CL problem consists in finding the maximum likelihood estimate of $({\bf{z}}_{n})_{n\in\mathcal{S}}$ by solving the following problem:

where $\mathcal{S}_{n}=\{m{\in}\mathcal{S}|(n,m){\in}\mathcal{E}\}$, $\mathcal{A}_{n}=\{m{\in}\mathcal{A}{|}(n{,}m)\in\mathcal{E}\}$ and the coefficient $2$ in front of the second term of the sum comes from that $n\in S$ appears twice in the sum. Note that Problem (57) is NP-hard .

Problem (58) fits the form of Problem (2) and proposed ADLM approaches can readily be applied. The augmented Lagrangian of problem (58) can be written as

where ${\bf{y}}=({\bf{y}}_{1},\cdots,{\bf{y}}_{n})$ is the Lagrangian multiplier. Note that the variables ${\bf{x}}$ and ${\bf{y}}$ are separable among $n\in\mathcal{N}$. The resulting distributed-ADLM is as follows.

Algorithm 3: Distributed Alternating Direction Lagrangian Method (D-ADLM)

Initialization: Set $t=0$ and put initial values to ${\bf{z}}(t)$, ${\bf{y}}(t)$, and $\rho(t)$.

Subproblem: Each node $n\in\mathcal{N}$ solves

Communication/Averaging: ${\bf{z}}(t+1)$ is given by $\mbox{argmin}_{{\bf{z}}}~{}L_{\rho(t)}({\bf{x}}_{n}(t{+}1),{\bf{z}},{\bf{y}}(t))$, i.e.,

for $n\in\mathcal{S}$, where ${\bf{E}}_{i,n}$ is the column $n$ of the block matrix ${\bf{E}}_{i}$.

Local parameter update: Each node $n\in\mathcal{N}$ updates its local parameters $\rho(t)$ and ${\bf{y}}(t)$ accordingly.

Stopping criterion: If stopping criterion is met terminate, otherwise set $t=t+1$ and go to step 2.

Note that the D-ADLM can be carried out either as an ADPM or as an ADMM by performing $\rho(t)$ and ${\bf{y}}(t)$ updates at step 4 accordingly (compare with step 4 of ADPM and ADMM algorithms). In particular, in ADPM, all the nodes know the value of $\rho(t)$ for each $t$ and the nodes can update ${\bf{y}}_{n}(t)$, for all $n\in\mathcal{N}$, as they wish, as long as the sequence ${\bf{y}}_{n}(t)$ is bounded. In ADMM, all the nodes $n$ know the value of $\rho$ and update $y_{n}$ according to

As indicated in the first step, the initial setting of the algorithm should be agreed on among the nodes. Other steps can be carried out in a distributed manner with local message exchanges. Note that (60) is simply the average of the local copies of ${\bf{z}}_{n}$ and the corresponding dual variables [scaled by $\rho(t)$], which can be performed by employing standard gossiping algorithms, e.g., . Moreover, the last step requires a mechanism to terminate the algorithm. A natural stopping criterion is to fix the number of iterations, which requires no coordination among the nodes except at the beginning. In order to control the accuracy level $\epsilon$ of the coupling constraints, one can, for example, terminate the algorithm when ${\max_{n\in\mathcal{N}}}||{\bf{x}}_{n}(t){-}{\bf{E}}_{n}{\bf{z}}(t)||{<}\epsilon$. This, can be accomplished with an additional coordination among the nodes.

We compare D-ADLM with the following distributed gradient descent algorithm.

Algorithm 4: Distributed Gradient Descent (D-GD)

Initialization: Set $t{=}0$ and initialize $\rho(t)$, ${\bf{z}}(t)$, and $\bar{x}_{n}(t)={\bf{E}}_{n}{\bf{z}}(t)$ for all $n\in\mathcal{N}$.

Subproblem: Each node $n\in\mathcal{N}$ solves

Communication/Averaging: Each senor $n\in\mathcal{S}$ finds the average estimation of its localization by communicating with neighbors:

here ${\bf{E}}_{i,n}$ is the column $n$ of the block matrix ${\bf{E}}_{i}$. Set $\bar{{\bf{x}}}_{n}(t{+}1)={\bf{E}}_{n}{\bf{z}}(t{+}1)$, i.e., the average of the components pertaining to $n\in\mathcal{S}$.

Local parameter update: Each node $n{\in}\mathcal{N}$ updates $\rho(t)$.

Stopping criterion: If stopping criterion is met terminate, otherwise set $t=t+1$ and go to step 2.

Note that D-GD performs almost the same steps as D-ADLM. The main difference is in step 2): (59) in ADLM is a solution to an optimization problem while (62) in D-GD is a gradient descent step. In particular, the required communication is the same for both algorithms. Therefore, D-GD provides a fair comparison to the D-ADLM.

Let us next test the D-ADLM on a CL problem.

We consider a network with $S=10$, $A=4$. The 4 anchors are located at $(0,0),$ $(0,1),$ $(1,0),$ and $(1,1)$. The senors’ are positioned at uniform random in ${\times}$. There is an edge between two nodes $n,m{\in}\mathcal{N}$ if and only if the Euclidean distance between those is less than $0.5$. We have $\sigma^{2}{=}0.05D$, where $D$ is the average squared distance between distinct nodes $(n,m){\in}\mathcal{E}$. We consider the following algorithm settings:

where the first column identifies each setting, the second column indicates the algorithm used, the third column indicates whether the dual variable update is used or if no dual variable update is used, i.e., ${\bf{y}}(t){=}{\bf{0}}$, the forth column indicates the penalty/steps size used. We initialize the algorithms as ${\bf{z}}_{n}(0){=}(0.5,0.5)$ for all $n{\in}\mathcal{S}$. When the dual variable is updated we initialize it as ${\bf{y}}(0){=}{\bf{0}}$.

Fig. 2 depicts the results, where we have compactly written ${\bf{x}}=({\bf{x}}_{1},\cdots,{\bf{x}}_{n})$ and ${\bf{E}}=({\bf{E}}_{1},\cdots,{\bf{E}}_{n})$. Figs 2(a) and 2(b) depict scaled versions of $||{\bf{x}}(t)-{\bf{E}}{\bf{z}}(t)||$, the network consensus, and $||{\bf{E}}^{\mbox{\scriptsize T}}\nabla f({\bf{x}}(t))||$, the gradient of the objective function, respectively, as a function of iterations $t$. Together $||{\bf{x}}(t)-{\bf{E}}{\bf{z}}(t)||$ and $||{\bf{E}}^{\mbox{\scriptsize T}}\nabla f({\bf{x}}(t))||$ comprise the FON conditions of Problem (58), i.e., when both quantities converge to zero the FON conditions is asymptotically reached. Both Figs 2(a) and 2(b) demonstrate a decreasing trend for all algorithms. In Fig. 2(b), DGD and ADPM have noticeably slower decay rate than ADPM-y, ADMM-1, and ADMM-10. In Fig. 2(b), DGD, ADPM, and ADPM-y have noticeably slower decay rate than ADMM-1 and ADMM-10. Therefore, the results suggest that it can be beneficial to use the update (61).

Fig. 2(c) depicts an example of a dual variable for each of the algorithms where the the update (61) is used. Similar results were observed for the other dual variables. The figure shows that the dual variables converge, implying that ADMM-1 and ADMM-10 converge based on Proposition 3.

Fig. 2(a) depicts the objective value at each iteration. The algorithms achieve different objective values, which is not surprising since the objective is function nonconvex with multiple local minima. Fig 3 depicts the resulting location estimations for each algorithm, i.e., the estimation at the final iteration. Note that the orange diamond and five-pointed star lay under their purple counter parts and are therefore not visible in the figure. Despite the nonconvexities, all the algorithms converge to a good estimations close to the true locations of the nodes. The DGD achieves a visually better estimation of the diamond and the five-pointed star in Fig 3 than the other algorithms. Nevertheless, ADMM-1 and ADMM-10 achieve much better objective function values.

The gradients of $f_{n}$ for $n\in\mathcal{N}$ are unbounded, but still Assumption (2).b holds, which ensures that the sequence $({\bf{x}}(t),{\bf{z}}(t))$ of ADPM is bounded, see Lemma 1. Similar results can be derived for ADPM-y, ADMM-1, and ADMM-10 as long as the dual variables ${\bf{y}}(t)$ are bounded. On the other hand, from our numerical experiences, DGD turned out to be unstable for many initialisations where it reached floating point infinity in only few iterations.

VI Conclusions

We investigated the convergence behaviour of scalable variants of two standard nonconvex optimization methods: a novel method we call Alternating Direction Penalty Method and the well known Alternating Direction Method of Multipliers, variants of the Quadratic Penalty Method and the Method of Multipliers, respectively. Our theoretical results showed the ADPM asymptotically reaches primal feasibility under assumptions that hold widely in practice and provided sufficient conditions for when ADPM asymptotically reaches the first order necessary conditions for optimality. Furthermore, we provided sufficient conditions for the asymptotic convergence of ADMM to the first order necessary condition for local optimality and provided a class of problems where thous conditions hold. Finally, we demonstrated how the methods can be used to design distributed algorithms for nonconvex cooperative localization in wireless sensor networks.

References