李有堂，梅鶴齡

（蘭州理工大學(xué)機(jī)電工程學(xué)院，甘肅蘭州 730050）

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

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

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

隨著科技的發(fā)展，基礎(chǔ)科學(xué)也在進(jìn)步，對(duì)于不同的優(yōu)化問(wèn)題采用不同的優(yōu)化算法，一些有約束問(wèn)題往往采用無(wú)約束優(yōu)化算法進(jìn)行求解。通過(guò)以上綜合分析，提出了一種求解有約束優(yōu)化問(wèn)題的有限元分割共軛方向法，可以杜絕所求優(yōu)化解為局部最優(yōu)解的產(chǎn)生。

1 共軛方向法

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

1.1 共軛方向法基本原理

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

設(shè)目標(biāo)函數(shù)為：

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

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

式（3）表明，經(jīng)(k+1)次迭代后，Xk+1→X*,Xk+1為目標(biāo)函數(shù)沿Sk方向的一個(gè)極小點(diǎn)。則：

對(duì)于二元二次函數(shù)只需進(jìn)行兩次直線搜索就可以求到極小值點(diǎn)。

圖1 二元二次函數(shù)搜索圖

1.2 共軛方向法

共軛方向法具有二次終止性，是一個(gè)概念性算法，實(shí)現(xiàn)算法的關(guān)鍵在如何選取共軛方向[11]，不同的選取會(huì)產(chǎn)生不同的共軛方向法。其通用格式如下：

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

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

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

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

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

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

2 有限元分割共軛方向法

許多優(yōu)化算法在理論上是用來(lái)解決無(wú)約束優(yōu)化問(wèn)題的，但是在實(shí)際工程問(wèn)題中往往需要解決的是有約束的優(yōu)化問(wèn)題[12]，所以一些有約束優(yōu)化問(wèn)題往往采用無(wú)約束優(yōu)化算法進(jìn)行求解[13]。針對(duì)共軛方向法所求解有可能為局部最優(yōu)解的問(wèn)題，對(duì)共軛方向法加以改進(jìn)，用以求解有約束的優(yōu)化問(wèn)題。算法執(zhí)行過(guò)程如下所示：

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

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

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

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

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

第六步：根據(jù)共軛方向的構(gòu)造方法獲得搜索方向dk+1，使得。令k=k+1，轉(zhuǎn)至第三步。

第七步：根據(jù)極值保存數(shù)組所得各個(gè)極值中求取最小值點(diǎn)，最后輸出在該約束內(nèi)的全局最優(yōu)解。

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

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

3 目標(biāo)函數(shù)的算例驗(yàn)證

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

目前多數(shù)優(yōu)化問(wèn)題的解決依賴于計(jì)算機(jī)軟件，如MATLAB 軟件的優(yōu)化工具箱[14]，可用MATLAB 根據(jù)以上兩種算法的執(zhí)行過(guò)程進(jìn)行編程，然后用所編程序分別求解以上目標(biāo)函數(shù)的最優(yōu)解。

3.1 共軛方向法的算例驗(yàn)證

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

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

表1 共軛方向法不同初始點(diǎn)迭代結(jié)果

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

3.2 有限元分割共軛方向法的算例驗(yàn)證

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

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

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

由表2 所得極值與表1 所得極值進(jìn)行對(duì)比，可以得出表2 所得極值小于表1 所有極值。這說(shuō)明有限元分割共軛方向法的迭代結(jié)果優(yōu)于共軛方向法，并且可以避免在求解過(guò)程中陷入局部最優(yōu)解的缺點(diǎn)。通過(guò)編程驗(yàn)證可知，當(dāng)有限元分割共軛方向法的分割單元長(zhǎng)度越小，則所得解越優(yōu)，就當(dāng)今科技發(fā)展的程度，計(jì)算速度已不是問(wèn)題[16]，所以該優(yōu)化計(jì)算算法具有很大的實(shí)際應(yīng)用價(jià)值。

4 結(jié)論

該文在共軛方向法的基礎(chǔ)上提出了有限分割的共軛方向法，并通過(guò)MATLAB 編程對(duì)兩種算法的尋優(yōu)結(jié)果進(jìn)行對(duì)比，可得出的主要結(jié)論如下：

1）提出的有限元分割共軛方向法的迭代結(jié)果優(yōu)于共軛方向法，并且可以避免在求解過(guò)程中陷入局部最優(yōu)解的缺點(diǎn)。

2）有限元分割共軛方向法具有可移植性，可以根據(jù)不同的問(wèn)題可以進(jìn)行不同參數(shù)設(shè)置，可以作為求解大規(guī)模優(yōu)化問(wèn)題的主要方法。

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

4）有限元分割共軛方向法具有簡(jiǎn)單、易于編程、需要的儲(chǔ)存空間小等優(yōu)點(diǎn)。

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

6）當(dāng)有限元分割共軛方向法的分割單元長(zhǎng)度越小，則所求解越優(yōu)。