# The Extension of Auxiliary Problem Principle for Solving Dynamic Economic Dispatch Problem in Power Systems

Authors: Yaming Ren
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this paper, we study the convex optimization problem with linear constraint, and the objective function is composed ofm separable convex functions. Considering the special case where the objective function is composed of two separable convex functions, the auxiliary problem principle (APP) is an effective parallel distributed algorithm for solving the special case. Inspired by the principle of APP, a natural idea to solve separable convex optimization problem with m ≥ 3 is to extend the method of APP, resulting in the APP-like algorithm. The convergence of the APP-like algorithm is not clear yet. In this paper, we give a sufficient condition for the convergence of the APP-like algorithm. Specifically, the APP algorithm is a special case of the APP-like algorithm when m = 2. However, simulation results show that the convergence efficiency of the APP-like algorithm is affected by the selection of penalty parameter. Therefore, we propose an improved APP-like algorithm in this paper. Simulation results show that the improved APP-like algorithm is robust to the selection of penalty parameter and that the convergence efficiency of the improved APP-like algorithm is better when compared with the APP-like algorithm.


---

## Body

## 1. Introduction

For the following convex problem with linear constrain,(1)minf1x1+f2x2,s.tA1x1+A2x2=b,x1∈Ω1andx2∈Ω2,,where f1:Rm1⟶R and f2:Rm2⟶R are convex function, x1∈Rm1 and x2∈Rm2 are closed convex sets, A1∈Rr×m1 and A2∈Rr×m2 are the given fixed matrices, and b∈Rr is the given fixed vector.Further analysis of problem (1) shows that the objective function of problem (1) is separable without intersecting variables. Then, a natural idea is whether a splitting algorithm can be adopted to solve problem (1). The alternating direction multiplier method (ADMM) is an effective distributed iteration strategy [1] for solving problem (1) and has been widely used to solve engineering problems [2, 3]. For problem (1), the corresponding ADMM iteration strategy can be expressed as follows [4]:(2)x1k+1=argminf1x1+c2A1x1+A2x2k−b2+−λk,A1x1|x1∈Ω1,x2k+1=argminf2x2+c2A1x1k+1+A2x2−b2+−λk,A2x2|x2∈Ω2λk+1=λk−cA1x1k+1+A2x2k+1−b,,where λ∈Rr represents the Lagrange multiplier, c>0 represents penalty parameter, and ⋅,⋅ denotes the inner product, i.e., x,x=xTx.In this paper, we further consider the general case of problem (1), the objective functions are composed of m separable convex functions (m≥3) with linear constraint.(3)min∑i=1mfixi,s.t∑i=1mAixi=b,xi∈Ωii=1,2,…,mBy comparing problem (1) with problem (3), an intuitive idea is to directly apply ADMM to solve problem (3) resulting in an ADMM-like iteration strategy is shown in the following equation:(4)x1k+1=argminf1x1+c2A1x1+∑j=2mAjxjk−b2+−λk,A1x1|x1∈Ω1,x2k+1=argminf2x2+c2A1x1k+1+A2x2+∑j=3mAjxjk−b2+−λk,A2x2|x2∈Ω2,xik+1=argminfixi+c2∑j=1i−1Ajxjk+1+Aixik+∑j=i+1mAixik−b2+−λk,Aixi|xi∈Ωixmk+1=argminfmxm+c2∑j=1m−1Ajxjk+1+Amxmk−b2+−λk,Amxm|xm∈Ωm,λk+1=λk−c∑j=1mAjxjk+1−b,.For problem (1), the ADMM-like method is the classical ADMM on the condition that m = 2. It is clear that the classical ADMM is convergent [1]. However, we cannot prove the convergence of ADMM-like iteration strategy when m≥3 [5]. To tackle the divergence of ADMM-like method, predictive correction ADMM-like iteration strategies ADM-G (ADM with Gaussian back substitution) [6] and ADBC (alternating direction-based contraction method) [7] are proposed. Specifically, for given wk=x1k,x1k,…,xmk,λk, the prediction results w˜k is generated by ADMM-like method (4) and the correction results wk+1 is generated by wk+1=wk+αw˜k−wk, where α represents the correction step size (The expressions of parameter α are different in ADM-G and ADBC). The introduction of correction step ensures the convergence of the ADMM-like iterative strategy, but the correction step needs to calculate the inverse matrix, which greatly increases the complexity of the iterative strategy.ADM-G and ADBC both belong to the Gaussian Seidel iterative scheme. The Gauss-Seidel iterative scheme can use the latest iteration information in solving each sub-problem to obtain a better convergence rate. At the same time, due to the serial computation form of the Gauss-Seidel iterative scheme, the total time consumption of each iteration in the prediction step is equal to the sum of the time consumption of all sub-problems. According to the above description, the Gauss-Seidel iterative scheme requires a long computing time when the problem scale is large (in other words, when the value ofm is large). Then, the parallel form is recommended when the problem scale is large. The auxiliary problem principle (APP), which was proposed by G. Cohen in 1980 [8], is an effective parallel distributed algorithm [9]. The iteration strategy of the auxiliary problem principle for solving (1) can be expressed as follows:(5)x1k+1=argminf1x1+β2A1x12−βA1x1,A1x1k+−λk+cA1x1k+A2x2k−b,A1x1|x1∈Ω1,x2k+1=argminf2x2+β2A2x22−βA2x2,A2x2k+−λk+cA1x1k+A2x2k−b,A2x2|x2∈Ω2,λk+1=λk−cA1x1k+1+A2x2k+1−b,,where β>2c is a sufficient condition for the convergence of auxiliary problem principle iterative strategy [10], other symbols have the same meaning as (4). Reference [11] further discussed APP and derive its O(1/n) convergence rate . In order to facilitate the analysis of the mathematical properties of the auxiliary problem principle, the equivalent form of the APP is given [11].(6)x1k+1=argminf1x1+β−c2A1x1−A1x1k2+c2A1x1+A2x2k−b2+−λk,A1x1|x1∈Ω1,x2k+1=argminf2x2+β−c2A2x2−A2x2k2+c2A1x1k+A2x2−b2+−λk,A2x2|x2∈Ω2,λk+1=λk−cA1x1k+1+A2x2k+1−b,,Inspired by the principle of APP, a natural idea for solving problem (3) is to extend the APP from problem (1) to problem (3), resulting in an APP-like algorithm as follows:(7)x1k+1=argminf1x1+β−c2A1x1−A1x1k2+c2A1x1+∑j=2mAjxjk−b2+−λk,A1x1|x1∈Ω1,x2k+1=argminf2x2+β−c2A2x2−A2x2k2+c2A1x1k+A2x2+∑j=3mAjxjk−b2+−λk,A2x2|x2∈Ω2,xik+1=argminfixi+β−c2Aixi−Aixik2+c2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2+−λk,Aixi|xi∈Ωixmk+1=argminfmxm+β−c2Amxm−Amxmk2+c2∑j=1m−1Ajxjk+Amxmk−b2+−λk,Amxm|xm∈Ωm,λk+1=λk−c∑j=1mAjxjk+1−b,,The convergence of APP-like algorithm (7) is not clear yet. In this paper, we prove that β>mc is a sufficient condition for the convergence of APP-like algorithm. Specifically, the APP algorithm is a special case of the APP-like algorithm when m = 2. This is the first innovation of this paper.For APP algorithm, the penalty parameterc is a given positive number. For APP-like algorithm, the setting method of the penalty parameter c is same as that in APP algorithm. Simulation results show that the convergence efficiency of APP-like algorithm is affected by the selection of penalty parameter. Therefore, we propose an improved APP-like algorithm in this paper. Compared with APP-like algorithm, the improved APP-like algorithm is robust in terms of the selection of penalty parameter, and the convergence efficiency of the improved APP-like algorithm is better. This is the second innovation of this paper.


