# Distributed Learning Algorithms and Lossless Convex Relaxation for Economic Dispatch with Transmission Losses and Capacity Limits

Authors: Kwang-Ki K. Kim
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

This paper considers problems of economic dispatch in power networks that contain independent power generation units and loads. For efficient distributed economic dispatch, we present a mechanism of multiagent learning in which each agent corresponding to a generation unit updates the power generation based on the received information from the neighborhood. The convergence of the proposed distributed learning algorithm to the global optimal solution is analyzed. Another method of distributed economic dispatch we propose is a decentralized iterative linear projection method in which the necessary optimality conditions are solved without considering the generation capacities and the obtained solutions are iteratively projected onto the convex set corresponding to the generation capacities. A centralized method based on semidefinite programming for economic dispatch with a loss coefficient matrix is also presented for comparisons. For demonstration, the proposed methods of distributed economic dispatch are applied to a 6-generator test case and the three different methods of economic dispatch give the same solutions. We also analyze parametric dependence of the optimal power generation profiles on varying power demands in economic dispatch.


---

## Body

## 1. Introduction

The smart grid infrastructure including smart sensors and meters and communication technology has triggered revisiting fundamental problems of power systems research. In such energy system infrastructures with communication networks, different independent units take the control and operational responsibility in different areas of the system [1, 2].In particular, economic dispatch with integration of distributed generators and energy storage systems in a smart grid infrastructure is one of the major challenges for large-scale complex power networks to meet the total power demand by allocating demand among many independently operated distributed generators in an efficient way with guaranteed quality of service and safety [3]. Because of distributed and hierarchical structures of power supplies and demands, and their connections through information and communication infrastructures, it requires distributed mechanisms of dispatching electrical power demands among available generation units in efficient ways. Several distributed algorithms for economic dispatch have been presented in the literature, whereas many of existing approaches to economic dispatch are centrally performed. In [4, 5], the authors propose the distributed incremental cost consensus algorithm in which the dual variable corresponding to the marginal price and the power generation mismatches are updated by a weighted-sum consensus rule. But such algorithms do not consider any transmission constraints.Other consensus-based distributed algorithms for economic dispatch are presented by different research groups. For the method presented in [6], each generator learns the mismatch between demand and total power generation by communication over a strongly connected graph and corrects its own power generation to achieve the consensus. In [7, 8], the authors present a consensus-based distributed bisection method in which the dual variable corresponding to the marginal price is explicitly computed by a bisection method with power generation updates of distributed generators. In addition, the authors of [9] propose a distributed method of lambda-iteration in which the conventional lambda-iteration method [10] is modified to take the presence of prohibited operating zones and to avoid an oscillatory phenomenon. In [11], a game-theoretic learning distributed algorithm based on population dynamics without considering transmission losses is presented. Another game-theoretic approach is presented by the authors of [12] in which a cooperative game is formulated for optimal power aggregation to minimize the total generation cost while meeting the generation capacity constraints. Evolutionary algorithms are also applied to the problem of economic dispatch: genetic algorithm [13], particle swarm optimization [14], and evolutionary programming techniques [15].Our contribution is threefold. First, we present a method of primal-dual iteration for computing optimal power generation profiles in economic dispatch with transmission losses and generation limits. The proposed algorithm is based on distributed computations of the independent decision-making processes with information exchange. The convergence of the proposed algorithm to the global optimum is analyzed. Secondly, semidefinite programming relaxation of the associated quadratic constrained quadratic program formulated from a constrained economic dispatch problem. This convex relaxation is shown to be exact; i.e., strong duality holds. Thirdly, we present a decentralized method of iterative linear projection for the same class of economic dispatch. This algorithm is based on iterative projections of linear system solution corresponding to the reduced KKT conditions and its convergence is guaranteed with relatively small size of iteration numbers. In addition, the explicit dependence of the optimal power generation profiles on varying power demand is investigated in terms of multiparametric programming. This paper is organized as follows.Section2 presents a distributed iteration method for economic dispatch in the presence of generation capacity limits and quadratic transmission losses. In Section 3, a semidefinite programming relaxation of the associated quadratic constrained quadratic program is studied and its strong duality is analyzed. In addition, the explicit parametric dependence of the optimal generation profiles on varying power demand is investigated. To demonstrate the effectiveness of the proposed distributed and convex relaxation algorithms, the methods are applied to the IEEE 26-bus 6-generator test case in Section 4. Section 5 concludes this paper.


## 2. Distributed Economic Dispatch in Smart Grids

### 2.1. A Brief Introduction to Economic Dispatch

Economic dispatch is an optimization problem in which the objective is to minimize the total power generation cost under physical limitations of distributed generators and demand-supply balance that are represented as inequality and equality constraints:(1)EDminimize∑i=1Nfipisubjecttopimin≤pi≤pimax;i=1,2,…,N∑i=1Npi-∑i=1N∑j=1NpiBijpj=Pdwhere pi refers to the power generation output of the generator i, and pimin and pimax are the minimum and maximum generation output limits of the generator i, respectively. The power loss in transmission is given as a quadratic form parameterized by the loss-coefficient matrix B [10]. The power generation cost functions fi:R+→R+ for i=1,2,…,N are usually modeled as quadratic forms:(2)fipi=12aipi2+bipi+ciwhere ai([$/MW2]), bi([$/MW]), and ci([$]) denote the cost coefficients of generator i.


### 2.2. Optimality Conditions for Economic Dispatch

Consider a Lagrange function (or Lagrangian) defined by(3)Lp1,p2,…,pN,μ≔∑i=1Nfipi+μPd+∑i=1N∑j=1NpiBijpj-∑i=1Npifor which the equality constraint corresponding to the power balance is relaxed and integrated into the objective function by introducing a Lagrange multiplier μ∈R. With this definition of Lagrangian, the necessary conditions for optimality are given as follows: (1)
Stationarity:(4)∇piLp1∗,p2∗,…,pN∗,μ∗=0fori=1,2,…,N(2)
Primal feasibility:(5)Pd+∑i=1N∑j=1Npi∗Bijpj∗-∑i=1Npi∗=0(6)pimin≤pi∗≤pimaxfori=1,2,…,NTo find an optimal demand allocation in economic dispatch (1), we need to solve N+1 equations while satisfying 2N inequalities for N+1 variables (p1∗,p2∗,…,pN∗,μ∗) in (4)~(6).


### 2.3. Multiagent Learning for Distributed Economic Dispatch

