線性約束優(yōu)化問題的相容解優(yōu)化法及其應(yīng)用

丘文千， 丘 凌

（1.浙江省電力設(shè)計院，杭州 310012；2.國網(wǎng)浙江省電力公司經(jīng)濟技術(shù)研究院，杭州 310008）

線性約束優(yōu)化問題的相容解優(yōu)化法及其應(yīng)用

丘文千1， 丘 凌2

（1.浙江省電力設(shè)計院，杭州 310012；2.國網(wǎng)浙江省電力公司經(jīng)濟技術(shù)研究院，杭州 310008）

給出一種求解線性約束優(yōu)化問題的數(shù)值方法，利用廣義逆矩陣方法求取與線性約束條件等價的線性不定方程組的相容解集合，并利用粒子群優(yōu)化算法直接在相容解集合中尋優(yōu)，稱之為相容解優(yōu)化法或相容解直接優(yōu)化法，可用于求解線性規(guī)劃問題，也可用于求解具有線性約束的非線性規(guī)劃問題。該方法具有算法簡捷、數(shù)值穩(wěn)定性好等特點，對于具有線性約束的非線性規(guī)劃問題，比一般的非線性規(guī)劃方法更快捷有效。結(jié)合相容解優(yōu)化法在直流偏磁限流電阻優(yōu)化計算的應(yīng)用實例，驗證了方法的有效性和實用性。

最優(yōu)化方法；廣義逆矩陣；粒子群優(yōu)化方法；限制短路電流；抑制直流偏磁

1 線性約束的最優(yōu)化問題

線性約束優(yōu)化問題是指如下形式的有約束優(yōu)化問題：

式中：A為m×n矩陣；x為n維列向量；b為m維列向量；xmin和xmax分別為x取值的下限和上限。

在以上公式中，目標函數(shù)f（x）可以是線性函數(shù)，也可以是非線性函數(shù)，式（2）為線性約束條件，式（3）為變量取值范圍限制。顯然，最優(yōu)化方法中的線性規(guī)劃和二次規(guī)劃都是線性約束優(yōu)化問題的特例。對于線性約束優(yōu)化問題，如果目標函數(shù)f（x）為線性函數(shù)，式（3）為變量x的非負條件，即得到如下線性規(guī)劃模型：

線性規(guī)劃是研究線性約束條件下線性目標函數(shù)極值問題的數(shù)學(xué)理論和方法，是運籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、較為成熟的一個重要分支。工業(yè)、農(nóng)業(yè)、運輸、資源配置、軍事、經(jīng)濟管理等眾多領(lǐng)域的優(yōu)化問題通過建立線性規(guī)劃模型得到求解，在實際應(yīng)用中發(fā)揮著非常重要作用。線性規(guī)劃有較多限制，如變量非負條件、線性目標函數(shù)等要求，都限制了其應(yīng)用范圍。如果這些要求不能滿足，如目標函數(shù)為非線性函數(shù)f（x），則成為具有線性約束的非線性規(guī)劃問題。特別地，如果目標函數(shù)f（x）為二次函數(shù)，則得到二次規(guī)劃模型[1]如下：

式中：H為n×n對稱正定矩陣；c為n維列向量。

二次規(guī)劃是非線性規(guī)劃的一類特殊問題，求解方法相對成熟，在很多方面都有應(yīng)用，已經(jīng)成為運籌學(xué)、經(jīng)濟數(shù)學(xué)、管理科學(xué)、系統(tǒng)分析和組合優(yōu)化科學(xué)的基本方法。但對于一般的具有線性約束的非線性規(guī)劃問題，需要采用非線性規(guī)劃方法求解，增加了求解難度。

對于上述線性約束優(yōu)化問題，本文給出一種基于廣義逆矩陣[2]的數(shù)值方法，即利用廣義逆矩陣方法求取線性不定方程組的相容解集合，并利用粒子群優(yōu)化算法直接在相容解集合中尋優(yōu)，故稱之為相容解優(yōu)化法或相容解直接優(yōu)化法，可用于求解線性規(guī)劃問題，也可用于求解具有線性約束的非線性規(guī)劃問題。相容解優(yōu)化法對于變量沒有非負條件要求，變量上下限處理[3]方便，并具有算法簡捷、數(shù)值穩(wěn)定性好等特點，因此比線性規(guī)劃方法的適用范圍更廣，而對于具有線性約束的非線性規(guī)劃問題，則比一般的非線性規(guī)劃方法更快捷有效。

2 粒子群優(yōu)化算法

