PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Algorithms for Optimal Power Flow Problem

Albert Y. S. Lam, Baosen Zhang, David Tse

arXiv:1109.5229v1math.OCcs.SYeess.SY

TL;DR

OPF is generally non-convex, and solving it efficiently matters for real-time use as renewable energy increases. The paper decomposes convexified OPF into coordinated subproblems using primal and dual algorithms. Its simulations report roughly linear computation-time growth for cumulative solving and size-independent time for parallel distributed solving.

  • Problem

    OPF is generally non-convex, and efficient solution is desirable for real-time use as renewable energy increases.

    Source: §I · p. 1

  • Method

    The paper decomposes convexified OPF into smaller subproblems and proposes primal and dual algorithms to coordinate them.

    Source: §I · p. 2

  • Results

    For distribution-network simulations, cumulative computation time grows roughly linearly with network size, while distributed computation time is independent of size.

    Source: §VI · p. 11

  • Takeaways & Limitations

    The algorithms outperform centralized solving without decomposition, especially for tree-structured problems, and the dual method also outperforms centralized solving on networks without tree structure.

    Source: §VIII · p. 12

    The primal algorithm can fail to update shared edge variables efficiently near the SDP feasible-region boundary, whereas the dual update avoids this issue.

    Source: §VII · p. 12

Abstract

from arXiv · show

Optimal power flow (OPF) is an important problem for power generation and it is in general non-convex. With the employment of renewable energy, it will be desirable if OPF can be solved very efficiently so its solution can be used in real time. With some special network structure, e.g. trees, the problem has been shown to have a zero duality gap and the convex dual problem yields the optimal solution. In this paper, we propose a primal and a dual algorithm to coordinate the smaller subproblems decomposed from the convexified OPF. We can arrange the subproblems to be solved sequentially and cumulatively in a central node or solved in parallel in distributed nodes. We test the algorithms on IEEE radial distribution test feeders, some random tree-structured networks, and the IEEE transmission system benchmarks. Simulation results show that the computation time can be improved dramatically with our algorithms over the centralized approach of solving the problem without decomposition, especially in tree-structured problems. The computation time grows linearly with the problem size with the cumulative approach while the distributed one can have size-independent computation time.

I. INTRODUCTION

The paper targets efficient OPF for growing power networks, where the problem is generally non-convex and centralized solution can be impractical. It formulates a convexified problem and relies on zero-duality-gap conditions to recover an optimal solution for supported network structures.

A. Problem Formulation

  • OPF minimizes generation cost subject to demand and physical network constraints, but quadratic voltage-power relations make the general problem non-convex.The paper notes that heuristic methods are not guaranteed optimal, while DC-OPF relies on lossless lines, constant voltage, and small voltage angles and is not accurate in all circumstances.Source: §I · p. 1

I. INTRODUCTION

  • Distributed primal and dual algorithms coordinate decomposed OPF subproblems using only one-hop power-network neighbors, with computation time independent of bus count in parallel and roughly linear when cumulative.The reported tests include IEEE radial distribution feeders, random tree networks, and IEEE transmission benchmarks.Source: §I · p. 2

B. Zero Duality Gap

  • For tree, lossless-cycle, or combined tree-and-cycle networks, the simplified OPF and its SDP relaxation have equivalent optimal solutions under the stated zero-duality-gap result.The cited result also establishes that the SDP has a rank-one solution.Source: B. Zero Duality Gap · pp. 2–3

C. Graph Structure

The paper uses maximal-clique structure to decompose the SDP and develops a primal algorithm that coordinates subproblems through shared matrix components. This decomposition is designed to permit independent subproblem solves and can accommodate SDP solvers beyond interior-point methods.

C. Graph Structure

  • A graph is made chordal by adding fill-in edges, after which maximal cliques define the subproblems; for a tree, each network edge forms a maximal clique.The paper constructs the clique set from the matrix sparsity graph using an elimination ordering, fill-in computation, and a maximal-clique algorithm.Source: C. Graph Structure · p. 3

III. ALGORITHMS

  • The decomposition can use an appropriate SDP algorithm, not only an interior-point method, allowing future efficient SDP solvers to be incorporated.The algorithms produce positive semidefinite matrices, with a separate mechanism described for recovering the voltage vector.Source: C. Graph Structure · p. 3, §III · p. 3

A. Primal Algorithm

  • The primal method fixes shared matrix components to make maximal-clique subproblems independent, then updates the shared components in a master problem.Given shared components, the clique subproblems can be solved in parallel.Source: A. Primal Algorithm · p. 4

B. Dual Algorithm

The dual algorithm decomposes the problem by maximal cliques and coordinates clique subproblems through equalities linking shared variables. Lagrange multipliers update those equalities asynchronously, while averaging shared-variable copies can produce a feasible matrix before convergence.

