线性约束优化问题的相容解优化法及其应用

丘文千， 丘 凌

（1.浙江省电力设计院，杭州 310012；2.国网浙江省电力公司经济技术研究院，杭州 310008）

线性约束优化问题的相容解优化法及其应用

丘文千1， 丘 凌2

（1.浙江省电力设计院，杭州 310012；2.国网浙江省电力公司经济技术研究院，杭州 310008）

给出一种求解线性约束优化问题的数值方法，利用广义逆矩阵方法求取与线性约束条件等价的线性不定方程组的相容解集合，并利用粒子群优化算法直接在相容解集合中寻优，称之为相容解优化法或相容解直接优化法，可用于求解线性规划问题，也可用于求解具有线性约束的非线性规划问题。该方法具有算法简捷、数值稳定性好等特点，对于具有线性约束的非线性规划问题，比一般的非线性规划方法更快捷有效。结合相容解优化法在直流偏磁限流电阻优化计算的应用实例，验证了方法的有效性和实用性。

最优化方法；广义逆矩阵；粒子群优化方法；限制短路电流；抑制直流偏磁

1 线性约束的最优化问题

线性约束优化问题是指如下形式的有约束优化问题：

式中：A为m×n矩阵；x为n维列向量；b为m维列向量；xmin和xmax分别为x取值的下限和上限。

在以上公式中，目标函数f（x）可以是线性函数，也可以是非线性函数，式（2）为线性约束条件，式（3）为变量取值范围限制。显然，最优化方法中的线性规划和二次规划都是线性约束优化问题的特例。对于线性约束优化问题，如果目标函数f（x）为线性函数，式（3）为变量x的非负条件，即得到如下线性规划模型：

线性规划是研究线性约束条件下线性目标函数极值问题的数学理论和方法，是运筹学中研究较早、发展较快、应用广泛、较为成熟的一个重要分支。工业、农业、运输、资源配置、军事、经济管理等众多领域的优化问题通过建立线性规划模型得到求解，在实际应用中发挥着非常重要作用。线性规划有较多限制，如变量非负条件、线性目标函数等要求，都限制了其应用范围。如果这些要求不能满足，如目标函数为非线性函数f（x），则成为具有线性约束的非线性规划问题。特别地，如果目标函数f（x）为二次函数，则得到二次规划模型[1]如下：

式中：H为n×n对称正定矩阵；c为n维列向量。

二次规划是非线性规划的一类特殊问题，求解方法相对成熟，在很多方面都有应用，已经成为运筹学、经济数学、管理科学、系统分析和组合优化科学的基本方法。但对于一般的具有线性约束的非线性规划问题，需要采用非线性规划方法求解，增加了求解难度。

对于上述线性约束优化问题，本文给出一种基于广义逆矩阵[2]的数值方法，即利用广义逆矩阵方法求取线性不定方程组的相容解集合，并利用粒子群优化算法直接在相容解集合中寻优，故称之为相容解优化法或相容解直接优化法，可用于求解线性规划问题，也可用于求解具有线性约束的非线性规划问题。相容解优化法对于变量没有非负条件要求，变量上下限处理[3]方便，并具有算法简捷、数值稳定性好等特点，因此比线性规划方法的适用范围更广，而对于具有线性约束的非线性规划问题，则比一般的非线性规划方法更快捷有效。

2 粒子群优化算法

粒子群优化算法[4]是一类基于群体智能的启发式优化方法。在粒子群优化算法中，优化问题的可行解被表示为搜索空间中粒子的空间位置q，优化问题的目标函数值被表示为粒子的适应度值，优化搜索过程通过粒子在搜索空间中的飞行改变其空间位置q来实现，因此每个粒子有一个速度v决定其飞行方向和距离。执行粒子群优化算法时，先随机赋予D维空间的M个粒子（粒子群规模）的初始位置q（0）和初始速度v（0），然后通过一个迭代算法搜索其最优解。在迭代过程中，根据粒子群的个体极值和全局极值来更新每个粒子的速度和位置。粒子群的个体极值是指每个粒子自身迄今所达到的最优解，表示为pi（k）=（pi1（k），…，piD（k）），其中的k为迭代次数；粒子群的全局极值是指整个粒子群迄今所达到的最优解，表示为 pg（k）=（pg1（k），…，pgD（k））。 对于第k+1次迭代计算，粒子i根据式（10）和式（11）来更新其速度 vi（k+1）=（vi1（k+1），…，viD（k+1））和位置qi（k+1）=（qi1（k+1），…，qiD（k+1））：