## 2. Preliminaries

For a general convex optimization problem is as follows:(8)minfx|x∈Ω,where fx:Rn⟶R is the convex function and Ω is the closed convex set. Assuming x∗ is the optimal solution of the convex optimization problem (8), it can be shown that point x∗ must be in the feasible region, and all feasible directions starting from point x∗ are the ascending directions of the convex optimization problem (8). Supposing we use ∇fx to represent the first derivative of function fx, using Sfx to represent all feasible directions of the function fx at point x, and using Sdx to represent all descending directions of the function fx at point x:(9)Sfx=s∈Rn|s=x′−x,x′∈Ω,(10)Sdx=s∈Rn|sT∇fx<0.According to the definition (9 and 10), it can be known that the sufficient and necessary conditions for x∗ to be the optimal solution of the convex optimization problem (8) can be expressed as follows:(11)x∗∈Ω,Sfx∗∩Sdx∗=∅.According to the above description, it can be known that solving the convex optimization problem (8) is equivalent to solving the following variational inequality problem:(12)x∈Ω,x′−xT∇fx≥0,∀x′∈Ω.It is clear that problem (8) contains no equality constraint condition, and problem (3) contains an equality constraint condition. Problem (3) can be easily transformed into a mathematical form of problem (8) by means of Lagrange function. The symbol λ in (13) represents the Lagrange multiplier. According to the above description, the variational inequality (VI) can be used to express the first-order optimality condition of the optimization problem (3) [12]. Let W:=Ω1×Ω2×⋯×Ωm×Rr, solving (3) is equivalent to solving w∗=x1∗,x2∗,⋯,xm∗,λ∗∈W, which satisfies following inequalities:(13)f1x1−f1x1∗+x1−x1∗−A1Tλ∗≥0,f2x2−f2x2∗+x2−x2∗−A2Tλ∗≥0,fmxm−fmxm∗+xm−xm∗−AmTλ∗≥0λ−λ∗∑i=1mAixi∗−b=0,,∀w∈W,and the compact form of (13) can be written as follows:(14)fx−fx∗+w−w∗Fw∗≥0,where(15)x=x1x2⋮xm,fx=∑i=1mfixi,w=x1x2⋮xmλ,Fw=−A1Tλ−A2Tλ⋮−AmTλ∑i=1mAixi−b,and Fw is monotonic operator.Definition 1.
For the operatorF, if the operator F satisfies(16)Fu−FvTu−v≥0,∀u,v∈Rn.
OperatorF is monotone operator [13].


## 3. Convergence Analysis of the APP-Like Algorithm

Lemma 1.
Let sequencewk is generated by APP-like algorithm (7). If β>mc, then we obtain:(17)limk⟶∞Aixik+1−Aixik=0,limk⟶∞Aixik+1=Aixi∗,i=1,2,⋯,m,(18)limk⟶∞λk+1−λk=0,limk⟶∞λk+1=λ∗.Proof of Lemma 1.
According to the description in section2, solving the sub-problems in (7) is equivalent to solving xik+1, which satisfies(19)f1x1−f1x1k+1+x1−x1k+1T,β−cA1TA1x1k+1−A1x1k+cA1TA1x1k+1+∑j=2mAjxjk−b−AiTλk≥0,∀x1∈Ω1,(20)fixi−fixik+1+xi−xik+1T,β−cAiTAixik+1−Aixik+cAiT∑j=1i−1Ajxjk+Aixik+1+∑j=i+1mAjxjk−b−AiTλk≥0,∀xi∈Ωi�2≤i≤m−1.(21)fmxm−fmxmk+1+xm−xmk+1T,β−cAmTAmxik+1−Amxik+cAmT∑j=1m−1Ajxjk+Amxmk+1−b−AmTλk≥0,∀xm∈Ωm.
Considering(22)λk+1=λk−c∑i=1mAixik+1−b.
Combing (19)–(22), we obtain(23)fx−fxk+1+w−wk+1TFwk+1+Mwk+1−wk≥0,∀w∈W,where(24)M=β−cA1TA1−cA1TA2⋯−cA1TAm0−cA2TA1β−cA2TA2⋯−cA2TAm0⋮⋱⋱⋱⋮−cAmTA1−cAmTA2⋯β−cAmTAm00⋯001cIr.
By settingw=w∗ in (23), we obtain(25)w∗−wk+1TMwk+1−wk≥fxk+1−fx∗+wk+1−w∗TFwk+1.
MappingF is monotone, so we have(26)wk+1−w∗TFwk+1≥wk+1−w∗TFw∗.
By combining (14) and (26), we obtain(27)fxk+1−fx∗+wk+1−w∗TFwk+1≥0.
By combining (25)–(27), we obtain(28)w∗−wk+1TMwk+1−wk≥0⇒w∗−wk+wk−wk+1TMwk+1−wk≥0⇒w∗−wkTMwk+1−wk≥wk−wk+1TMwk−wk+1.
By using (28), we obtain(29)wk−w∗M2−wk+1−w∗M2=wk−w∗M2−wk−w∗−wk−wk+1M2=2w∗−wkTMwk+1−wk−wk−wk+1M2≥2wk−wk+1M2−wk−wk+1M2=wk−wk+1M2.
And (29) can be rewritten as follows:(30)vk−v∗G2−vk+1−v∗G2≥vk−vk+1G2,where(31)v=A1x1A2x2⋮Amxmλ,G=β−c−c⋯−c0−cβ−c⋯−c0⋮⋱⋱⋱⋮−c−c⋯β−c00⋯001cIr.
Considering(32)vk−vk+1G2=∑i=1m∑j=i+1mAixik−Aixik+1−Ajxjk−Ajxjk+1cIr2+∑i=1mβ−mcAixik−Aixik+1Ir2+λk+1−λk1cIr2≥0.For (32), it is clear that if β>mc, vk−vk+1G2=0 is true only and only if vk=vk+1. Therefore, we can say that matrix G is a symmetric positive matrix when β>mc and (30) is Fejér monotone [14]. Then, we can obtain(33)limk⟶∞Aixik+1−Aixik=0,limk⟶∞Aixik+1=Aixi∗,i=1,2,⋯,m,(34)limk⟶∞λk+1−λk=0�limk⟶∞λk+1=λ∗.
Based on above discussion, the proof of Lemma 1 is completed.
According to the description of Lemma1, it is clear that if all Ai�i=1,2,⋯,m are full column rank matrices, then we can obtain limk⟶∞xik+1=xi∗ and limk⟶∞λk+1=λ∗. In other words, the sequence wk generated by APP-like algorithm (7) approximates the optimal solution of problem (3) on the premise that all Ai�i=1,2,⋯,m are full column rank matrices and β>mc. However, in solving practical problems, we cannot guarantee that all Ai�i=1,2,⋯,m are full column rank matrices. For the general matrix Ai�i=1,2,⋯,m, Lemma 2 is given.Lemma 2.
Let sequencewk is generated by APP-like algorithm (7). If problem (3) is convex, continuous, differentiable, and satisfies the following equation:(35)limk⟶∞Aixik+1−Aixik=0,limk⟶∞λk+1−λk=limk⟶∞c∑i=1mAixik+1−b=0,
then, the sequencewk converges to the optimal solution w∗ of problem (3).Proof of Lemma 2.
For convex optimization problem, according to the Karloch-Kuhn-Tucker condition (KKT condition), it is very convenient to determine whether the current iteration point is the optimal solution of the convex optimization problem. For problem (3), if the current iteration point w∈W satisfies the following equality constraints:(36)∇fixi−AiTλ=0,i=1,2,⋯,m,(37)∑i=1mAixi−b=0�xi⊂Ωi,then the current iteration point w is the optimal solution of the optimization problem (3).
The sequencewk is generated by APP-like algorithm (7). It is clear that x1k+1⊂Ω1 satisfy the following equality:(38)∇f1x1k+1+β−cA1TA1x1k+1−A1x1k+cA1TAixik+1+∑j=2mAjxjk−b−A1Tλk=0⇒∇f1x1k+1−A1Tλk+1+β−cA1TA1x1k+1−A1x1k+cA1TAixik+1+∑j=2mAjxjk−b−A1Tλk−λk+1=0⇒∇f1x1k+1−A1Tλk+1=A1Tλk−λk+1−β−cA1TA1x1k+1−A1x1k−cA1TAixik+1+∑j=2mAjxjk−b=cA1T∑j=1mAjxjk+1−b−β−cA1TA1x1k+1−A1x1k−cA1T∑j=1mAjxjk+1−b+∑j=2mAjxjk−Ajxjk+1=−β−cA1TA1x1k+1−A1x1k−cA1T∑j=2mAjxjk−Ajxjk+1.
Similarly, we can obtain(39)∇fixik+1−AiTλk+1=−β−cAiTAixik+1−Aixik−cAiT∑j=1i−1Ajxjk−Ajxjk+1+∑j=i+1mAjxjk−Ajxjk+1�xi⊂Ωi�2≤i≤m−1,and(40)∇fmxmk+1−AmTλk+1=−β−cAmTAmxmk+1−Amxmk−cAmT∑j=1m−1Ajxjk−Ajxjk+1�xm⊂Ωm.
According to the description of Lemma1, it is clear that,(41)limk⟶∞Axik+1−Axik=0,limk⟶∞λk+1−λk=limk⟶∞c∑i=1mAixik+1−b=0.
By combining (38)–(41), we can obtain(42)limk⟶∞∇fixik+1−AiTλk+1=0,i=1,2,⋯,m,(43)limk⟶∞∑i=1mAixik+1−b=0�xi⊂Ωi.
Therefore, we can say that sequencewk generated by APP-like algorithm (7) converges to the optimal solution w∗ of problem (3) when problem (3) is convex, continuous, differentiable, and satisfies (35).
Therefore, the proof of Lemma 2 is completed.


