常见最优潮流算法分析

ｈ（ｕ，ｘ）≤０ 式中：ｆ 为优化的目标函数，可以是电力系统的发电费用函数，发电 燃料，系统的有功网损，无功补偿的经济效益等；ｇ 为等式约束条件，即 节点的注入潮流平衡；ｈ 为电力系统的各种安全约束条件，包括节点电 压约束，发电机节点的有功功率约束，支路潮流约束，变压器变比约束， 可变电容器约束，线路两端的电压相角差约束等；ｕ，ｘ 为电力系统的输 入变量和状态变量。 六十年代初期，法国学者 Ｊ．Ｃａｐｅｎｔｉｅｒ 首先提出了建立在严格的数 学基础上的最优潮流模型。随后的四十年里，广大学者对最优潮流问题 做了大量的工作和研究。在这些研究工作中，一部分是采用不同的目标 函数或包含不同的约束条件从而构成不同应用范围的最优潮流模型， 另外一部分工作是从改善收敛性能和提高计算速度的角度，提出了求 解最优潮流的各种计算方法。 １． 线性规划法 线性规划是数学规划的一个重要分支，它在理论和实践上都比较 成熟，因而应用十分广泛。线性规划法是在一组线性约束条件下，寻找 线性目标函数的最大值或最小值的优化方法。一般线性规划问题用矩 阵表示如下：
然不小。 为了解决以上问题，从 ２０ 世纪 ９０ 年代以来，人们尝试用内点法求
解最优潮流问题。目前它已被扩展应用于求解二次规划和非线性规划， 成为解决最优潮流问题的最新算法。具体来讲，内点法主要有三大类算 法：投影尺度法（ｐｒｏｊｅｃｔｉｖｅ ｓｃａｌｉｎｇ，即 Ｋａｒｍａｒｋａｒ 原型算法）、仿射尺度法 （ａｆｆｉｎｅ ｓｃａｌｉｎｇ）和路径跟随法 （ｐａｔｈ ｆｏｌｌｏｗｉｎｇ，又称原—对偶内点算法）。投 影尺度法实用性较差，在实际应用中较少使用；仿射尺度法在确定初始 内点可行解时比较复杂，并且在最优点附近收敛速度较慢；而原—对偶 内点算法收敛迅速，鲁棒性强，对初值的选择不敏感，是目前广泛使用 的一种内点算法。原—对偶路径跟踪内点法的基本思路是在保持解的 原始可行性和对偶可行性的同时，沿 ２ 条原 － 对偶路径寻到最优解，而 在此过程中能始终维持原始解和对偶解的可行性。文献［５］以原 － 对偶 内点法为基本算法解算最优潮流问题，综合考虑非线性目标函数和约 束条件，结合牛顿法最优潮流先进的稀疏矩阵技术，提出了一种新的原 － 对偶内点算法，确立了迭代步长选取原则和障碍参数修正策略。
２．３ 内点法 １９８４ 年，印度数学家 Ｎ．Ｋａｒｍａｒｋａｒ 提出了在线性规划中具有多项 式时间复杂度的算法，即内点法。内点法最初是作为一种线性规划算 法，是为了解决单纯形法计算量随变量规模急剧增加而提出来的。它本 质上是拉格朗日函数、牛顿法和对数障碍函数法三者的结合。内点法的 迭代次数和系统规模无关且始终在可行域内部寻优；并且在可行域边 界设置一道障碍，当迭代靠近边界时函数值陡增，使迭代点始终位于可 行域内部，因此也称之为障碍函数法。 考虑线性问题的一般形式：
ｍｉｎ ＣＸ ｓ．ｔ． ＡＸ＝ｂ
Ｘ≥０ 其中 Ａ 是 ｍ×ｎ 矩阵，Ｃ 是 ｎ 维行向量，ｂ 是 ｎ 维行列向量。 １．１ 单纯形法和对偶单纯形法 求解线性规划问题最基本的方法是单纯形法和对偶单纯形法。单 纯形法的基本思路是从一个基本可行解出发，求一个使目标函数有所 改善的基本可行解；通过不断改进基本可行解，力图达到最优基本可行 解。它是 Ｇ．Ｂ．Ｄａｎｔｚｉｇ 在 １９４７ 年提出来的，后来许多学者又对其进行了 改进，如修正单纯形法。修正单纯形法的基本思路是给定初始基本可行 解后，通过修改旧基的逆来获得新基的逆，进而完成单纯形法的其他运 算。对偶单纯形的基本思路是从原问题的一个对偶可行的基本解出发， 求改进的对偶可行的基本解，当得到的对偶可行的基本解是原问题的 可行解时，就达到最优解。在使用单纯形法和对偶单纯形法求解线性规 划问题时，每次迭代都要把整个表格重新计算一遍，不必要地计算了 许多与迭代过程无关的数据，从而使计算机的存贮量大，计算量也大。 文献［１］研究了线性规划对偶单纯形法的改进。通过改进原始的单 纯形法思想，建立了标准型线性规划对偶单纯形法的一种改进算法。与 原对偶单纯形法相比，改进算法的存贮量和计算量大大减少。文献［２］ 给出了一种可以避免退化情况的单纯型方法和对偶单纯型方法。
当前，对牛顿法最优潮流的研究已经进入实用化阶段。估计起作用 的不等式约束集是实施牛顿法的关键，采用特殊的线性规划技术处理 不等式约束能使牛顿法最优潮流经过少数几次主迭代便得到收敛。文 献［３，４］对最优潮流牛顿算法实际应用中的两个主要困难分别作了详尽 的分析研究，并提出了相应的处理对策。
牛顿法的优点（： １）不但利用了目标函数的一阶导数，而且还利用了 目标函数的二阶导数；（２）考虑了梯度变化的趋势，所得到的搜索方向 比梯度法好，能较快地找到最优点；（３）不区分状态变量和控制变量，充 分利用了电力网络的物理特征，运用了稀疏解算技术，直接对拉格朗日 函数的 Ｋｕｈｎ－Ｔｕｃｋｅｒ 条件进行牛顿法迭代求解，收敛快速；（４）基于全空 间优化，如果初值选好，海森阵正定，收敛速度更快。缺点： （１）要求目标 函数是二阶连续可微的；（２）每次迭代都需计算海森阵及其逆阵，计算量 大，必须结合稀疏矩阵技术求解；（３） 用试验迭代法确定有效约束集，编 程实现困难；（４） 对应控制变量的 Ｈｅｓｓｉａｎ 阵对角元易出现小值或零值， 造成矩阵奇异；（５） 引入的 Ｌａｇｒａｎｇｅ 乘子的初值对迭代计算的稳定性影 响很大。
— ４１７ —
科技信息
高校理科研究
有二阶收敛速度的算法。牛顿法的难点在于对违约不等式约束的处理。 在迭代过程中，由于中间变量一般不满足潮流方程，所以要对中间变量 修正。修正后，又无法判断不等式约束是否越界，因而也就无法形成罚 函数，最终会明显改变计算结果。对违约不等式约束的处理方式目前有 两种：（１） 逐次迭代修正法；（２） 起作用的不等式约束集法（在最优点处化 为等式约束）。但决定起作用的不等式约束集是非常复杂困难的，必须 采用试探法求解。牛顿法的另一个难点是对应控制变量的 Ｈｅｓｓｉａｎ 阵对 角元易出现小值或零值，造成矩阵奇异。
引言 所谓最优潮流（Ｏｐｔｉｍａｌ Ｐｏｗｅｒ Ｆｌｏｗ）就是指当电力系统的结构参数 和负荷情况给定时，通过控制变量的优化选择，找到能够满足所有约束 条件并使系统某一性能指标和目标函数达到最优时的潮流分布。电力 系统最优潮流的历史发展过程可以追溯到二十世纪 ６０ 年代初期。基于 协调方程的经典经济调度方法虽然方法简单，计算速度快，适应实时计 算，但是协调方程式不能计及安全性约束（包括节点电压越界及线路过 负荷等）。随着电力系统规模的不断扩大和特大事故的不断发生 （如 １９７７ 年美国纽约网的停电事故和 １９７８ 年法国全国大停电事故），人们 开始将经济性和安全性统一考虑起来。而以数学规划为模型的最优潮 流能够很好地处理约束条件。它不但能在模型中引入凡是表示成状态 变量和控制变量函数的各种不等式约束条件，而且能将电力系统对于 经济性、安全性和电能质量这三个指标完美地统一起来。因而，自从诞 生之初，最优潮流就得到高度重视。 最优潮流是一个多变量的多约束条件的非线性的规划问题，它的 数学模型一般可以概括为： 目标函数：ｍｉｎｆ（ｕ，ｘ） 约束条件：ｇ（ｕ，ｘ）＝０
科技信息
高校理科研究
常见最优潮流算法分析
山东科技大学 ２００６ 级研究生 刘晓东