B. Dual Algorithm

  • Lagrange multipliers are assigned to the equalities, and each subproblem is solved using the corresponding aggregate multipliers.The equalities can be arranged in different ways, provided each copy appears in at least one equality.Source: B. Dual Algorithm · pp. 5–6
  • Each maximal clique yields a subproblem, but copies of shared variables must be constrained to agree across cliques.The algorithm represents the shared-variable consistency conditions as equalities between copies.Source: B. Dual Algorithm · pp. 5–6
  • Multiplier updates drive shared-variable copies closer together so their consistency equalities hold at convergence.The updates adjust the price according to the difference between the two copies.Source: B. Dual Algorithm · p. 6
  • Before convergence, averaging copies of each shared variable constructs a feasible matrix from otherwise infeasible clique solutions.The unaveraged copies need not satisfy the consistency equalities before convergence.Source: B. Dual Algorithm · p. 6
  • Updates can be asynchronous because coordination between subproblems occurs through the multiplier updates, so synchronization is not required.An update can be made when the relevant pair of copies has been computed.Source: B. Dual Algorithm · p. 6

C. Computation of Voltage

After either algorithm converges, assuming zero duality gap, the optimal matrix has the form W = vv^H. Bus voltage magnitudes and line angle differences are then recovered from entries of W.

C. Computation of Voltage

  • With zero duality gap, convergence of either algorithm yields the optimal matrix W = vv^H.This matrix is the basis for recovering the network voltages.Source: C. Computation of Voltage · p. 6
  • The voltage magnitude at bus i is recovered as |Vi| = √Wii.The diagonal entries of W provide the bus voltage magnitudes.Source: C. Computation of Voltage · p. 6
  • For a line between buses i and k, its voltage angle difference is obtained from Wik = |Vi||Vk|ejθik, then fixing one bus angle to zero determines network voltages.Either endpoint can solve for the angle difference, with the other endpoint sending its voltage magnitude.Source: C. Computation of Voltage · p. 6

IV. QUADRATIC COST FUNCTION

For quadratic costs, the paper extends its linear-cost OPF algorithms with an outer iteration. It solves a linear-cost problem for fixed auxiliary variables and uses a gradient step to optimize those variables.

IV. QUADRATIC COST FUNCTION

  • For quadratic cost functions, the linear-cost solution algorithms are used as subroutines within an additional outer loop.The paper assumes the cost function is convex, with ci2 > 0 for each bus.Source: §IV · p. 7
  • For fixed z, the reformulated problem has linear costs, so an algorithm from the preceding sections can solve it.The resulting costs are c_i1 − 2√c_i2 z_i for each bus i.Source: §IV · p. 7
  • A gradient algorithm optimizes z using the gradient evaluated from an optimal primal-dual solution that depends on z.The derivative given is ∂J/∂z_i = −2Tr(√c_i2 A_i W*) − 2z_i.Source: §IV · p. 7

V. ILLUSTRATIVE EXAMPLES

The examples illustrate the algorithms on two network structures and show how their components and communication are arranged.

V. ILLUSTRATIVE EXAMPLES

  • One example is an n-bus radial network with height equal to one, used to illustrate maximal cliques sharing a common bus.Source: §V · p. 7
  • A five-bus network with a four-bus ring illustrates sharing across multiple levels of buses and edges.Source: §V · p. 7
  • The examples also show where algorithm components are implemented and how communication is carried out.Source: §V · p. 7

A. n-Bus Radial Network

The radial-network primal algorithm decomposes the problem into clique subproblems coordinated through shared W_nn. Subproblems are solved in parallel, and bus n updates the shared variable from their returned multipliers.

1) Primal Algorithm:

  • Each branch and its end nodes form a maximal clique, with W_nn shared across the cliques through slack variables X_nn,l.The clique subproblems are SDPs with 2 × 2 variables.Source: 1) Primal Algorithm · p. 8
  • Given W_nn, each clique solves its own subproblem independently, and the master problem coordinates the shared variable.The passage identifies φ_l(W_nn) as the optimal value of subproblem l given W_nn.Source: 1) Primal Algorithm · p. 8
  • Clique buses solve their subproblems in parallel and return λ_nn,l, which bus n uses to update W_nn.For most interior-point methods, the optimal primal and dual solutions come as a pair, so λ_nn,l requires no extra calculation.Source: 1) Primal Algorithm · p. 8

2) Dual Algorithm:

The dual algorithm coordinates clique subproblems by assigning prices to equality constraints on shared variables. Clique nodes solve in parallel and send their results to bus n, which updates and redistributes the prices.

2) Dual Algorithm:

  • The dual decomposition enforces equality among clique copies X_nn,l of the shared variable W_nn.The equalities are arranged with Lagrangian multipliers.Source: 2) Dual Algorithm · p. 8
  • Each clique subproblem is an SDP with a 2 × 2 variable, and its price is updated for the shared-variable constraints.Source: 2) Dual Algorithm · p. 8
  • Clique nodes solve in parallel and send their optimal X_nn values to bus n, which updates each price when the corresponding pair arrives and multicasts it back.Source: 2) Dual Algorithm · p. 8

B. Five-Bus Network with a Four-Bus Ring

For the five-bus network with a four-bus ring, the primal algorithm uses a chordal decomposition into three cliques. Coordinating buses exchange shared variables and multipliers to coordinate their subproblems.