式中：ω称为惯性权重，ω＜1；c1，c2称为加速常数（或学习因子）；r1，r2为[0，1]之间的独立随机数。

在式（10）中，较大的ω能增加粒子的飞行距离，可以加速粒子搜索新的区域，一般可在初期采用较大数值，后期采用较小数值；c1，c2分别调节向全局极值方向和个体极值方向的飞行步长，在优化搜索初期，将c1设定大些，c2设定小些，使粒子具有较强的全局最优搜寻能力，随着迭代次数的增加，c1逐渐减小，c2逐渐增大，使粒子具有较强的局部最优搜寻能力。

粒子群优化算法迭代过程的中止，一般遵循以下准则：

（1）全局极值达到预期的优化目标。

（2）经过多次迭代运算，全局极值趋于稳定，不再下降（求最小值）或上升（求最大值）。

（3）迭代次数达到规定的最大迭代数。

粒子群优化算法简单，易于实现，并具有计算速度快、收敛性和数值稳定性好等特点，特别适合解决一些非线性、多维变量、不可微、多峰值的复杂优化问题。

3 相容解优化法

为便于讨论，将线性约束优化问题变换为如下标准形式：

式中：A为任意m×n矩阵，一般m≠n；x为n维列向量；b为m维列向量。

根据广义逆理论，若线性方程组Ax=b是相容的，则x=A-b是方程组Ax=b的一个特解，A-是矩阵A的任一个g逆，而x=A-b+（I-A-A）q则是线性方程组Ax=b的一般解，q是与x同维的任意向量[2]。因此可将式（12）—（14）变换为等价的优化模型：

式（16）即为线性方程组Ax=b的相容解表达式，从方程组Ax=b的任一特解x=A-b出发，由任意的一组向量q即可求得对应的一组相容解x。对式（17）可采用罚函数法处理。与粒子群优化算法结合，相容解优化法的具体步骤如下：

（1）求得A-b和（I-A-A）。

（2）随机产生与x同维的向量q，由式（16）求得相容解x，共需产生M组相容解x。

（3）按式（10）、式（11）更新向量q，由式（16）求得相容解x。

（4）满足中止准则就结束计算，否则转步骤3。

在上述优化过程中，需多次反复运用式（16）由q计算x，如果Ax=b为常系数线性方程组，则其中A-b和（I-A-A）的数值在优化过程中都固定不变，在求取相容解x时仅需要一些乘法和加法运算，显然比每次直接求解式（13）更为方便快捷。

4 在直流偏磁限流电阻优化中的应用

4.1 研究背景

高压直流输电系统在单极-大地回路运行方式下，直流电流经换流站接地极入地，巨大的直流电流在邻近的交流电网接地点感应出很高的直流电位，在变压器绕组和输电线路形成直流通道中产生直流电流，流经变压器绕组的直流电流会产生变压器直流偏磁现象[5，6]，给变压器和交流电网的安全运行造成诸多不良影响[7-9]。为抑制流经变压器绕组的直流电流，串接电阻法是较为可行有效的解决方案，即在变压器中性点和地网之间串入一个阻值为数欧姆的限流电阻，使流入变压器中性点的直流电流减小到工程上可接受的程度。但限流电阻会改变电网直流电流的分布，甚至导致某些支路直流电流放大，因此，对配置方案必须进行系统分析研究。

4.2 建立模型

