多目標規劃的有效解的研究

鄭玉秋

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

【關鍵詞】多目標規劃；賦范空間；有效解

【基金項目】項目名稱及編號：《亞純函數正規族及相關問題》（NEPUQN2014-23）.

多目標最優化是近20年迅速發展起來的一門新興學科，作為最優化的一個重要分支，它主要研究在某種意義下的多個數值目標同時最優化問題.多目標最優化的起源可以追溯到經濟學中A.Smith（1977）關于經濟平衡和F.Y.Edgeworth（1896，1906）在經濟福利理論著作中，不僅提出了多目標最優化問題，并且還引進了pareto最優化概念，這對多目標最優化學科的形成起著十分重要的作用和深遠的影響.

多目標規劃是在變量滿足約束的條件下，研究多個可數值化的目標函數同時最小化的問題，一般地，多目標規劃可以描述成如下形式：

（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）是約束變量.

多目標遇到的問題是如何衡量目標函數的好壞，我們知道對于單目標規劃來說，對任意的x1，x2∈R，總可以比較f（x1），f（x2）的大小，但對于多目標來說，就不那么簡單了，因為這時f（x1）=（f1（x1），f2（x1），…，fP（x1））T與f（x2）=（f1（x2），f2（x2），…，fP（x2））T，實際上都是P維向量，如何比較它們的大小是新問題，如何界定多目標最優化解的概念成為一個首要問題，多目標規劃的概念通常與向量集的有效點的概念有比較密切的關系.

一、預備知識

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

定義1 給定一個向量集x∈Rn，對于點x0∈X，若x∈X，有x0≤x，則稱x0是X的絕對最小點（即絕對最小向量）.

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

集合X的所有絕對最小點、有效點和弱有效點的集合分別記為Ea，Ep，Ewp.

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

下面這個定理將從幾何的角度描述有效點及弱有效點.

定理1 設x0∈XRn，則

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

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

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

下面從代數的角度描述有效點和弱有效點的特征.

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

（1）對于某個η∈Rn++，函數ηTx=∑ηixi，x∈X在x0處取到最小值；

（2）對于某個η∈Rn+，η>0，函數ηTx（x∈X）在x0處取到嚴格最小值；

（3）對于某個η∈Rn+，η>0，函數ηTx（x∈X）在x0處取到最小值.

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

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

根據定義3我們知道多目標規劃的（弱）有效解與其目標可行域的（弱）有效點有緊密聯系，我們歸納成如下定理.

二、主要結果

定理3 對于多目標規劃問題（VP），令Z=f（S）表示目標函數在定義域S上的值域（目標可行域），Z的有效點集和弱有效點集記為Zp和Zwp，則有：

（1）Sp=∪f*∈Zp{x∈S|f（x）=f*}；

（2）Swp=∪f*∈Zwp{x∈S|f（x）=f*}.

至于集合Sa，Sp，Swp之間的關系，有如下定理.

定理4 對于多目標規劃問題（VP），必有

（1）SaSpSwpS；

（2）當Sa≠時，Sa=Sp；

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

證明 先證（1），當Sa=時，結論自然成立.當Sa=時，若存在x*∈Sa，但x*Sp，則根據有效解Sp的定義，可知存在x∈S，使得f（x）

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

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

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