## 4. The Improved APP-Like Algorithm and Convergence Analysis

In Section3, we prove the convergence of the proposed APP-like algorithm. In this section, we will discuss the parameter selection of the proposed APP-like algorithm and give the improved APP-like algorithm. In addition, we will prove the convergence of the improved APP-like algorithm.


### 4.1. The Improved APP-Like Algorithm

For the proposed APP-like algorithm, the objective function containsc/2A1x1+∑j=2mAjxjk−b2, we can say that c/2A1x1+∑j=2mAjxjk−b2 represents the penalty function for the equality constraint ∑i=1mAixi=b of the original optimization problem. The concept of penalty functions reminds us of the concept of exterior penalty function. To be specific, the solution of the exterior penalty function tends to be optimal solution as the penalty parameter tends to infinity. However, when the penalty parameter tends to infinity, it is easy to cause the ill of exterior penalty functions. Fortunately, for the proposed APP-like algorithm, the objective function contains not only the penalty function but also the Lagrange function. This method of combining the punishment function and the Lagrange function is called augmented Lagrange function method, and the obvious advantage is that the penalty parameter tends to infinity is not required as the convergence condition of the proposed APP-like algorithm.According to the description of (30), the sequence vk generated by the proposed APP-like algorithm gradually approaches the optimal solution and the penalty functions c/2A1x1+∑j=2mAjxjk−b2 gradually approach zero, which means the convergence efficiency of the proposed APP-like algorithm becomes progressively worse when the current iteration point approximates the optimal solution. Inspired by the method of exterior penalty function, we propose the iterative strategy of penalty parameter as follows:(44)ck+1=2∗ck,k<kstop,ck,k≥kstop,,where kstop is an integer greater than one. According to the description of (44) and considering the initial penalty parameter c0>0, it can be known that the sequence ck has upper and lower bounds, which means the iterative strategy of penalty parameter will not cause the ill-conditioned Hessian matrix of objective function.For APP-like algorithm withm ≥ 3, the objective function contains β−c/2Aixi−Aixik2 and the parameter β is set to be β>mc in order to ensure the convergence of APP-like algorithm. Based on the above discussion, we can give the improved the APP-like algorithm as follows:(45)x1k+1=argminf1x1+βk−ck2A1x1−A1x1k2+ck2A1x1+∑j=2mAjxjk−b2+−λk,A1x1|x1∈Ω1,x2k+1=argminf2x2+βk−ck2A2x2−A2x2k2+ck2A1x1k+A2x2+∑j=3mAjxjk−b2+−λk,A2x2|x2∈Ω2,xik+1=argminfixi+βk−ck2Aixi−Aixik2+ck2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2+−λk,Aixi|xi∈Ωi,xmk+1=argminfmxm+βk−ck2Amxm−Amxmk2+ck2∑j=1m−1Ajxjk+Amxmk−b2+−λk,Amxm|xm∈Ωm,λk+1=λk−ck∑j=1mAjxjk+1−b,ck+1=2∗ck,k<kstop,ck+1=ck,k≥kstop,βk+1=m+δck+1,δ>0..


### 4.2. Convergence Analysis of the Improved APP-Like Algorithm

Lemma 3.
Let sequencewk is generated by improved APP-like algorithm (45). If problem (3) is convex, continuous, and differentiable, then sequence wk converges to the optimal solution w∗ of problem (3).Proof.
of Lemma 3.
For givenwk, wk+1 is generated by the improved APP-like algorithm. Based on the description of the improved APP-like algorithm, it is clear that ck=c0×2kstop and βk=ck×2kstopm+δ when k≥kstop. According to the proof of Lemma1, if k≥kstop, then we can get(46)vk−v∗M2−vk+1−v∗M2≥vk−vk+1M2,where(47)v=A1x1A2x2⋮Amxmλ,M=βk−ck−ck⋯−ck0−ckβk−ck⋯−ck0⋮⋱⋱⋱⋮−ck−ck⋯βk−ck00⋯001ckIr,ck=c0×2kstop,βk=c0×2kstopm+δ.
Ifk≥kstop, the matrix M is a fixed symmetric positive definite matrix. Similar to the analysis of (30), we can obtain (46) Fejér monotone. Then, we can obtain(48)limk⟶∞Aixik+1−Aixik=0,limk⟶∞Aixik+1=Aixi∗,i=1,2,⋯,m,(49)limk⟶∞λk+1−λk=0�limk⟶∞λk+1=λ∗.
Based on the description of Lemma2, it is clear that sequence wk converges to the optimal solution w∗ of problem (3) if it is convex, continuous, and differentiable.
Therefore, the proof of Lemma 3 is completed.