To find a solution profile(p1∗,p2∗,…,pN∗,μ∗) that satisfies the optimality conditions (4)~(6), we develop an iterative method of distributed optimization that is based on multiagent learning. Figure 1 shows a schematic diagram for message exchanges and updates among the aggregator (denoted by Node 0) and the agents (indexed by 1,2,…,N). Best response dynamics of power generation updates for agents and gradient descent dynamics of price updates for the aggregator are depicted in Figure 2 as block diagrams with arrows denoting message exchanges.Figure 1
A schematic diagram for physical connections and communication in power-generation grid. The solid black lines denote the electrical connections between generators, the blue dashed arrows denote communication links between generators, the red dotted arrow denotes the broadcasting of the Lagrange multiplier, and the blue dotted arrows denote the generators’ willing-to-supply powers for given Lagrange multiplier.Figure 2
Block diagram of distributed iterative computations of primal-dual variables in economic dispatch with coupled power loss. The update rulesBRi and GDi are defined in (10) and (11), respectively.


#### 2.3.1. Primal Updates (Distributed Learning)

Define setsNi≜j:Bij≠0 for i=1,2,…,N and the associated vector pNi=(pj)j∈Ni∈R|Ni|, where |Ni| denotes the cardinality of the set Ni. Each unit of the ith generator receives the current computation of pNi from its neighbourhood Ni and the current computation of Lagrangian multiplier μ and updates its computation of pi by solving a local optimization (7)pik+1≔argminpimin≤pi≤pimaxLipi,pNik,μkwhere (8)Lipi,pNik,μk≜fipi+μk2pi∑j∈NiBijpjk-pifor k=0,1,… and for each i=1,2,…,N. More succinctly, we write(9)pik+1≔BRipNik,μkfori=1,2,…,Nwhere the ith local optimization (7) has a unique solution for every k=0,1,…, provided that ai≠0 due to its strict convexity. We note that the ith local optimization (7) has the following closed-form solution:(10)pik+1=piminforp~ik<piminpimaxforp~ik>pimaxp~ikforpimin≤p~ik≤pimaxwhere p~i(k)≜1/aiμ(k)1-∑j∈NiBijpj(k)-bi.


#### 2.3.2. Dual Update

The Lagrangian multiplier is updated to enforce the demand-supply balance to be satisfied. The aggregator receives the current computations ofpi for i=1,…,N and revises its previous computation of μ by (11)μk+1≔μk+αk+1Pd+PLk+1-∑i=1Npik+1where PL(k+1)≜∑i=1N∑j∈Nipi(k+1)Bijpj(k+1) denotes the power loss computed for iteration steps k=0,1,…, and α(k+1)>0 is a user-defined step size.Figure2 shows how such primal and dual updates are performed with exchange of information among neighboring agents (or generators) and the aggregator.


### 2.4. Decentralized Relaxed Convex QP

Consider a simpler case of ED in (1) for which the power loss coefficients Bij (i,j=1,2,…,N) are neglected:(12)ED′minimize∑i=1Nfipisubject  topimin≤pi≤pimax;i=1,2,…,N∑i=1Npi=PdFor this case with quadratic cost functions in (2), necessary conditions for optimality are given as the following linear system:(13)a10⋯0-10a2⋱⋮-1⋮⋱⋱0⋮0⋯0aN-111⋯10p1∗p2∗⋮pN∗μ∗=-b1-b2⋮-bNPdand(14)pimin≤pi≤pimaxfori=1,2,…,N.Note that if ai≠0 for all i so that system (13) is linearly independent, then we have a unique closed-form solution for (13):(15)pi∗=1aiδβ+δPd-bifori=1,2,…,Nμ∗=δβ+Pdwhere δ=(∑i=1N1/ai)-1 and β=∑i=1Nbi/ai. The vector p=p1∗p2∗⋯pN∗⊤∈RN obtained in the closed-form (15) does not necessarily satisfy the capacity constraints (14).Define the following sets of indices:(16)Iminp≜i:pi<piminImaxp≜i:pi>pimaxLet I(p)≜Imin(p)⋃Imax(p) define its union and a complementary set I~(p)≜1,2…,N-Imax(p). For the given solution vector p obtained in (15), consider the following reduced economic dispatch(17)ED′pminimize∑i∈I~pfipisubjecttopimin≤pi≤pimax;i∈I~p∑i∈I~ppi=Pd-∑i∈Imaxppimaxwhere the generators corresponding to the set Imax(p) are assigned to produce their upper limits in capacity and the remaining generators are further considered as design variables for optimization. Similar to (15), a closed-form solution satisfying necessary conditions for optimality is obtained as follows:(18)pi∗=pimaxfori∈Imaxp1aiδ~β~+δ~P~d-bifori∈I~pμ∗=δ~β~+P~dwhere δ~=(∑i∈I~1/ai)-1, β~=∑i∈I~bi/ai, and P~d=Pd-∑i∈Imax(p)pimax. Note that this update again does not guarantee satisfaction of the capacity constraints and this process must be iteratively performed. This iteration method stops when the set of saturated generators are the same in subsequent computations, i.e., I~(p(k))≡I~(p(k-1)), and the resultant optimal solution is given by (19)pi∗=piminfori∈Iminpkpimaxfori∈Imaxpk1aiδ~β~+δ~P~d-bifori∈I~pkwhere(20)δ~=∑i∈I~pk-Iminpk1ai-1,β~=∑i∈I~pk-Iminpkbiai,P~d=Pd-∑i∈Imaxpkpimax-∑i∈Iminpkpimin.Proposition 1.
Letp(0) be given by (15) and define a recursive equation p(k)≔F(p(k-1)), where F:RN→RN is defined by (18). If there exists p∈Δ≜p∈RN:pimin≤pi≤pimax;i=1,2,…,N such that ∑i=1Npi=Pd, then this recursive equation with the initial condition p(0) given in (15) converges.Proof.
Let the optimal value ofED′(p) in (17) be J(p). Starting from the initial condition p(0), we define a sequence of real numbers ηk≔J(p(k-1)) for k≥1. From the update rule in (18), this sequence is monotonically nondecreasing, i.e., ηk≤ηk+1 for k≥1, and it has an upper bound since there exists p∈Δ≜p∈RN:pimin≤pi≤pimax;i=1,2,…,N such that ∑i=1Npi=Pd. From the monotone convergence theorem [16], this sequence converges. Due to strict convexity of fi for all i, p(k) is uniquely defined for each ηk for all k≥1 and the convergence of ηk implies the convergence of p(k).It is also not hard to see that any initial conditionp(0)∈Δ guarantees convergence of F:RN→RN defined by (18) to a unique solution of the economic dispatch (12). That is because I(p0)=1,2,…,N and p(1) is given as (15). Figure 3 shows the iterative message-passing between the aggregator (Node 0) and distributed generators (Nodes 1,2,…,N). Notice that the broadcasting message announced by the aggregator at time step k is a tuple (δ(k),β(k),Pd(k)) that is computed from the collected private messages mik=aik,bik,sik:i=1,2,…,N by following (18).Figure 3
A schematic diagram for decentralized iterative computations and message passing. The aggregator (Node0) broadcasts the values of (δ[$/MW2],β[MW]) and Pd[MW], and each generator i (Node i) sends a private message mi=(ai[$/MW2],bi[$/MW],si∈-1,0,1) to the aggregator, where si=-1 implies the ith generator decides to produce its lower limit, i.e., pimin, si=1 implies the ith generator decides to produce its upper limit, i.e., pimax, and si=0 implies the ith generator wants to continue negotiation by receiving new values of δ, β, and Pd from the aggregator.Remark 2.
In our iterative message-passing framework for distributed economic dispatch that is depicted in Figure3, it is assumed that all generators report theirtrue cost (function) parameters (ai,bi),i=1,2,…,N. It is, of course, possible that a generator can take advantage of lying to the cost parameters. It is our future work to design a pricing mechanism computing μ based on the reported cost parameters so that none of generators can benefit from lying. Such a problem is related to the problem of parameterized supply function equilibrium [17–19].In the presence of nontrivial transmission loss coefficientsBij, the proposed linear iterative projection method has to be modified. A heuristic method can be applied to take the loss coefficients into account. At each iteration step k, the power demand Pd(k) is replaced by Pd(k)+∑i=1N∑j=1Npi(k-1)Bijpj(k-1) that is computed and broadcasted by the aggregator as depicted in Figure 3. Upon a new residual power demand Pd(k)+∑i=1N∑j=1Npi(k-1)Bijpj(k-1) is computed, saturated generators are excluded in planning and allocation is performed among generators not yet reached the limits (see Figure 4).Figure 4
A schematic diagram of water-filling in decentralized multiagent learning. When power demand increases asPd′, each unsaturated generator j that does not meet its capacity limit is required to produce additional power Pd′-Pd1/aj/∑i∈I~1/ai, where I~ refers to the set of unsaturated generators.


