求解多目標(biāo)優(yōu)化問(wèn)題的非單調(diào)牛頓法的超線性收斂性

任潔,彭建文

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

1.引言

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

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

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

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

2.預(yù)備知識(shí)

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

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

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

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

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

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

2)x不是多目標(biāo)優(yōu)化問(wèn)題(2.1)的Pareto平穩(wěn)點(diǎn),當(dāng)且僅當(dāng)θN(x)＜0,或等價(jià)地,當(dāng)且僅當(dāng)dN(x)0.

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

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

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

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

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

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

在下一個(gè)命題中,說(shuō)明了算法3.1是有定義的,因?yàn)榭傆幸粋€(gè)滿足非單調(diào)Armijo條件(3.10)的步長(zhǎng),以便生成迭代序列{xk}.

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

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

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

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

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

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

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

證首先,我們證明對(duì)所有i=1,···,m有

接下來(lái),我們證明當(dāng)k →+∞時(shí),θN(xk)和‖‖dN(xk)‖‖都收斂到0.

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

5.局部超線性收斂率

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

6.結(jié)論

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