連續(xù)負梯度方向獲得共軛方向的六尋優(yōu)化方法*

尹曉麗，孫 鳳，李春明+

1.中國石油大學（華東）機電工程學院，山東 青島 266580

2.中國石油大學（華東）中國石油大學勝利學院，山東 東營 257061

1 引言

優(yōu)化方法逐漸形成了龐大的理論體系。目前，其主要研究方向多集中在群體智能[1]、聚類算法[2-3]、數(shù)據(jù)存儲[4]等優(yōu)化問題的研究。

上述算法屬于基于其他理論的優(yōu)化方法。經(jīng)典的優(yōu)化方法是針對可解析建模優(yōu)化問題和可求或可測量目標函數(shù)優(yōu)化問題而提出來的，包括一維優(yōu)化方法、多維無約束優(yōu)化方法、多維有約束優(yōu)化方法、多目標優(yōu)化方法和離散變量優(yōu)化方法。在流場模擬[5]、車輛傳動機構(gòu)設(shè)計[6]、資源分配[7]、振動控制[8]等領(lǐng)域發(fā)揮著重要的作用。

經(jīng)典的多維無約束優(yōu)化方法在近幾十年沒有太大的發(fā)展。但是，在求解顯式目標函數(shù)優(yōu)化問題、可解析目標函數(shù)優(yōu)化問題、大型稀疏系數(shù)矩陣線性方程組[9-10]等方面發(fā)揮著重要的作用。

負梯度方向因為其局部最速下降特性而成為許多優(yōu)化方法的首選方向，比如坐標變換法、共軛方向法、共軛梯度法、由幾何法獲得共軛方向的算法[11]、優(yōu)選可用方向法等。

共軛方向的構(gòu)造方法有多種，比如：從不同初始點出發(fā)沿同一尋優(yōu)方向獲得的最優(yōu)點連線是該尋優(yōu)方向的共軛方向[12-13]。

在《優(yōu)化方法》的教學實踐和課題相關(guān)算法的研究探索當中，發(fā)現(xiàn)連續(xù)兩次沿負梯度方向?qū)?yōu)，初始點與終止點連線符合上述共軛方向的構(gòu)造特征，于是提出了三個算法。

2 共軛方向的證明

2.1 共軛尋優(yōu)方向的定義與意義

在以設(shè)計變量為坐標軸所張成的設(shè)計空間當中，相互平行的矢量指同一尋優(yōu)方向，任一矢量的正反向為同一尋優(yōu)方向。在三維設(shè)計空間當中，兩個尋優(yōu)方向的最大夾角是90°。

對于一般N維二次目標函數(shù)：

沿方向s(0)尋優(yōu)之后，如果令最優(yōu)點（該方向上極小點的數(shù)值近似點）指向式（1）極值點的方向為s(1)，則s(0)和s(1)滿足以下關(guān)系式：

稱為s(0)和s(1)關(guān)于G共軛。這是新方向s(1)指向極值點的必要條件。從任意初始點出發(fā)，依次沿相互關(guān)于G共軛的尋優(yōu)方向進行一維尋優(yōu)，最多經(jīng)過N次尋優(yōu)即可找到極值點。對于二維的式（1），沿任一方向?qū)?yōu)之后，再沿其共軛方向?qū)?yōu)即可找到極值點。

2.2 兩次同方向?qū)?yōu)獲共軛方向的證明

設(shè)x(k)、x(k+1)為從不同點出發(fā)，沿方向s(j)進行一維尋優(yōu)而得到的兩個最優(yōu)點。在該兩點處，梯度方向g(k)、g(k+1)是目標函數(shù)等值面（線）的法線，而s(j)是該面（線）的切線，兩者相互垂直，則s(j)和g(k)、g(k+1)之間存在以下關(guān)系：

根據(jù)式（1），有：

式（3）的兩式相減，仍然等于0，即：

如圖1所示，若取方向：

則s(k)和s(j)滿足式（2）。

2.3 連續(xù)負梯度方向?qū)?yōu)獲共軛方向的解釋