B. Five-Bus Network with a Four-Bus Ring

  • Adding a fill-in edge between buses 2 and 3 yields cliques {1, 2, 3}, {2, 3, 4}, and {4, 5}.Buses 2 and 4 coordinate the first and second cliques, and the second and third cliques, respectively.Source: B. Five-Bus Network with a Four-Bus Ring · p. 9

1) Primal Algorithm: 

  • The three clique subproblems are given different combinations of W variables: subproblem 1 receives W_22 and W_33; subproblem 2 receives W_22, W_33, and W_44; subproblem 3 receives W_44.Source: 1) Primal Algorithm:  · p. 9
  • Buses 1, 4, and 5 solve the clique subproblems, return Lagrangian multipliers, and buses 2 and 3 update shared variables.Bus 4 receives bus 5’s λ_44,3 along with its own λ_44,2.Source: 1) Primal Algorithm:  · p. 9

2) Dual Algorithm:

The dual algorithm for the ring network distributes clique subproblems across buses 1, 4, and 5. Coordinating buses send prices, receive slack-variable copies, and update the prices.

2) Dual Algorithm:

  • Table I is labeled as normalized CPU time for distribution test feeders.Source: Table I · p. 10
  • The three clique subproblems optimize over variables for buses 1–3, 2–4, and 4–5, respectively.Each displayed subproblem is an SDP with a positive-semidefinite clique variable.Source: 2) Dual Algorithm · p. 10
  • At time t, bus 2 announces υ22,1, υ23,1, and υ33,1 to buses 1 and 4, while bus 4 sends υ44,1 to bus 5; after solving, buses send X values back.Buses 1 and 4 send X22,1, X23,1, and X33,1, and X22,2, X23,2, and X33,2, respectively, to bus 2; bus 5 sends X44,3 to bus 4.Source: 2) Dual Algorithm · p. 10

VI. SIMULATION RESULTS

The simulations compare centralized OPF solving with primal and dual decomposition on distribution feeders, radial networks, and transmission benchmarks. On tree-structured distribution problems, decomposition changes how runtime scales with network size; the dual algorithm is also reported as preferable to centralized solving on transmission benchmarks.

VI. SIMULATION RESULTS

  • The comparison measures SDP-solver CPU time for centralized, cumulative, and distributed approaches; cumulative subproblems are solved sequentially, while distributed subproblems run in parallel.The reported success criterion is reaching an objective value within 10^-2 of the global minimum within 100 iterations.Source: §VI · p. 11
  • Tests include distribution feeder benchmarks and 100 randomly generated instances per network, plus radial networks with 100 instances per size and IEEE transmission benchmarks.All algorithms converged within 100 iterations for the feeder instances; radial-network average CPU times were plotted on a logarithmic scale.Source: §VI · p. 11
  • For distribution networks, centralized CPU time grows rapidly with network size, cumulative runtime grows roughly linearly, and distributed runtime is size-independent.Both primal and dual algorithms converge very fast on these distribution-network tests.Source: §VI · p. 11
  • The dual algorithm misses the 100-iteration stopping criterion on a small fraction of small networks, but its success rate approaches 100% as network size grows.On average, the dual requires slightly less CPU time than the primal.Source: §VI · p. 11
  • On IEEE transmission benchmarks, the dual algorithm is more desirable than centralized solving; the primal algorithm was not applied.Table II reports normalized CPU times, iterations to convergence, and initial step sizes; clique configurations and step sizes were selected for this simulation.Source: Table II · p. 10, §VI · p. 11

VII. DISCUSSION

The discussion distinguishes when the primal and dual algorithms are suited to different network structures and update conditions. The conclusion reports linear runtime growth for cumulative solving and size-independent runtime for parallel solving on tree-structured problems, while identifying extensions as future work.

VII. DISCUSSION

  • Primal coordination shares less information between buses because a bus computes its common solution locally; the dual requires each subproblem to acquire all its bus information.The paper notes this favors situations with sensitive bus information.Source: §VII · p. 11
  • Communication uses one-hop exchanges between neighboring nodes, with links needed only along existing transmission lines.No overlay communication network with a different topology is required.Source: §VII · p. 11
  • The dual can handle ring networks, whereas primal updates of fill-in edges can fail after large steps and become inefficient near the feasible boundary.The dual avoids this update issue, and averaging shared variables can keep a solution feasible.Source: §VII · pp. 11–12
  • Irregular networks offer many possible clique decompositions, making performance depend on clique selection and step-size tuning; tree-structured performance is easier to predict.For trees, each branch and its attached nodes form a maximal clique, simplifying decomposition.Source: §VII · p. 12
  • The dual tolerates communication delays better: a delayed subproblem can affect some υ updates, while primal shared-variable updates require λ from all involved subproblems.The dual is asynchronous and allows different pairings of variables when its equalities are formed.Source: §VII · p. 12

VIII. CONCLUSION

  • For tree-structured problems, cumulative runtime grows linearly with problem size, while parallel solving makes computation time independent of size; the dual also outperforms centralized solving without tree structure.The paper identifies adding constraints and supporting nonlinear objectives as future work.Source: §VIII · p. 12
Loading 1109.5229v1…