第40卷　第4期2006年4月 西　安　交　通　大　学　学　报J OU RNAL O F XI′AN J IAO TON G U N IV ERSIT YVol.40　№4Ap r.2006基于辅助问题原理及内点法的分区并行最优潮流算法商小乐,李建华,刘　锐,李　夏(西安交通大学电气工程学院,710049,西安)摘要:针对大电网在最优化问题计算中存在计算时间长、矩阵维数高等问题,按照电力系统的实际地理分布,在某些联络线处将整个电网分解为多个相对独立的子系统,子系统间通过边界节点产生的约束条件进行协调,建立了一个基于辅助问题原理(A PP)的多分区并行最优潮流计算模型.应用A PP方法,将大电网最优潮流问题转化为多个规模相对较小子系统的并行协调优化问题,在每个子系统中采用跟踪中心轨迹内点法求解子系统的优化问题.测试算例的计算结果表明,该算法减少了整个问题的矩阵维数,降低了问题的求解难度,具有较强的收敛性、快速性和实用性.关键词:最优潮流;多分区;辅助问题原理;并行计算;内点法中图分类号:TM744　文献标识码:A　文章编号:0253Ο987X(2006)04Ο0468Ο05Paralleled Optimal Pow er Flow Algorithm B ased on Auxiliary ProblemPrinciple and Interior Point AlgorithmShang Xiaole,Li Jianhua,Liu Rui,Li Xia(School of Electrical Engineering,Xi′an Jiaotong University,Xi′an710049,China)Abstract:To solve t he difficulties of long comp uting period and huge mat rix dimensions in t he t raditional large scale optimal power flow(O PF)algorit hms,a complex power system is decom2 posed into several logical independent subsystems geograp hically,which are coordinated via re2 st rictions of t he jointed borders.A dist ributed processing model based on subsystem decomposi2 tion and auxiliary problem p rinciple(A PP)met hod is p roposed,where t he large scale system O PF p roblem is decompo sed into several parallel coordinating subsystem optimization ones and solved wit h t he interior point algorit hm.It is demonst rated t hat t he algorit hm rapidly reduces t he dimensions and t he calculation complexity of overall OPF problem wit h higher efficiency and con2 vergence.K eyw ords:optimal power flow;subsystem decompo sition;auxiliary problem p rinciple;parallel comp utation;interior point algorit hm 随着电力系统规模不断扩大和对在线实时分析要求的不断提高,传统算法在计算速度上已经无法满足需求,人工智能算法虽然可以得到较好的优化解,但计算速度缓慢.此外,传统算法和人工智能算法目前都面临着大系统所带来的维数灾难问题,快速、稳定的最优潮流算法已经成为大规模电力系统计算与运行控制的关键.近年来,并行算法正逐渐应用到各种科学计算当中.在电力系统计算方面,并行算法也有了一些应用[1Ο4],这些方法采用服务器/客户端结构,主从进程之间存在大量数据交换,造成了数据收集和发送时的瓶颈.文献[5Ο7]提出了一种新的并行计算方法,它应用辅助问题原理[8],将一个整体的最优化问题分解为多个相对独立的子问题,并采用并行迭代求解子问题的方式来完成对整个问题的求解,为电力系统并行优化计算提供了一种新思路.本文所讨论的是基于辅助问题原理(A PP)方法及跟踪中心轨迹内点法的分区并行最优潮流算法,收稿日期:2005Ο09Ο16.　作者简介:商小乐(1982～),男,硕士生;李建华(联系人),女,教授.介绍了算法的基本公式,完成了算法程序编制和算例测试.1　最优潮流(O PF )数学模型本文采用发电费用最小为目标,数学模型为min F (x )=min∑ni =1(ai 2P 2G i +a i 1P G i +a i 0)(1)s.t.h (x )=0,g (x )≤0(2)式中:x ={P ,Q ,θ,V },表示发电机有功、无功出力、无功电源出力以及节点电压角度、电压幅值等控制变量以及状态变量;a i 2P 2G i +a i 1P G i +a i 0表示第i 台发电机组的发电费用;h (x )、g (x )分别表示等式约束和不等式约束条件.2　大电网的分解大电网通常可按照地域分为多个区域,各个区域之间通过联络线进行连接,本文通过联络线入手,对整个电网进行区域的划分,以图1为例说明分区的过程.(a )分区前(b )分区后图1　电网的分区电网可以表示为图1a 的形式,区域A 和B 依靠中间的联络线C 互相连接,将整个网络通过“撕裂”边界节点的方式分成两个子系统,并在两个子系统分界处添加虚拟发电机,见图1b ,用于在分解之后,协调两个子系统之间有功、无功等电气量的平衡.在分解前,变量x ={x 1,x 2,y },x 1、x 2、y 分别表示子系统A 、B 的内部变量和边界变量.在分解时,通过“复制”边界节点,得到了2组边界变量y 1、y 2.对于整个电网而言,“撕裂”产生的边界节点应在电气量上相同,即y 1=y 2=y .当电网分区之后,目标函数应该分为两个部分,分别表示子系统A 、B 的发电费用.因为边界节点上增加的虚拟发电机的发电费用是0,虚拟发电机的引入不会影响整个网络的目标函数值,虚拟发电机仅在整个计算中,为各子系统之间的协调提供方法.因此,将原目标函数改写为min F (x )=min F 1(x 1)+min F 2(x 2)(3) 无论对整个电网还是对分区后的子系统进行讨论,网络本身的等式约束和不等式约束都没有改变.对于边界节点,由于子系统间在边界节点上应具有相同的电气量,应该增加一个等式约束条件.在分区之后,将约束条件修改为h 1(x 1,y 1)=0,g 1(x 1,y 1)≤0h 2(x 2,y 2)=0,g 2(x 2,y 2)≤0θ(y )=y 1-y 2=0(4)式中:y ={y 1,y 2}.3　A PP 原理及其应用不考虑子系统内部的约束条件,仅考虑由于分区产生的边界点约束,此时根据式(3)、式(4),优化问题的拉格朗日函数可以写为L (x ,λ)=F 1(x 1)+F 2(x 2)+〈λ,θ(y )〉(5)为了提高算法的收敛性,本文采用增广拉格朗日方法,即在原拉格朗日函数上增加一个二次项L (x ,λ)=F 1(x 1)+F 2(x 2)+〈λ,θ(y )〉+c 2〈θ(y ),θ(y )〉(6)式中:c 为常数.可以看出,引入二次项并不会影响最终的计算结果,当最后迭代收敛时,子系统间边界节点电气量趋向一致,此时二次项的值趋向0.二次项的加入虽然提高了算法的收敛性,但是同时破坏了两个子系统之间的可分性,因为加入的二次项本身是不可分解的.在这种情况下,引入辅助问题原理[8,9]来解决这个问题.311　APP 的原理以及在本文中的应用将L (x ,λ)看作由J (x ,λ)和J 2(x )两部分构成L (x ,λ)=J (x ,λ)+J 2(x )(7)其中J (x ,λ)可微,J 2(x )为不一定可微.若能构造出一个辅助问题G (x ,λ)+εJ 2(x )(8)且G (x ,λ)满足条件G ′(x 3,λ3)=εJ ′(x 3,λ3)(9)其中(x 3,λ3)表示原问题的解,则原问题可转化为求解G (x ,λ)+εJ 2(x )的鞍点问题,其中G (x ,λ)被称为辅助函数,其理论证明见文献[8].根据式(6)、式(7),分别令964　第4期 商小乐,等:基于辅助问题原理及内点法的分区并行最优潮流算法J(x,λ)=〈λ,θ(y)〉+c2〈θ(y),θ(y)〉(10)J2(x)=F(x)(11)并构造辅助函数为G(x,λ)=K(x,λ)+　〈εJ′(x,λ)-K′(x,λ),(x,λ)〉(12)其中K(x,λ)为核函数,则对原问题的求解可转化为求解下面的问题G(x,λ)+εJ2(x)=K(x,λ)+〈εJ′(x,λ)-K′(x,λ),(x,λ)〉+εF(x)(13)取核函数K(x,λ)=K(x)+12‖λ‖2(14)根据A PP两层算法模型[8],可按照下式求解式(13) x k+1=arg min{K(x)+〈εJ′x(x k,λk)-K′x(x k),x〉+εF(x)}(15)λk+1=λk+αθ(y k+1)(16)将式(10)带入式(15),考虑〈θ′(y),y〉=θ(y),得x k+1=arg min{K(x)+〈-K′x(x k),x〉+ε〈cθ(y k)+λk,θ(y)〉+εF(x)}(17)λk+1=λk+αθ(y k+1)(18) 根据式(10)知K(x)只包含边界变量,为了提高算法的收敛性,K(x)应为二次函数,取K(x)=β2‖y‖2(19)带入式(17),有x k+1=arg min β2‖y-y k‖2+ε〈λk+cθ(y k),θ(y)〉+εF(x)-β2‖y k‖2(20) 为了计算方便,可以取ε=1.对于引入的其他3个常数参数α、β、c,为了满足A PP方法的收敛性,在选取它们的值时,应该满足条件0<α<2c(21)并令β=2α根据式(20),略去常数项-β2‖y k‖2,并将θ(y)展开,可将对式(6)的求解转化为如下的迭代过程求解(x1k+1,y1k+1,x2k+1,y2k+1)=　arg min β2‖y1-y k1‖2+β2‖y2-y k2‖2+(λk+c(y k1-y k2))T(y1-y2)+F1(x1)+F2(x2)(22)λk+1=λk+α(y k+11-y k+12)(23) 显然,可将式(22)所表示的优化问题分解为2个子问题进行求解.于是,我们可以得到子系统A 对应的优化问题(x k+11,y k+11)=arg minβ2‖y1-y k1‖2+(λk+c(y k1-y k2))T y1+F1(x1)(24)λ1k+1=λ1k+α(y k+11-y k+12)(25) 子系统B有相似的优化公式.从式(24)中可以看出,在计算子系统优化问题时,仅需知道子系统内部变量以及相邻子系统边界变量前一次的优化值,即计算是相对独立的.在所有子系统完成对优化问题的求解时,相邻子系统间要互相交换边界点变量值,并用其更新λ,开始下一次迭代.当相应的边界节点上的虚拟发电机达到功率平衡、电压及相角趋向一致时,迭代过程完成.312　分区后电压相量参考点的处理在计算过程中,当网络被分为若干子系统时,每个子系统都选取了自己的平衡节点作为参考,而不是以全网的平衡节点作为参考,那么子系统参考点与全网参考点必然存在一个角度差值,如图2所示.图2　子系统间的角度问题 例如,对于节点k(设其电压向量为U・′k),它以所属子系统的平衡节点(设其电压向量为U・′0)为参考点时,电压相角为α,它以整个网的平衡节点(设其电压向量为U・′0)为参考点时,电压相角为β.可以推得,子系统参考点相对于整个网络参考点存在一个β-α的差值.在处理子系统之间的角度等式约束时,就必须考虑这个差值.对于本文的情况而言,可以直接将两个子系统边界节点角度平均值的差作为子系统间的角度差值.对于多个子系统情况,可以参考文献[10].4　子系统优化问题的内点法求解前面将一个大网络的优化问题分解为2个子系统的优化问题,并针对各个子系统形成了各自的目标函数及约束条件,以子系统A为例,其子优化问题及其约束为074西　安　交　通　大　学　学　报 第40卷　min f (x 1,y 1)=minβ2‖y 1-y k 1‖2+(λk +c (y k 1-y k 2))T y 1+F 1(x 1)(26)s.t.h (x 1,y 1)=0,g ≤g (x 1)≤g(27)对各子系统新的目标函数的优化问题,本文采用跟踪中心轨迹内点法[11]进行求解.将式(27)中的不等式约束转化为等式约束g (x 1)+u =g ,g (x 1)-l =g (28)其中松弛变量l =(l 1,…,l r )T ,u =(u 1,…,u r )T ,应该满足l >0,　u >0这样原问题转化为min f (x 1,y 1)(29)s.t.h (x 1,y 1)=0g (x 1)+u =g ,g (x 1)-l =gl >0,u >0(30)把目标函数改造为障碍函数,该函数在可行域内近似于原目标函数,在边界时变得很大,也称为原优化问题的对偶问题min f (x 1,y 1)-μ∑rj =1lg (l j)-μ∑rj =1lg (u j)(31)s.t.h (x 1,y 1)=0g (x 1)+u =g ,g (x 1)-l =g(32) 通过对目标函数的变换,把含不等式约束的优化问题转化成只含有等式约束的对偶问题,可直接用拉格朗日乘子法进行求解,当原对偶问题的对偶间隙趋向于0时,对偶问题的解收敛至原问题的解.5　测试算例与结果分析在对测试算例进行计算时,采用的计算机为双P ΟIII800处理器,512M 内存,使用P Thread 线程函数实施并行计算,使用信号灯、异步信号等方法对各个子系统的计算线程进行同步,算法流程见图3.511　测试算例本文选取了4个测试算例,算例1、2由IEEE30节点数据构造得到,算例3、4由IEEE118节点构造得到,网络的基本数据如表1所示.本文选取α=115,β=3,c =3,以‖y 1-y 2‖<ξmax 作为收敛判据,并选取ξmax 为0103.为了比较算法的计算结果和加快计算速度的能力,本文分别使用了如下方式计算最优潮流:表1　测试算例编号节点数子系统节点数边界节点数支路数发电机数无功源数130(15,18)34133258(30,30)282663234(118,118)235632764232(118,118)43563276图3　算法流程 (1)不分区采用内点算法对整个网络进行计算;(2)采用本文方法,使用单CPU 串行计算;(3)采用本文方法,使用2个CPU 并行计算.在上边提到的3种方式中,后两者的计算结果是相同的,仅在计算时间上不同.512　结果分析从优化结果上进行对比,表2记录了几种方式下得到的总发电费用(模拟值)的最优化结果.比较发现,在采用方式2、3计算时,虽然停止条件ξmax 为0103(选取得比较大),但是优化结果最大误差仅相差1%左右,对于工程应用,这种误差是可以接受的.表2　优化结果(发电费用)的对比编号发电费用方式1方式2、3误差/%1234111853142312533234710227234614757111179728231479313471229913461214800147019701060108174　第4期 商小乐,等:基于辅助问题原理及内点法的分区并行最优潮流算法 表3记录了几种方式下计算时间及本文方法在满足收敛条件下需要的迭代次数,图4为采用本文方法计算边界值误差的收敛曲线.从结果来看,该算法在最初几次迭代收敛很快,但是当边界误差下降到一定值之后,收敛速度明显变慢.ξmax 的选取应在保证工程需求的前提下,尽量减少算法的迭代次数.表3　测试算例迭代次数与计算时间编号计算时间/s 方式1方式2方式3迭代次数1234010400115319160119166301310014701410201410800117901291813688128313655图4　‖y 1k -y 2k ‖的收敛曲线 由于计算时间与迭代次数成正比,并且程序在线程同步时也要消耗一定的时间,因此算例1和算例2的计算时间比传统方法多,该算法并无优势.由于采用分解协调的方法将整个网络分成几个子系统,使其求解矩阵维数大大降低,而矩阵的维数是影响计算时间和精度的重要因素,因此对算例3、算例4进行计算时,该方法在时间上取得了明显的优势.在目前系统越联越大,即将形成全国大电网的情况下,本文所提方法会有很大的实用价值.6　结　论本算法将大电网优化问题转化为多个子系统互相协调的并行优化问题,通过几个算例对算法进行了测试,验证了算法的收敛性和快速性.该算法具有如下特点:(1)降低了每个子问题的矩阵维数,降低了整个问题求解难度,将各个子问题并行求解,加快了整个问题的求解速度;(2)每次各子系统问题求解完毕后,仅在相邻子系统间交换边界变量数据,减少了子系统间数据的交换量,避免了数据传输带来的瓶颈;(3)电网的分区既可以按照地域进行划分,便于在电力市场方面的应用,也可以按照区域数均匀地划分,使得每个子系统规模相近,每个子问题的求解时间趋于平均,从而加快程序运行速度;(4)测试中发现,在满足式(21)的情况下,3个常数的取值明显影响算法的收敛性,合适的取值对于整个算法是十分重要的.参考文献:[1]　薛　巍,舒继武,王心丰,等.电力系统潮流并行算法的研究进展[J ].清华大学学报(自然科学版),2002,42(9):1192Ο1195.[2]　周红宇,马维新,袁　斌,等.电力系统网络方程并行算法研究及潮流并行计算的实现[J ].清华大学学报(自然科学版),1994,34(4):95Ο101.[3]　程新功,厉吉文,曹立霞,等.基于电网的多目标分布式并行无功优化研究[J ].中国电机工程学报,2003,23(10):109Ο113.[4]　潘哲龙,张伯明,孙宏斌,等.分布计算的遗传算法在无功优化中的应用[J ].电力系统自动化,2001,25(6):37Ο41.[5]　K im B H ,Baldick R.Coarse 2grained distributed opti 2mal power flow [J ].IEEE Trans on Power Systems ,1997,12(2):932Ο939.[6]　K im B H ,Baldick R.A comparison of distributedoptimal power flow algorithms [J ].IEEE Trans on Power Systems ,2000,15(2):599Ο604.[7]　Batut J ,Renaud A.Daily generation scheduling opti 2mization with transmission constraints :a new class of algorithms [J ].IEEE Trans on Power Systems ,2000,7(3):982Ο989.[8]　Cohen G.Auxiliary problem principle and decomposi 2tion of optimization problems [J ].Journal of Optimi 2zation Theory and Application ,1980,32(3):277Ο305.[9]　Cohen G.Optimization by decomposition and coordina 2tion :a unified approach [J ].IEEE Trans on Automatic Control ,1978,AC 232(2):222Ο232.[10]Losi A ,Russo M.On the application of auxiliaryproblem principle [J ].Journal of Optimization Theory and Application ,2003,117(2):377Ο396.[11]王锡凡,方万良,杜正春,等.现代电力系统分析[M ].北京:科学出版社,2003.(编辑　杜秀杰)274西　安　交　通　大　学　学　报 第40卷　。