## 2.1. A Brief Introduction to Economic Dispatch

Economic dispatch is an optimization problem in which the objective is to minimize the total power generation cost under physical limitations of distributed generators and demand-supply balance that are represented as inequality and equality constraints:(1)EDminimize∑i=1Nfipisubjecttopimin≤pi≤pimax;i=1,2,…,N∑i=1Npi-∑i=1N∑j=1NpiBijpj=Pdwhere pi refers to the power generation output of the generator i, and pimin and pimax are the minimum and maximum generation output limits of the generator i, respectively. The power loss in transmission is given as a quadratic form parameterized by the loss-coefficient matrix B [10]. The power generation cost functions fi:R+→R+ for i=1,2,…,N are usually modeled as quadratic forms:(2)fipi=12aipi2+bipi+ciwhere ai([$/MW2]), bi([$/MW]), and ci([$]) denote the cost coefficients of generator i.


## 2.2. Optimality Conditions for Economic Dispatch

Consider a Lagrange function (or Lagrangian) defined by(3)Lp1,p2,…,pN,μ≔∑i=1Nfipi+μPd+∑i=1N∑j=1NpiBijpj-∑i=1Npifor which the equality constraint corresponding to the power balance is relaxed and integrated into the objective function by introducing a Lagrange multiplier μ∈R. With this definition of Lagrangian, the necessary conditions for optimality are given as follows: (1)
Stationarity:(4)∇piLp1∗,p2∗,…,pN∗,μ∗=0fori=1,2,…,N(2)
Primal feasibility:(5)Pd+∑i=1N∑j=1Npi∗Bijpj∗-∑i=1Npi∗=0(6)pimin≤pi∗≤pimaxfori=1,2,…,NTo find an optimal demand allocation in economic dispatch (1), we need to solve N+1 equations while satisfying 2N inequalities for N+1 variables (p1∗,p2∗,…,pN∗,μ∗) in (4)~(6).


## 2.3. Multiagent Learning for Distributed Economic Dispatch

To find a solution profile(p1∗,p2∗,…,pN∗,μ∗) that satisfies the optimality conditions (4)~(6), we develop an iterative method of distributed optimization that is based on multiagent learning. Figure 1 shows a schematic diagram for message exchanges and updates among the aggregator (denoted by Node 0) and the agents (indexed by 1,2,…,N). Best response dynamics of power generation updates for agents and gradient descent dynamics of price updates for the aggregator are depicted in Figure 2 as block diagrams with arrows denoting message exchanges.Figure 1
A schematic diagram for physical connections and communication in power-generation grid. The solid black lines denote the electrical connections between generators, the blue dashed arrows denote communication links between generators, the red dotted arrow denotes the broadcasting of the Lagrange multiplier, and the blue dotted arrows denote the generators’ willing-to-supply powers for given Lagrange multiplier.Figure 2
Block diagram of distributed iterative computations of primal-dual variables in economic dispatch with coupled power loss. The update rulesBRi and GDi are defined in (10) and (11), respectively.


### 2.3.1. Primal Updates (Distributed Learning)

Define setsNi≜j:Bij≠0 for i=1,2,…,N and the associated vector pNi=(pj)j∈Ni∈R|Ni|, where |Ni| denotes the cardinality of the set Ni. Each unit of the ith generator receives the current computation of pNi from its neighbourhood Ni and the current computation of Lagrangian multiplier μ and updates its computation of pi by solving a local optimization (7)pik+1≔argminpimin≤pi≤pimaxLipi,pNik,μkwhere (8)Lipi,pNik,μk≜fipi+μk2pi∑j∈NiBijpjk-pifor k=0,1,… and for each i=1,2,…,N. More succinctly, we write(9)pik+1≔BRipNik,μkfori=1,2,…,Nwhere the ith local optimization (7) has a unique solution for every k=0,1,…, provided that ai≠0 due to its strict convexity. We note that the ith local optimization (7) has the following closed-form solution:(10)pik+1=piminforp~ik<piminpimaxforp~ik>pimaxp~ikforpimin≤p~ik≤pimaxwhere p~i(k)≜1/aiμ(k)1-∑j∈NiBijpj(k)-bi.


### 2.3.2. Dual Update

