分布式牛顿法三篇

2024-09-12

分布式牛顿法篇1

标准的无线网络的分布式最优化算法是基于拉格朗日对偶分解架构和次梯度算法 (LD-SG) [1DD], 尽管它在理论和工程上很有吸引力, 但性能在实践中却不令人满意, 并且次梯度法的收敛缓慢, 步长选择敏感[2D]。由于有这些限制, 在本文中, 我将分布式牛顿法[3D]引入无线网络, 以Ad Hoc网络为例进行理论分析, 为无线网络中的二阶算法创建一个新的理论架构。这种方法的理论基础是它作为一个二阶方法, 在确定搜索方向上利用了梯度和海森矩阵的信息, 因此拥有更快的二次收敛速度。

1网络模型

在Ad Hoc网络中, 用N表示网络中的节点集合, l表示节点间的链路, L表示链路的集合, f为源节点 Src (f) 到目的节点Dst (f) ( 的数据流, F为数据流集合, 为网络的拓扑结构, b表示判断节点n是否是数据流f的源节点或目的节点的矩阵向量。

在网络层:设每个节点的输入量和输出量是平衡的, 则有为数据流f上所有链路l的路由矢量, x (f) s为源节点的速率。

在链路层:由于链路间相互存在干扰, 每个无线链路的容量不仅与信号自身有关, 还与其他链路的干扰水平有关。因此当无线链路l在每个时刻ti只能被一个信息流占用时, 为了使链路时刻保持稳定, 无线链路l上传输的信息流速率之和不能超过该链路的信道容量, 即, 其中C (i) l表示在ti时刻链路l的容量。本文中用) 表示网络的整体效用, 为了实现网络效用最大化, 联合网络层和数据链路层的约束条件来实现跨层设计。

2分布式牛顿法

根据网络模型中对目标函数和约束条件的介绍, 跨层优化问题用如下公式表示出来:

利用对数障碍函数法[4D]将目标函数问题重组, 重组后的等式如下:

上式中的u>0为参数常量 , , 表示上式中出现的所有变量。

本文的关键是求解牛顿方向Δqk和对偶变量wk , 其中牛顿方向主要有三部分组成:Δx (f) t、Δr(f)l和Δtl , 为了求解牛顿方向,

其中根据KKT条件[5DD] , [6DD]可以得出如下等式 , 其中是qg) ( 在qk处的海森矩阵, wk为在第k次迭代时的对偶变量:

要求解Hk , 先对g (qk) 求一阶和二阶导 , 令, 定义如下等式:

本文中我们利用矩阵分解理论[7D]设计一种分布式迭代算法来计算牛顿方向 ) Δr (f) l和Δtl。与S有关的 Δx (f) s在上文中已经计算出来, 将Hk中与S相关的行列删除得到如下式子:

令为了从H1中分得到一个非奇异矩阵, 可以进行如下分解, 式中的α为可以调节收敛速度快慢的参数因子:

根据矩阵分解理论, 联合等式 (7) 和 (13) 可以求得

同理令最终可以求解出对偶变量 w (f) n为:

文中所提算法流程如下:

( 1 ) 初始化 : 对每个源、节点和每条链路 , 给x (f) s, w (f) n, r (f) l, f附初始值;

(2) 利用公式 (11) (15) (16) 来更新原始牛顿方向的更新Δx (f) s、Δr (f) l和Δtl

(3) 在每个节点处利用公式 (17) 更新对偶变量 w (f) n ;

(4) 通过预先设置终止时间或者达到牛顿方向所满足的要求都可以终止该算法, 否则进入步骤 (2) 。

3实验仿真与分析

文中将以10个节点的Ad Hoc网络场景为例, 对所提出的分布式牛顿法进行仿真, 效用函数用) 表示, 并且链路之间的干扰是任意的, 收敛速度的快慢可以通过参数因子α来调节。对于牛顿方向Δqk的收敛速度如图1所示, 当α =0.1时, 错误率达到10-6需要的迭代次数为9;当α =1时, 错误率达到10-6需要的迭代次数为20。对于对偶变量wk的收敛速度如图2所示, 当α =0.1时, 错误率达到10-6需要的迭代次数为21;当α =1时, 错误率达到10-6需要的迭代次数为43。当α值在0.1到1之间变化, 从图中可以看出, α越小, 收敛速度越快, 根据不同的场景, 选择合适的α值从而可以得到满足要求的收敛速度。

在文中的网络场景中, 分布式牛顿法的收敛行为如下图3所示, 从图中可以看出, 在一定的误差范围内, 利用此算法只需要24次迭代, 就可以使近似目标函数值收敛到原始问题目标函数值, 由此可以看出收敛速度很快, 效率很高。

