彭雪珂，周光明，趙文杰

(湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，湖南 湘潭 411105)

最近幾十年來,向量優(yōu)化的理論與方法被廣泛應(yīng)用于金融、管理和最優(yōu)決策等領(lǐng)域.向量優(yōu)化問題的提出最早源于經(jīng)濟(jì)學(xué).1896年,經(jīng)濟(jì)學(xué)家Pareto[1]將許多不好比較的目標(biāo)從政治經(jīng)濟(jì)學(xué)的角度歸納為多目標(biāo)規(guī)劃問題.隨后,他提出的Pareto最優(yōu)解[2]概念極大地促進(jìn)了向量優(yōu)化問題的發(fā)展.1951年,Koopmans[3]首次提出Pareto有效解概念.同年,Kuhn等[4]在提出向量優(yōu)化問題的Pareto最優(yōu)解的同時(shí),還對該解存在的充分和必要條件進(jìn)行了研究.之后,向量優(yōu)化理論問題受到了學(xué)者們的關(guān)注,并獲得了許多重要的研究成果[5-10].

多項(xiàng)式優(yōu)化是一類重要的非線性規(guī)劃,關(guān)于這類優(yōu)化問題的局部最優(yōu)研究可以參考非線性規(guī)劃中的研究方法.許多學(xué)者專注于探討該類問題的全局優(yōu)化[11-14].近些年,學(xué)者們還對其理論與算法進(jìn)行了研究[15-22].目前,求解多項(xiàng)式全局優(yōu)化問題主要有SOS方法和Lasserre松弛方法.當(dāng)向量優(yōu)化問題中的目標(biāo)函數(shù)和約束條件都由多項(xiàng)式描述時(shí),稱之為向量多項(xiàng)式優(yōu)化問題.筆者擬采用Lasserre松弛方法得到向量多項(xiàng)式優(yōu)化問題的最優(yōu)解.Lasserre松弛方法在滿足一定秩條件的時(shí)候可以得到原多項(xiàng)式問題的最優(yōu)值,且Lasserre[14]已證明下界序列的收斂性.該方法對于求解具有多項(xiàng)式特性的問題非常有效.

1 預(yù)備知識

向量優(yōu)化問題的一般形式為[5]

minf(x)=(f1(x),f2(x),…,fk(x))T,
s.t.gj(x)≥0j=1,2,…,p,
hr(x)=0r=1,2,…,q.

(1)

其中：x=(x1,…,xn)T為n維決策變量；fi(x)(i=1,…,k)，gj(x)(j=1,…,p),hr(x)(r=1,…,q)都是Rn→R的連續(xù)向量函數(shù).記約束集合

K∶={x∈Rn|gj(x)≥0,j=1,…,p,hr(x)=0,r=1,…,q}.

(2)

從純粹的數(shù)學(xué)角度出發(fā),向量優(yōu)化問題的“最優(yōu)解”與通常數(shù)值意義上比較大小的概念有所區(qū)別,它表示均衡或者“非劣”.因此,引入非劣解(也稱為有效解),它表示不劣于可行解集中的任何一個(gè)解.

定義1[5]設(shè)x*∈K,若對于?x∈K,有fi(x*)≤fi(x)(i=1,2,…,k),則稱x*為問題(1)的絕對最優(yōu)解.

考慮一類特殊的向量優(yōu)化問題.即問題(1)中的目標(biāo)函數(shù)和約束條件都是由多項(xiàng)式描述的,fi(x)∈R[x](i=1,2,…,k),gj(x)∈R[x](j=1,2,…,p),hr(x)∈R[x](r=1,2,…,q)均為實(shí)多元多項(xiàng)式,稱這樣的問題為向量多項(xiàng)式優(yōu)化問題.為了描述的方便,記為

(3)

假設(shè)fi(x)的最高次數(shù)為mi(i=1,2,…,k),實(shí)值多項(xiàng)式gj(x)次數(shù)不超過wj(j=1,2,…,p),實(shí)值多項(xiàng)式hr(x)次數(shù)不超過vr(r=1,2,…,q).

對于一般的多項(xiàng)式優(yōu)化問題,Lasserre[14]提出了松弛優(yōu)化方法.即利用矩-SOS松弛將原問題轉(zhuǎn)化為半定規(guī)劃問題(SDP),并通過求解一系列的SDP問題,得到一個(gè)單調(diào)遞增收斂于原問題全局最優(yōu)值的下界序列.

令

(4)

(5)

給定一個(gè)實(shí)值多項(xiàng)式p(x)∈R[x],考慮如下帶約束多項(xiàng)式優(yōu)化問題：

(6)

其中:p(x)的最高次數(shù)為m;

(7)

s.t.MN(y)0,

并證明了如下結(jié)果：