The Lagrangian multiplier is updated to enforce the demand-supply balance to be satisfied. The aggregator receives the current computations ofpi for i=1,…,N and revises its previous computation of μ by (11)μk+1≔μk+αk+1Pd+PLk+1-∑i=1Npik+1where PL(k+1)≜∑i=1N∑j∈Nipi(k+1)Bijpj(k+1) denotes the power loss computed for iteration steps k=0,1,…, and α(k+1)>0 is a user-defined step size.Figure2 shows how such primal and dual updates are performed with exchange of information among neighboring agents (or generators) and the aggregator.


## 2.3.1. Primal Updates (Distributed Learning)

Define setsNi≜j:Bij≠0 for i=1,2,…,N and the associated vector pNi=(pj)j∈Ni∈R|Ni|, where |Ni| denotes the cardinality of the set Ni. Each unit of the ith generator receives the current computation of pNi from its neighbourhood Ni and the current computation of Lagrangian multiplier μ and updates its computation of pi by solving a local optimization (7)pik+1≔argminpimin≤pi≤pimaxLipi,pNik,μkwhere (8)Lipi,pNik,μk≜fipi+μk2pi∑j∈NiBijpjk-pifor k=0,1,… and for each i=1,2,…,N. More succinctly, we write(9)pik+1≔BRipNik,μkfori=1,2,…,Nwhere the ith local optimization (7) has a unique solution for every k=0,1,…, provided that ai≠0 due to its strict convexity. We note that the ith local optimization (7) has the following closed-form solution:(10)pik+1=piminforp~ik<piminpimaxforp~ik>pimaxp~ikforpimin≤p~ik≤pimaxwhere p~i(k)≜1/aiμ(k)1-∑j∈NiBijpj(k)-bi.


## 2.3.2. Dual Update

The Lagrangian multiplier is updated to enforce the demand-supply balance to be satisfied. The aggregator receives the current computations ofpi for i=1,…,N and revises its previous computation of μ by (11)μk+1≔μk+αk+1Pd+PLk+1-∑i=1Npik+1where PL(k+1)≜∑i=1N∑j∈Nipi(k+1)Bijpj(k+1) denotes the power loss computed for iteration steps k=0,1,…, and α(k+1)>0 is a user-defined step size.Figure2 shows how such primal and dual updates are performed with exchange of information among neighboring agents (or generators) and the aggregator.


## 2.4. Decentralized Relaxed Convex QP

Consider a simpler case of ED in (1) for which the power loss coefficients Bij (i,j=1,2,…,N) are neglected:(12)ED′minimize∑i=1Nfipisubject  topimin≤pi≤pimax;i=1,2,…,N∑i=1Npi=PdFor this case with quadratic cost functions in (2), necessary conditions for optimality are given as the following linear system:(13)a10⋯0-10a2⋱⋮-1⋮⋱⋱0⋮0⋯0aN-111⋯10p1∗p2∗⋮pN∗μ∗=-b1-b2⋮-bNPdand(14)pimin≤pi≤pimaxfori=1,2,…,N.Note that if ai≠0 for all i so that system (13) is linearly independent, then we have a unique closed-form solution for (13):(15)pi∗=1aiδβ+δPd-bifori=1,2,…,Nμ∗=δβ+Pdwhere δ=(∑i=1N1/ai)-1 and β=∑i=1Nbi/ai. The vector p=p1∗p2∗⋯pN∗⊤∈RN obtained in the closed-form (15) does not necessarily satisfy the capacity constraints (14).Define the following sets of indices:(16)Iminp≜i:pi<piminImaxp≜i:pi>pimaxLet I(p)≜Imin(p)⋃Imax(p) define its union and a complementary set I~(p)≜1,2…,N-Imax(p). For the given solution vector p obtained in (15), consider the following reduced economic dispatch(17)ED′pminimize∑i∈I~pfipisubjecttopimin≤pi≤pimax;i∈I~p∑i∈I~ppi=Pd-∑i∈Imaxppimaxwhere the generators corresponding to the set Imax(p) are assigned to produce their upper limits in capacity and the remaining generators are further considered as design variables for optimization. Similar to (15), a closed-form solution satisfying necessary conditions for optimality is obtained as follows:(18)pi∗=pimaxfori∈Imaxp1aiδ~β~+δ~P~d-bifori∈I~pμ∗=δ~β~+P~dwhere δ~=(∑i∈I~1/ai)-1, β~=∑i∈I~bi/ai, and P~d=Pd-∑i∈Imax(p)pimax. Note that this update again does not guarantee satisfaction of the capacity constraints and this process must be iteratively performed. This iteration method stops when the set of saturated generators are the same in subsequent computations, i.e., I~(p(k))≡I~(p(k-1)), and the resultant optimal solution is given by (19)pi∗=piminfori∈Iminpkpimaxfori∈Imaxpk1aiδ~β~+δ~P~d-bifori∈I~pkwhere(20)δ~=∑i∈I~pk-Iminpk1ai-1,β~=∑i∈I~pk-Iminpkbiai,P~d=Pd-∑i∈Imaxpkpimax-∑i∈Iminpkpimin.Proposition 1.
Letp(0) be given by (15) and define a recursive equation p(k)≔F(p(k-1)), where F:RN→RN is defined by (18). If there exists p∈Δ≜p∈RN:pimin≤pi≤pimax;i=1,2,…,N such that ∑i=1Npi=Pd, then this recursive equation with the initial condition p(0) given in (15) converges.Proof.
Let the optimal value ofED′(p) in (17) be J(p). Starting from the initial condition p(0), we define a sequence of real numbers ηk≔J(p(k-1)) for k≥1. From the update rule in (18), this sequence is monotonically nondecreasing, i.e., ηk≤ηk+1 for k≥1, and it has an upper bound since there exists p∈Δ≜p∈RN:pimin≤pi≤pimax;i=1,2,…,N such that ∑i=1Npi=Pd. From the monotone convergence theorem [16], this sequence converges. Due to strict convexity of fi for all i, p(k) is uniquely defined for each ηk for all k≥1 and the convergence of ηk implies the convergence of p(k).It is also not hard to see that any initial conditionp(0)∈Δ guarantees convergence of F:RN→RN defined by (18) to a unique solution of the economic dispatch (12). That is because I(p0)=1,2,…,N and p(1) is given as (15). Figure 3 shows the iterative message-passing between the aggregator (Node 0) and distributed generators (Nodes 1,2,…,N). Notice that the broadcasting message announced by the aggregator at time step k is a tuple (δ(k),β(k),Pd(k)) that is computed from the collected private messages mik=aik,bik,sik:i=1,2,…,N by following (18).Figure 3
A schematic diagram for decentralized iterative computations and message passing. The aggregator (Node0) broadcasts the values of (δ[$/MW2],β[MW]) and Pd[MW], and each generator i (Node i) sends a private message mi=(ai[$/MW2],bi[$/MW],si∈-1,0,1) to the aggregator, where si=-1 implies the ith generator decides to produce its lower limit, i.e., pimin, si=1 implies the ith generator decides to produce its upper limit, i.e., pimax, and si=0 implies the ith generator wants to continue negotiation by receiving new values of δ, β, and Pd from the aggregator.Remark 2.
In our iterative message-passing framework for distributed economic dispatch that is depicted in Figure3, it is assumed that all generators report theirtrue cost (function) parameters (ai,bi),i=1,2,…,N. It is, of course, possible that a generator can take advantage of lying to the cost parameters. It is our future work to design a pricing mechanism computing μ based on the reported cost parameters so that none of generators can benefit from lying. Such a problem is related to the problem of parameterized supply function equilibrium [17–19].In the presence of nontrivial transmission loss coefficientsBij, the proposed linear iterative projection method has to be modified. A heuristic method can be applied to take the loss coefficients into account. At each iteration step k, the power demand Pd(k) is replaced by Pd(k)+∑i=1N∑j=1Npi(k-1)Bijpj(k-1) that is computed and broadcasted by the aggregator as depicted in Figure 3. Upon a new residual power demand Pd(k)+∑i=1N∑j=1Npi(k-1)Bijpj(k-1) is computed, saturated generators are excluded in planning and allocation is performed among generators not yet reached the limits (see Figure 4).Figure 4
A schematic diagram of water-filling in decentralized multiagent learning. When power demand increases asPd′, each unsaturated generator j that does not meet its capacity limit is required to produce additional power Pd′-Pd1/aj/∑i∈I~1/ai, where I~ refers to the set of unsaturated generators.


