多目標(biāo)規(guī)劃的有效解的研究

鄭玉秋

【摘要】在一般的賦范空間，我們給出了向量集上有效解的定義，從幾何、代數(shù)角度描述了它的性質(zhì)，并證明了有效解及弱有效解的關(guān)系.

【關(guān)鍵詞】多目標(biāo)規(guī)劃；賦范空間；有效解

【基金項(xiàng)目】項(xiàng)目名稱(chēng)及編號(hào)：《亞純函數(shù)正規(guī)族及相關(guān)問(wèn)題》（NEPUQN2014-23）.

多目標(biāo)最優(yōu)化是近20年迅速發(fā)展起來(lái)的一門(mén)新興學(xué)科，作為最優(yōu)化的一個(gè)重要分支，它主要研究在某種意義下的多個(gè)數(shù)值目標(biāo)同時(shí)最優(yōu)化問(wèn)題.多目標(biāo)最優(yōu)化的起源可以追溯到經(jīng)濟(jì)學(xué)中A.Smith（1977）關(guān)于經(jīng)濟(jì)平衡和F.Y.Edgeworth（1896，1906）在經(jīng)濟(jì)福利理論著作中，不僅提出了多目標(biāo)最優(yōu)化問(wèn)題，并且還引進(jìn)了pareto最優(yōu)化概念，這對(duì)多目標(biāo)最優(yōu)化學(xué)科的形成起著十分重要的作用和深遠(yuǎn)的影響.

多目標(biāo)規(guī)劃是在變量滿足約束的條件下，研究多個(gè)可數(shù)值化的目標(biāo)函數(shù)同時(shí)最小化的問(wèn)題，一般地，多目標(biāo)規(guī)劃可以描述成如下形式：

（VP）minf（x）=（f1（x），f2（x），…，fp（x））T，x∈R，

S={x∈En|g（x）=g1（x），g2（x），…，gm（x）}T≤0，

h（x）=（h1（x），h2（x），…，hi（x））T=0，

其中x是決策變量，gi（x），hj（x）是約束變量.

多目標(biāo)遇到的問(wèn)題是如何衡量目標(biāo)函數(shù)的好壞，我們知道對(duì)于單目標(biāo)規(guī)劃來(lái)說(shuō)，對(duì)任意的x1，x2∈R，總可以比較f（x1），f（x2）的大小，但對(duì)于多目標(biāo)來(lái)說(shuō)，就不那么簡(jiǎn)單了，因?yàn)檫@時(shí)f（x1）=（f1（x1），f2（x1），…，fP（x1））T與f（x2）=（f1（x2），f2（x2），…，fP（x2））T，實(shí)際上都是P維向量，如何比較它們的大小是新問(wèn)題，如何界定多目標(biāo)最優(yōu)化解的概念成為一個(gè)首要問(wèn)題，多目標(biāo)規(guī)劃的概念通常與向量集的有效點(diǎn)的概念有比較密切的關(guān)系.

一、預(yù)備知識(shí)

在討論向量集的有效點(diǎn)之前，約定如下記號(hào)：對(duì)于任意兩個(gè)向量x=（x1，x2，…，xn）T，y=（y1，y2，…，yn）T∈Rn，令x=yxi=yi，i=1，2，…，n；x

定義1 給定一個(gè)向量集x∈Rn，對(duì)于點(diǎn)x0∈X，若x∈X，有x0≤x，則稱(chēng)x0是X的絕對(duì)最小點(diǎn)（即絕對(duì)最小向量）.

定義2 若不存在x∈X使得x

集合X的所有絕對(duì)最小點(diǎn)、有效點(diǎn)和弱有效點(diǎn)的集合分別記為Ea，Ep，Ewp.

為了從幾何角度描述有效點(diǎn)和弱有效點(diǎn)，我們約定：將X平移x0得到的集合記為X+x0；非負(fù)錐Rn+={x∈Rn|x≥0}；正錐Rn++={x∈Rn|x>0}.

下面這個(gè)定理將從幾何的角度描述有效點(diǎn)及弱有效點(diǎn).

定理1 設(shè)x0∈XRn，則

（1）x0是X的有效點(diǎn)，即x0∈EpX∩（x0-Rn+）={x0}.

（2）x0是X的弱有效點(diǎn)，即x0∈EωpX∩（x0-Rn++）=.

若對(duì)任意給定的范數(shù)空間X，Y，AY，CY是Y上的凸錐，intC≠，定義在Y上的有效點(diǎn)和弱有效點(diǎn)有下面的性質(zhì)：A∩（x0-C）={x0}，A∩（x0-intC）=.

下面從代數(shù)的角度描述有效點(diǎn)和弱有效點(diǎn)的特征.

定理2 給定x0∈XRn，考慮下面條件：

（1）對(duì)于某個(gè)η∈Rn++，函數(shù)ηTx=∑ηixi，x∈X在x0處取到最小值；

（2）對(duì)于某個(gè)η∈Rn+，η>0，函數(shù)ηTx（x∈X）在x0處取到嚴(yán)格最小值；

（3）對(duì)于某個(gè)η∈Rn+，η>0，函數(shù)ηTx（x∈X）在x0處取到最小值.

若條件（1）或（2）成立，則x0是X的有效點(diǎn)，若條件（3）成立，則x0是X的弱有效點(diǎn).

定義3 設(shè)x0∈S，如果不存在x∈S，使f（x）

根據(jù)定義3我們知道多目標(biāo)規(guī)劃的（弱）有效解與其目標(biāo)可行域的（弱）有效點(diǎn)有緊密聯(lián)系，我們歸納成如下定理.

二、主要結(jié)果

定理3 對(duì)于多目標(biāo)規(guī)劃問(wèn)題（VP），令Z=f（S）表示目標(biāo)函數(shù)在定義域S上的值域（目標(biāo)可行域），Z的有效點(diǎn)集和弱有效點(diǎn)集記為Zp和Zwp，則有：

（1）Sp=∪f(wàn)*∈Zp{x∈S|f（x）=f*}；

（2）Swp=∪f(wàn)*∈Zwp{x∈S|f（x）=f*}.

至于集合Sa，Sp，Swp之間的關(guān)系，有如下定理.

定理4 對(duì)于多目標(biāo)規(guī)劃問(wèn)題（VP），必有

（1）SaSpSwpS；

（2）當(dāng)Sa≠時(shí)，Sa=Sp；

（3）若可行域S為凸集，f是S上嚴(yán)格凸的向量函數(shù)（即fi=（i=1，2，…，p）都是S上的嚴(yán)格凸函數(shù)），則Sp=Swp.

證明 先證（1），當(dāng)Sa=時(shí)，結(jié)論自然成立.當(dāng)Sa=時(shí)，若存在x*∈Sa，但x*Sp，則根據(jù)有效解Sp的定義，可知存在x∈S，使得f（x）

再證SpSwp，此時(shí)，不妨設(shè)Sp≠，若存在x*∈Sp，但是x*Swp，則存在x∈S，使得f（x）

（2）根據(jù)結(jié)論（1），只需要證明SpSa，假設(shè)x*Sp，但是x*S.由于Sa≠，所以存在x∈Sa，使得f（x）≤f（x*）.注意到x*Sa，所以f（x）≠f（x*），于是得到f（x）

（3）根據(jù)結(jié)論（1），我們只需證明SwpSp.假設(shè)x*Swp，但是x*Sp.根據(jù)有效解的定義，存在x∈Sa，使得f（x）