2 向量多項(xiàng)式優(yōu)化問題的數(shù)值方法

筆者基于求解多項(xiàng)式優(yōu)化問題的Lasserre松弛方法[14],以及求解一般向量優(yōu)化問題的主要目標(biāo)法、線性加權(quán)和法和理想點(diǎn)法[5],分別提出求解向量多項(xiàng)式優(yōu)化問題的主要目標(biāo)法、線性加權(quán)和法和理想點(diǎn)法.這些方法的總體思路是將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù),從而得到一個(gè)多項(xiàng)式優(yōu)化問題,再利用Lasserre松弛方法求解該問題.

2.1 向量多項(xiàng)式優(yōu)化問題的主要目標(biāo)法

假定要同時(shí)考察k個(gè)目標(biāo)f1(x),…,fk(x),其中變量x∈K,由(2)式所定義.在不考慮其他目標(biāo)時(shí),記第i個(gè)目標(biāo)的最優(yōu)值

(8)

相應(yīng)的最優(yōu)解記為xi*(i=1,2,…,k).

假設(shè)f1(x)為主要目標(biāo),而對其他k-1個(gè)目標(biāo)fi(x)(i=2,…,k)有一組允許的界限值,即希望滿足以下條件:

fi(x)≤fi(xi*)+aii=2,…,k,

(9)

其中ai為取定的合適常數(shù).通過添加額外的約束條件,問題(3)轉(zhuǎn)化成如下多項(xiàng)式優(yōu)化問題：

(10)

(11)

基于Lasserre松弛方法求解向量多項(xiàng)式優(yōu)化問題的主要目標(biāo)法的步驟如下：

(ⅰ)對于給定的原向量多項(xiàng)式優(yōu)化問題(3),確定f1(x)為主要目標(biāo),則當(dāng)f1(x)取得最小時(shí),其他k-1個(gè)目標(biāo)需滿足條件(9)；

(ⅱ)對所有的i=2,…,k,求解問題(8),求出對應(yīng)的xi*；

現(xiàn)證明用以上主要目標(biāo)法求得的解是原向量多項(xiàng)式優(yōu)化問題(3)的弱有效解.

下面對向量多項(xiàng)式優(yōu)化問題的主要目標(biāo)法進(jìn)行數(shù)值實(shí)驗(yàn).數(shù)值實(shí)驗(yàn)的運(yùn)行環(huán)境是：操作系統(tǒng)為Win10的8GB RAM的計(jì)算機(jī),處理器為Intel i5-6500 dual core@3.20 Hz,調(diào)用Matlab R2016b軟件,求解單目標(biāo)多項(xiàng)式優(yōu)化問題的軟件包為GloptiPoly 3[17](這個(gè)軟件包的核心算法是基于Lasserre松弛方法).線性加權(quán)和法和理想點(diǎn)法的數(shù)值實(shí)驗(yàn)運(yùn)行環(huán)境與此相同.

算例1考慮向量多項(xiàng)式優(yōu)化問題：

0≤x1≤2,0≤x2≤3.

0≤x1≤2,0≤x2≤3.

用Lasserre松弛方法求解上述問題,得到最優(yōu)值約為-16.667 5,x*≈(0.669 6,1.598 0),對應(yīng)目標(biāo)函數(shù)值(f1(x*),f2(x*))≈(-16.667 5,-5.847 2).由定理3可知,x*也為原向量多項(xiàng)式優(yōu)化問題的弱有效解.

算例2考慮向量多項(xiàng)式優(yōu)化問題：

0≤x1≤3,0≤x2≤4.

該問題中的約束條件取自文獻(xiàn)[17].假設(shè)其主要目標(biāo)函數(shù)為f1(x)=-x1-x2，則當(dāng)f1(x)取得最小時(shí),目標(biāo)函數(shù)f2(x)要滿足條件(9).這里設(shè)置ai=|fi(xi*)/10|,對于i=2,求解對應(yīng)問題(10),即

minf1(x)=-x1-x2,

0≤x1≤3,0≤x2≤4.

用Lasserre松弛方法求解上述問題,得到最優(yōu)值約為-4.053 7,x*≈(0.611 6,3.442 1),對應(yīng)目標(biāo)函數(shù)值(f1(x*),f2(x*))≈(-4.053 7，-3.212 2).由定理3可知,x*也為原向量多項(xiàng)式優(yōu)化問題的弱有效解.

算例3考慮向量多項(xiàng)式優(yōu)化問題：

x1+x2+x3≤4,3x2+x3≤6,0≤x1≤2,x2≥0,0≤x3≤3.

該問題中的約束條件取自文獻(xiàn)[18].假設(shè)其主要目標(biāo)函數(shù)為f1(x)=-2x1+x2-x3,則當(dāng)f1(x)取得最小時(shí),目標(biāo)函數(shù)f2(x)要滿足條件(9).這里設(shè)置ai=|fi(xi*)/3|,對于i=2,求解對應(yīng)問題(10),即