在针对特高压直流输电工程落点后对浙江电网的直流偏磁影响课题研究中，为实现从系统整体上优化限流电阻的配置，达到抑制直流偏磁电流、减少限流电阻装置对系统影响和配置费用较少的优化目标，提出了直流偏磁电流分布的解耦计算方法，并在此基础上建立了限流电阻优化配置模型，其约束条件为满足系统电路方程（包括地上部分和地下部分）、变压器直流偏磁电流不超限值、限流电阻不超限值等，优化目标可选择偏磁电流平方和最小，或偏磁限流电阻的代数和最小，或系统中接入的偏磁限流电阻个数最少，或上述目标的组合[4，10]。

式（18）为目标函数式，模型以偏磁电流平方和与限流电阻代数和的组合为目标函数；式（19）为系统电路方程；式（20）为系统偏磁电流约束条件；式（21）为限流电阻约束条件。

式中：a1，…，al，b1，…，bm和 q1为权重系数；gij表示直流网络节点导纳矩阵i行j列元素；ui为节点i的直流电位；ci为节点i的直流注入电流；n为系统节点数；dk为变压器支路k的偏磁电流；dk，max为dk的最大容许值；l为系统中变压器支路数；rg和 rg，max分别为限流电阻及其上限值；m为可接入个数；m1为实际接入数；pg为离散变量，pg={0，1}，pg=1表示接入限流电阻，pg=0表示不接入。

由于公式中包含了离散变量pg，增加了问题的复杂性，用传统优化方法求解比较困难。

4.3 优化方法

上述模型中，系统电路方程的系数矩阵随着优化过程中限流电阻的改变而变化，一般方法需要在优化过程中反复求解模型中的n阶系统电路方程。若采用粒子群优化算法，假定粒子群规模为M，最大迭代次数为N，优化过程中需要求解n阶线性方程组M×N次（如用高斯消去法求解，每次所需要的乘除法次数为由于研究系统规模大，计算量非常庞大。为此，运用相容解优化法对上述模型进行改进，先将系统中l个变压器支路的电流作为变量引入系统电路方程，引入新变量后系统电路方程数n不变，变量数为n+l（n个节点直流电位和l个变压器支路电流），将系统电路方程由变系数线性方程组变换为等价的常系数线性不定方程组，然后运用广义逆矩阵方法直接从其相容解中求得满足要求的优化解。具体如下：

对于支路k（两端节点为p和q），电流dk（从p到q为正）为：

因此可得：

对于系统中的l个变压器支路，若以dk（k=1，…，l）表示变压器支路k的偏磁电流，并假定支路1两端节点为a和b，支路l两端节点为r和s，以ui（i=1，…，n）及dk（k=1，…，l）为变量，可用矩阵形式表示如下：

式（26）的方程数为n，变量数为n+l，当l≥1时为线性不定方程，可表示为Ax=b，优化模型具有式（12）—（14）的形式，可运用相容解优化法求解。求得满足要求的优化解x后，按下式求取限流电阻：

式中：rk为p-q支路（支路k）的电阻，rk=-1/gpq；rg为p-q支路中须接入的限流电阻。

同样，采用粒子群优化算法，相容解优化法在优化过程中需按式（16）计算相容解x共M×N次，由于A-b和（I-A-A）的数值都固定不变，仅要求计算1次，其后每次按式（16）求取相容解x仅需少量的乘法和加法运算，且q中与rg无关的分量可取0，所需乘除法次数仅为（n+l）×m次，远小于采用高斯消去法求解每次所需要的乘除法次数，因而计算速度非常快。

4.4 应用效果

以某规划特高压直流输电受端系统为研究对象，分析单极-大地回路方式下地中电流在电网的分布规律以及对变压器的偏磁影响，网络规模为47个节点、65个支路，其中变压器支路35个，限流电阻可接入支路13个[10]。文献[10]中提出3种具体的算法：对其中0～1变量的计算值与设定的阈值比较后取整的粒子群优化算法；将普通粒子群优化算法与二进制粒子群优化算法相结合的混合型粒子群优化算法；将粒子群优化算法与遗传算法相结合的混合优化算法。对此算例和3种算法，运用相容解优化法改进前后计算结果相同，但改进后的计算速度可提高数十倍。改进前的优化时间分别为51 s，51 s和6 416 s，运用相容解优化法改进后分别为1 s，1 s和104 s。