4结束语

通过对算法的分析和仿真可以看出, 在一定范围内, 一个设计合理的分布式牛顿法将拥有更快的二次收敛速度。下一步的工作将进一步证明:相比于一阶的拉格朗日对偶分解法, 该算法不仅具有更快的收敛速度, 还拥有更短的平均队列长度。本文的算法还可以进一步被推广应用到无线网络的随机信道模型研究和云计算的资源分配等方面, 分布式牛顿法将充分发挥它的优势, 拥有更广阔的应用空间。

参考文献

[1]Xiaojun Lin, Shroff N B, Srikant R.A tutorial on cross-layer optimization in wireless networks[J].Selected Areas in Communications, IEEE Journal on, 2006, 24 (8) :1452-1463.

[3]Ermin Wei, Ozdaglar A, Eryilmaz A, Jadbabaie A.A distributed newton method for dynamic Network Utility Maximization with delivery contracts[C].Princeton:IEEE Computer Society, 2012:1-6.

[4]Jia Liu, Hanif D.Sherali.A Distributed Newton Approach for Joint Multi-Hop Routing and Flow Control:Theory and Algorithm[C].Orlando:Institute of Electrical and Electronics Engineers Inc, 2012:2489-2497.

[5]Stephen B, Lieven V.Convex Optimization[M].UK:Cambridge University Press, 2004.

分布式牛顿法篇2

牛顿法是电力系统潮流计算采用较为广泛的一种方法,其收敛速度快,但存在对初值敏感的缺点,初值选取不当可能会带来病态潮流问题。因此,初值的选取是影响牛顿法潮流计算的根本性问题之一[1]。

参考文献[2-4] 通过对雅可比矩阵进行适当改造得到改进牛顿- 拉夫逊法。参考文献[5] 提出了牛顿潮流计算的收敛性定理,可评价所选初值能否保证计算收敛。参考文献[6] 提出了一种小阻抗支路零功率法的初值给定方法,能够在一定程度上改善含小阻抗支路系统的病态潮流计算问题。参考文献[7] 提出了求解同伦曲线的潮流计算方法,使初值进入收敛范围。以上诸多研究相比于传统牛顿法体现了一定的优势,但对初值敏感问题并未找到完善的解决方法,也未对初值的不同给定方法做过较为全面的比较。

本文首先对牛顿法潮流计算方法的特点及其初值敏感问题做了简述;其次介绍了本文选取的几种初值给定方法;然后就几种不同的初值给定方法在IEEE9、IEEE39和韶关电网等多个系统上进行了仿真测试。根据计算结果,对不同的初值给定方法进行了对比分析,验证了以上方法对改善牛顿法潮流计算初值敏感问题的实用性。

1牛顿法潮流计算机理简述

设系统除平衡节点外共有n个节点,其中r个PV节点,m个PQ节点,b条支路,则各节点的功率方程如下:

式中,Pi、Qi分别为节点i注入有功功率和无功功率,Ui和Uj分别为节点i和节点j的电压幅值, Gij和Bij分别为连接节点i与节点j的支路的电导和电纳,θij为节点i和节点j的电压相角差。

文中核心计算程序采用传统经典牛顿法进行潮流计算,其修正方程式可以表示为:

式中,ΔP、ΔQ分别为节点注入有功功率和无功功率的不平衡量;Δθ、ΔU分别为电压相角和电压幅值的修正量。为第k次迭代时的雅可比矩阵。

雅可比矩阵的奇异情况将直接决定方程组的收敛性。考虑到P与θ、Q与U的强相关关系,H子块的占优地位可以得到保障,但是对于L子块:

当系统含有小阻抗支路或者重负荷时,L子块的主对角元优势不复存在,雅可比矩阵的数值条件恶化,潮流的收敛性减弱[8]。

2几种初值给定方法

在节点功率不平衡量方程与雅可比矩阵系数中,导纳元素为已知常数,电压幅值和电压相角为变量,节点功率不平衡量方程与雅可比矩阵系数都是U、θ的函数。根据牛顿法原理可知,初值选取离真解越近,越容易收敛。文中选取了平直启动法、直流潮流法、PQ分解法、高斯- 塞德尔法和部分功率法作为给定初值的基本方法。

2.1平直启动法

平直启动法将电压相角的初值设为0,PV节点与平衡节点的电压幅值设为给定值,而将PQ节点的电压幅值的初值设为1。大多数情况下,采用平直启动进行牛顿法潮流计算能够可靠收敛。但对于某些病态系统,其运行状态与额定状态差异较大, 采用平直启动很可能会带来较大的功率不平衡量而导致潮流计算收敛性恶化。由于简单易操作,平直启动是进行潮流计算时广泛采用的一种方法。