## 4.1. The Improved APP-Like Algorithm

For the proposed APP-like algorithm, the objective function containsc/2A1x1+∑j=2mAjxjk−b2, we can say that c/2A1x1+∑j=2mAjxjk−b2 represents the penalty function for the equality constraint ∑i=1mAixi=b of the original optimization problem. The concept of penalty functions reminds us of the concept of exterior penalty function. To be specific, the solution of the exterior penalty function tends to be optimal solution as the penalty parameter tends to infinity. However, when the penalty parameter tends to infinity, it is easy to cause the ill of exterior penalty functions. Fortunately, for the proposed APP-like algorithm, the objective function contains not only the penalty function but also the Lagrange function. This method of combining the punishment function and the Lagrange function is called augmented Lagrange function method, and the obvious advantage is that the penalty parameter tends to infinity is not required as the convergence condition of the proposed APP-like algorithm.According to the description of (30), the sequence vk generated by the proposed APP-like algorithm gradually approaches the optimal solution and the penalty functions c/2A1x1+∑j=2mAjxjk−b2 gradually approach zero, which means the convergence efficiency of the proposed APP-like algorithm becomes progressively worse when the current iteration point approximates the optimal solution. Inspired by the method of exterior penalty function, we propose the iterative strategy of penalty parameter as follows:(44)ck+1=2∗ck,k<kstop,ck,k≥kstop,,where kstop is an integer greater than one. According to the description of (44) and considering the initial penalty parameter c0>0, it can be known that the sequence ck has upper and lower bounds, which means the iterative strategy of penalty parameter will not cause the ill-conditioned Hessian matrix of objective function.For APP-like algorithm withm ≥ 3, the objective function contains β−c/2Aixi−Aixik2 and the parameter β is set to be β>mc in order to ensure the convergence of APP-like algorithm. Based on the above discussion, we can give the improved the APP-like algorithm as follows:(45)x1k+1=argminf1x1+βk−ck2A1x1−A1x1k2+ck2A1x1+∑j=2mAjxjk−b2+−λk,A1x1|x1∈Ω1,x2k+1=argminf2x2+βk−ck2A2x2−A2x2k2+ck2A1x1k+A2x2+∑j=3mAjxjk−b2+−λk,A2x2|x2∈Ω2,xik+1=argminfixi+βk−ck2Aixi−Aixik2+ck2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2+−λk,Aixi|xi∈Ωi,xmk+1=argminfmxm+βk−ck2Amxm−Amxmk2+ck2∑j=1m−1Ajxjk+Amxmk−b2+−λk,Amxm|xm∈Ωm,λk+1=λk−ck∑j=1mAjxjk+1−b,ck+1=2∗ck,k<kstop,ck+1=ck,k≥kstop,βk+1=m+δck+1,δ>0..


## 4.2. Convergence Analysis of the Improved APP-Like Algorithm

Lemma 3.
Let sequencewk is generated by improved APP-like algorithm (45). If problem (3) is convex, continuous, and differentiable, then sequence wk converges to the optimal solution w∗ of problem (3).Proof.
of Lemma 3.
For givenwk, wk+1 is generated by the improved APP-like algorithm. Based on the description of the improved APP-like algorithm, it is clear that ck=c0×2kstop and βk=ck×2kstopm+δ when k≥kstop. According to the proof of Lemma1, if k≥kstop, then we can get(46)vk−v∗M2−vk+1−v∗M2≥vk−vk+1M2,where(47)v=A1x1A2x2⋮Amxmλ,M=βk−ck−ck⋯−ck0−ckβk−ck⋯−ck0⋮⋱⋱⋱⋮−ck−ck⋯βk−ck00⋯001ckIr,ck=c0×2kstop,βk=c0×2kstopm+δ.
Ifk≥kstop, the matrix M is a fixed symmetric positive definite matrix. Similar to the analysis of (30), we can obtain (46) Fejér monotone. Then, we can obtain(48)limk⟶∞Aixik+1−Aixik=0,limk⟶∞Aixik+1=Aixi∗,i=1,2,⋯,m,(49)limk⟶∞λk+1−λk=0�limk⟶∞λk+1=λ∗.
Based on the description of Lemma2, it is clear that sequence wk converges to the optimal solution w∗ of problem (3) if it is convex, continuous, and differentiable.
Therefore, the proof of Lemma 3 is completed.


## 5. Application

In this section, we firstly give the mathematical model of the power system dynamic economic dispatching problem (DEDP) and point out that the mathematical model for DEDP can be easily transformed into the multiseparable convex problem with linear constraints studied in this paper. After that, we use the proposed APP-like algorithm and improved APP-like algorithm to solve DEDP and analyze the corresponding simulation results. We coded by the MATLAB 2018b, and all codes were implemented on Dell T5820 Server with Xeon- W-2102 CPU at 2.9 GHz and 16G of memory.


### 5.1. The Mathematical Model of the Dynamic Economic Dispatching Problem for Power System

The mathematical model of dynamic economic dispatching problem for power system can be expressed as follows:(50)minF=∑h=1H∑i=1NfPi,h=∑h=1H∑i=1NaiPi,h2+biPi,h+ci,s.t∑i=1NPi,h=PD,h,h=1,2,⋯,H,Pi,min≤Pi,h≤Pi,max,h=1,2,⋯,H,Pi,h−Pi,h−1≤rui,h=2,⋯,H,Pi,h−1−Pi,h≤rdi,h=2,⋯,H,,where F represents the objective function, N represents the total number of power generation unit, H represents the total dispatching period of power generation unit, Pi,h represents the output of the ith power generation unit in the hth dispatching period, ai, bi, and ci are given parameters in objective function, PD,h represents the system load in the hth dispatching period, and rui and rdi are the upper and lower ramp rate limits for the ith generation unit and are given.For problem (50), the equivalent mathematical model can be rewritten as follows:(51)min∑i=1HFixi,s.t∑i=1NAixi=b,xi∈Ωii=1,2,⋯,N,,where(52)Ai=IN×N,(53)b=PD,1,PD,h,⋯,PD,HT,(54)xi=Pi,1,Pi,2,⋯,Pi,HT,i=1,2,⋯,N,(55)Ωi=xi|Pi,min≤Pi,h≤Pi,max,h=1,2,⋯,H;Pi,h−Pi,h−1≤rui,Pi,h−1−Pi,h≤rdi,h=2,⋯,H,(56)Fixi=∑h=1HaiPi,h2+biPi,h+ci.It is clear thatAi in (52) is full column rank matrices. Therefore, we can directly use the APP-like algorithm and improved APP-like algorithm to solve problem (51) in the form of distributed parallel.


### 5.2. Test System

In this section, a test system [15] containing ten generation units is presented to verify the validity and correctness of the proposed algorithms. The data refer to generation units are shown in Table 1. In addition, the demand of the ten-unit test system was divided into 24 intervals in reference [15]. Reference [16] employs the demand data in 1–8 intervals as the data refer to system demand. In this paper, we also employ the demand data in 1–8 intervals as in reference [16] and the data refer to system demand are shown in Table 2. For the test system, according to the description in Section 5.1, the original optimization problem can be decomposed into ten sub-optimization problems. The information shown in Table 1 shows that the output upper and lower limits, for the 10th generation unit, are both 55. Therefore, in the actual simulation process, we can directly set the output of the 10th generation unit to be 55, and only solve nine sub-optimization problems.Table 1
The data refer to generation units [15].
UnitP max (MW)P min (MW)a ($/MW2h)b ($/MWh)c ($/h)Ur (MW/hour)Dr (MW/hour)14701500.0004321.6958.2808024601350.0006321.051313.680803340730.0003920.81604.0780804300600.000723.9471.650505243730.0007921.620480.2950506160570.0005617.87601.7550507130200.0021116.51502.730308120470.004823.23639.43030980200.1090819.58455.630301055550.0095122.54692.43030Table 2
The data refer to system demand [16].
Period12345678Load (MW)10361110125814061480162817021776


