Mathematics
Computer Science-2021.gz:143306
Computer Science Mathematics
614d08b22e3785115ed2438c4c70214d45501542
Distributed Optimization with Global Constraints Using Noisy Measurements

We propose a new distributed optimization algorithm for solving a class of constrained optimization problems in which (a) the objective function is separable (i.e., the sum of local objective functions of agents), (b) the optimization variables of distributed agents, which are subject to nontrivial local constraints, are coupled by global constraints, and (c) only noisy observations are available to estimate (the gradients of) local objective functions. In many practical scenarios, agents may not be willing to share their optimization variables with others. For this reason, we propose a distributed algorithm that does not require the agents to share their optimization variables with each other; instead, each agent maintains a local estimate of the global constraint functions and share the estimate only with its neighbors. These local estimates of constraint functions are updated using a consensus-type algorithm, while the local optimization variables of each agent are updated using a first-order method based on noisy estimates of gradient. We prove that, when the agents adopt the proposed algorithm, their optimization variables converge with probability 1 to an optimal point of an approximated problem based on the penalty method.


I. INTRODUCTION
Large engineered systems, such as telecommunication networks and electric power grids, are becoming more complex and often comprise subsystems that use different technologies or are controlled autonomously or by different entities. Consequently, centralized resource management or system optimization becomes increasingly impractical or impossible. This naturally calls for a distributed optimization framework that will enable distributed subsystems or agents to optimize both their local performance and, in the process, the overall system performance. What complicates the problem further is that many practical systems have global constraints (e.g., endto-end delay requirements) that couple the decisions of more than one agent; hence satisfying these constraints will require coordination among the agents.
We study the problem of designing a distributed algorithm for a set of agents to solve a constrained optimization problem. The problem has both (a) separate local constraints for each agent and (b) global constraints that agents must satisfy together and, hence, couple the optimization variables of the agents. Moreover, the analytic expression for the global objective function or its gradient is not assumed known to every agent. For example, in many practical cases, the objective functions or constraint functions are summable (e.g., the aggregate cost of all agents). In such cases, the local objective functions of an agent may be unknown to other agents. Also, in many engineered systems, the actual costs for optimizing resource utilization need to be estimated based on measurements, which contain observation noise. Consequently, the agents must rely on noisy observations to update their optimization variables.
This setting applies to a wide range of real-world applications, including communication networks. For example, in the fifth-generation (5G) and future 6G systems, many heterogeneous subsystems (e.g., radio access networks vs. wired core networks) wish to minimize their own costs of delivering services and, at the same time, need to collectively assure end-to-end quality-of-service (QoS), e.g., end-to-end delays or packet loss rates, for different applications such as automated manufacturing, telesurgery, and remote controlled aerial and ground vehicles.
Since the global constraint functions depend on the optimization variables of more than one agent, their values are not always known to all agents. Thus, handling such global constraints will require the agents to exchange information. In many cases, computing and disseminating the exact values of global constraint functions to all agents will incur excessive computing and communication overheads, or cause prohibitive delays. To cope with the challenge, we adopt the penalty method and propose a new consensus-based algorithm for agents to estimate the global constraint function values in a distributed manner. We prove that, under some technical conditions, the proposed algorithm ensures almost sure convergence to an optimal point when the problem with a suitable penalty function is convex.