從x(0)出發(fā)，沿目標函數(shù)的負梯度方向-g(0)尋優(yōu)獲得最優(yōu)點x(1)，再從x(1)出發(fā)，沿負梯度方向-g(1)尋優(yōu)獲得最優(yōu)點x(2)，則兩個尋優(yōu)方向分別為x(1)處目標函數(shù)等值面（線）的切線和法線，兩者相互垂直。x(0)可視為從某點出發(fā)沿-g(1)尋優(yōu)而獲得的最優(yōu)點。因此，根據(jù)2.2節(jié)，x(0)→x(2)是-g(1)的共軛方向，即：

2.4 連續(xù)負梯度方向?qū)?yōu)獲共軛方向的證明

最優(yōu)點的梯度方向與尋優(yōu)方向相垂直，有：

對于多維一般目標函數(shù)，-g(0)和-g(2)不一定平行。根據(jù)式（1），x(0)與x(2)點處的梯度為：

g(0)=Gx(0)+b

g(2)=Gx(2)+b

兩式相減，得：

上式左乘-g(1)。根據(jù)式（7）和式（8），等號左端為0。根據(jù)式（2）、式（6）所示方向s與-g(1)關(guān)于G共軛，或者說，s為-g(1)的共軛方向。

2.3 節(jié)和2.4 節(jié)從兩個不同角度的分析是本文提出三尋法和六尋法的理論依據(jù)。

3 基于輔助方向的共軛方向法

根據(jù)2.2 節(jié)的證明，每次初始點和尋優(yōu)方向確定之后，同時以尋優(yōu)路線之外的某一輔助點為起點沿該尋優(yōu)方向?qū)?yōu)，兩次尋優(yōu)的最優(yōu)點連線作為下一次的尋優(yōu)方向。該輔助點可以是當前點處負梯度方向上的一點。尋優(yōu)方案（見圖2）為：

（1）從x(0)出發(fā)，沿s尋得最優(yōu)點x；

（2）在x點處的-g方向上適當取一點x(1)；

（3）從x(1)出發(fā)，沿s尋優(yōu)獲得x(2)；

（4）從x(2)出發(fā)，沿方向(x→x(2))尋得x(3)；

（5）如果x(3)滿足終止條件，則結(jié)束尋優(yōu)；

（6）令s為(x→x(2))，x(3)為x，轉(zhuǎn)（2）。

Fig.2 Optimal scheme on negative gradient direction圖2 基于負梯度方向的尋優(yōu)方案圖

對于一般目標函數(shù)的二維優(yōu)化問題，上述算法相當于每輪兩個相互共軛方向的共軛方向輪換法。對于式（1）所示的二維優(yōu)化問題，每一輪的x→x(2)與s關(guān)于G共軛，即指向極值點。

4 基于負梯度方向的三尋法

對于以下二次二維無約束優(yōu)化問題[11]：

沿負梯度方向的尋優(yōu)過程如圖3所示。由2.3節(jié)的分析和2.4 節(jié)的證明可知：x(0)→x(2)和x(1)→x(3)兩個方向均指向優(yōu)化問題的極值點，兩者交點即為極值點。對于非二次目標函數(shù)，兩者交點不一定為極值點，也不是任一方向上的最優(yōu)點，用求交點的方法確定新點不科學。因此，連續(xù)沿負梯度方向進行三次尋優(yōu)，從而獲得兩個共軛方向，以其交點作為新點的方法不宜采用。

Fig.3 Optimal process of negative gradient direction method圖3 負梯度方向法的尋優(yōu)過程

基于以上分析，提出基于負梯度方向的三尋法，其尋優(yōu)方案為：

（1）從初始點x(0)出發(fā)，沿-g(0)尋優(yōu)得x(1)；

（2）從x(1)出發(fā)，沿-g(1)尋優(yōu)得x(2)；

（3）從x(2)出發(fā)，沿x(0)→x(2)尋優(yōu)得x(3)；

（4）如果x(3)滿足終止條件，則結(jié)束尋優(yōu)；否則令x(3)為x(0)，轉(zhuǎn)（1）。

5 基于負梯度方向的六尋法

對于多維優(yōu)化問題，圖3的兩條共軛方向也不一定相交。沿兩者的公垂線也不一定尋得較好的最優(yōu)點。經(jīng)第6章的算例驗證，上述假設(shè)是正確的。

