有限元分割的共軛方向優化算法

李有堂，梅鶴齡

（蘭州理工大學機電工程學院，甘肅蘭州 730050）

隨著科技的進步和發展，精密、超精密設備與加工技術標志著一個國家制造領域的尖端技術水平，已成為當今世界各國進行科技競爭的一個重要手段[1]。計算機的快速發展以及互聯網的迅速普及，信息在互聯網上爆發式增長，文本、圖像、音頻、視頻等的發展導致表達數據需要更高的維度[2]。這些改變無疑對數據類問題的處理提出了更高的要求，不僅對數據的處理效率和便捷度提出了要求，對估算計算的數值要求有更高的準確度(誤差降低到滿足要求的范圍內)。

無約束優化算法作為最優化方法的基礎，在交通運輸、工農業生產、金融、貿易等眾多領域有著廣泛應用。伴隨著信息技術的飛速發展,變量維數的劇增以及結構復雜性的增強，能有效求解大規模無約束優化問題的算法顯得尤為重要[3]。在優化算法的發展過程中，1964 年由鮑威爾提出的共軛方向法(Conjugate Direction Method)起到了舉足輕重的作用。共軛方向法可以在有限步數內找到二次函數的極值點和極值，并且對非二次函數只要具有連續二階導數，也是一種有效的算法[4]。但是，共軛方向法的主要缺點是更換方向后所產生的n個矢量有可能是近似線性相關的，即這些矢量接近于平行。這樣就會出現維度退化現象，導致只能找到局部最優解，有可能使真正的全局最優解漏掉[5]。

針對共軛方向法的該缺陷，在實際工程應用中通過與其他算法組合或對算法進行改進以提高解決問題的準確度[6]。例如：在一些優化問題中，當粒子群算法(PSO)經過一段時間的迭代后，會陷入局部最優解的局部極小值中，這時采用共軛方向法，以局部最優解作為初始猜測，將高維函數優化問題轉化為低維函數優化問題，幫助粒子群算法克服局部極小問題[7]；對于移動機器人全局路徑規劃問題，先用共軛方向法搜索局部最優解，再用改進模擬退火算法(SAA)跳出局部最優解，依此更新溫度值，如此反復操作，直至找到全局最優解[8]；針對遺傳模擬退火算法的局部搜索能力不足，并且有可能早熟和遺失最優解的問題，提出一種將遺傳模擬退火算法和共軛方向法相結合的混合遺傳模擬退火算法[9]；還有對多維優化問題的求解，通過對Powell 機械優化方法的改進，提出了方向組不降維的構造共軛方向法[10]。

隨著科技的發展，基礎科學也在進步，對于不同的優化問題采用不同的優化算法，一些有約束問題往往采用無約束優化算法進行求解。通過以上綜合分析，提出了一種求解有約束優化問題的有限元分割共軛方向法，可以杜絕所求優化解為局部最優解的產生。

1 共軛方向法

共軛方向法是利用共軛方向作為搜索方向的無約束極小算法，而且已證明這類算法應用于具有正定Hesse 矩陣的二次函數時，最多n次迭代即可達到極小點。這類算法具有有限收斂性，形成共軛方向的方法很多，每一種不同的構造共軛方向的方法形成一種具體的共軛方向法，因而共軛方向法是一大類算法[4]。

1.1 共軛方向法基本原理

m個n維向量S1,S2,…,Sm，滿足=0，i≠j且A正定，則這m個向量一定是線性無關的。在n維空間中的任意向量，均可以用n個線性無關的n維向量表示。

設目標函數為：

它的極小點為X*，初始點X0,S0,S1,S2,…,Sn-1為關于A的n個共軛向量，則有：

將式（2）寫成差分格式：

式（3）表明，經(k+1)次迭代后，Xk+1→X*,Xk+1為目標函數沿Sk方向的一個極小點。則：

對于二元二次函數只需進行兩次直線搜索就可以求到極小值點。

圖1 二元二次函數搜索圖

1.2 共軛方向法

共軛方向法具有二次終止性，是一個概念性算法，實現算法的關鍵在如何選取共軛方向[11]，不同的選取會產生不同的共軛方向法。其通用格式如下：

第一步：任取X0∈Rn,0 ≤ε＜＜1,k=0，計算g0=g(X0)和初始點X0的下降方向d0，s.t.；第二步：求解minf(Xk+αdk),λ≥0，得解αk(即αk是一維搜索的最優解)；

第三步：計算αk、Xk+1，使得Xk+1=Xk+αkdk；

第四步：若Xk+1滿足迭代終止準則‖gk+1‖≤ε，停止迭代，輸出Xk+1；否則，轉至第五步；

第五步：根據共軛方向的構造方法獲得搜索方向dk+1，使得dTk+1Gdj=0,j=0,1,…,k。令k=k+1，轉至第二步。

共軛方向法的程序流程圖如圖2 所示。

圖2 共軛方向法的程序流程圖

2 有限元分割共軛方向法

