PaperlayerView exact revision on arXiv

Source-linked AI summary

A Distributed Approach for the Optimal Power Flow Problem Based on ADMM and Sequential Convex Approximations

S. Magnússon, P. C. Weeraddana, C. Fischione

arXiv:1401.4621v2math.OC

TL;DR

OPF is a nonconvex, NP-hard problem, while existing SDP approaches are limited to special network classes and may fail to produce feasible operating points. The paper combines ADMM with sequential convex approximations to solve bus-level subproblems in a distributed manner. Numerical experiments substantiate convergence and show near-optimal performance with scalability advantages over global methods.

  • Problem

    OPF is nonconvex and NP-hard, while SDP-based approaches are limited to special network classes and can fail to provide feasible operating points.

  • Method

    The paper decomposes general nonconvex OPF into bus-level problems, coordinating them with ADMM and sequential convex approximations through limited neighboring communication.

  • Results

    For large test examples, the relative objective value is on the order of 10^-3 and is not affected by network size, while convergence across considered cases is 99.99%-100%.

  • Takeaways & Limitations

    The proposed method provides a distributed approach to general nonconvex OPF with mathematically and numerically substantiated convergence properties.

Abstract

from arXiv · show

The optimal power flow (OPF) problem, which plays a central role in operating electrical networks is considered. The problem is nonconvex and is in fact NP hard. Therefore, designing efficient algorithms of practical relevance is crucial, though their global optimality is not guaranteed. Existing semi-definite programming relaxation based approaches are restricted to OPF problems where zero duality holds. In this paper, an efficient novel method to address the general nonconvex OPF problem is investigated. The proposed method is based on alternating direction method of multipliers combined with sequential convex approximations. The global OPF problem is decomposed into smaller problems associated to each bus of the network, the solutions of which are coordinated via a light communication protocol. Therefore, the proposed method is highly scalable. The convergence properties of the proposed algorithm are mathematically substantiated. Finally, the proposed algorithm is evaluated on a number of test examples, where the convergence properties of the proposed algorithm are numerically substantiated and the performance is compared with a global optimal method.

I. INTRODUCTION

OPF optimizes generation and dispatch across an electrical network while meeting demand and physical laws. The paper targets general, scalable distributed methods because existing approaches face scalability, network-class, or feasibility limitations.

  • OPF determines generator outputs and dispatches power to optimize a network-wide objective while satisfying demand and physical laws.
  • Because OPF is nonconvex and NP-hard, practical algorithms generally require approximations or heuristics.
  • Existing SDP-based methods are limited to special network classes and may fail to produce feasible operating points under a nonzero duality gap.
  • Centralized methods scale poorly, whereas distributed methods can exploit network sparsity and reduce the need to collect sensitive data centrally.
  • The paper develops a distributed method for general nonconvex OPF that handles non-quadratic convex objectives and is not restricted to zero-duality network classes.
  • ADMM coordinates bus-level computations with limited neighboring communication, while sequential approximations address subproblem nonconvexity.

A. Centralized formulation

The centralized OPF formulation optimizes generation and network variables under electrical and operational constraints. It is reformulated into a consensus structure so local bus problems share only consistency constraints.

  • A. Centralized formulation: For fixed demands, OPF tunes generation, flow, current, and voltage variables to minimize convex generation cost under network relationships and system limits.
  • A. Centralized formulation: The formulation includes physical-law constraints for current, power flow, and line quantities, plus bounds on power, current, and voltage variables.
  • A. Centralized formulation: Nonconvex constraints make the centralized OPF problem NP-hard, motivating an efficient decentralized solution method.
  • B. Distributed formulation: The problem is equivalently reformulated so all constraints except one consistency constraint decouple among buses.
  • B. Distributed formulation: Each bus maintains local copies of neighboring voltages and enforces agreement through consistency constraints.
  • B. Distributed formulation: The neighborhood N_k contains bus k and its connected neighbors, defining the voltage copies used by each local formulation.
  • B. Distributed formulation: The distributed formulation groups local variables and constraints into affine, nonlinear equality, and convex inequality components.
  • B. Distributed formulation: Consensus constraints absorb the original coupling, yielding a general consensus problem suitable for decomposition methods.