实际上，粗略分析2种方法的计算量也可以说明这一点。在本例中，n=47，l=35，m=13，采用高斯消去法，每次求解n维线性方程组的乘除法次数为36 801次，而采用相容解优化法，每次计算相容解x的乘除法次数仅1 066次，两者之比为34.5，这就是相容解优化法计算效率高的原因。如果算题规模增加一倍，即n=94，l=70，m= 26，2种算法的乘除法次数之比为67.0，可见算题规模越大，相容解优化法的计算效率越高。在短路限流器配置与优化中的应用也证明了相容解优化法的有效性和实用性[12]。

5 结语

本文给出了求解线性约束优化问题的相容解优化法，可用于求解线性规划、二次规划以及具有线性约束的非线性规划问题，具有算法简捷、计算速度快、数值稳定性好等特点。通过在直流偏磁限流电阻优化中的应用，验证了该方法的有效性和实用性，运用相容解优化法改进后，计算速度可提高数十倍，效果非常显著，满足了研究课题计算分析的要求。

[1]陈宝林．最优化理论与算法（第2版）[M]．北京：清华大学出版社，2005.

[2]杨篪引，马正午，孙宇，等．电子计算机应用数学[M]．北京：冶金工业出版社，1979.

[3]何建坤，江道琪，陈松华．实用线性规划及计算机程序[M]．北京：清华大学出版社，1985.

[4]丘文千．电力系统优化规划模型与方法[M]．杭州：浙江大学出版社，2012.

[5]陈晴，陶佳，丘文千．变压器直流偏磁现象及其抑制装置的设计[J]．电力建设，2012，33（11）∶33-36.

[6]皇甫成，阮江军，张宇，等．变压器直流偏磁的仿真研究及限制措施[J]．高电压技术，2006，32（9）∶117-120.

[7]张英．直流输电系统接地极电流对交流变压器的影响及抑制措施[J]．广东电力，2008，21（4）∶28-31.

[8]袁春峰，周行星，顾承昱，等．多回直流输电系统地下电流场对长三角地区电网的影响[J]．华东电力，2008，36（11）∶29-32.

[9]蒋伟，吴广宁，黄震，等．特高压直流输电系统的地中电流对变压器的影响及其计算[J]．高压电器，2008，44（6）∶534-536，540.

[10]丘文千．直流偏磁计算与限流电阻优化配置方法研究[J]．浙江电力，2013，32（4）∶1-5，27.

[11]易大义，蒋叔豪，李有法．数值方法[M]．杭州：浙江科学技术出版社，1984.

[12]丘凌，丘文千．短路限流器的配置与优化[J]．浙江电力，2014，33（8）∶4-9.

（本文编辑：方明霞）

Compatible Solutions Optimization Method for Linear Constrained Optimization Problem and Its Application

QIU Wenqian1，QIU Ling2
（1.Zhejiang Electric Power Design Institute，Hangzhou 310012，China；2.State Grid Zhejiang Economy Research Institute，Hangzhou 310008，China）

The paper presents a numerical method for solving linear constrained optimization problems，called compatible solutions optimization method or compatible solutions direct optimization method，which uses the generalized inverse matrix method to calculate the compatible solutions set of the linear indefinite equations which are equivalent to the linear constraints to find the optimal solution directly from the compatible solutions set by particle swarm optimization algorithm.The method can be used to solve the linear programming problem and nonlinear programming problems with linear constraints.The method is characterized by its simple algorithm and numerical stability，so it is faster and more efficient than any other methods in solving nonlinear programming problems with linear constraints.In accordance with the application of compatible solutions optimization method in optimized calculation of DC bias current-limiting resistor，the paper verifies that the method is effective and practicable.

optimal method；generalized inverse matrix；particle swarm optimization；short circuit current limiting;inhibition of DC bias

TM744

A

1007-1881（2015）12-0034-05

2015-06-02

丘文千（1952），男，教授级高级工程师，从事电力系统规划、工程设计与技术管理工作。