粒子群優(yōu)化算法[4]是一類基于群體智能的啟發(fā)式優(yōu)化方法。在粒子群優(yōu)化算法中，優(yōu)化問題的可行解被表示為搜索空間中粒子的空間位置q，優(yōu)化問題的目標函數(shù)值被表示為粒子的適應(yīng)度值，優(yōu)化搜索過程通過粒子在搜索空間中的飛行改變其空間位置q來實現(xiàn)，因此每個粒子有一個速度v決定其飛行方向和距離。執(zhí)行粒子群優(yōu)化算法時，先隨機賦予D維空間的M個粒子（粒子群規(guī)模）的初始位置q（0）和初始速度v（0），然后通過一個迭代算法搜索其最優(yōu)解。在迭代過程中，根據(jù)粒子群的個體極值和全局極值來更新每個粒子的速度和位置。粒子群的個體極值是指每個粒子自身迄今所達到的最優(yōu)解，表示為pi（k）=（pi1（k），…，piD（k）），其中的k為迭代次數(shù)；粒子群的全局極值是指整個粒子群迄今所達到的最優(yōu)解，表示為 pg（k）=（pg1（k），…，pgD（k））。 對于第k+1次迭代計算，粒子i根據(jù)式（10）和式（11）來更新其速度 vi（k+1）=（vi1（k+1），…，viD（k+1））和位置qi（k+1）=（qi1（k+1），…，qiD（k+1））：

式中：ω稱為慣性權(quán)重，ω＜1；c1，c2稱為加速常數(shù)（或?qū)W習(xí)因子）；r1，r2為[0，1]之間的獨立隨機數(shù)。

在式（10）中，較大的ω能增加粒子的飛行距離，可以加速粒子搜索新的區(qū)域，一般可在初期采用較大數(shù)值，后期采用較小數(shù)值；c1，c2分別調(diào)節(jié)向全局極值方向和個體極值方向的飛行步長，在優(yōu)化搜索初期，將c1設(shè)定大些，c2設(shè)定小些，使粒子具有較強的全局最優(yōu)搜尋能力，隨著迭代次數(shù)的增加，c1逐漸減小，c2逐漸增大，使粒子具有較強的局部最優(yōu)搜尋能力。

粒子群優(yōu)化算法迭代過程的中止，一般遵循以下準則：

（1）全局極值達到預(yù)期的優(yōu)化目標。

（2）經(jīng)過多次迭代運算，全局極值趨于穩(wěn)定，不再下降（求最小值）或上升（求最大值）。

（3）迭代次數(shù)達到規(guī)定的最大迭代數(shù)。

粒子群優(yōu)化算法簡單，易于實現(xiàn)，并具有計算速度快、收斂性和數(shù)值穩(wěn)定性好等特點，特別適合解決一些非線性、多維變量、不可微、多峰值的復(fù)雜優(yōu)化問題。

3 相容解優(yōu)化法

為便于討論，將線性約束優(yōu)化問題變換為如下標準形式：

式中：A為任意m×n矩陣，一般m≠n；x為n維列向量；b為m維列向量。

根據(jù)廣義逆理論，若線性方程組Ax=b是相容的，則x=A-b是方程組Ax=b的一個特解，A-是矩陣A的任一個g逆，而x=A-b+（I-A-A）q則是線性方程組Ax=b的一般解，q是與x同維的任意向量[2]。因此可將式（12）—（14）變換為等價的優(yōu)化模型：

式（16）即為線性方程組Ax=b的相容解表達式，從方程組Ax=b的任一特解x=A-b出發(fā)，由任意的一組向量q即可求得對應(yīng)的一組相容解x。對式（17）可采用罰函數(shù)法處理。與粒子群優(yōu)化算法結(jié)合，相容解優(yōu)化法的具體步驟如下：

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

（2）隨機產(chǎn)生與x同維的向量q，由式（16）求得相容解x，共需產(chǎn)生M組相容解x。

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

（4）滿足中止準則就結(jié)束計算，否則轉(zhuǎn)步驟3。

在上述優(yōu)化過程中，需多次反復(fù)運用式（16）由q計算x，如果Ax=b為常系數(shù)線性方程組，則其中A-b和（I-A-A）的數(shù)值在優(yōu)化過程中都固定不變，在求取相容解x時僅需要一些乘法和加法運算，顯然比每次直接求解式（13）更為方便快捷。

4 在直流偏磁限流電阻優(yōu)化中的應(yīng)用

4.1 研究背景