III. DISTRIBUTED SOLUTION METHOD

The distributed solution method applies ADMM to separate bus-level private updates from shared voltage and dual updates. Local computations are coordinated through a closed-form net-variable update and light communication.

  • ADMM is used as the basis for solving the distributed OPF formulation, with the augmented Lagrangian separable across buses.
  • Each ADMM iteration updates private bus variables by solving local optimization problems, then updates the shared net variable and dual variables.
  • The algorithm stops according to iteration limits, consistency decrements, or other stated convergence criteria.
  • The net-variable update solves an unconstrained quadratic optimization problem with a closed-form solution.
  • Net-variable communication and dual-variable updates can be performed distributively with light communication or locally at each bus.

B. The subproblems: Private variable update

The private-variable subproblem is solved by sequential convex approximations. Nonconvex constraints are replaced locally by convex approximations and refined iteratively until a stopping condition is met.

  • Sequential convex approximations provide an efficient alternative to exponentially complex global methods for the NP-hard subproblem.
  • Convex constraints are retained, while the nonconvex constraints are approximated to obtain tractable subproblems.
  • The voltage-magnitude feasible set has a donut shape and is therefore nonconvex.
  • A convex subset of the donut is constructed using affine approximations, including a tangent hyperplane at a selected point.
  • Nonlinear equality constraints are approximated with first-order Taylor expansions around the current iterate.
  • The approximation is refined iteratively by updating the expansion point until the stopping criterion is satisfied.
  • Each iteration solves a convex optimization problem, while initialization uses the current voltage and uniquely determined remaining components.
  • The subroutine can stop when the relevant voltage decrement is below a threshold, with an optional maximum iteration count.

C. On the use of quadratic programming (QP) solvers

The method exploits convex subproblem structure to solve updates efficiently, with distributed net-variable averaging and local dual-variable updates requiring limited coordination.

  • Quadratic objective functions allow problem (16) to be solved efficiently with specialized QP solvers.General interior-point methods remain applicable, but QP solvers can provide higher efficiency when the objective is quadratic.
  • The net variable update has a unique closed-form solution from an unconstrained convex quadratic optimization problem.The update is obtained from the optimality conditions of problem (13).
  • Net-variable components are updated by averaging copies maintained among neighboring buses.This averaging can be implemented with fully distributed algorithms such as gossiping.
  • Each bus updates its dual variables locally using the scaled discrepancy between net variables and its own copies.

IV. PROPERTIES OF THE DISTRIBUTED SOLUTION METHOD

The solution method repeatedly convexifies the nonconvex subproblems and refines the approximations. Its behavior can include infeasibility, convergence, or cycling, while the stated optimality result depends on an empirical convergence scenario and strict feasibility assumptions.

  • Convergence properties: The original OPF subproblem is nonconvex and NP-hard, so ADMM-based approaches lack general convergence guarantees.General convergence results are available for the convex case, but not automatically for this nonconvex setting.
  • Sequential convex approximations: Algorithm 2 replaces nonconvex functions with first-order Taylor approximations and nonconvex sets with convex inner approximations.For the representative problem, the convex set satisfies ˇZ ⊆Z, and the expansion point determines the Taylor approximation.
  • Graphical scenarios: Sequential refinement may make the approximated problem infeasible, converge to a desired point, or switch between two points without convergence.The infeasibility scenarios arise from an improper set approximation or approximation point, while the switching scenario alternates between points A and B.
  • Initialization and empirical behavior: Approximation points and convex-set choices strongly influence Algorithm 2, so unfavorable initializations must be avoided.The paper reports that particular choices often produce the convergent scenario and rarely produce the infeasible or cycling scenarios.
  • Optimality properties: Under Assumption 1, Algorithm 2 outputs points satisfying the KKT conditions for problem (12).The assumption includes convergence of the relevant sequence and strict satisfaction of constraint (16h).
  • Optimality properties: Because the convergent scenario is empirically dominant, the resulting point is characterized as locally optimal or globally optimal.This conclusion is tied to the empirical observation that Assumption 1 usually holds.