### 5.3. Simulation Analysis

#### 5.3.1. APP-Like Algorithm for Solving Test System

In this section, we use APP-like algorithm to solve the test system and observe the influence of parameter on the convergence efficiency of APP-like algorithm. We set the maximum number of iterations as 50. For the iterative strategy of penalty parameter shown in (44), we set kstop=30 and δ=0.1. The convergence condition is set to maxwk+1−wk<0.0001. If the convergence condition is not satisfied when the number of iterations is greater than 50, then we can say that the corresponding algorithm fail to convergence with maximum iterations.The simulation results based on the APP-like algorithm for the test system are shown in Table3. In order to verify the influence of different penalty parameter settings on the convergence efficiency of the APP-like algorithm, we designed five different penalty parameter settings named Case1–Case5, respectively, which are shown in the first column in Table 3. After that, the second column represents the initial parameter setting of the APP-like algorithm, the third column represents the number of iterations when convergence conditions are met, and the fourth column represents the value of maxwk+1−wk when convergence conditions is met or the number of iterations reaches the maximum iterations. In addition, the word “Fail” in Table 3 represents the corresponding algorithm fail to convergence with maximum iterations. The curve of maxwk+1−wk changing with the number of iterations is shown in Figure 1.Table 3
The simulation results based on APP-like algorithm for test system.
CaseParameterIterationmaxwk+1−wkCase1c = 1, β = 9.1cFail0.3987Case2c = 10, β = 9.1cFail0.0589Case3c = 100, β = 9.1cFail0.0061Case4c = 1000, β = 9.1cFail6.1481 × 10−4Case5c = 10000, β = 9.1c226.2349 × 10−5Figure 1
The curve ofmaxabswk+1−wk based on the APP-like algorithm.According to the data in Table3 and the curve in Figure 1, it can be known that the APP-like algorithm meets the convergence condition only under case5. By comparison, the APP-like algorithm fails to converge or stops convergence prematurely under case1-case4. For the further analysis of Figure 1 and Table 3, we find that the value of maxwk+1−wk gradually approaches the convergence condition with the increase of the penalty parameter. Let's recall the iterative formula (7) of APP-like algorithm. Taking the ith sub-optimization problem as an example, there are two terms (β−c/2Aixi−Aixik2 and c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2) related to the penalty parameter in the objective function. c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 represents the punishment for the equality constraint. For case1-case4 in Table 3 and Figure 2, at the initial stage of iteration, it is obvious that maxwk+1−wk is large, so c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 can play a good punishment role. However, as maxwk+1−wk approaches zero gradually, the penalty effect of c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 decreases gradually when the penalty parameter is set smaller. This explains the reason why case1-case4 in Table 3 and Figure 2 fail to convergence.Figure 2
The curve ofmaxabswk+1−wk based on improved APP-like algorithm.The existence ofβ−c/2Aixi−Aixik2 is to ensure the convergence of the APP-like algorithm. However, we must realize that the existence of β−c/2Aixi−Aixik2 also prevents the update of the current iteration point. Therefore, we expect β−c/2Aixi−Aixik2 to be as small as possible under the premise of ensuring the convergence of the APP-like algorithm. In fact, for the APP-like algorithm, the value of penalty parameters and β/c is given. That is to say that the APP-like algorithm ignores the role of β−c/2Aixi−Aixik2 in the iterative process on the premise of ensuring algorithm convergence.


#### 5.3.2. Improved APP-Like Algorithm for Solving Test System

In this section, we use improved APP-like algorithm to solve the test system and observe the influence of parameter on convergence efficiency of improved APP-like algorithm. In order to comparison with the results of APP algorithm, the initial parameter settings of improved APP-like algorithm are the same as those of the APP algorithm. The simulation results based on improved APP-like algorithm for the test system are shown in Table4. The columns in Table 4 have the same meaning as the columns in Table 3. The curve of maxwk+1−wk based on improved APP-like algorithm changing with iterations is shown in Figure 2.Table 4
The simulation results based on improved APP-like algorithm for test system.
CaseParameterIterationmaxwk+1−wkCase1c0 = 1, βk = 9.1ck146.2929 × 10−5Case2c0 = 10, βk = 9.1ck145.8110 × 10−5Case3c0 = 100, βk = 9.1ck179.0122 × 10−5Case4c0 = 1000, βk = 9.1ck208.0008 × 10−5Case5c0 = 10000, βk = 9.1ck208.0579 × 10−5According to the information shown in Table4 and Figure 2, we must admit that the trends of these curves of maxwk+1−wk are not entirely consistent. However, the curves of maxwk+1−wk with different initial penalty parameter values maintain similar trends, and can quickly meet convergence condition. That is to say, for improved APP-like algorithm, the selection of penalty parameters is robust to a certain extent.The difference between APP-like algorithm and improved APP-like algorithm lies in the updating of penalty parameters. For APP-like algorithm, the penalty parameter is given in advance and remains unchanged in the iterative process. For improved APP-like algorithm, the initial value of penalty parameters is given, but it is updated (The iterative strategy of penalty parameter can be found in (44)) in the iterative process.According to the analysis of APP-like algorithm in section5.3.1, it can be found that APP-like algorithm has achieved better convergence effect by setting a larger penalty parameter value to ensure that c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 plays an effective punishment role. Comparatively speaking, improved APP-like algorithm has achieved better convergence effect by updating the penalty parameter to ensure that c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 plays an effective punishment role. Both methods can achieve better convergence characteristics, and we cannot say which algorithm is better.Let's turn our attention toβ−c/2Aixi−Aixik2. APP-like algorithm ignores the role of β−c/2Aixi−Aixik2 because the parameters β and c are given in advance. In fact, we expect β−c/2Aixi−Aixik2 to be as small as possible under the premise of ensuring the convergence of the algorithm.According to the information shown in Table4 and Figure 2, obviously, the smaller the initial value of penalty parameter is set, the better the convergence characteristic of improved APP-like algorithm will be. According to the description of iteration strategy (44) for penalty parameters, it can be known that penalty parameter has upper and lower bounds in the iterative process. For the improved APP-like algorithm, if we give a small initial value of the penalty parameter, the value of βk−ck/2Aixi−Aixik2 will be smaller throughout the iteration. This is why, in Figure 2, the smaller the initial value of penalty parameter is, the better the convergence efficiency is.In the above part, we analyze the influence of penalty parameter on the convergence efficiency of the improved APP-like algorithm. If we further analyzeβk−ck/2Aixi−Aixik2, we will find that the value of βk−ck/2Aixi−Aixik2 is related not only to the punishment parameter but also to the parameter βk. The simulation results based on APP-like algorithm for the test system with different βk/ck are shown in Table 5. The corresponding curve of maxwk+1−wk is shown in Figure 3. According to the information shown in Table 5 and Figure 3, it is clear that, for the same initialization penalty parameter, the smaller βk/ck is, the better the convergence efficiency of APPP algorithm is under the premise of ensuring the convergence of improved APP-like algorithm. The simulation results shown in Table 5 and Figure 3 are in agreement with our theoretical analysis of βk−ck/2Aixi−Aixik2.Table 5
The simulation results based on improved APP-like algorithm with differentβ.
CaseParameterIterationmaxwk+1−wkCase1c0 = 10, βk = 9.1ck146.2929 × 10−5Case2c0 = 100, βk = 20ck268.9700 × 10−5Case3c0 = 1000, βk = 30ckFail1.6000 × 10−3Case4c0 = 1, βk = 40ckFail7.0000 × 10−2Figure 3
The curve of max (abs(wk+1-wk)) based on improved APP-like algorithm with different β.According to the theoretical analysis in Section4 and the simulation results in Section 5, we suggest using the improved APP-like algorithm. Compared with the APP-like algorithm, the penalty parameter selection of improved APP-like algorithm is robust and the convergence efficiency of improved APP-like algorithm is better. Our suggestions for the initial parameters of improved APP-like algorithm are shown as follows:(1)
It is better to select a smaller initial value of the penalty parameter, and 1 or less is suggested as the initial value of the penalty parameter.(2)
On the premise of ensuring convergence, it is recommended to select parameterβk as small as possible, and βk=m+0.1ck is suggested, where m presents the objective functions, which is composed of m separable convex functions.