## 3. Further Characteristics of Economic Dispatch

### 3.1. Convex Relaxation of QCQP

Consider the following optimization problem:(21)minimize∑i=1Nfipisubject  topimin≤pi≤pimax;i=1,2,…,N∑i=1Npi-∑i=1N∑j=1NpiBijpj≥Pdin which the equality constraint corresponding to demand-supply balance of ED in (1) is relaxed to be inequality. This can be rewritten as the following quadratically constrained quadratic programming (QCQP):(22)minimize12p⊤Ap+b⊤p+csubject  topmin≤p≤pmaxp⊤Bp-1N⊤p+Pd≤0where B is symmetric, but not necessarily positive semidefinite, so that this QCQP might be nonconvex. A method of convex relaxation can be applied to obtain the following semidefinite program (SDP): (23)minimize12tr⁡AP+b⊤p+csubjecttopmin≤p≤pmaxtr⁡BP-1N⊤p+Pd≤0Ppp⊤1⪰0where the linear matrix inequality is obtained from the Schur complement lemma for P-pp⊤⪰0 This inequality corresponds to convexification of the equality P=pp⊤.Lemma 3 (lossless relaxation).
The optimal values and the associated solutions of (22) and (23) are the same.Proof.
Let a solution of the optimization (22) be p¯. Substituting P=p¯p¯⊤+Q with Q⪰0 into the optimization (23), we have(24)minimize12tr⁡AQ+12p¯⊤Ap¯+b⊤p¯+csubjecttotr⁡BQ+p¯⊤Bp¯-1N⊤p¯+Pd≤0Q⪰0which reduces to(25)minimizetr⁡AQsubjecttotr⁡BQ≤0Q⪰0where the constant factor 1/2 in the objective function is removed for notational convenience. By considering a Lagrange function L(Q,λ)=tr⁡A+λBQ and from the positive definiteness of A≻0, the weak duality gives (26)optimal  value  of25≥maxλ≥0minQ⪰0LQ,λ=0ifA+λB⪰0-∞otherwiseand this implies that theunique optimal solution of (25) is Q∗≡0. Therefore, we conclude that the optimal solution of (23) is indeed the rank-one matrix P∗≡p¯p¯⊤ with an optimal solution p¯ of (22).


### 3.2. Multiparametric Programming

Consider the economic dispatch problem in (12). We analyze the dependence of the optimal solutions to the total power demand:(27)pi∗Pdfori=1,2,…,NProposition 4.
Suppose that there existsp∈Δ such that ∑i=1Npi=Pd. Every pi∗(Pd) is monotonically nondecreasing and continuously piecewise affine in Pd≥0 for i=1,2,…,N.Proof.
For the givenPd>0 and the corresponding optimal solution p∗(Pd) of the optimization (12), consider the optimization (17) with p=p∗(Pd) and the associated computation (18). Then, there exists a small enough ϵ>0 such that(28)pi∗Pd+ϵ=piminfori∈Iminp∗Pdpimaxfori∈Imaxp∗Pdpi∗Pd+1/ai∑j∈I~1/ajϵfori∈I~p∗Pdis the optimal solution of the economic dispatch (12) when the power demand is given by Pd+ϵ. In other words, the index sets Imin(p∗(Pd+ϵ)) and Imax(p∗(Pd)) remain the same and the optimal solutions pi∗(Pd) corresponding to the index set I~(p∗(Pd)) change as pi∗(Pd)+1/ai/∑j∈I~1/ajϵ. This shows that optimal solution p∗(Pd) is (elementwise)monotonically nondecreasing andcontinuously piecewise affine in Pd≥0.Now we analyze theexplicit dependence of the optimal power generation profile p∗ on the power demand Pd for which the results from multiparametric programming (MPP) [20] are exploited. We can rewrite the problem of economic dispatch in (12) as the following quadratic programming:(29)V∗Pd≔minimize12p⊤Ap+b⊤p+csubjecttoHp≤r+EPdwhere(30)A=a10⋯00a2⋱⋮⋮⋱⋱00⋯0aN,b=b1b2⋮bN,c=∑i=1NciH=1N×1⊤-1N×1⊤IN×NIN×N,r=00pmax-pmin,E=110N×10N×1with 1N×1 all ones vector in RN, 0N×1 all zeros vector in RN, IN×N identity matrix in RN×N, and pmax(min)=p1max(min)p2max(min)⋯pNmax(min)⊤∈RN. The associated KKT conditions are given by(31)Ap+H⊤w=0stationarity(32)Hp-r-EPd≤0primal  feasibility(33)w≥0dual  feasibility(34)w⊤Hp-r-EPd=0complementaritywhere w∈R(2N+2) is a (vector) Lagrange multiplier corresponding to the inequality in (29). For given Pd with which the optimization in (29) can be solved, the corresponding optimizer p yields the set of active constraints defined as(35)IaPd≜i∈J:Hip=ri+EiPdwhere J=1,2,…,2N+2 and (·)i denotes the ith row of the argument. The rows of the constraints matrices H, r, and E corresponding to the index set Ia(Pd) are extracted to construct the matrices HIa(Pd), rIa(Pd), and EIa(Pd) that would be rewritten in the following compact forms: HIa, rIa, and EIa, respectively, by hiding its dependence of Pd. By definition of Ia(Pd), we have the equality conditions of optimality(36)HIap-rIa-EIaPd=0.Combining the two systems of equations (31) and (36) gives(37)-HIaA-1H⊤w-rIa-EIaPd=0where H⊤w=HIa⊤wIa because the complementarity condition (34) implies wIac=0 for Iac=J∖Ia. Therefore, we obtain an active (vector) Lagrange multiplier(38)w=-HIaA-1HIa⊤-1rIa-HIaA-1HIa⊤-1EIaPdand the corresponding (primal) optimizer(39)p=-A-1HIa⊤wIa=A-1HIa⊤HIaA-1HIa⊤-1EIaPd+A-1HIa⊤HIaA-1HIa⊤-1rIawhere the inverse exists provided that the active constraints are linearly independent. Note that the active Lagrange multiplier and optimizer obtained in (38) and (39), respectively, are affine functions in Pd. The next step is to find or characterize all the points Pd′ in the neighborhood of Pd in which the optimizer p(Pd′) has the same set of active constraints, i.e., Ia(Pd′)=Ia(Pd) so that p(Pd′) is of the same form as (39). Such neighborhood of Pd can be obtained by substituting (39) and (38) into (32) and (33), respectively. Furthermore, it turns out that the neighborhood is a polyhedron(40)Pl≜Pd′∈R+:QlPd′≤qlwhere(41)Ql=HA-1HIa⊤HIaA-1HIa⊤-1EIa-EHIaA-1HIa⊤-1EIa,ql=r-HA-1HIa⊤HIaA-1HIa⊤-1rIa-HIaA-1HIa⊤-1rIaare computed from a given Pd and the associated optimizer p(Pd).Remark 5.
We have shown that the affine dependence of the optimal power generation profiles on the power demand can be explicitly analyzed. This parameterization could be useful when the power demands are not known a priori but forecasted with uncertainty. Analyzing the required power generation profiles over the wide range of power demands offline would help the system operator to schedule the power supply in smaller time-scales.


