線性約束優化問題的相容解優化法及其應用

丘文千， 丘 凌

（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），男，教授級高級工程師，從事電力系統規劃、工程設計與技術管理工作。