A. Related Literature
Distributed optimization has attracted extensive attention and accumulated a large body of literature (e.g., [3], [7], [12], [14], [18], [19] and references therein), because it has broad applications and also serves as a foundation for distributed machine learning, Here, we summarize only the most closely related studies that considered stochastic constrained optimization problems with a summable objective function, and point out the key differences between them and our study. We emphasize that this is not meant to be an exhaustive list.
Recently, consensus optimization has been an active research area. Srivastava and Nedić [17] proposed a distributed stochastic optimization algorithm for solving constrained optimization problems, in which the feasible set is assumed to be the intersection of the feasible sets of individual agents. Each agent maintains a local copy of the global optimization variables, which are updated using a consensus-type algorithm. They showed that these local copies converge asymptotically to a common optimal point with probability 1 (w.p.1). Bianchi and Jakubowicz [2] proposed a stochastic gradient algorithm for solving a non-convex optimization problem. Every agent maintains a local copy of global optimization variables and updates its local copy using a projected stochastic gradient algorithm that requires the knowledge of the global feasible set. The agents then exchange their local copies with neighbors and update them using a consensus-type algorithm. They proved that, under the proposed algorithm, agents' local copies of optimization variables converge w.p.1 to the set of stationary or Karush-Kuhn-Tucker (KKT) points of the global objective function. In another study, Chatzipanagiotis and Zavlanos [5] proposed a distributed algorithm for solving a convex optimization problem with affine equality constraints in the presence of noise. This algorithm is based on their earlier work called accelerated distributed augmented Lagrangians [4], [6], and requires exchanges of global optimization variables among all agents.
We consider different settings in which the objective functions are separable and local optimization variables are coupled via global constraints. In order to cope with the coupling introduced by global constraints, each agent maintains local estimates of global constraint functions along with local optimization variables, and only the estimates of global constraint functions are exchanged with neighbors. Our algorithm is better suited for scenarios in which agents may not want to share their own local optimization variables with each other. For instance, autonomous systems or domains with their own private networks may not wish to reveal how they manage their networks. Furthermore, a large system likely contains subsystems that utilize different networking technologies (e.g., WiFi networks, cellular radio access networks, and wired core networks), which are managed differently. We also note that, as explained in [3], the dual problem of the constrained optimization problem we consider in this paper can be formulated as a consensus optimization problem. However, existing algorithms and results in the literature are not applicable to our settings, especially with noisy observations. A more closely related line of research is distributed resource allocation. Many prior studies in this area focused on deterministic cases with linear resource constraints, where local objective functions are differentiable and strictly convex with Lipschitz continuous gradients that are available to the agents (e.g., [3], [7], [13]). More recently, Yi et al. [20] considered stochastic resource allocation problems with local constraints and global affine equality constraints in the presence of both observation and communication noise, where local constraints are determined by continuously differentiable convex functions. They proposed a new algorithm based on a primal-dual approach: each agent maintains local multipliers and auxiliary variables shared with other agents. These multipliers and auxiliary variables along with (primal) variables are updated using a combination of stochastic approximation (with decreasing step sizes) and consensus-type algorithms.
The distributed optimization problems we study can also be viewed as state-based games: Li and Marden [10] formulated the problem of designing a distributed algorithm for solving an optimization problem with affine inequality constraints as one of designing decoupled utility functions for distributed agents, using a penalty or barrier method. This approach leads to a state-based potential game, whose potential function is the objective function of an approximated problem, and the Nash equilibrium solves the approximated problem. Consequently, under the assumption that the analytic expressions for the objective functions are known and the exact gradients can be computed with no noise, they proved that when each agent tries to maximize its own local utility independently, their local decision variables converge to an optimal point of the approximated problem.
Our contributions: All the above studies require exact local projections by assuming simple local constraint sets. In this paper, we relax this assumption and consider a distributed optimization problem where local objective functions are convex (possibly nonsmooth) and local constraints are not assumed to be projection-friendly. We combine a stochastic subgradient method with a dynamic consensus tracking approach. Also, to deal with general local functional constraints, we adopt the idea of approximate projections from [16]; a similar approach is also used in [9] for distributed consensus optimization.
In addition, our work extends the study by Li and Marden [10] to the case where the analytic expressions for the local objective functions of agents or their gradients are unavailable and instead need to be estimated using noisy observations. We demonstrate that the agents can track the global constraint functions using a simpler dynamic consensus tracking algorithm, even for nonlinear global constraint functions. We prove that our algorithm converges to a Nash equilibrium of the aforementioned state-based potential game in [10], and no agent can increase its utility (equivalently, decrease its cost) in the state-based potential game via unilateral deviation.
Notation: Define IN := {0, 1, 2 . . .} to be set of nonnegative integers. We use x + to denote max(0, x). Unless stated otherwise, all vectors are column vectors and · denotes the ℓ 2 norm, i.e., · = · 2 . Given a vector x or a vector function f , we denote the kth element by x k and f k , respectively. The vector of zeros (resp. ones) of appropriate dimension is denoted by 0 (resp. 1). For a convex function f : When it is clear from the context, we will also use ∂f (x) to denote the subdifferential at x. Given a closed convex set S and a vector x, P S (x) denotes the projection of x onto the set S and d S (x) := x − P S (x) is the distance from x to S. If S is a finite set, |S| denotes its cardinality. Given a sequence of random variables (RVs) or vectors R(t), t ∈ IN, we use R t to denote the collection {R(τ ) : τ ∈ {0, . . . , t}}.

