Source-linked AI summary
Initialization-free Distributed Algorithms for Optimal Resource Allocation with Feasibility Constraints and its Application to Economic Dispatch of Power Systems
Peng Yi, Yiguang Hong, Feng Liu
TL;DR
The paper studies distributed resource allocation when agents keep objective, resource, and feasibility data private while satisfying global and local constraints. It proposes two initialization-free continuous-time projected algorithms, establishes convergence results, and applies them to changing power-grid economic dispatch settings.
Problem
The problem is to minimize the sum of private local objectives while satisfying a global resource constraint and each agent’s local feasibility constraint.
Method
The paper proposes fully distributed continuous-time algorithms based on projection and differentiated projection, using only local data and neighbor communication.
Results
The algorithms converge for strictly convex objectives, support scalable economic dispatch under changing data or configurations, and require no initialization coordination.
Takeaways & Limitations
The method supports plug-and-play operation and general non-box local feasibility constraints in dynamic power-grid settings.
Takeaways & Limitations
Open problems include convergence-rate estimates with general local constraints, nonsmooth objectives, noisy observations, and integration with physical grid dynamics.
Abstract
from arXiv · showhide
In this paper, the distributed resource allocation optimization problem is investigated. The allocation decisions are made to minimize the sum of all the agents' local objective functions while satisfying both the global network resource constraint and the local allocation feasibility constraints. Here the data corresponding to each agent in this separable optimization problem, such as the network resources, the local allocation feasibility constraint, and the local objective function, is only accessible to individual agent and cannot be shared with others, which renders new challenges in this distributed optimization problem. Based on either projection or differentiated projection, two classes of continuous-time algorithms are proposed to solve this distributed optimization problem in an initialization-free and scalable manner. Thus, no re-initialization is required even if the operation environment or network configuration is changed, making it possible to achieve a "plug-and-play" optimal operation of networked heterogeneous agents. The algorithm convergence is guaranteed for strictly convex objective functions, and the exponential convergence is proved for strongly convex functions without local constraints. Then the proposed algorithm is applied to the distributed economic dispatch problem in power grids, to demonstrate how it can achieve the global optimum in a scalable way, even when the generation cost, or system load, or network configuration, is changing.
1. Introduction
The paper addresses distributed resource allocation with private agent data, local feasibility constraints, and changing network conditions by developing initialization-free projected algorithms.
- Distributed resource allocation is motivated by applications in economics, communication, sensor networks, and power grids.
- Private local objectives, resource data, and feasibility constraints must be coordinated without a central decision-making center.
- Local feasibility constraints create additional difficulty because they change the optimality conditions relative to unconstrained resource allocation.
- Initialization coordination becomes impractical when loads, capacities, costs, or network membership change, especially in dynamic power grids.
- Two fully distributed continuous-time projected algorithms maintain local feasibility and asymptotically enforce the network resource constraint without feasible initial allocations.
- Convergence is established using Laplacian and projection properties together with the LaSalle invariance principle, with applications to scalable economic dispatch.
2. Preliminaries and problem formulation
This section introduces convex-analysis and graph-theoretic tools, then formulates distributed resource allocation with global and local feasibility constraints, private agent data, and cooperative optimization over a connected network.
- 2.1. Convex analysis and projection: Convex feasibility is described through normal, feasible-direction, and tangent cones, with the tangent cone characterized as the closure of feasible directions and the polar of the normal cone.These geometric objects support constrained projection-based analysis.
- 2.1. Convex analysis and projection: Projection maps a point onto a closed convex set, while differentiated projection maps a feasible point and direction to a tangent-cone-compatible direction.The differentiated projection has explicit interior and boundary cases based on cone normals.
- 2.1. Convex analysis and projection: The projection operation satisfies a nonexpansive-type inequality relating ||PΩ(x) − y||² to ||x − y||² for feasible y.The section also introduces convexity, locally Lipschitz gradients, and strong convexity properties.
- 2.2. Graph theory: Information exchange is modeled by a graph whose directed edges identify which agents can access one another’s information; connectedness means every pair is linked by a path.Adjacency and degree matrices define the graph Laplacian.
- 2.2. Graph theory: For a connected undirected graph, the Laplacian has a simple zero eigenvalue associated with 1_n, while all remaining eigenvalues are positive.The eigenvalues are ordered from the positive second eigenvalue through the nth eigenvalue.
- 2.3. Problem formulation: Each agent chooses x_i ∈ R^m using private resource data d_i, local feasible set Ω_i, and objective f_i(x_i), while allocations must satisfy the global resource constraint and x_i ∈ Ω_i.The whole allocation is represented by X = col(x_1, ..., x_n).
- 2.3. Problem formulation: The DRAO problem extends earlier distributed allocation models by adding general local feasibility constraints, which also generalize prior box constraints.The local objectives, resources, and feasibility sets are not shared, so agents cooperate through the network without a center.
- 2.3. Problem formulation: Continuously differentiable convex objectives with locally Lipschitz gradients and positive definite Hessians imply strict convexity and uniqueness, alongside finite optimality, Slater feasibility, and undirected connected communication assumptions.Finite solutions are readily guaranteed in cases such as quadratic objectives and compact feasible sets.
3. Projected algorithm for DRAO
The projected distributed algorithm combines gradient-flow and consensus dynamics with local projection to preserve feasibility and reach optimal resource allocation without initialization coordination.
- Algorithm structure: Each agent uses only its local allocation data and neighboring agents’ auxiliary variables, so the algorithm requires no central coordinator.The local data include d_i, f_i(x_i), and Ω_i; shared information consists of neighboring λ_j and z_j variables.
- Feasibility and optimality: Projection preserves each local feasibility constraint throughout the trajectory when the initial allocation lies in its local feasible set.Nagumo’s theorem establishes invariance of Ω_i under the projected dynamics.
- Feasibility and optimality: With local feasibility constraints, optimal allocations need not have equal marginal costs because normal-cone terms create a feasibility-related price difference.This differs from the unconstrained condition requiring equal marginal costs.
- Algorithm structure: The algorithm combines projected gradient flows with proportional-integral consensus dynamics, treating λ_i as local shadow prices that must reach consensus.Consensus among local shadow prices represents the global market-clearing price.
- Initialization-free operation: The network resource constraint is enforced asymptotically without requiring it to hold initially, eliminating initialization coordination and enabling adaptation to changing network configurations.The algorithm can operate in a plug-and-play manner when agents leave or join dynamical networks.
- Feasibility and optimality: Under the stated assumptions and bounded feasible initial points, trajectories remain bounded and converge to an equilibrium whose allocation is optimal for DRAO.The equilibrium satisfies the KKT conditions, while LaSalle’s invariance principle establishes convergence.
4. Differentiated projected algorithm for DRAO
The differentiated projected algorithm applies tangent-cone projections to distributed resource allocation with local feasibility constraints. It preserves feasibility, converges under strong convexity, and converges exponentially when local constraints are absent.
- Algorithm design: The algorithm differentiates the projection operator by projecting each agent’s descent-plus-dual direction onto its local tangent cone.This extends the projected dynamics while requiring tangent-cone computation.
- Computational trade-off: Compared with the projected algorithm, the differentiated version adds the burden of computing tangent cones, although closed forms are available for polyhedra, Euclidean balls, and boxes.The paper identifies common convex feasible sets for which tangent-cone computation is tractable.
- Algorithm design: The differentiated projected algorithm is distributed and requires no initialization coordination, allowing it to process online data in dynamic networks.Agents can operate without repeating a coordination procedure when network data or configuration changes.
- Correctness and convergence: Starting from feasible initial points, the trajectories remain within every local feasibility set, and the algorithm has an equilibrium whose allocation is optimal.The feasibility guarantee follows from projected dynamics and the equilibrium characterization.
- Correctness and convergence: For strongly convex local objectives with Lipschitz gradients, bounded trajectories converge to equilibrium; without local constraints, convergence is exponential.The convergence theorem assumes bounded feasible initial points and states exponential convergence only when Ωi = Rm.
- Correctness and convergence: The convergence proof uses strong convexity, Laplacian connectivity, and a Lyapunov-function analysis to establish convergence of the differentiated dynamics.The analysis derives negative Lyapunov-function derivatives using the algebraic connectivity of the network Laplacian.
5. Distributed economic dispatch in power grids
The paper applies its distributed algorithm to economic dispatch with generation capacity constraints, testing adaptation to changing data, configurations, and network scale. The simulations show asymptotic power balance and optimality without re-initialization, including a 1000-control-area case.
- The distributed economic dispatch problem minimizes total generation cost while meeting total load within each generator’s capacity bounds.
- The differentiated projected algorithm keeps generation within local capacity bounds and converges without initialization coordination.Each agent projects its local generation onto its capacity bounds when necessary.
- The power balance gap asymptotically decreases to zero without re-initialization, while the optimality condition is satisfied asymptotically.Consensus among λ_i values also converges in the reported performance indexes.
- The IEEE 118-bus simulation changes loads, generation capacities, generation costs, and bus connectivity during operation.Changes include load variations at 100s, capacity variations at 200s, cost variations at 300s, bus disconnection at 400s, and reconnection at 500s.
- At t = 80s, the 1000-control-area simulation shows lower consensus error, near-achieved power balance, and satisfied optimality across varying operating conditions.The large-scale example uses changing loads, generation costs and capacities, and a regenerated connected graph each period.
6. Conclusions
The paper concludes that projected continuous-time distributed algorithms address resource allocation with local feasibility constraints without initialization coordination. It highlights plug-and-play economic dispatch applications while identifying unresolved convergence, nonsmoothness, noise, and physical-dynamics challenges.
- The proposed projected algorithms are scalable, initialization-free, and adaptable to changing working conditions.
- The method supports general non-box local feasibility constraints, including quadratic constraints relevant to inverter-based devices.
- Application examples indicate potential for plug-and-play operation and smarter power-grid operation in dynamic environments.
- Open problems include nonsmooth objectives, convergence-rate estimates with general local constraints, noisy observations, and coupling with physical power-grid dynamics.