高壓直流輸電系統(tǒng)在單極-大地回路運行方式下，直流電流經(jīng)換流站接地極入地，巨大的直流電流在鄰近的交流電網(wǎng)接地點感應(yīng)出很高的直流電位，在變壓器繞組和輸電線路形成直流通道中產(chǎn)生直流電流，流經(jīng)變壓器繞組的直流電流會產(chǎn)生變壓器直流偏磁現(xiàn)象[5，6]，給變壓器和交流電網(wǎng)的安全運行造成諸多不良影響[7-9]。為抑制流經(jīng)變壓器繞組的直流電流，串接電阻法是較為可行有效的解決方案，即在變壓器中性點和地網(wǎng)之間串入一個阻值為數(shù)歐姆的限流電阻，使流入變壓器中性點的直流電流減小到工程上可接受的程度。但限流電阻會改變電網(wǎng)直流電流的分布，甚至導(dǎo)致某些支路直流電流放大，因此，對配置方案必須進行系統(tǒng)分析研究。

4.2 建立模型

在針對特高壓直流輸電工程落點后對浙江電網(wǎng)的直流偏磁影響課題研究中，為實現(xiàn)從系統(tǒng)整體上優(yōu)化限流電阻的配置，達到抑制直流偏磁電流、減少限流電阻裝置對系統(tǒng)影響和配置費用較少的優(yōu)化目標，提出了直流偏磁電流分布的解耦計算方法，并在此基礎(chǔ)上建立了限流電阻優(yōu)化配置模型，其約束條件為滿足系統(tǒng)電路方程（包括地上部分和地下部分）、變壓器直流偏磁電流不超限值、限流電阻不超限值等，優(yōu)化目標可選擇偏磁電流平方和最小，或偏磁限流電阻的代數(shù)和最小，或系統(tǒng)中接入的偏磁限流電阻個數(shù)最少，或上述目標的組合[4，10]。

式（18）為目標函數(shù)式，模型以偏磁電流平方和與限流電阻代數(shù)和的組合為目標函數(shù)；式（19）為系統(tǒng)電路方程；式（20）為系統(tǒng)偏磁電流約束條件；式（21）為限流電阻約束條件。

式中：a1，…，al，b1，…，bm和 q1為權(quán)重系數(shù)；gij表示直流網(wǎng)絡(luò)節(jié)點導(dǎo)納矩陣i行j列元素；ui為節(jié)點i的直流電位；ci為節(jié)點i的直流注入電流；n為系統(tǒng)節(jié)點數(shù)；dk為變壓器支路k的偏磁電流；dk，max為dk的最大容許值；l為系統(tǒng)中變壓器支路數(shù)；rg和 rg，max分別為限流電阻及其上限值；m為可接入個數(shù)；m1為實際接入數(shù)；pg為離散變量，pg={0，1}，pg=1表示接入限流電阻，pg=0表示不接入。

由于公式中包含了離散變量pg，增加了問題的復(fù)雜性，用傳統(tǒng)優(yōu)化方法求解比較困難。

4.3 優(yōu)化方法

上述模型中，系統(tǒng)電路方程的系數(shù)矩陣隨著優(yōu)化過程中限流電阻的改變而變化，一般方法需要在優(yōu)化過程中反復(fù)求解模型中的n階系統(tǒng)電路方程。若采用粒子群優(yōu)化算法，假定粒子群規(guī)模為M，最大迭代次數(shù)為N，優(yōu)化過程中需要求解n階線性方程組M×N次（如用高斯消去法求解，每次所需要的乘除法次數(shù)為由于研究系統(tǒng)規(guī)模大，計算量非常龐大。為此，運用相容解優(yōu)化法對上述模型進行改進，先將系統(tǒng)中l(wèi)個變壓器支路的電流作為變量引入系統(tǒng)電路方程，引入新變量后系統(tǒng)電路方程數(shù)n不變，變量數(shù)為n+l（n個節(jié)點直流電位和l個變壓器支路電流），將系統(tǒng)電路方程由變系數(shù)線性方程組變換為等價的常系數(shù)線性不定方程組，然后運用廣義逆矩陣方法直接從其相容解中求得滿足要求的優(yōu)化解。具體如下：

對于支路k（兩端節(jié)點為p和q），電流dk（從p到q為正）為：

因此可得：

對于系統(tǒng)中的l個變壓器支路，若以dk（k=1，…，l）表示變壓器支路k的偏磁電流，并假定支路1兩端節(jié)點為a和b，支路l兩端節(jié)點為r和s，以ui（i=1，…，n）及dk（k=1，…，l）為變量，可用矩陣形式表示如下：

式（26）的方程數(shù)為n，變量數(shù)為n+l，當l≥1時為線性不定方程，可表示為Ax=b，優(yōu)化模型具有式（12）—（14）的形式，可運用相容解優(yōu)化法求解。求得滿足要求的優(yōu)化解x后，按下式求取限流電阻：

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