### 3.3. Uncertain Transmission Loss and Power Demand

In Section3.2, a method of multiparametric programming is suggested for taking care of uncertain power demand Pd. By applying MPP, economic generation dispatch is computed as a function of Pd in (38) and (39). In addition to uncertain power demand Pd, we also need to consider uncertain or variable power loss PL that is parameterized as a quadratic function ∑i=1N∑j=1NpiBijpj. The loss coefficients Bij are not certain but can be assumed to be bounded as(42)Bijmin≤Bij≤Bijmax,fori,j=1,2,…,Nwhere Bijmin and Bijmax refer to the lower and upper bounds of Bij, respectively. For more general representation of uncertain loss coefficient matrix B, we assume that B is not fixed but belongs to a convex polytope that has a finite number of vertices:(43)B∈ConvB0,B1,…,Blwhere Conv· denotes the convex hull of a set. In other words, there exists t0,t1,…,tl∈[0,1] with ∑τ=0ltτ=1 such that B=∑τ=0ltτB(τ). This implies that the quadratic loss function is parameterized as PL(p)=∑τ=0l∑i=1N∑j=1NtkpiBij(τ)pj, where tτ∈[0,1] are not known but uncertain. To take care of uncertain loss coefficients, the three proposed methods need to be modified.Modified SDP Method. The SDP method presented in (23) is modified to take the uncertain loss coefficient matrix B in (43) as follows: (44)minimize12tr⁡AP+b⊤p+csubject  topmin≤p≤pmaxtr⁡BτP-1N⊤p+Pd≤0,forτ=0,1,…,lPpp⊤1⪰0that is indeed robust optimization counterpart of (23).Modified Iterative Primal-Dual Method. The iterative primal-dual method presented in (7) and (11) is modified to take the uncertain loss coefficient matrix B in (43) as follows:(45)pik+1≔BRipNik,μkfori=1,2,…,Nμk+1≔μk+αk+1Pd+PLk+1-∑i=1Npik+1where(46)PLk+1≔max0≤τ≤l∑i=1N∑j∈Nipik+1Bijτpjk+1that is the worst-case line loss for given pi(k+1),i=1,2,…,N.Modified Iterative Linear Projection Method. The iterative primal-dual method presented in (19) is modified to take the uncertain loss coefficient matrix B in (43) as follows: (47)pik+1=piminfori∈Iminpkpimaxfori∈Imaxpk1aiδ~β~+δ~P~d-bifori∈I~pkwhere(48)P~d=Pd+max0≤τ≤l∑i=1N∑j∈NipikBijτpjk-∑i∈Imaxpkpimax-∑i∈Iminpkpimin,and δ~ and β~ are defined the same as (19).


## 3.1. Convex Relaxation of QCQP

Consider the following optimization problem:(21)minimize∑i=1Nfipisubject  topimin≤pi≤pimax;i=1,2,…,N∑i=1Npi-∑i=1N∑j=1NpiBijpj≥Pdin which the equality constraint corresponding to demand-supply balance of ED in (1) is relaxed to be inequality. This can be rewritten as the following quadratically constrained quadratic programming (QCQP):(22)minimize12p⊤Ap+b⊤p+csubject  topmin≤p≤pmaxp⊤Bp-1N⊤p+Pd≤0where B is symmetric, but not necessarily positive semidefinite, so that this QCQP might be nonconvex. A method of convex relaxation can be applied to obtain the following semidefinite program (SDP): (23)minimize12tr⁡AP+b⊤p+csubjecttopmin≤p≤pmaxtr⁡BP-1N⊤p+Pd≤0Ppp⊤1⪰0where the linear matrix inequality is obtained from the Schur complement lemma for P-pp⊤⪰0 This inequality corresponds to convexification of the equality P=pp⊤.Lemma 3 (lossless relaxation).
The optimal values and the associated solutions of (22) and (23) are the same.Proof.
Let a solution of the optimization (22) be p¯. Substituting P=p¯p¯⊤+Q with Q⪰0 into the optimization (23), we have(24)minimize12tr⁡AQ+12p¯⊤Ap¯+b⊤p¯+csubjecttotr⁡BQ+p¯⊤Bp¯-1N⊤p¯+Pd≤0Q⪰0which reduces to(25)minimizetr⁡AQsubjecttotr⁡BQ≤0Q⪰0where the constant factor 1/2 in the objective function is removed for notational convenience. By considering a Lagrange function L(Q,λ)=tr⁡A+λBQ and from the positive definiteness of A≻0, the weak duality gives (26)optimal  value  of25≥maxλ≥0minQ⪰0LQ,λ=0ifA+λB⪰0-∞otherwiseand this implies that theunique optimal solution of (25) is Q∗≡0. Therefore, we conclude that the optimal solution of (23) is indeed the rank-one matrix P∗≡p¯p¯⊤ with an optimal solution p¯ of (22).