［摘 要］最优化理论和算法是一个重要的数学分支，它研究的问题是讨论如何在众多的方案中找出最优方案的方法。这类问题普 遍存在。其中对于电力系统来说，最优潮流就属于这类问题。随着最优化理论的发展，最优潮流的算法层出不穷。本文回顾了近二 十年来最优潮流的逐步发展的过程，较为详细地分析了几种经典的优化方法，同时总结了各种优化方法的优缺点，并对最优潮流的 进一步发展进行了深入的探讨。 ［关键词］最优潮流 线性规划 非线性规划
ｍｉｎ ｆ（ｘ） ｓ．ｔ． Ａｘ≥ｂ
Ｅｘ＝ｅ 其中 ｆ（ｘ）为目标函数，Ａ 为 ｍ×ｎ 矩阵，Ｅ 为 l×ｎ 矩阵，ｂ 和 ｅ 分别为 ｍ 维和 l 维列向量。在非线性规划方法中，最突出的几种方法是简约梯 度法、牛顿法和内点法。二次规划法是非线性规划方法中的特殊情况。 ２．１ 简化梯度法 简化梯度法是第一种能够较好地求解较大规模最优潮流问题的算 法。梯度法实际上等同于无约束问题的最速下降法，它的基本思想是从 一个迭代点出发，选择目标函数值下降最快的方向作为最优方向，以便 尽快达到极小点。目标函数值下降最快的方向是负梯度方向，梯度法因 此得名。１９６８ 年 Ｄｏｍｍｅｌ 和 Ｔｉｎｎｅｙ 在进行优化计算时利用牛顿拉夫逊 潮流程序，采用梯度法进行搜索，用罚函数处理违约的不等式约束。该 方法程序设计简便，所需存储量小，对初始点无特殊要求，而且能够较 好地求解较大规模最优潮流问题，所以成为第一种有效的优化潮流方 法。由于该法仅在控制变量子空间上寻优，故称为简化梯度法。 简化梯度法提出后，Ｐｅｓｃｈｏｎ 在 １９７１ 年随后提出了广义简化梯度 法（ＧＲＧ）。ＧＲＧ 法在处理函数不等式约束时，并不像简约梯度法采用罚 函数处理违约的不等式约束，而是在发现约束被破坏时将关联的控制 变量与状态变量暂时对调，并再计算一次潮流，继续进行优化。 该算法优点（： １）原理简单直观；（２） 具有一阶收敛性，程序设计比较 简单，存储需求比较小。缺点：（１）在迭代过程中会出现锯齿现象，收敛 性较差，尤其是在接近最优点附近收敛速率很慢，当目标函数的 Ｈｅｓ－ ｓｉａｎ 矩阵的条件数（Ｈｅｓｓｉａｎ 矩阵的最大最小特征值之比） 较大时，算法 的收敛性进一步变坏；（２）其状态变量维数较高，即每次迭代都要重新 计算潮流，计算量很大，计算效率很低；（３）当采用罚函数处理不等式 时，罚因子数值的选取对算法的收敛速度影响很大。 虽然简约梯度法存在着很大缺点，如今在最优潮流计算中很少应 用，但它是求解较大规模最优潮流问题成功的首例，为后来的最优潮流 算法发展奠定了基础。 ２．２ 牛顿法 牛 顿 法 是 １９８４ 年 由 Ｄ．Ｉ．Ｓｕｎ 提 出 的 ， 它 是 一 种 直 接 求 解 Ｋｕｈｎ－Ｔｕｃｋｅｒ 等式寻优的方法，它的出现是最优潮流发展过程中的一次 飞跃。相比简化梯度法，牛顿法具有更好的收敛性，这在于它是一种具
ｍｉｎ ｃｘ ｓ．ｔ． Ａｘ≤ｂ 其中 ｃ，ｘ∈Ｒｎ，Ａ 是 ｍ×ｎ 矩阵。内点法的基本思想是从内点出发，沿 可行方向求出使目标函数值下降的后继内点，再从得到的内点出发，沿 另一个可行方向求出使目标函数值下降的内点，重复以上步骤，得出一 个由内点组成的序列，使得目标函数值严格单调下降，当满足终止条件 时停止迭代。 虽然用梯度法与牛顿法求解大规模电力系统问题已不太困难，但 是这些方法在处理不等式约束集方面仍有困难。解决的方法有罚函数 法、乘子罚函数法、ＧＲＧ 法和积极约束集启发式策略法。罚函数法在罚 因子增大时，容易造成 Ｈｅｓｓｉａｎ 矩阵条件数过大的病态；乘子罚函数法 的罚因子选择对于不同的系统需要进行大量的试探工作，同时在处理 的不等式约束过多时，容易出现交替违反的现象；ＧＲＧ 法在状态变量和 控制变量的划分上变动频繁，给计算带来一定的难度；积极约束集启发 式策略法，虽然一些改进策略使得对于识别起作用不等式约束集的工 作得到一定进展，然而伴随着约束的进入与退出起作用集，其计算量仍