2.2直流潮流法

直流潮流法模型简单,将非线性电力系统潮流问题简化为线性电路问题,求解速度很快,从而使分析计算十分方便。实际应用中的直流潮流方程为:

式中,P为节点注入功率相量;θ为节点电压的相角相量;B为节点导纳矩阵。

直流潮流法计算所得的电压相角精度与研究系统本身有很大关系。在线路潮流达到兆瓦级的系统中,简易的直流模型可能并不能很好地匹配实际情况,但其为交流潮流计算提供的相角初值一般要优于平直启动[8]。

2.3 PQ分解法

PQ分解法抓住高压电网的主要矛盾,对有功功率和无功功率进行解耦迭代。其电压修正方程式可以表示为:

在精度要求较高时,PQ分解法收敛速度低于牛顿法。在实际系统的潮流计算中,PQ分解法所能达到的收敛精度要低于牛顿法。换个角度也就是说,PQ分解法可以将功率不平衡量限制到一个相对较小的范围之内。由于在其迭代过程中,系数矩阵的所有元素维持常数,因此其对初值的依赖程度相对牛顿法弱,这也正是利用PQ分解法提供初值的理论基础。

2.4高斯-塞德尔法

基于节点阻抗矩阵的高斯- 塞德尔迭代法提出于上世纪60年代。为讨论其计算性能,仅列出系统中除平衡节点( 设为节点1) 外,其余都属于PQ节点的最简单情况的迭代公式,见式(7)、式(8) :

式中,Psj、Qsj分别为节点j给定的注入有功、无功功率,Uj(k )、Ij(k )分别为节点j电压和电流的第k次迭代值,Zij为节点阻抗矩阵的元素,Uj(k)为Uj(k)的共轭。

在大系统中,高斯- 塞德尔法内存需求和计算量都很大,一般不被采用。高斯- 塞德尔法在不发散的情况下可以作为提供较好初值的一种手段。

2.5部分功率法

部分功率法是一种近似潮流的计算方法。其核心思想为:保持负荷的功率因数不变,将系统的负荷水平和发电机( 平衡机除外) 的出力同时下降到某一负荷系数k,在此水平下计算出系统的潮流解。得到的近似方式中系统负荷的分配比例保持不变,功率传输特征与初始潮流相近且计算简单。具体的,负荷系数k下的潮流解满足( 设1节点为平衡节点) :

式中,Pi'、Qi'分别为近似潮流解下i节点的有功功率和无功功率。Pi s、Qi s分别为原方式下i节点的给定有功功率和无功功率。很明显,当将其带入到原方式下计算时,可以保证任一节点( 平衡节点除外) 的初始不平衡有功功率和无功功率分别为(1-k)Pis和(1-k)Qis。因此,在保证部分功率法计算收敛的情况下,k取得越大,初始不平衡功率越小。在实际计算中,取k∈(0.8,0.9) 可以获得比较理想的效果。

3初值给定计算流程

初值给定的基本思想是:当遇到初值敏感引起的潮流计算收敛性恶化甚至不收敛情况时,利用第2节中给出的几种方法给出初值,减小功率的不平衡量,即让初值进入到牛顿法的收敛域内,再用牛顿法进行迭代计算出潮流解。

平直启动法不需要额外的计算步骤,直流潮流法只需一步计算。而PQ分解法、高斯 - 塞德尔法和部分功率法则都具有迭代步骤。为了保证初值给定朝着不平衡量减小的方向进行,对于上述三种方法,若第k步迭代所得的最大不平衡量满足,则将UN作为输出初值。

由于计算核心方法为牛顿法,因此可以与成熟( 如稀疏) 技术有机衔接,使该方法符合工程实际。其优点在于只需要对给定初值方法的迭代过程进行简单的控制,而不用增加牛顿法的程序处理,程序复杂程度显著减小。计算的输入输出模式和流程分别如图1和图2所示。

4算例分析

潮流数值计算过程中出现的病态问题,主要包括系统含有小阻抗支路和重负荷等2种情况[9]。本文针对上述两种情况导致的病态系统均作了计算分析。

4.1含小阻抗支路的病态系统

本文对含有小阻抗支路的6节点系统[6]、IEEE9节点系统和IEEE39节点系统进行了计算分析。

图3为6节点系统,为2个电源通过1台三绕组变压器向2个负荷供电,三绕组变压器中压绕组( 支路4-6) 的等值电抗为小阻抗支路,线路参数和节点数据已在图3中标识,未标明单位者均为标幺值。

图4为IEEE9节点系统。本文将网络参数进行了一定的修改,将每条支路的R/X进行了适当放大, 其取值范围为(1/10、15/1)。