C. Optimality properties of ADMM-DOPF solution

The paper formalizes ADMM-DOPF’s output using approximate KKT optimality and analyzes how local KKT properties extend to the full distributed solution. Under Assumption 1, the method achieves quantified approximate optimality, although feasibility and optimality are not guaranteed in general.

  • The method cannot guarantee that its eventual output is optimal or even feasible for the original NP-hard OPF problem.
  • Algorithm 2 produces a KKT point for the local problem solved at each ADMM-DOPF step.
  • (δ, ǫ)-KKT optimality formalizes approximate feasibility, stationarity, dual feasibility, and complementary slackness for nonconvex problems.The definition applies to inequality and equality constraints with associated dual variables.
  • ADMM-DOPF consistency residuals need not vanish, but suitable ρ usually produces a small practically negligible error floor.The consistency error is quantified through δ_k for subsequent optimality analysis.
  • Under Assumption 1, ADMM-DOPF terminates at an (a−1¯δ, b−1ρ2¯δ)-KKT optimal point.Here, ¯δ quantifies the aggregate consistency error, while ρ is the ADMM penalty parameter and a, b are normalization factors.
  • After 5000 ADMM-DOPF iterations with ρ = 10^6, simulations yielded δ on the order of 10^-12 and ǫ on the order of 10^-1 or smaller.

V. NUMERICAL RESULTS

Numerical experiments evaluate Algorithm 2 on modified OPF test networks, focusing on convergence behavior and feasibility. The algorithm achieved high convergence rates and returned power injections with very high feasibility accuracy.

  • Experimental setup: The experiments compare the proposed algorithm with branch and bound, a centralized Matpower solver, and an SDP relaxation on four nonzero-duality-gap examples.The test cases were selected to study convergence where SDP-based approaches may not provide feasible operating points.
  • Convergence behavior: Algorithm 2 was executed 11060000 times, with infeasible approximated subproblems occurring only 6 times (≈0.00008%).All six occurrences arose at buses in the 300-bus example during ADMM iterations 137–143.
  • Convergence behavior: 99.995% of cases converged to points satisfying the KKT conditions for N = 3 and max_iter = 20, while overall convergence ranged from 99.99%-100%.Increasing max_iter improved convergence for N = 300 and left it unchanged for N = 3, 9, 14, 30, and 118.
  • Feasibility: The returned voltages were always feasible, while power injections could be infeasible and were assessed using the degree of feasibility metric DF.DF is measured in MVA and is evaluated across buses and ADMM iterations using empirical CDFs and histograms.
  • Feasibility: The worst-case accuracy of the returned power injections was 2.5 × 10−10.The empirical CDF and histogram results indicate high-accuracy feasibility across all considered cases.

B. Connection to Proposition 2

The numerical evaluations connect δ and ǫ to Proposition 2 by examining their convergence, feasibility implications, and relationship with ADMM iterations and penalty parameters. The experiments also assess objective quality, runtime scalability, and constraint feasibility.

  • δ behavior: δ decreases across penalty parameters, generally approaching smaller error floors as ρ increases, although convergence is slower for the 30-bus example.For 3-, 9-, and 14-bus cases, larger ρ drives δ closer to zero; the 30-bus case remains decreasing at the final iterations for ρ = 10^9, ..., 10^13.
  • ǫ behavior: ǫ generally decreases with ADMM iterations, reaching 10^-2 to 10^-11 in 3-, 9-, and 14-bus cases, but falling below 10^-2 only for ρ = 10^6 in the 30-bus case.Under Assumption 1, simultaneous convergence of δ and ǫ to zero supports convergence to a KKT optimal point.
  • Feasibility: The returned generator variables are feasible with very high precision, with worst-case infeasibility on the order of 10^-10 per ADMM iteration.The remaining constraint (10f) still requires separate feasibility verification when computing a sensible operating point.
  • Scalability: Parallel running time is independent of network size across the 9-, 14-, 30-, 118-, and 300-bus examples, indicating scalability.The 3-bus case has higher parallel time because each subproblem handles more variables.
  • Objective quality: Relative objective error is on the order of 10^-3 for 30-, 118-, and 300-bus cases and 10^-6 for 3-, 9-, and 14-bus cases.For the 3- and 9-bus examples, ρ = 10^6 yields relative objective values on the order of 10^-6.
  • Objective quality: The objective discrepancy is 0.1% or less after 10000 ADMM iterations and 1% or less after 3000 iterations relative to the optimum.These results compare ADMM-DOPF operating points with optimal values in the reported test cases.