許多優化算法在理論上是用來解決無約束優化問題的，但是在實際工程問題中往往需要解決的是有約束的優化問題[12]，所以一些有約束優化問題往往采用無約束優化算法進行求解[13]。針對共軛方向法所求解有可能為局部最優解的問題，對共軛方向法加以改進，用以求解有約束的優化問題。算法執行過程如下所示：

第一步：任取X0∈Rn,X0=(x1,x2,…,xn)，若x1∈[a1,b1],x2∈[a2,b2],…,xn∈[an,bn],ai,bi∈R,i=1,2,…,n。將各個維數的取值區間進行有限分割，按各個維數的區間劃分節點進行排列組合。例如：令xi=[ai,b1]∪[c1,c2]∪,…,∪[cm-1,cm]∪[cm,bi]，然后依次取區間分割節點ai,c1,c2,…,cm,bi為xi的值，最后將xi的節點其他xj的節點依次進行排列組合，取得初始點X0,m∈R,i≠j,i=1,2,…n,j=1,2,…n。

第二步：取初始點X0,0 ≤ε＜＜,1,k=0，計 算g0=g(X0)和初始點X0的下降方向d0,s.t.dT0g0＜0；

第三步：求解minf(Xk+αdk),λ≥0，得解αk(即αk是一維搜索的最優解)；

第四步：計算αk,Xk+1，使得Xk+1=Xk+αkdk；

第五步：若Xk+1滿足迭代終止準則‖gk+1‖≤ε，停止迭代，輸出Xk+1，將其保存于極值保存數組，然后轉至第一步選取新的起始點；否則，轉至第六步；

第六步：根據共軛方向的構造方法獲得搜索方向dk+1，使得。令k=k+1，轉至第三步。

第七步：根據極值保存數組所得各個極值中求取最小值點，最后輸出在該約束內的全局最優解。

有限元分割共軛方向法的程序流程圖如圖3所示。

圖3 有限元分割共軛方向法的程序流程圖

3 目標函數的算例驗證

以求解f(x)最小值為例：

目前多數優化問題的解決依賴于計算機軟件，如MATLAB 軟件的優化工具箱[14]，可用MATLAB 根據以上兩種算法的執行過程進行編程，然后用所編程序分別求解以上目標函數的最優解。

3.1 共軛方向法的算例驗證

根據圖2 所介紹的共軛方向法的程序流程圖用MATLAB 進行編程，定義精度為0.000 01，計算程序如下：

選取不同初值X0進行迭代計算，可以得到不同的極值和極值點，如表1 所示。

表1 共軛方向法不同初始點迭代結果

從計算結果可以看出，雖然定義的精度相同，但是選擇不同的初始點進行迭代，所得到的極值點和極值各不相同，并且計算結果的差距較大。該結果充分證明了共軛方向法存在的缺點，會陷入局部極值而無法找到全局最優點。就科技的發展而言，計算速度已不是問題，最主要的問題是計算結果的準確度，這就意味著需要更優的計算方法解決準確度問題[15]。

3.2 有限元分割共軛方向法的算例驗證

根據圖3 的有限元分割共軛方向法的程序流程圖進行MATLAB 編程，定義精度也為0.000 01，并設置預期極值為0(所設預期極值應大于最終計算極值，如果所設預期極值不大于計算極值，計算結果將會是設置的預期結果，需重新設置預期極值進行重新計算)，計算程序如下：

令初始點X0=(x1,x2,x3)，由題知x1,x2,x3∈[-1,1]，設每個分割單元的長度均相等，分割單元長度為0.1，則x1、x2、x3的分割節點可取為-1,-0.9,…,0.9,1。將所設參數代入所編程序中進行迭代計算，可以得到最終的極值和極值點，如表2 所示。

表2 有限元分割共軛方向法迭代結果

由表2 所得極值與表1 所得極值進行對比，可以得出表2 所得極值小于表1 所有極值。這說明有限元分割共軛方向法的迭代結果優于共軛方向法，并且可以避免在求解過程中陷入局部最優解的缺點。通過編程驗證可知，當有限元分割共軛方向法的分割單元長度越小，則所得解越優，就當今科技發展的程度，計算速度已不是問題[16]，所以該優化計算算法具有很大的實際應用價值。

4 結論

該文在共軛方向法的基礎上提出了有限分割的共軛方向法，并通過MATLAB 編程對兩種算法的尋優結果進行對比，可得出的主要結論如下：

1）提出的有限元分割共軛方向法的迭代結果優于共軛方向法，并且可以避免在求解過程中陷入局部最優解的缺點。

2）有限元分割共軛方向法具有可移植性，可以根據不同的問題可以進行不同參數設置，可以作為求解大規模優化問題的主要方法。

3）有限元分割共軛方向法克服了最速下降法的慢收斂性，并且保留了共軛方向法的優點，具有二次終止性。

4）有限元分割共軛方向法具有簡單、易于編程、需要的儲存空間小等優點。

5）有限元分割共軛方向法不受維度限制，可以用于多維問題的求解。

6）當有限元分割共軛方向法的分割單元長度越小，則所求解越優。