图5为IEEE39节点系统,本文根据实际情况对部分支路的R/X进行了适当修改,其取值范围为(1/5、5/1),此时系统已经呈现一定规模的较严重的小阻抗支路病态情况。

计算的收敛判据为功率误差小于或等于10-5MW。数值计算结果如表1所示。

由表1可知,采用平直启动法时,三个含小阻抗支路病态系统的潮流计算均不收敛。但采用其他四种方法给定初值时,计算收敛性得到改善。由结果可知,初始最大不平衡功率的大小与迭代次数有一定的相关性。一般来说,初始最大不平衡功率越小,对收敛越有利,迭代次数越少。四种初值给定方法都明显减小了初始最大不平衡功率。这也说明, 给定的初值更逼近潮流解,因此迭代次数出现了明显下降。另一方面,迭代次数也不完全随不平衡功率的减少而减少,还受到迭代路径的影响。例如, 在IEEE39节点系统的计算中,利用部分功率法给定初值时系统的初始最大不平衡功率小于高斯- 塞德尔法对应的功率,但其迭代次数却多于高斯- 塞德尔法。对比除平直启动法外的其他四种初值给定方法可知,部分功率法对于减少初值最大不平衡功率效果最为明显,高斯- 塞德尔法次之。PQ分解法所给出的初值虽能改善收敛特性,但其对牛顿法迭代次数的降低效果要稍弱于其他方法。这可能是因为较高的R /X破坏了PQ分解法使用的前提。因此,在含小阻抗支路的病态潮流计算时,也需充分考虑PQ分解法自身的收敛性。结果充分说明,采用适当的方法给定牛顿法迭代的初值可以有效解决含小阻抗支路系统的病态潮流问题。

4.2重负荷病态系统

随着系统负荷的不断加重,其节点电压随之下降。如果系统是小干扰稳定的并且是电压稳定的, 系统潮流解存在。当电力系统运行在极限稳定边界时,潮流方程的雅可比矩阵接近奇异,牛顿法的收敛范围减小。由于收敛域发生很大变化,平直启动往往很难收敛[7]。因此,给出合理的初值对重负荷病态系统的潮流计算很有意义。

为分析不同初值给定方法对重负荷病态潮流的作用,再以IEEE39节点标准系统为算例,以两种不同的方式修改负荷水平。第一种方式为 :保持节点3的功率因数不变,将节点3上的负荷增至原来的6.2倍,该系统记为IEEE39节点系统1。第二种方式为 :保持各节点功率因数不变,提升系统的整体负荷水平。同时,等倍数地增加发电机的有功出力。本文采用这种方式将IEEE39节点系统的负荷水平提升至标准数据的2.3倍,此时系统记为IEEE39节点系统2。上述两个系统计算收敛判据为功率误差小于或等于10-5MW(Mvar)。

同样,保持韶关电网461节点实际系统各节点负荷的功率因数不变,将其负荷水平和发电机有功出力提升至原来的1.7倍,进行计算分析。考虑到系统规模较前几个系统大,计算收敛判据为最大功率不平衡量小于或等于10 -3 MW(Mvar)。计算结果见表2,其中IEEE39节点系统2的迭代过程如图6所示。

由计算结果可知,在重负荷病态系统的潮流计算中,直流潮流法、PQ分解法、高斯- 塞德尔法和部分功率法对于改善牛顿法潮流计算的收敛性都有较为明显的作用。其中,部分功率法给出的初值带来的不平衡功率最小,因此它使迭代次数降低最多。特别是在单点过负荷的病态系统(IEEE39节点系统1) 中,最大不平衡功率只有0.002 Mvar,且使用牛顿法计算1次即达到收敛。在韶关461节点实际系统中,部分功率法同样体现出了极大的优势。因此,在过负荷导致的病态潮流计算中,采用部分功率法给定初值可以有效地改善潮流计算的收敛性。

5结语

本文针对牛顿- 拉夫逊法进行潮流计算时的初值敏感问题,使用多种方法来进行初值给定。通过在6节点、IEEE9、IEEE39等多个系统的仿真和韶关系统潮流计算实例分析,可得如下结论:

(1) 平直启动法给定初值最为简单,但其在应对含有小阻抗支路或者重负荷病态系统的潮流计算时收敛性不够理想。

(2) 在进行含小阻抗支路的病态系统潮流计算时,直流潮流法、PQ分解法、高斯- 塞德尔法和部分功率法均能改善其计算收敛性。其中,部分功率法和高斯- 塞德尔法的改善效果最为显著。

(3) 计算重负荷病态系统潮流时,部分功率法在减少初始最大不平衡功率和迭代次数方面有着较大优势。