同樣，采用粒子群優(yōu)化算法，相容解優(yōu)化法在優(yōu)化過程中需按式（16）計算相容解x共M×N次，由于A-b和（I-A-A）的數(shù)值都固定不變，僅要求計算1次，其后每次按式（16）求取相容解x僅需少量的乘法和加法運算，且q中與rg無關(guān)的分量可取0，所需乘除法次數(shù)僅為（n+l）×m次，遠小于采用高斯消去法求解每次所需要的乘除法次數(shù)，因而計算速度非常快。

4.4 應(yīng)用效果

以某規(guī)劃特高壓直流輸電受端系統(tǒng)為研究對象，分析單極-大地回路方式下地中電流在電網(wǎng)的分布規(guī)律以及對變壓器的偏磁影響，網(wǎng)絡(luò)規(guī)模為47個節(jié)點、65個支路，其中變壓器支路35個，限流電阻可接入支路13個[10]。文獻[10]中提出3種具體的算法：對其中0～1變量的計算值與設(shè)定的閾值比較后取整的粒子群優(yōu)化算法；將普通粒子群優(yōu)化算法與二進制粒子群優(yōu)化算法相結(jié)合的混合型粒子群優(yōu)化算法；將粒子群優(yōu)化算法與遺傳算法相結(jié)合的混合優(yōu)化算法。對此算例和3種算法，運用相容解優(yōu)化法改進前后計算結(jié)果相同，但改進后的計算速度可提高數(shù)十倍。改進前的優(yōu)化時間分別為51 s，51 s和6 416 s，運用相容解優(yōu)化法改進后分別為1 s，1 s和104 s。

實際上，粗略分析2種方法的計算量也可以說明這一點。在本例中，n=47，l=35，m=13，采用高斯消去法，每次求解n維線性方程組的乘除法次數(shù)為36 801次，而采用相容解優(yōu)化法，每次計算相容解x的乘除法次數(shù)僅1 066次，兩者之比為34.5，這就是相容解優(yōu)化法計算效率高的原因。如果算題規(guī)模增加一倍，即n=94，l=70，m= 26，2種算法的乘除法次數(shù)之比為67.0，可見算題規(guī)模越大，相容解優(yōu)化法的計算效率越高。在短路限流器配置與優(yōu)化中的應(yīng)用也證明了相容解優(yōu)化法的有效性和實用性[12]。

5 結(jié)語

本文給出了求解線性約束優(yōu)化問題的相容解優(yōu)化法，可用于求解線性規(guī)劃、二次規(guī)劃以及具有線性約束的非線性規(guī)劃問題，具有算法簡捷、計算速度快、數(shù)值穩(wěn)定性好等特點。通過在直流偏磁限流電阻優(yōu)化中的應(yīng)用，驗證了該方法的有效性和實用性，運用相容解優(yōu)化法改進后，計算速度可提高數(shù)十倍，效果非常顯著，滿足了研究課題計算分析的要求。

[1]陳寶林．最優(yōu)化理論與算法（第2版）[M]．北京：清華大學(xué)出版社，2005.

[2]楊篪引，馬正午，孫宇，等．電子計算機應(yīng)用數(shù)學(xué)[M]．北京：冶金工業(yè)出版社，1979.

[3]何建坤，江道琪，陳松華．實用線性規(guī)劃及計算機程序[M]．北京：清華大學(xué)出版社，1985.

[4]丘文千．電力系統(tǒng)優(yōu)化規(guī)劃模型與方法[M]．杭州：浙江大學(xué)出版社，2012.

[5]陳晴，陶佳，丘文千．變壓器直流偏磁現(xiàn)象及其抑制裝置的設(shè)計[J]．電力建設(shè)，2012，33（11）∶33-36.

[6]皇甫成，阮江軍，張宇，等．變壓器直流偏磁的仿真研究及限制措施[J]．高電壓技術(shù)，2006，32（9）∶117-120.

[7]張英．直流輸電系統(tǒng)接地極電流對交流變壓器的影響及抑制措施[J]．廣東電力，2008，21（4）∶28-31.

[8]袁春峰，周行星，顧承昱，等．多回直流輸電系統(tǒng)地下電流場對長三角地區(qū)電網(wǎng)的影響[J]．華東電力，2008，36（11）∶29-32.

[9]蔣偉，吳廣寧，黃震，等．特高壓直流輸電系統(tǒng)的地中電流對變壓器的影響及其計算[J]．高壓電器，2008，44（6）∶534-536，540.

[10]丘文千．直流偏磁計算與限流電阻優(yōu)化配置方法研究[J]．浙江電力，2013，32（4）∶1-5，27.

[11]易大義，蔣叔豪，李有法．數(shù)值方法[M]．杭州：浙江科學(xué)技術(shù)出版社，1984.

[12]丘凌，丘文千．短路限流器的配置與優(yōu)化[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），男，教授級高級工程師，從事電力系統(tǒng)規(guī)劃、工程設(shè)計與技術(shù)管理工作。