## 5.1. The Mathematical Model of the Dynamic Economic Dispatching Problem for Power System

The mathematical model of dynamic economic dispatching problem for power system can be expressed as follows:(50)minF=∑h=1H∑i=1NfPi,h=∑h=1H∑i=1NaiPi,h2+biPi,h+ci,s.t∑i=1NPi,h=PD,h,h=1,2,⋯,H,Pi,min≤Pi,h≤Pi,max,h=1,2,⋯,H,Pi,h−Pi,h−1≤rui,h=2,⋯,H,Pi,h−1−Pi,h≤rdi,h=2,⋯,H,,where F represents the objective function, N represents the total number of power generation unit, H represents the total dispatching period of power generation unit, Pi,h represents the output of the ith power generation unit in the hth dispatching period, ai, bi, and ci are given parameters in objective function, PD,h represents the system load in the hth dispatching period, and rui and rdi are the upper and lower ramp rate limits for the ith generation unit and are given.For problem (50), the equivalent mathematical model can be rewritten as follows:(51)min∑i=1HFixi,s.t∑i=1NAixi=b,xi∈Ωii=1,2,⋯,N,,where(52)Ai=IN×N,(53)b=PD,1,PD,h,⋯,PD,HT,(54)xi=Pi,1,Pi,2,⋯,Pi,HT,i=1,2,⋯,N,(55)Ωi=xi|Pi,min≤Pi,h≤Pi,max,h=1,2,⋯,H;Pi,h−Pi,h−1≤rui,Pi,h−1−Pi,h≤rdi,h=2,⋯,H,(56)Fixi=∑h=1HaiPi,h2+biPi,h+ci.It is clear thatAi in (52) is full column rank matrices. Therefore, we can directly use the APP-like algorithm and improved APP-like algorithm to solve problem (51) in the form of distributed parallel.


## 5.2. Test System

In this section, a test system [15] containing ten generation units is presented to verify the validity and correctness of the proposed algorithms. The data refer to generation units are shown in Table 1. In addition, the demand of the ten-unit test system was divided into 24 intervals in reference [15]. Reference [16] employs the demand data in 1–8 intervals as the data refer to system demand. In this paper, we also employ the demand data in 1–8 intervals as in reference [16] and the data refer to system demand are shown in Table 2. For the test system, according to the description in Section 5.1, the original optimization problem can be decomposed into ten sub-optimization problems. The information shown in Table 1 shows that the output upper and lower limits, for the 10th generation unit, are both 55. Therefore, in the actual simulation process, we can directly set the output of the 10th generation unit to be 55, and only solve nine sub-optimization problems.Table 1
The data refer to generation units [15].
UnitP max (MW)P min (MW)a ($/MW2h)b ($/MWh)c ($/h)Ur (MW/hour)Dr (MW/hour)14701500.0004321.6958.2808024601350.0006321.051313.680803340730.0003920.81604.0780804300600.000723.9471.650505243730.0007921.620480.2950506160570.0005617.87601.7550507130200.0021116.51502.730308120470.004823.23639.43030980200.1090819.58455.630301055550.0095122.54692.43030Table 2
The data refer to system demand [16].
Period12345678Load (MW)10361110125814061480162817021776


## 5.3. Simulation Analysis

### 5.3.1. APP-Like Algorithm for Solving Test System

In this section, we use APP-like algorithm to solve the test system and observe the influence of parameter on the convergence efficiency of APP-like algorithm. We set the maximum number of iterations as 50. For the iterative strategy of penalty parameter shown in (44), we set kstop=30 and δ=0.1. The convergence condition is set to maxwk+1−wk<0.0001. If the convergence condition is not satisfied when the number of iterations is greater than 50, then we can say that the corresponding algorithm fail to convergence with maximum iterations.The simulation results based on the APP-like algorithm for the test system are shown in Table3. In order to verify the influence of different penalty parameter settings on the convergence efficiency of the APP-like algorithm, we designed five different penalty parameter settings named Case1–Case5, respectively, which are shown in the first column in Table 3. After that, the second column represents the initial parameter setting of the APP-like algorithm, the third column represents the number of iterations when convergence conditions are met, and the fourth column represents the value of maxwk+1−wk when convergence conditions is met or the number of iterations reaches the maximum iterations. In addition, the word “Fail” in Table 3 represents the corresponding algorithm fail to convergence with maximum iterations. The curve of maxwk+1−wk changing with the number of iterations is shown in Figure 1.Table 3
The simulation results based on APP-like algorithm for test system.
CaseParameterIterationmaxwk+1−wkCase1c = 1, β = 9.1cFail0.3987Case2c = 10, β = 9.1cFail0.0589Case3c = 100, β = 9.1cFail0.0061Case4c = 1000, β = 9.1cFail6.1481 × 10−4Case5c = 10000, β = 9.1c226.2349 × 10−5Figure 1
The curve ofmaxabswk+1−wk based on the APP-like algorithm.According to the data in Table3 and the curve in Figure 1, it can be known that the APP-like algorithm meets the convergence condition only under case5. By comparison, the APP-like algorithm fails to converge or stops convergence prematurely under case1-case4. For the further analysis of Figure 1 and Table 3, we find that the value of maxwk+1−wk gradually approaches the convergence condition with the increase of the penalty parameter. Let's recall the iterative formula (7) of APP-like algorithm. Taking the ith sub-optimization problem as an example, there are two terms (β−c/2Aixi−Aixik2 and c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2) related to the penalty parameter in the objective function. c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 represents the punishment for the equality constraint. For case1-case4 in Table 3 and Figure 2, at the initial stage of iteration, it is obvious that maxwk+1−wk is large, so c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 can play a good punishment role. However, as maxwk+1−wk approaches zero gradually, the penalty effect of c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 decreases gradually when the penalty parameter is set smaller. This explains the reason why case1-case4 in Table 3 and Figure 2 fail to convergence.Figure 2
The curve ofmaxabswk+1−wk based on improved APP-like algorithm.The existence ofβ−c/2Aixi−Aixik2 is to ensure the convergence of the APP-like algorithm. However, we must realize that the existence of β−c/2Aixi−Aixik2 also prevents the update of the current iteration point. Therefore, we expect β−c/2Aixi−Aixik2 to be as small as possible under the premise of ensuring the convergence of the APP-like algorithm. In fact, for the APP-like algorithm, the value of penalty parameters and β/c is given. That is to say that the APP-like algorithm ignores the role of β−c/2Aixi−Aixik2 in the iterative process on the premise of ensuring algorithm convergence.