II. SETUP AND PROPOSED ALGORITHM
We are interested in solving a constrained optimization problem of the form given below using a distributed algorithm, where (a) the objective function is separable, and (b) the global (inequality) constraints couple the optimization variables of the agents: where A is the set of N agents, φ i and y i are the local objective function and the local optimization variables, respectively, of agent i, y = (y i : i ∈ A) is the vector of optimization variables, G i is the local constraint set of agent i, G := i∈A G i is the feasible set, and g = (g 1 , . . . , g K ) is the vector consisting of K global constraint functions.
is a nonempty convex set assumed to be projection friendly (e.g., box, simplex, ball constraints), and the setG i is given byG where c ik 's are local constraint functions, and K i is the set of agent i's local (inequality) constraints. We are interested in scenarios in which the constraint setK i is large orG i is not projection friendly. Here, G i0 can be regarded as a hard constraint whileG i represents soft constraints.
Unlike in [5], [10], we do not assume that the constraint functions are affine. Instead, we assume that each agent i knows its contributions to global constraint function given by g i , but not g j , j ∈ A \ {i}. This assumption is reasonable in many practical problems with distributed decision makers.
A popular approach to constrained optimization is the penalty method, which adds a penalty to the objective function when one or more constraints are violated. Although a general penalty function can be used in our problem, we assume a specific penalty function to facilitate our exposition. Consider the following approximated problem with a penalty function: where µ > 0 is a penalty parameter, K G is the set of K global constraints, and the second term in Φ is the penalty function. The original problem in (1) is recovered by letting µ → ∞. Throughout the paper, we assume that µ is fixed and known to all the agents. The function Φ is convex on G provided that φ i and g i , i ∈ A, are convex. The usual gradient projection method does not lead to a distributed algorithm because the penalty function and its gradient are coupled. Furthermore, we are interested in scenarios in which (a) the analytic expression of local objective function φ i and its gradient are unknown to agent i and (b) only noisy measurements are available to estimate them. To address these issues, we propose a new algorithm that requires each agent i to keep an estimate e i (t) of the constraint functions g(y(t)), which are updated via dynamic consensus tracking. These estimates are used to approximate the gradient of the penalty function and are updated using a consensus-type algorithm.

A. Proposed Algorithm
Every agent i ∈ A will first randomly choose its initial local optimization variables y i (0)) in G i0 and its estimate of (average) global constraint functions e i (0) = g i (y i (0)) based on its own contributions. Subsequently, at each iteration, it updates them according to the following algorithm: V i (t) are random vectors, γ t is a step size at iteration t, 1 K it ⊂K i in (3b) is a random set of indices selected by agent i independently at each iteration t, 2 and d ik is a subgradient of c ik at z i (t) when c ik (z i (t)) > 0 and d ik = d = 0 otherwise. The value of d is unimportant since the summand is equal to zero in this case. For simplicity, we assume that K it is chosen according to a uniform distribution U i over the set S i := {S ⊂K i | |S| = s i } for some s i ≥ 1, and take any β it in some [β i ,β i ] ⊂ (0, 2/s i ) for all iterations t. In practice, we may choose s i ≪ |K i | to limit the number of constraints considered in (3b) (even s i = 1). We assume that agent i uses the same weight β it for all chosen local constraints in (3b). But, it can employ different weights for different constraints which, for example, depend on the value of constraint functions. We assume that G i0 is simple enough so that P Gi0 (·) can be evaluated efficiently.
Note that agent i ∈ A needs to exchange its estimate e i only with its neighbors reflected in the weight matrix W (t) = [w ij (t) : i, j ∈ A], which is allowed to be timevarying. This update rule is designed based on a dynamic consensus algorithm (e.g., [8]) in order to track the average of the global constraint functions. As a result, we can view e i (t) as a local estimate of the average global constraint functions.
We note that, in our setting, the subgradient ∂φ i (y i (t)) in (4) is unavailable to agent i; instead, only the second term in (4) can be computed by agent i and a noisy estimate of the subgradient given by the sum ∂φ i (y i (t)) + V i (t) is available to the agent for the update in (3a).
The random projection step in (3b) is borrowed from [16] (see also [11]), but we do not restrict to selecting only a single constraint at each iteration. The idea is that if the constraint c ik is violated at z i (t) for some randomly selected k, i.e., c ik (z i (t)) > 0, in order to reduce this violation, the algorithm updates the optimization variables in the direction of −d ik with a step size β it c ik (zi(t)) d ik 2 according to (3b). This projection step, though simple, is beneficial in dealing with nontrivial and computationally intractable constraints, including linear matrix inequalities and robust linear inequalities (e.g., [16]).
For each t ∈ IN, we define F t to be the σ-field generated by is the random index set of the constraints chosen by agent i in (3b) at iteration s. Throughout the paper, we use t [·] to denote the conditional expectation [· | F t ].