VI. CONCLUSIONS

The section describes a sequential convex-approximation procedure that progressively refines local feasible-set approximations while solving quadratic programs. The procedure terminates when the solution satisfies the current approximations and otherwise adds affine or hyperplane refinements.

  • Sequential approximation: The method approximates nonlinear feasible boundaries with polyhedral sets and affine functions whose precision increases over successive iterations.The construction targets feasible regions associated with constraints (16g) and (16h).
  • Algorithm 3: Algorithm 3 initializes approximations, solves a quadratic program, checks feasibility, and refines the approximation when the check fails.The QP uses pG_k, p̄_k, q̄_k, and z_k as variables.
  • Sequential approximation: The initial set approximates the exterior boundary of the donut-shaped feasible region with an equilateral octagon.Subsequent iterations add hyperplanes to the exterior boundary when the candidate lies outside the current approximation.
  • Stopping and refinement: The algorithm terminates when γ̄_k(z^(m̄)) ≤ 0 and all relevant voltage components lie in the approximated feasible sets.Otherwise, it increases approximation precision and repeats the QP solve.

APPENDIX B PROOFS

The appendix proves that limits of the sequential approximations recover the original functions and gradients, enabling the limiting solution to satisfy feasibility, dual feasibility, complementary slackness, and stationarity conditions.

  • KKT conditions: The proof establishes primal feasibility, dual feasibility, complementary slackness, and vanishing Lagrangian derivative for the limiting solution.Together, these are the KKT conditions required for the original problem.
  • Approximation limits: Lemma 1 states that function values and gradients of the first-order approximations converge to those of the original function as the iterates converge.Specifically, both the approximation and its gradient converge at z⋆.
  • Approximation limits: The limiting approximations equal the original functions and gradients at z⋆, providing the bridge from the approximated problem to the original problem.This identity is used to transfer optimality properties between the two formulations.
  • KKT conditions: Identical constraints and the construction of the approximated sets allow dual feasibility and complementary slackness to transfer to the original formulation.The components associated with the approximated constraint are identically zero in the limiting argument.

B. Proof of Proposition 2

The proof of Proposition 2 relates the global consistency and stationarity measures δ and ǫ to local approximation errors. It uses quadratic Taylor identities and convergence of the ADMM iterates to show that the approximation and gradient errors vanish.

  • Consistency measure: Under Assumption 1, Proposition 1 supplies feasibility of all original constraints except (10f), allowing δ to be expressed as a scaled average local inconsistency.The relation is δ = a^-1 δ̄, where a is the length of the local inconsistency vector.
  • Stationarity measure: The stationarity measure satisfies ǫ = b^-1ρ^2δ̄, linking it directly to the inconsistency measure and penalty parameter.Here b is the length of the limiting primal-dual variable vector.
  • Taylor approximation: For the quadratic function h, the Taylor remainder equals (1/2)(z^(m) − z)^T H(z^(m) − z), and the gradient error equals H(z^(m) − z).The Hessian H has constant entries and does not depend on z.
  • Convergence: As z^(m) converges to z⋆, both the function-value and gradient errors converge to zero.The proof obtains these limits from the Taylor remainder and gradient-error identities.
Loading 1401.4621v2…