### 5.3.2. Improved APP-Like Algorithm for Solving Test System

In this section, we use improved APP-like algorithm to solve the test system and observe the influence of parameter on convergence efficiency of improved APP-like algorithm. In order to comparison with the results of APP algorithm, the initial parameter settings of improved APP-like algorithm are the same as those of the APP algorithm. The simulation results based on improved APP-like algorithm for the test system are shown in Table4. The columns in Table 4 have the same meaning as the columns in Table 3. The curve of maxwk+1−wk based on improved APP-like algorithm changing with iterations is shown in Figure 2.Table 4
The simulation results based on improved APP-like algorithm for test system.
CaseParameterIterationmaxwk+1−wkCase1c0 = 1, βk = 9.1ck146.2929 × 10−5Case2c0 = 10, βk = 9.1ck145.8110 × 10−5Case3c0 = 100, βk = 9.1ck179.0122 × 10−5Case4c0 = 1000, βk = 9.1ck208.0008 × 10−5Case5c0 = 10000, βk = 9.1ck208.0579 × 10−5According to the information shown in Table4 and Figure 2, we must admit that the trends of these curves of maxwk+1−wk are not entirely consistent. However, the curves of maxwk+1−wk with different initial penalty parameter values maintain similar trends, and can quickly meet convergence condition. That is to say, for improved APP-like algorithm, the selection of penalty parameters is robust to a certain extent.The difference between APP-like algorithm and improved APP-like algorithm lies in the updating of penalty parameters. For APP-like algorithm, the penalty parameter is given in advance and remains unchanged in the iterative process. For improved APP-like algorithm, the initial value of penalty parameters is given, but it is updated (The iterative strategy of penalty parameter can be found in (44)) in the iterative process.According to the analysis of APP-like algorithm in section5.3.1, it can be found that APP-like algorithm has achieved better convergence effect by setting a larger penalty parameter value to ensure that c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 plays an effective punishment role. Comparatively speaking, improved APP-like algorithm has achieved better convergence effect by updating the penalty parameter to ensure that c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 plays an effective punishment role. Both methods can achieve better convergence characteristics, and we cannot say which algorithm is better.Let's turn our attention toβ−c/2Aixi−Aixik2. APP-like algorithm ignores the role of β−c/2Aixi−Aixik2 because the parameters β and c are given in advance. In fact, we expect β−c/2Aixi−Aixik2 to be as small as possible under the premise of ensuring the convergence of the algorithm.According to the information shown in Table4 and Figure 2, obviously, the smaller the initial value of penalty parameter is set, the better the convergence characteristic of improved APP-like algorithm will be. According to the description of iteration strategy (44) for penalty parameters, it can be known that penalty parameter has upper and lower bounds in the iterative process. For the improved APP-like algorithm, if we give a small initial value of the penalty parameter, the value of βk−ck/2Aixi−Aixik2 will be smaller throughout the iteration. This is why, in Figure 2, the smaller the initial value of penalty parameter is, the better the convergence efficiency is.In the above part, we analyze the influence of penalty parameter on the convergence efficiency of the improved APP-like algorithm. If we further analyzeβk−ck/2Aixi−Aixik2, we will find that the value of βk−ck/2Aixi−Aixik2 is related not only to the punishment parameter but also to the parameter βk. The simulation results based on APP-like algorithm for the test system with different βk/ck are shown in Table 5. The corresponding curve of maxwk+1−wk is shown in Figure 3. According to the information shown in Table 5 and Figure 3, it is clear that, for the same initialization penalty parameter, the smaller βk/ck is, the better the convergence efficiency of APPP algorithm is under the premise of ensuring the convergence of improved APP-like algorithm. The simulation results shown in Table 5 and Figure 3 are in agreement with our theoretical analysis of βk−ck/2Aixi−Aixik2.Table 5
The simulation results based on improved APP-like algorithm with differentβ.
CaseParameterIterationmaxwk+1−wkCase1c0 = 10, βk = 9.1ck146.2929 × 10−5Case2c0 = 100, βk = 20ck268.9700 × 10−5Case3c0 = 1000, βk = 30ckFail1.6000 × 10−3Case4c0 = 1, βk = 40ckFail7.0000 × 10−2Figure 3
The curve of max (abs(wk+1-wk)) based on improved APP-like algorithm with different β.According to the theoretical analysis in Section4 and the simulation results in Section 5, we suggest using the improved APP-like algorithm. Compared with the APP-like algorithm, the penalty parameter selection of improved APP-like algorithm is robust and the convergence efficiency of improved APP-like algorithm is better. Our suggestions for the initial parameters of improved APP-like algorithm are shown as follows:(1)
It is better to select a smaller initial value of the penalty parameter, and 1 or less is suggested as the initial value of the penalty parameter.(2)
On the premise of ensuring convergence, it is recommended to select parameterβk as small as possible, and βk=m+0.1ck is suggested, where m presents the objective functions, which is composed of m separable convex functions.


## 5.3.1. APP-Like Algorithm for Solving Test System

In this section, we use APP-like algorithm to solve the test system and observe the influence of parameter on the convergence efficiency of APP-like algorithm. We set the maximum number of iterations as 50. For the iterative strategy of penalty parameter shown in (44), we set kstop=30 and δ=0.1. The convergence condition is set to maxwk+1−wk<0.0001. If the convergence condition is not satisfied when the number of iterations is greater than 50, then we can say that the corresponding algorithm fail to convergence with maximum iterations.The simulation results based on the APP-like algorithm for the test system are shown in Table3. In order to verify the influence of different penalty parameter settings on the convergence efficiency of the APP-like algorithm, we designed five different penalty parameter settings named Case1–Case5, respectively, which are shown in the first column in Table 3. After that, the second column represents the initial parameter setting of the APP-like algorithm, the third column represents the number of iterations when convergence conditions are met, and the fourth column represents the value of maxwk+1−wk when convergence conditions is met or the number of iterations reaches the maximum iterations. In addition, the word “Fail” in Table 3 represents the corresponding algorithm fail to convergence with maximum iterations. The curve of maxwk+1−wk changing with the number of iterations is shown in Figure 1.Table 3
The simulation results based on APP-like algorithm for test system.
CaseParameterIterationmaxwk+1−wkCase1c = 1, β = 9.1cFail0.3987Case2c = 10, β = 9.1cFail0.0589Case3c = 100, β = 9.1cFail0.0061Case4c = 1000, β = 9.1cFail6.1481 × 10−4Case5c = 10000, β = 9.1c226.2349 × 10−5Figure 1
The curve ofmaxabswk+1−wk based on the APP-like algorithm.According to the data in Table3 and the curve in Figure 1, it can be known that the APP-like algorithm meets the convergence condition only under case5. By comparison, the APP-like algorithm fails to converge or stops convergence prematurely under case1-case4. For the further analysis of Figure 1 and Table 3, we find that the value of maxwk+1−wk gradually approaches the convergence condition with the increase of the penalty parameter. Let's recall the iterative formula (7) of APP-like algorithm. Taking the ith sub-optimization problem as an example, there are two terms (β−c/2Aixi−Aixik2 and c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2) related to the penalty parameter in the objective function. c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 represents the punishment for the equality constraint. For case1-case4 in Table 3 and Figure 2, at the initial stage of iteration, it is obvious that maxwk+1−wk is large, so c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 can play a good punishment role. However, as maxwk+1−wk approaches zero gradually, the penalty effect of c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 decreases gradually when the penalty parameter is set smaller. This explains the reason why case1-case4 in Table 3 and Figure 2 fail to convergence.Figure 2
The curve ofmaxabswk+1−wk based on improved APP-like algorithm.The existence ofβ−c/2Aixi−Aixik2 is to ensure the convergence of the APP-like algorithm. However, we must realize that the existence of β−c/2Aixi−Aixik2 also prevents the update of the current iteration point. Therefore, we expect β−c/2Aixi−Aixik2 to be as small as possible under the premise of ensuring the convergence of the APP-like algorithm. In fact, for the APP-like algorithm, the value of penalty parameters and β/c is given. That is to say that the APP-like algorithm ignores the role of β−c/2Aixi−Aixik2 in the iterative process on the premise of ensuring algorithm convergence.