B. Assumptions
We impose the following assumptions on the optimization problem in (2).
where K∼Ui [·] denotes the expectation when the random set K is chosen according to U i over the set S i . d. The optimal set of (2), denoted by Y * , is nonempty.
Here, without loss of generality we assume the same Lipschitz constant L. Note that we do not assume differentiability of any involved functions or compactness of constraint sets. Assumption 1-c, in particular condition (5), is known to be quite general and plays an important role in the convergence analysis of algorithms involving random projection in (3b); see [11] for a further discussion on this assumption as well as sufficient conditions for (5) to hold.
We allow the distribution of the perturbation V(t) := (V i (t) : i ∈ A) to depend on the optimization variables y(t). The distribution of V(t) when y(t) = y is denoted by µ y . Assumption 2. The perturbation satisfies (i) v µ y (dv) = 0 for all y ∈ G and (ii) sup y∈G v 2 µ y (dv) =: ν < ∞. We will use below the following standard assumptions on the step sizes.

Assumption 4.
Steps sizes γ t , t ∈ IN, are positive and satisfy (i) t∈I N γ t = ∞ and (ii) t∈I N γ 2 t < ∞.
The following result is a direct consequence of the assumption that weight matrices W (t), t ∈ IN, are doubly stochastic. Lemma 1. Under Assumption 3, the following holds: We will also use the following result on the mixing property of a sequence of doubly stochastic weight matrices [19,Theorem 4.2].
Lemma 2. Consider the following iterates for all i ∈ A.
where ε i (t) ∈ IR K is arbitrary, and W (t) satisfies Assumption 3. Then, there exist C 1 > 0 and C 2 > 0 such that The lemma states that, over a larger timescale, the Q-strong connectivity has a similar mixing effect as a static, strongly connected graph.
The following results will be used frequently in our proofs.
Lemma 3. For any a, b ∈ R and any η > 0,

Lemma 4. Under Assumptions 1 and 3, for any i ∈ A,
Proof. We drop the dependence on t for notational simplicity. It follows from (4) and (7) that where we used the Lipschitz continuity of Φ, g ik and the function max(·, 0). Thus, which follows from the equivalence of norms.
We also make use of the following classical results on the convergence of a sequence of nonnegative RVs.
Then, w.p.1, (i) t∈I N u t < ∞ and (ii) v t converges to some nonnegative RV v.

III. CONVERGENCE ANALYSIS
In this section, we demonstrate that when all agents update their local optimization variables (y i (t)) and local estimates of global constraint functions (e i (t)) using our proposed algorithm in (3), y(t) converges to the optimal set Y * w.p.1. (Theorem 3). We prove this result with the help of a series of auxiliary results.
Lemma 7. Under Assumption 1, for any y i ∈ G i , we have for all i ∈ A, k ∈ K, and τ > 0, whereβ it = (2−siβit)βit Proof. The proof of (11a) is similar to those given in [11], [16], but we provide it here for completeness. For any y i ∈ G i , where the first inequality follows from (3b) and the nonexpansiveness property of projection. Since c + ik is a convex function and d ik ∈ ∂c + ik (z i (t)), it follows that , where we used c + ik (y i ) = 0 for all y i ∈ G i . Moreover, by Cauchy-Schwarz inequality As a result, using the above bounds in (12), , and (11a) now follows from Assumption 1-c.
Although our result is similar to those in [9], [11], it contains an extra term e i (t) −ē(t) 2 in (11b), which measures the disagreements among the agents' local estimates of the global constraint functions. Roughly speaking, for the algorithm to converge, it is necessary that this term decays to 0. Much of the challenge lies in properly bounding this term, which is not bounded a priori. To this end, let us define The following result relates a t with y(t)−w 2 and Φ(w)− Φ P G (y(t)) for any w ∈ G and any choice of step size γ t . Theorem 1. Under Assumptions 1 and 2, the following holds for any t ∈ IN, w ∈ G, and positive sequence {κ t : t ∈ IN}: where ρ =β 4C withβ = inf i,tβit , D 1 = L 2 ρ + 10(2L 2 N + ν) and D 2 = 20L 2 Kµ 2 .
Proof. First, for any w i ∈ G i , by Lemma 7, we have By the nonexpansive property of projection, the first term on the RHS can be expanded further as Thus, we have We bound the last two terms in (16) as follows. First, where the second inequality follows from Lemma 4. Second, for any κ t > 0, where we used the Lipschitz continuity of g ik in the first inequality, and (8) of Lemma 3 in the second inequality.