Source-linked AI summary
Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
Tsung-Hui Chang, Angelia Nedić, Anna Scaglione
TL;DR
The paper tackles distributed optimization with globally coupled costs and inequality constraints when each agent has only local knowledge. It proposes a consensus-based primal-dual perturbation algorithm that combines average consensus with perturbed subgradient updates, and proves convergence to an optimal primal-dual solution under standard assumptions. Numerical studies demonstrate its application to distributed sparse regression and smart-grid demand response control.
Problem
Distributed optimization must address globally coupled costs and inequality constraints when agents access only local information.
Method
The PDP algorithm combines average consensus with a primal-dual perturbed subgradient method to estimate global functions and update local variables.
Results
The proposed algorithm converges to a global optimal primal-dual solution of the considered problem under the stated assumptions.
Takeaways & Limitations
The method supports distributed optimization with local knowledge for applications including sparse regression and smart-grid demand response control.
Abstract
from arXiv · showhide
Various distributed optimization methods have been developed for solving problems which have simple local constraint sets and whose objective function is the sum of local cost functions of distributed agents in a network. Motivated by emerging applications in smart grid and distributed sparse regression, this paper studies distributed optimization methods for solving general problems which have a coupled global cost function and have inequality constraints. We consider a network scenario where each agent has no global knowledge and can access only its local mapping and constraint functions. To solve this problem in a distributed manner, we propose a consensus-based distributed primal-dual perturbation (PDP) algorithm. In the algorithm, agents employ the average consensus technique to estimate the global cost and constraint functions via exchanging messages with neighbors, and meanwhile use a local primal-dual perturbed subgradient method to approach a global optimum. The proposed PDP method not only can handle smooth inequality constraints but also non-smooth constraints such as some sparsity promoting constraints arising in sparse optimization. We prove that the proposed PDP algorithm converges to an optimal primal-dual solution of the original problem, under standard problem and network assumptions. Numerical results illustrating the performance of the proposed algorithm for a distributed demand response control problem in smart grid are also presented.
I. INTRODUCTION
The paper addresses distributed optimization with globally coupled convex costs and coupled inequality constraints when agents possess only local information. It proposes a consensus-based primal-dual perturbation method and establishes convergence to a global optimal primal-dual solution.
- Problem and motivation: The problem extends prior distributed methods to general convex inequality constraints that couple all agents’ variables and a globally coupled non-separable cost.Such formulations arise in regression and smart-grid demand response and power-flow control.
- Problem and motivation: Agents access only local mapping and constraint functions, requiring coordination through exchanged neighbor messages.The formulation is designed for networks where global information is unavailable or costly to share.
- Proposed method: The consensus-based PDP algorithm combines average consensus with a local primal-dual perturbed subgradient update.Agents exchange estimates of global costs and constraints before performing one primal-dual variable update.
- Proposed method: Unlike conventional updates using preceding primal-dual iterates, PDP computes subgradients at perturbation points obtained from neighbor messages.The perturbation mechanism is the algorithm’s main departure from existing consensus-based primal-dual subgradient methods.
- Proposed method: The method provides efficient perturbation-point constructions for both smooth and non-smooth constraint functions.This includes sparsity-promoting constraints relevant to sparse regression.
- Results: Convergence analysis shows strong convergence of local primal-dual iterates to a global optimal primal-dual solution.Numerical studies apply the method to sparse regression and smart-grid demand response control.
II. PROBLEM FORMULATION, APPLICATIONS AND BRIEF REVIEW
The paper formulates a network optimization problem with local variables and mappings, a globally coupled cost, and global inequality constraints under local knowledge and neighbor-only communication. It relates this formulation to smart-grid control, regression, and other network applications.
- A. Problem Formulation: Each of N agents has a local decision variable x_i, constraint set X_i, and continuous local mapping function f_i.The mappings combine M continuous scalar components.
- A. Problem Formulation: The network objective is a continuous function of the agents’ local mappings, while the agents jointly satisfy global inequality constraints.The formulation permits coupling through both the cost and constraints.
- A. Problem Formulation: Agents know only their local mapping, constraint function, and local constraint set, and must solve the problem through neighbor communication.The stated goal is a distributed algorithm using neighbor-only communication.
- B. Application to Smart Grid Control: Demand-side management models retailer costs caused by deviations between purchased power bids and customers’ aggregate real-time load.Demand excess or shortfall produces power-balance costs.
- B. Application to Smart Grid Control: Customer appliance controls determine load profiles over a time horizon, with local control constraints and costs for insufficient or excessive power bids.The control variables and load-profile structure depend on the appliance model.
- B. Application to Smart Grid Control: The formulation also covers regression, network-flow, microgrid, and power-flow control problems.The paper specifically mentions distributed sparse regression and network-lifetime optimization as examples.
- B. Application to Smart Grid Control: Distributed control is attractive for smart grids because agent failure has limited system impact and centralized collection can burden scalability and privacy.The proposed algorithm is applied to a DSM problem.
C. Centralized PD Subgradient Method
The centralized primal-dual subgradient method addresses convex constrained optimization through saddle-point iterations, but standard convergence can require restrictive assumptions or globally solved inner problems. Perturbed updates remove strict convexity and concavity requirements, while proximal perturbations extend the method to non-smooth constraints.
- Dual and saddle-point formulation: The Lagrange dual problem reformulates the constrained optimization task as a saddle-point problem over primal variables and nonnegative dual variables.The saddle-point relation connects primal-dual solutions of the original and dual problems.
- Primal-dual updates: A primal-dual subgradient iteration updates primal variables by projection and dual variables using subgradients of the Lagrangian.The method handles the inner problem inexactly rather than globally solving it at every iteration.
- Convergence limitations: Strict convexity in x and strict concavity in λ are often assumed to guarantee convergence of the whole sequence, but these conditions do not hold in general.Without such conditions, typical analyses establish convergence only for a subsequence.
- Perturbed updates: Perturbed primal-dual subgradient updates converge to a saddle point without strict convexity and concavity when perturbation points and step sizes are carefully chosen.The updates evaluate perturbed subgradients by replacing each variable with a perturbation point in the opposing update.
III. PROPOSED CONSENSUS-BASED DISTRIBUTED PDP ALGORITHM
The paper develops a distributed counterpart of the primal-dual perturbation method by combining local primal-dual updates with consensus-based estimates of global objective and constraint information. Under the stated network and problem framework, the algorithm converges to optimal primal-dual solutions, including for non-smooth constraints.
- Algorithm formulation: The proposed method is a distributed counterpart of the primal-dual perturbation subgradient method.It targets the saddle-point formulation while preserving distributed operation.
- Bounded dual formulation: The bounded dual domain is used because it bounds the dual variable and the primal subgradient, which supports the distributed convergence analysis.The bounded-domain saddle-point problem has the same optimal dual solution as the Lagrange dual problem.
- Distributed information estimates: Each agent maintains local copies of dual and auxiliary variables to estimate global objective and inequality-constraint quantities.The auxiliary estimates are updated through neighbor communication.
- Iteration steps: At each iteration, agents perform averaging consensus, compute local perturbation points, update primal-dual variables, and update auxiliary estimates.The procedure uses current neighbor messages before local perturbed subgradient updates.
- Guarantees and evaluation: Under the stated problem and network assumptions, the algorithm is proved to converge, and the paper directs readers to numerical results for performance evaluation.The convergence proof is presented in the following section, while numerical performance is evaluated later.
IV. CONVERGENCE ANALYSIS
The convergence-analysis section introduces additional assumptions on the optimization problem and network, states the main convergence results, and provides their proofs.
- Assumptions: Additional assumptions on the problem and network model are presented before the convergence results.These assumptions precede the main theorem statements.
- Results and proofs: The section presents the main convergence results and gives their proofs in subsequent subsections.The proofs are divided between Sections IV-C and IV-D.
A. Assumptions
The convergence analysis relies on convexity, regularity, boundedness, Slater feasibility, smoothness conditions where needed, and a sufficiently connected doubly stochastic time-varying network. Under these assumptions and suitable step sizes, the algorithm converges to optimal primal and dual solutions, including with non-smooth constraints.
- Problem assumptions: The feasible sets are compact, convex, and the problem is convex, with a Slater point ensuring strong duality.The objective and constraint functions are assumed convex on the relevant domains.
- Regularity assumptions: Objective and constraint functions have bounded or Lipschitz-continuous gradients or subgradients, with continuous differentiability additionally required for smooth constraints.These regularity conditions ensure well-behaved Lagrangian (sub-)gradients.
- Network assumptions: The time-varying weighted directed network uses positive self and link weights, doubly stochastic matrices, and uniformly bounded-window strong connectivity.These conditions ensure agents can sufficiently and equally influence one another.
- Proximal perturbations: The same convergence result holds for non-smooth constraint functions when proximal perturbation points are used.The result identifies optimal primal and dual solutions of the original problem.
- Gradient perturbations: With suitable non-increasing step sizes and gradient perturbation points, the distributed iterates converge to an optimal primal solution and an optimal dual solution.The theorem imposes a bound on ρ1 in addition to the step-size conditions.
C. Proof of Theorem 2
The proof establishes convergence of the distributed primal-dual iterates to a saddle point and verifies asymptotic primal-dual optimality under the stated assumptions.
- Consensus and centralized counterparts: Three key lemmas establish consensus for the estimated dual and perturbation variables across agents.The proof introduces centralized counterparts and shows local perturbation points converge to common values.
- Proof-scope note: The detailed proof of one supporting lemma is omitted and deferred to the electronic companion.This is the explicit proof-scope limitation stated in the section.
- Convergence to a saddle point: Under the assumptions, the primal-dual iterate pairs converge to a saddle point of problem (15).The argument uses boundedness, summability, perturbation-point relations, and a step-size restriction.
- Primal-dual optimality: The convergent iterates asymptotically satisfy the primal-dual optimality conditions of the original problem.Proposition 1 and Lemma 7 provide the final optimality connection used to conclude Theorem 2.
- Convergence to a saddle point: The limiting primal-dual pair belongs to X × D and forms a saddle point of problem (15).Existence follows from compactness, continuity, and the Slater condition, with dual optima contained in D.
- Averaging variant: The proof also permits an ordinary running average in place of the running weighted average when the step size has the specified form.The stated form is a_k = a/(b + k), with a > 0 and b ≥ 0.
D. Proof of Theorem 3
Theorem 3 follows the proof strategy of Theorem 2, replacing one distributed perturbation relation with an analogous relation for centralized perturbation points.
- Proof strategy: Theorem 3 reuses the proof line of Theorem 2, with Lemma 5 replaced by a corresponding centralized perturbation lemma.The needed relation links centralized perturbation points to the primal-dual iterates.
- Limit-point characterization: Under the stated assumptions and step-size condition, any limit point of the primal-dual iterates is a saddle point of problem (15).The result additionally assumes the relevant Lagrangian difference tends to zero and the iterates converge to a point in X × D.
V. SIMULATION RESULTS
The simulations evaluate the PDP method on distributed demand response control and relate its convergence, computational cost, and scheduling performance to comparator methods.
- Convergence comparison: Figure 1(a) compares objective-value convergence for PDP, distributed PD, and DDS methods using running-average iterates.The experiment uses a randomly generated network with N = 400 customers.
- Convergence comparison: Within 100 iterations, PDP and DDS show comparable convergence behavior and outperform the distributed PD method.The figure reports the comparison for the objective values in (61).
- Demand response performance: All three optimization methods improve power balancing relative to the load profile without demand-side management control.The scheduled profiles are produced by combining each method with the certainty equivalent control approach.
- Demand response performance: 45.65% reduction: PDP lowers the scheduled-load cost from 4.49 × 10^4 KW for unscheduled load to 2.44 × 10^4 KW.DDS achieves 2.38 × 10^4 KW, while distributed PD achieves 3.81 × 10^4 KW.
- Sparse regression: The PDP method is also applied to distributed sparse regression with a non-smooth constraint function.Simulation results for that application are referenced separately.
VI. CONCLUSIONS
The paper presents a consensus-based PDP algorithm for globally coupled constrained optimization and establishes distributed convergence to a global optimal primal-dual solution.
- Contribution: The PDP algorithm combines average consensus with a primal-dual perturbed subgradient method for globally coupled costs and inequality constraints.This formulation is intended for agents operating with distributed information.
- Theoretical result: The convergence analysis shows that agents across the network achieve a global optimal primal-dual solution in a distributed manner.The conclusion states this as the principal theoretical result.
- Applications: Effectiveness is demonstrated on smart-grid demand response control and sparse linear regression problems.The demand-response comparison specifically concerns PDP, DDS, and distributed PD methods.
- Comparative performance: PDP has better convergence properties than the non-perturbed distributed PD method.For demand response control, PDP performs comparably with DDS while being computationally cheaper.
APPENDIX A
Appendix A establishes convergence properties of the primal and dual perturbation updates, using convexity, Lipschitz continuity, bounded gradients, and projection continuity. Under the stated limit conditions and stepsize bound, the limit point satisfies primal-dual optimality conditions.
- Convergence proof: A convex decomposition lemma and optimality conditions establish the relation between perturbation points and the Lagrangian updates.The proof applies Lemma 9 and uses the linearity of the Lagrangian in the dual variable.
- Convergence proof: The proof bounds the primal and dual perturbation updates using bounded gradients and Lipschitz continuity assumptions.The argument invokes bounded gradients, Lipschitz continuity of ∇F and constraint functions, and bounded dual variables.
- Limit behavior: When the Lagrangian difference tends to zero and the iterates converge, the perturbation points approach the corresponding primal and dual iterates.With the stated bound on ρ1, both ∥x(k−1) − α̂(k)∥ and ∥λ̂(k−1) − β̂(k)∥ tend to zero.
- Optimality: The limit point is simultaneously a primal minimizer and dual maximizer of the Lagrangian over X and D.Projection continuity yields the saddle-point conditions for (x̂⋆, λ̂⋆).
APPENDIX C
Appendix C shows that perturbation errors and consensus-related terms vanish under the stated assumptions. These limits support primal and dual optimality of the resulting limit point.
- Error bounds: The analysis bounds the consensus and perturbation terms using convexity, bounded constraint functions, Lipschitz continuity, and bounded gradients.The proof repeatedly combines these assumptions to control the error terms in the recursive inequalities.
- Error limits: The weighted running averages of the relevant error terms converge to zero as the dual iterates converge.Lemma 6 and the weighted-average argument establish vanishing dual-disagreement contributions.
- Error limits: The primal perturbation discrepancy also vanishes: limk→∞∥x(k−1) − α̂(k)∥ = 0.This follows from the preceding bound and the assumed stepsize condition.
- Optimality: The dual feasibility limit is obtained by combining inequalities for λ̂⋆+δ and λ = 0 with convergence of the dual iterates.The resulting limit establishes the second term in relation (58).
- Optimality: The joint iterate and perturbation pair asymptotically coincide, enabling the proof that the limit point minimizes the Lagrangian over X.The argument uses the bound on ρ1 and the convergence assumption for the iterates.