任潔,彭建文

(重慶師范大學數學科學學院,重慶 401331)

1.引言

在多目標優(yōu)化中,我們要對多個目標函數同時最小化或同時最大化,由于單個點一般不可能使得所有給定的目標函數同時取得最優(yōu)值,因此,人們往往使用Pareto最優(yōu)性的概念.這類優(yōu)化問題在許多領域都有應用,包括工程、設計、選址問題、空間探索、統(tǒng)計學、管理科學、環(huán)境分析等領域.

標量化方法[1]是將多目標優(yōu)化問題轉化為單目標的數學規(guī)劃問題進行求解,是求解多目標優(yōu)化問題最有效的方法之一.特別地,所謂的加權和方法將目標的線性組合作為標量重構的目標函數.然而,當原問題是非凸的多目標優(yōu)化問題時,可能無法得到該問題特定的Pareto最優(yōu)解.為了克服這一缺點,Ogata等人[2]還提出了次線性標量化方法.經典的求解多目標優(yōu)化問題的加權和方法的缺點是事先需要未知的權重參數來得到期望的解.另一種不涉及標量化的求解多目標優(yōu)化問題的方法是基于啟發(fā)式的方法[3],在這種情況下,不一定能保證此類算法所產生的點列收斂到多目標優(yōu)化問題的Pareto最優(yōu)解.

近年來,許多研究人員提出了一些不需要任何先驗信息的多目標優(yōu)化技術: 例如最速下降法[4]、牛頓法[5]、擬牛頓法[6]、投影梯度法[7]和共軛梯度法[8],這些方法是對相應的單目標優(yōu)化方法的推廣.在這些方法中,步長的選擇使目標函數值在每次迭代中都減小.但是,由于目標函數數量的增加,Armijo條件變得更加嚴格,可能導致更小的步長.然而,在非單調線搜索方法中,允許某些函數值的增加.正如一些研究人員指出,單目標優(yōu)化的非單調技術可以增加找到全局最優(yōu)解的可能性;此外,它們可以提高收斂速度(見文[9]).將非單調技術應用于復雜的非線性單目標優(yōu)化問題時,已有令人鼓舞的數值結果(見文[9-11]).最近,Mita[12]等人將非單調線搜索方法由單目標優(yōu)化問題推廣到多目標優(yōu)化問題,從而提出了求解無約束多目標優(yōu)化問題的非單調線搜索的最速下降法和牛頓法,并建立了它們的全局收斂性.ZHANG和Hager[11]提出并分析了求解無約束單目標優(yōu)化問題的非單調線搜索方法.Fliege等人[5]建立了求解多目標優(yōu)化問題的單調牛頓法的局部超線性收斂率.基于此,我們將給出求解多目標優(yōu)化問題的非單調牛頓法[12]的全局收斂性及其局部超線性收斂率的分析.

本文剩下的內容如下: 在第2節(jié),我們給出了一些符號說明和有關Pareto最優(yōu)性和Pareto平穩(wěn)性的概念.在第3節(jié),我們陳述了文[12]提出的求解無約束多目標優(yōu)化問題的非單調牛頓法.在第4節(jié),我們在適當的假設條件下給出了求解多目標優(yōu)化問題的非單調牛頓法的全局收斂性.在第5節(jié),我們建立了該算法的局部超線性收斂率.最后,我們在第6節(jié)中做出結論并提出未來研究的方向.

2.預備知識

3.非單調牛頓法

這一節(jié),我們將回顧文[12]提出的求解多目標優(yōu)化問題(2.1)的非單調牛頓法.

這里,對所有i=1,···,m,我們假設Fi是二階連續(xù)可微的,且對?x∈Rn,?2Fi(x)是正定的.在這種情況下,對于給定x∈Rn,通過求解下面的無約束問題來計算搜索方向:

因為?2Fi(x)是正定的,所以(3.1)的目標函數是強凸的.因此,用dN(x)表示其唯一最優(yōu)解,用θN(x)表示其最優(yōu)函數值,即

然后給出引理3.1的一個明顯的結論.

推論3.1[12]1)x是多目標優(yōu)化問題(2.1)Pareto平穩(wěn)點,當且僅當θN(x)=0,或等價地,當且僅當dN(x)=0.

2)x不是多目標優(yōu)化問題(2.1)的Pareto平穩(wěn)點,當且僅當θN(x)＜0,或等價地,當且僅當dN(x)0.

對于F:Rn →Rm,在一個非平穩(wěn)點x∈Rn,關于搜索方向dN(x)的Armijo法則為

其中δ∈(0,1),見文[5].

在這里,我們將使用由文[11]中單目標優(yōu)化的非單調Armijo條件推廣到多目標優(yōu)化的非單調Armijo條件.

基于以上討論,我們將回顧文[12](算法2、算法4)給出如下求解多目標優(yōu)化問題(2.1)的非單調牛頓法(算法3.1):

算法3.1步1 取初始點x0∈Rn,參數δ∈(0,1),ρ∈(0,1),μ ＞0,η∈[0,1].令k=0,C0=F(x0),q0=1.

引理3.2[12]對于算法3.1的每次迭代k,則有F(xk)≤Ck ≤Ak.

在下一個命題中,說明了算法3.1是有定義的,因為總有一個滿足非單調Armijo條件(3.10)的步長,以便生成迭代序列{xk}.

命題3.1[12]設xk是由算法3.1生成的序列,如果xk不是多目標優(yōu)化問題(2.1)的Pareto平穩(wěn)點,則存在一個步長αk ＞0滿足非單調Armijo條件(3.10).

4.非單調牛頓法的全局收斂性

首先,我們給出由非單調牛頓法(算法3.1)生成的步長的一個下界.

條件4.1假設對?i=1,···,m,?Fi滿足以下帶有常數L的Lipschitz連續(xù):

注4.1文[12]是將單目標優(yōu)化的相關結論推廣到多目標優(yōu)化,進而證明了求解多目標優(yōu)化問題的非單調牛頓法的全局收斂性(見文[12]的定理7).現在,下面我們將利用求解多目標優(yōu)化問題的牛頓法的相關結論直接證明非單調牛頓法(算法3.1)的全局收斂性,假設條件更合理,結論更直接.

定理4.1假設對?i=1,···,m,Fi(x)是下有界的,η ＜1,若條件4.1成立且存在常數c1＞0,使得

則由算法3.1生成的序列{xk}的每個極限點是多目標優(yōu)化問題(2.1)的Pareto平穩(wěn)點.

證首先,我們證明對所有i=1,···,m有

接下來,我們證明當k →+∞時,θN(xk)和‖‖dN(xk)‖‖都收斂到0.

命題4.1假設由算法3.1生成的序列{xk}是有界的,且它的極限點是多目標優(yōu)化問題(2.1)的Pareto平穩(wěn)點,假設存在常數a ＞0,使得對所有i=1,···,m和所有k,有

5.局部超線性收斂率

在此,我們將建立求解多目標優(yōu)化問題(2.1)的非單調牛頓法的局部超線性收斂率.首先,我們需要陳述一個條件.

6.結論

針對文[12]中提出的求解無約束多目標優(yōu)化問題的非單調牛頓法,在適當的條件下,我們證明了該算法生成的迭代序列的每一個極限點都是多目標優(yōu)化問題的Pareto平穩(wěn)點.在合理的假設下,建立了該算法的局部超線性收斂率.隨著研究的深入,我們未來將會提出新的非單調技術和研究求解多目標優(yōu)化問題的其他新的非單調算法.