## 3.2. Multiparametric Programming

Consider the economic dispatch problem in (12). We analyze the dependence of the optimal solutions to the total power demand:(27)pi∗Pdfori=1,2,…,NProposition 4.
Suppose that there existsp∈Δ such that ∑i=1Npi=Pd. Every pi∗(Pd) is monotonically nondecreasing and continuously piecewise affine in Pd≥0 for i=1,2,…,N.Proof.
For the givenPd>0 and the corresponding optimal solution p∗(Pd) of the optimization (12), consider the optimization (17) with p=p∗(Pd) and the associated computation (18). Then, there exists a small enough ϵ>0 such that(28)pi∗Pd+ϵ=piminfori∈Iminp∗Pdpimaxfori∈Imaxp∗Pdpi∗Pd+1/ai∑j∈I~1/ajϵfori∈I~p∗Pdis the optimal solution of the economic dispatch (12) when the power demand is given by Pd+ϵ. In other words, the index sets Imin(p∗(Pd+ϵ)) and Imax(p∗(Pd)) remain the same and the optimal solutions pi∗(Pd) corresponding to the index set I~(p∗(Pd)) change as pi∗(Pd)+1/ai/∑j∈I~1/ajϵ. This shows that optimal solution p∗(Pd) is (elementwise)monotonically nondecreasing andcontinuously piecewise affine in Pd≥0.Now we analyze theexplicit dependence of the optimal power generation profile p∗ on the power demand Pd for which the results from multiparametric programming (MPP) [20] are exploited. We can rewrite the problem of economic dispatch in (12) as the following quadratic programming:(29)V∗Pd≔minimize12p⊤Ap+b⊤p+csubjecttoHp≤r+EPdwhere(30)A=a10⋯00a2⋱⋮⋮⋱⋱00⋯0aN,b=b1b2⋮bN,c=∑i=1NciH=1N×1⊤-1N×1⊤IN×NIN×N,r=00pmax-pmin,E=110N×10N×1with 1N×1 all ones vector in RN, 0N×1 all zeros vector in RN, IN×N identity matrix in RN×N, and pmax(min)=p1max(min)p2max(min)⋯pNmax(min)⊤∈RN. The associated KKT conditions are given by(31)Ap+H⊤w=0stationarity(32)Hp-r-EPd≤0primal  feasibility(33)w≥0dual  feasibility(34)w⊤Hp-r-EPd=0complementaritywhere w∈R(2N+2) is a (vector) Lagrange multiplier corresponding to the inequality in (29). For given Pd with which the optimization in (29) can be solved, the corresponding optimizer p yields the set of active constraints defined as(35)IaPd≜i∈J:Hip=ri+EiPdwhere J=1,2,…,2N+2 and (·)i denotes the ith row of the argument. The rows of the constraints matrices H, r, and E corresponding to the index set Ia(Pd) are extracted to construct the matrices HIa(Pd), rIa(Pd), and EIa(Pd) that would be rewritten in the following compact forms: HIa, rIa, and EIa, respectively, by hiding its dependence of Pd. By definition of Ia(Pd), we have the equality conditions of optimality(36)HIap-rIa-EIaPd=0.Combining the two systems of equations (31) and (36) gives(37)-HIaA-1H⊤w-rIa-EIaPd=0where H⊤w=HIa⊤wIa because the complementarity condition (34) implies wIac=0 for Iac=J∖Ia. Therefore, we obtain an active (vector) Lagrange multiplier(38)w=-HIaA-1HIa⊤-1rIa-HIaA-1HIa⊤-1EIaPdand the corresponding (primal) optimizer(39)p=-A-1HIa⊤wIa=A-1HIa⊤HIaA-1HIa⊤-1EIaPd+A-1HIa⊤HIaA-1HIa⊤-1rIawhere the inverse exists provided that the active constraints are linearly independent. Note that the active Lagrange multiplier and optimizer obtained in (38) and (39), respectively, are affine functions in Pd. The next step is to find or characterize all the points Pd′ in the neighborhood of Pd in which the optimizer p(Pd′) has the same set of active constraints, i.e., Ia(Pd′)=Ia(Pd) so that p(Pd′) is of the same form as (39). Such neighborhood of Pd can be obtained by substituting (39) and (38) into (32) and (33), respectively. Furthermore, it turns out that the neighborhood is a polyhedron(40)Pl≜Pd′∈R+:QlPd′≤qlwhere(41)Ql=HA-1HIa⊤HIaA-1HIa⊤-1EIa-EHIaA-1HIa⊤-1EIa,ql=r-HA-1HIa⊤HIaA-1HIa⊤-1rIa-HIaA-1HIa⊤-1rIaare computed from a given Pd and the associated optimizer p(Pd).Remark 5.
We have shown that the affine dependence of the optimal power generation profiles on the power demand can be explicitly analyzed. This parameterization could be useful when the power demands are not known a priori but forecasted with uncertainty. Analyzing the required power generation profiles over the wide range of power demands offline would help the system operator to schedule the power supply in smaller time-scales.


## 3.3. Uncertain Transmission Loss and Power Demand

