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

彭雪珂，周光明，趙文杰

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

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

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

1 預備知識

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

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

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

(3)

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

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

令

(4)

(5)

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

(6)

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

(7)

s.t.MN(y)0,

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

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

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

2.1 向量多項式優(yōu)化問題的主要目標法

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

(8)

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

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

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

(9)

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

(10)

(11)

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

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

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

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

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

算例1考慮向量多項式優(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),對應目標函數(shù)值(f1(x*),f2(x*))≈(-16.667 5,-5.847 2).由定理3可知,x*也為原向量多項式優(yōu)化問題的弱有效解.

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

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

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

minf1(x)=-x1-x2,

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

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

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

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

該問題中的約束條件取自文獻[18].假設其主要目標函數(shù)為f1(x)=-2x1+x2-x3,則當f1(x)取得最小時,目標函數(shù)f2(x)要滿足條件(9).這里設置ai=|fi(xi*)/3|,對于i=2,求解對應問題(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),目標函數(shù)值(f1(x*),f2(x*))≈(-3.530 3,-9.333 4).由定理3可知,x*也為原向量多項式優(yōu)化問題的弱有效解.

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

(12)

(13)

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

(14)

(15)

s.t.MN(y)0，

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

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

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

(16)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 向量多項式優(yōu)化問題的理想點法

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

(17)

s.t.MN(y)0，

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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