minf1(x)=-2x1+x2-x3,

x1+x2+x3≤4,

3x2+x3≤6,

0≤x1≤2,x2≥0,0≤x3≤3,

用Lasserre松弛方法求解上述問題,得到最優(yōu)值約為-3.530 3,x*≈(2.000 0,0.874 3,0.404 6),目標(biāo)函數(shù)值(f1(x*),f2(x*))≈(-3.530 3,-9.333 4).由定理3可知,x*也為原向量多項(xiàng)式優(yōu)化問題的弱有效解.

2.2 向量多項(xiàng)式優(yōu)化問題的線性加權(quán)和法

(12)

(13)

其中:c為任意常數(shù)(c≠0);

(14)

(15)

s.t.MN(y)0，

基于Lasserre松弛方法求解向量多項(xiàng)式優(yōu)化問題的線性加權(quán)和法的步驟如下:

(ⅰ)對于給定的向量多項(xiàng)式優(yōu)化問題(3),利用α-法確定一組權(quán)系數(shù)λi(i=1,2,…,k)；

(ⅱ)做出新的目標(biāo)函數(shù)

(16)

(ⅲ)將原向量多項(xiàng)式優(yōu)化問題(3)轉(zhuǎn)化成單目標(biāo)多項(xiàng)式問題(16),用Lasserre松弛方法求解問題(16)的全局最優(yōu)解.

現(xiàn)證明用以上線性加權(quán)和法求得的解是原向量多項(xiàng)式優(yōu)化問題(3)的弱有效解.

證明過程與定理3類似,在此省略.

下面對向量多項(xiàng)式優(yōu)化問題的線性加權(quán)和法進(jìn)行數(shù)值實(shí)驗(yàn).

算例4考慮向量多項(xiàng)式優(yōu)化問題:

0≤x1≤2,0≤x2≤3.

該問題中的約束條件取自文獻(xiàn)[19].記約束集合

在約束集合K下,利用(14)式對目標(biāo)函數(shù)分別求得其最優(yōu)解為:

算例5考慮向量多項(xiàng)式優(yōu)化問題:

0≤x1≤3,0≤x2≤4.

該問題中的約束條件取自文獻(xiàn)[17].記約束集合

在約束集合K下,利用(14)式對目標(biāo)函數(shù)分別求得其最優(yōu)解為:

算例6考慮向量多項(xiàng)式優(yōu)化問題:

該問題中的約束條件取自文獻(xiàn)[19].記約束集合為

K={x∈R5|20x1+12x2+11x3+7x4+4x5≤40,0≤x1,x2,x3,x4,x5≤1}.

在約束集合K下,利用(14)式對目標(biāo)函數(shù)分別求得其最優(yōu)解為:

2.3 向量多項(xiàng)式優(yōu)化問題的理想點(diǎn)法

對于不同的模,可找到不同意義下的最優(yōu)點(diǎn),一般定義的p-模為

(17)

s.t.MN(y)0，

基于Lasserre松弛方法求解向量多項(xiàng)式優(yōu)化問題的理想點(diǎn)法的步驟如下:

(ⅱ)構(gòu)造新的目標(biāo)函數(shù)(17)；

下面證明用以上理想點(diǎn)法求得的解是原向量多項(xiàng)式優(yōu)化問題(3)的有效解.

證明過程與定理3類似,在此省略.

下面對求解向量多項(xiàng)式優(yōu)化問題的理想點(diǎn)法進(jìn)行數(shù)值實(shí)驗(yàn)(為了避免羅列太多結(jié)果,此處令p=1或p=2).

算例7考慮向量多項(xiàng)式優(yōu)化問題:

0≤x1≤2,0≤x2≤3.

該問題中的約束條件取自文獻(xiàn)[19].分別對單目標(biāo)f1(x),f2(x),f3(x)求得其最優(yōu)解,對應(yīng)的目標(biāo)值為:

算例8考慮向量多項(xiàng)式優(yōu)化問題:

0≤x1≤3,0≤x2≤4.

該問題中的約束條件取自文獻(xiàn)[17].分別對單目標(biāo)f1(x),f2(x)求得其最優(yōu)解,對應(yīng)的目標(biāo)值為:

3 結(jié)語

結(jié)合求解一般向量優(yōu)化問題的方法和Lasserre松弛方法,提出了求解向量多項(xiàng)式優(yōu)化問題的主要目標(biāo)法、線性加權(quán)和法和理想點(diǎn)法.數(shù)值實(shí)驗(yàn)結(jié)果表明這些方法都是有效的,都能得到原向量多項(xiàng)式優(yōu)化問題的弱有效解或有效解.