任潔,彭建文

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

1.引言

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

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

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

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

2.預(yù)備知識

3.非單調(diào)牛頓法

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

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

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

然后給出引理3.1的一個明顯的結(jié)論.

推論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,關(guān)于搜索方向dN(x)的Armijo法則為

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

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

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

算法3.1步1 取初始點x0∈Rn,參數(shù)δ∈(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是有定義的,因為總有一個滿足非單調(diào)Armijo條件(3.10)的步長,以便生成迭代序列{xk}.

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

4.非單調(diào)牛頓法的全局收斂性

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

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

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

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

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

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

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

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

5.局部超線性收斂率

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

6.結(jié)論

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