連續(xù)三次沿負梯度方向?qū)?yōu)所得兩條共軛方向上的兩個最優(yōu)點又指示了一條新的尋優(yōu)方向。利用該方向完善三尋法，即為六尋法。該六步尋優(yōu)方案為：

（1）從初始點x(0)出發(fā)，沿-g(0)尋優(yōu)得x(1)；

（2）從x(1)出發(fā)，沿-g(1)尋優(yōu)得x(2)；

（3）從x(2)出發(fā)，沿-g(2)尋優(yōu)得x(3)；

（4）從x(2)出發(fā)，沿s(3)=x(0)→x(2)得x(4)；

（5）從x(3)出發(fā)，沿s(4)=x(1)→x(3)得x(5)；

（6）從x(5)出發(fā)，沿s(5)=x(4)→x(5)得x(6)；

（7）如果x(6)滿足終止條件，則結(jié)束尋優(yōu)；否則令x(6)為x(0)，轉(zhuǎn)（1）。

第（4）步s(3)上的點x可表示為：

其目標函數(shù)為步長α的一元函數(shù)。六尋法的程序流程如圖4所示。

Fig.4 Program diagram of six search method圖4 六尋法程序流程圖

6 算例驗證

6.1 一般二次三維優(yōu)化問題

求解以下二次三維無約束優(yōu)化問題：

目標函數(shù)的梯度為：

根據(jù)極值條件：

?f(x)=0

該目標函數(shù)的極值點和極值為：

x*=[7.0 5.0 3.5]T

f(x*)=-20.75

二次目標函數(shù)的二階偏導數(shù)矩陣為常數(shù)陣。該算例的二階偏導數(shù)矩陣為：

正定，因此該點為極小點。

6.2 最佳尋優(yōu)步長的解析解

當尋優(yōu)起點x(k)和尋優(yōu)方向s(k)確定后，以x(k)為坐標原點，以s(k)為正方向建立局部一維坐標系。由式（11），s(k)上點的目標函數(shù)值為：

式中：

由極值條件：

可得最優(yōu)步長為：

在s(k)上的最優(yōu)點為：

6.3 尋優(yōu)結(jié)果

取初始點為：

x(0)=[1 1 1]T

f(x(0))=-6

初始尋優(yōu)步長取為0.1，終止條件值取為1.0×10-6。采用一維盲人探路法[14-15]獲得尋優(yōu)方向上的最優(yōu)點。采用六尋法尋優(yōu)，經(jīng)12 輪，共72 次一維尋優(yōu)

獲得最優(yōu)點和最優(yōu)解為：

x=[7.000 0 5.000 0 3.500 0]T

f(x)=-20.75

采用負梯度方向法尋優(yōu)，經(jīng)101次尋優(yōu)才獲得該尋優(yōu)結(jié)果。圖5 為尋優(yōu)過程，點線為負梯度方向法的，鋸齒現(xiàn)象較嚴重，即越接近于極值點尋優(yōu)效果越差；實線為六尋法的，共軛方向的尋優(yōu)效率較大，兩輪尋優(yōu)即非常接近于極值點；虛線僅表示尋優(yōu)方向；藍色五角星為初始點和極值點。由于三尋法的尋優(yōu)方向均包含在六尋法當中，從圖5可見三尋法的尋優(yōu)效果明顯不如六尋法的好。可見本文提出的六尋法具有計算效率較大，尋優(yōu)效果較好的特點。

Fig.5 Optimal process of example圖5 算例的尋優(yōu)過程

6.4 沿兩共軛方向中垂線尋優(yōu)的缺陷

在第一輪尋優(yōu)當中，在第四和第五個方向（s(3)和s(4)）上任意兩點之間的距離可表示為：

由極值條件：

可得方程組：

可求得：

α=1.070 5

β=0.451 0

對應(yīng)于兩條直線的公垂線垂足分別為：

x(α)=[3.252 1 1.751 5 1.248 7]T

x(β)=[3.125 1 2.242 7 0.914 3]T

相應(yīng)的目標函數(shù)值分別為：

f(x(α))=-13.443 4

f(x(β))=-12.756 3

兩者離第六次尋優(yōu)所得的最優(yōu)點較遠，因此沿s(3)和s(4)公垂線尋優(yōu)的效果較差。