## 5.3.2. Improved APP-Like Algorithm for Solving Test System

In this section, we use improved APP-like algorithm to solve the test system and observe the influence of parameter on convergence efficiency of improved APP-like algorithm. In order to comparison with the results of APP algorithm, the initial parameter settings of improved APP-like algorithm are the same as those of the APP algorithm. The simulation results based on improved APP-like algorithm for the test system are shown in Table4. The columns in Table 4 have the same meaning as the columns in Table 3. The curve of maxwk+1−wk based on improved APP-like algorithm changing with iterations is shown in Figure 2.Table 4
The simulation results based on improved APP-like algorithm for test system.
CaseParameterIterationmaxwk+1−wkCase1c0 = 1, βk = 9.1ck146.2929 × 10−5Case2c0 = 10, βk = 9.1ck145.8110 × 10−5Case3c0 = 100, βk = 9.1ck179.0122 × 10−5Case4c0 = 1000, βk = 9.1ck208.0008 × 10−5Case5c0 = 10000, βk = 9.1ck208.0579 × 10−5According to the information shown in Table4 and Figure 2, we must admit that the trends of these curves of maxwk+1−wk are not entirely consistent. However, the curves of maxwk+1−wk with different initial penalty parameter values maintain similar trends, and can quickly meet convergence condition. That is to say, for improved APP-like algorithm, the selection of penalty parameters is robust to a certain extent.The difference between APP-like algorithm and improved APP-like algorithm lies in the updating of penalty parameters. For APP-like algorithm, the penalty parameter is given in advance and remains unchanged in the iterative process. For improved APP-like algorithm, the initial value of penalty parameters is given, but it is updated (The iterative strategy of penalty parameter can be found in (44)) in the iterative process.According to the analysis of APP-like algorithm in section5.3.1, it can be found that APP-like algorithm has achieved better convergence effect by setting a larger penalty parameter value to ensure that c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 plays an effective punishment role. Comparatively speaking, improved APP-like algorithm has achieved better convergence effect by updating the penalty parameter to ensure that c/2∑j=1i−1Ajxjk+Aixik+∑j=i+1mAixik−b2 plays an effective punishment role. Both methods can achieve better convergence characteristics, and we cannot say which algorithm is better.Let's turn our attention toβ−c/2Aixi−Aixik2. APP-like algorithm ignores the role of β−c/2Aixi−Aixik2 because the parameters β and c are given in advance. In fact, we expect β−c/2Aixi−Aixik2 to be as small as possible under the premise of ensuring the convergence of the algorithm.According to the information shown in Table4 and Figure 2, obviously, the smaller the initial value of penalty parameter is set, the better the convergence characteristic of improved APP-like algorithm will be. According to the description of iteration strategy (44) for penalty parameters, it can be known that penalty parameter has upper and lower bounds in the iterative process. For the improved APP-like algorithm, if we give a small initial value of the penalty parameter, the value of βk−ck/2Aixi−Aixik2 will be smaller throughout the iteration. This is why, in Figure 2, the smaller the initial value of penalty parameter is, the better the convergence efficiency is.In the above part, we analyze the influence of penalty parameter on the convergence efficiency of the improved APP-like algorithm. If we further analyzeβk−ck/2Aixi−Aixik2, we will find that the value of βk−ck/2Aixi−Aixik2 is related not only to the punishment parameter but also to the parameter βk. The simulation results based on APP-like algorithm for the test system with different βk/ck are shown in Table 5. The corresponding curve of maxwk+1−wk is shown in Figure 3. According to the information shown in Table 5 and Figure 3, it is clear that, for the same initialization penalty parameter, the smaller βk/ck is, the better the convergence efficiency of APPP algorithm is under the premise of ensuring the convergence of improved APP-like algorithm. The simulation results shown in Table 5 and Figure 3 are in agreement with our theoretical analysis of βk−ck/2Aixi−Aixik2.Table 5
The simulation results based on improved APP-like algorithm with differentβ.
CaseParameterIterationmaxwk+1−wkCase1c0 = 10, βk = 9.1ck146.2929 × 10−5Case2c0 = 100, βk = 20ck268.9700 × 10−5Case3c0 = 1000, βk = 30ckFail1.6000 × 10−3Case4c0 = 1, βk = 40ckFail7.0000 × 10−2Figure 3
The curve of max (abs(wk+1-wk)) based on improved APP-like algorithm with different β.According to the theoretical analysis in Section4 and the simulation results in Section 5, we suggest using the improved APP-like algorithm. Compared with the APP-like algorithm, the penalty parameter selection of improved APP-like algorithm is robust and the convergence efficiency of improved APP-like algorithm is better. Our suggestions for the initial parameters of improved APP-like algorithm are shown as follows:(1)
It is better to select a smaller initial value of the penalty parameter, and 1 or less is suggested as the initial value of the penalty parameter.(2)
On the premise of ensuring convergence, it is recommended to select parameterβk as small as possible, and βk=m+0.1ck is suggested, where m presents the objective functions, which is composed of m separable convex functions.


## 6. Conclusion

In this paper, we study the convex optimization problem with linear constraint and the objective function is composed ofm separable convex functions. According to the properties of the objective function, it is natural to consider a distributed iterative strategy. ADM-G and ADBC are efficient algorithms to solve the optimization problem in the form of the Gaussian Seidel iterative scheme. Due to the serial computation form of Gauss-Seidel iterative scheme, ADM-G and ADBC needs more computing time when the problem scale is large (in other words, when the value of m is large). Then, a natural idea is to solve optimization problem in parallel. The auxiliary problem principle (APP) is an effective parallel distributed algorithm for solving separable convex optimization problem with m = 2. Inspired by the principle of APP, a natural idea is to extend the method of APP, resulting in an APP-like algorithm. Therefore, we firstly prove that β>mc is a sufficient condition for the convergence of APP-like algorithm. However, simulation results show the convergence efficiency of APP-like algorithm is sensitive to the selection of penalty parameter. In order to overcome the deficiency of APP-like algorithm, we proposed the improved APP-like algorithm with variable penalty parameter. Compared with APP-like algorithm, the improved APP-like algorithm is robust in terms of the selection of penalty parameter, and the convergence efficiency of improved APP-like algorithm is better.



---

*Source: 8794839-2022-06-24.xml*