In Section3.2, a method of multiparametric programming is suggested for taking care of uncertain power demand Pd. By applying MPP, economic generation dispatch is computed as a function of Pd in (38) and (39). In addition to uncertain power demand Pd, we also need to consider uncertain or variable power loss PL that is parameterized as a quadratic function ∑i=1N∑j=1NpiBijpj. The loss coefficients Bij are not certain but can be assumed to be bounded as(42)Bijmin≤Bij≤Bijmax,fori,j=1,2,…,Nwhere Bijmin and Bijmax refer to the lower and upper bounds of Bij, respectively. For more general representation of uncertain loss coefficient matrix B, we assume that B is not fixed but belongs to a convex polytope that has a finite number of vertices:(43)B∈ConvB0,B1,…,Blwhere Conv· denotes the convex hull of a set. In other words, there exists t0,t1,…,tl∈[0,1] with ∑τ=0ltτ=1 such that B=∑τ=0ltτB(τ). This implies that the quadratic loss function is parameterized as PL(p)=∑τ=0l∑i=1N∑j=1NtkpiBij(τ)pj, where tτ∈[0,1] are not known but uncertain. To take care of uncertain loss coefficients, the three proposed methods need to be modified.Modified SDP Method. The SDP method presented in (23) is modified to take the uncertain loss coefficient matrix B in (43) as follows: (44)minimize12tr⁡AP+b⊤p+csubject  topmin≤p≤pmaxtr⁡BτP-1N⊤p+Pd≤0,forτ=0,1,…,lPpp⊤1⪰0that is indeed robust optimization counterpart of (23).Modified Iterative Primal-Dual Method. The iterative primal-dual method presented in (7) and (11) is modified to take the uncertain loss coefficient matrix B in (43) as follows:(45)pik+1≔BRipNik,μkfori=1,2,…,Nμk+1≔μk+αk+1Pd+PLk+1-∑i=1Npik+1where(46)PLk+1≔max0≤τ≤l∑i=1N∑j∈Nipik+1Bijτpjk+1that is the worst-case line loss for given pi(k+1),i=1,2,…,N.Modified Iterative Linear Projection Method. The iterative primal-dual method presented in (19) is modified to take the uncertain loss coefficient matrix B in (43) as follows: (47)pik+1=piminfori∈Iminpkpimaxfori∈Imaxpk1aiδ~β~+δ~P~d-bifori∈I~pkwhere(48)P~d=Pd+max0≤τ≤l∑i=1N∑j∈NipikBijτpjk-∑i∈Imaxpkpimax-∑i∈Iminpkpimin,and δ~ and β~ are defined the same as (19).


## 4. Case Study

To demonstrate our methods of economic dispatch presented in Sections2 and 3, we consider the 6-generator test case whose generation cost parameters and generation limits are given in Table 1. This system contains six generation units, 26 buses, and 46 transmission lines [10]. The power loss function p⊤Bp is parameterized with a symmetric matrix of loss coefficients that is given by(49)B=10-30.2180.1030.009-0.0100.0020.0270.1030.1810.004-0.0150.0020.0300.0090.0040.417-0.131-0.153-0.107-0.010-0.015-0.1310.2210.0940.0500.0020.002-0.1530.0940.243-0.0000.0270.030-0.1070.050-0.0000.358Three different methods, (a) SDP method (centralized), (b) iterative primal-dual method (distributed), and (c) iterative linear projection method (distributed), are applied to find optimal solutions of economic dispatch with varying power demands. All numerical computations are carried out using MATLAB on a 1.6 GHz Intel Core i5 personal laptop with 8GB 1600 MHz DDR3.Table 1
Problem data for a test case of6 generators.
Generator a i b i c i p i m i n p i m a x i [ $ / M W 2 ] [ $ / M W ] [ $ ] [ M W ] [ M W ] 1 0.00375 2.00 0 50 200 2 0.01750 1.75 0 20 80 3 0.06250 1.00 0 15 50 4 0.00834 3.25 0 10 35 5 0.02500 3.00 0 10 30 6 0.02500 3.00 0 12 40Optimality. The resultant optimal power generation profiles computed by the proposed three optimization algorithms are presented in Figure 5. For power demands varying from 117 [MW] to 435 [MW], we observe that the three different methods give the exactly same results of economic generation dispatch. Generators 1 and 2 have smaller ai with larger upper bounds pimax, so that they become active in the sense that pi∗>pimin when Pd>Pdmin. When Generator 1 with the smallest marginal cost is saturated, i.e., p1∗=p1max, as Pd increases, the slopes corresponding to change rates of Generators 2 and 3 become larger. This is because the value of δ=(∑i=1N1/ai)-1 changes to the larger value (∑i≠1N1/ai)-1. Such changes in slopes occur whenever a generator is saturated in its upper limit. As a matter of fact, such changes in activeness and slopes are explicitly exploited in the iterative linear projection method that significantly reduces computational complexity.Figure 5
Economic dispatch solutions for varying power demands (from117 [MW] to 435 [MW]) obtained by three different methods: (a) SDP method, (b) iterative primal-dual method, and (c) iterative linear projection method.Computational Complexity. In Figure 6, we compare the computation times of the three proposed methods. It shows the histograms of the three different methods to compute the optimal economic dispatch profiles with varying total power demand ranging from 117 [MW] to 435 [MW]. Since the computation times heavily depend on the choice of the initial guesses of the primal and dual variables and the algorithms for solving semidefinite programs, we do not exploit any warm-start strategies for fair comparisons. We observe that the algorithm of iterative linear projection requires a significantly small size of iterations and tremendously fast speed in computations—it is three orders of magnitude faster than the primal-dual iteration method in average. The distributed algorithm based on primal-dual iteration is approximately three times faster than the centralized semidefinite program in average. The SDP method presented in (23) requires a test for positive semidefiniteness of a symmetric matrix whose size is N+1 with N(N+1)/2+N variables at each Newton-KKT iteration step of the interior-point method [21]. Such test has computational complexity O(N2+3N/2(N+1)4)+(N+1)Omin⁡N+12,N2+3N/2 in terms of floating-point operations [22], without exploiting any sparsity structures in problem. The primal-dual iteration method presented in (7) and (11) requires iterative projections that are decomposed into one-dimensional subspaces in primal updates and linear recursive computations in dual updates. Such procedure has computational complexity O(N2). The convergence rate is heavily dependent on the step-size α(k) and we choose α(k)>0 such that ∑α(k)=∞ and ∑(α(k))2<∞. The iterative linear projection method presented in (19) requires computations of multiplication and addition. Its computational complexity is O(N) and more importantly, the projection terminates in less than N steps. This reduces significant amounts of computation time.Figure 6
Comparison of computation times for three different numerical methods: (a) SDP method, (b) iterative primal-dual method, and (c) iterative linear projection method.


## 5. Conclusion

In this paper, we present three different methods of solving problems of economic dispatch with transmission losses. The iterative primal-dual method is indeed based on indirect approach to optimization in which the KKT conditions are solved in a distributed manner. The iterative linear projection method is based on closed-form solutions for the optimality conditions of unconstrained counterparts and the closed-form solutions are iteratively projected on the set corresponding to the capacity limits of generation units. The SDP method is based on the convex relaxation of the associated quadratic-constrained quadratic program whose exactness is shown from the strong duality. The parametric dependence of the power generation profiles is also analyzed with varying power demands in economic dispatch.



---

*Source: 9159851-2019-06-13.xml*