6.5 Rosenbrock目標函數(shù)的尋優(yōu)結(jié)果

將目標函數(shù)換為三維Rosenbrock 函數(shù)[16]。取初始點為：

x(0)=[-0.5 0.5 0.5]T

f(x(0))=15

采用負梯度方向法尋優(yōu)，經(jīng)過1 000 次一維尋優(yōu)，調(diào)用目標函數(shù)34 762 次，鋸齒現(xiàn)象極為嚴重，獲得遠離極值點的最優(yōu)點：

x=[0.955 79 0.913 30 0.833 74]T

f(x)=9.491 1×10-3

采用六尋法尋優(yōu)，經(jīng)過448 次一維尋優(yōu)，調(diào)用目標函數(shù)15 905次，獲得最優(yōu)點：

x=[0.999 93 0.999 86 0.999 72]T

f(x)=2.387 1×10-8

該復雜目標函數(shù)更加體現(xiàn)了六尋法的優(yōu)勢。

7 討論

7.1 本文的研究范疇

任何尋求最優(yōu)方案、最優(yōu)參數(shù)的方法都稱為優(yōu)化方法。在優(yōu)化方法理論體系當中，本文的研究屬于多維有約束優(yōu)化方法領(lǐng)域，對其他領(lǐng)域也有參考價值。

7.2 本文的理論意義

對于二維（N=2）二次目標函數(shù)的優(yōu)化問題，沿一個方向?qū)?yōu)之后，再沿任何方法得到的共軛方向進行一維尋優(yōu)，均是連續(xù)N次沿相互共軛的方向?qū)?yōu)，因此這些共軛方向均指向極值點。對于二維一般目標函數(shù)的優(yōu)化問題，共軛方向也是有效的尋優(yōu)方向。似乎共軛方向已經(jīng)完成了優(yōu)化方法的任務(wù)。

但是，對于N>2 的優(yōu)化問題，所有方法得到的共軛方向不一定相同，其尋優(yōu)效果必然有所差異。本文的研究在于探索有效的尋優(yōu)方向。期間，進行了許多有效的探索。比如第3 章基于輔助方向的算法和第4章三尋法。作為階段性研究成果，這些創(chuàng)新算法均可成文發(fā)表。但是，探索出六尋法之后，這些算法就顯得黯然失色了，因此只作為本文的輔助內(nèi)容出現(xiàn)。

7.3 先進性分析

優(yōu)化算法在數(shù)學推導的基礎(chǔ)上容易獲得創(chuàng)新，比如本文的第3 章、第4 章兩個算法。但是，只有經(jīng)過算例的計算機程序驗證才稱得上是成功的創(chuàng)新。很多成功的創(chuàng)新因為沒有程序驗證而悄然消失。

本文提供了較完整的C語言計算機程序，研究結(jié)果的可重復性強。本文的計算沒有依賴于優(yōu)化計算軟件，為難以由優(yōu)化軟件解決的特殊優(yōu)化問題提供了工具。對優(yōu)化方法學科的發(fā)展具有積極的推動意義。

8 結(jié)論

六尋法充分利用了共軛方向的優(yōu)勢，通俗易懂，算法簡潔，程序?qū)崿F(xiàn)容易，尋優(yōu)效果好。算例證明了其有效性和實用性[17]。一般二次目標函數(shù)的計算量比負梯度方向法的減小28.70%，比Rosenbrock 目標函數(shù)的減小54.25%。

本文的算例經(jīng)手算一輪之后，驗證了一維盲人探路算法計算程序的正確性。同時檢驗了沿第四、第五尋優(yōu)方向的公垂線尋優(yōu)不能尋得較好最優(yōu)點的假設(shè)。

附錄（主要計算程序）：

目前許多研究領(lǐng)域的優(yōu)化問題依賴于計算機軟件，如Matlab 軟件的優(yōu)化工具箱、ANSYS 有限元分析軟件、Solidworks建模軟件的優(yōu)化方法插件等。本文研究新的優(yōu)化算法，必須進行計算機程序設(shè)計。采用可移植性和通用性都較強的C語言進行程序設(shè)計。

六尋法的計算子程序如下：