一般多目標(biāo)優(yōu)化問題的凝聚同倫內(nèi)點(diǎn)算法

賀 莉， 郭 旭， 溫延紅， 戴嘉軒

(1.長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長春 130012;2.長春職業(yè)技術(shù)學(xué)院， 吉林 長春 130033)

一般多目標(biāo)優(yōu)化問題的凝聚同倫內(nèi)點(diǎn)算法

賀 莉1， 郭 旭1， 溫延紅2， 戴嘉軒1

(1.長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長春 130012;2.長春職業(yè)技術(shù)學(xué)院， 吉林 長春 130033)

用凝聚函數(shù)把等價轉(zhuǎn)化后的不等式約束條件進(jìn)行光滑逼近，對目標(biāo)函數(shù)進(jìn)行線性加權(quán)轉(zhuǎn)化成單目標(biāo)函數(shù)，然后利用組合同倫內(nèi)點(diǎn)方法求解多目標(biāo)優(yōu)化問題的最小弱有效解，并證明該方法是整體收斂的。

多目標(biāo)規(guī)劃; 凝聚函數(shù); 同倫方法

0 引 言

凝聚同倫內(nèi)點(diǎn)方法是求解非凸非光滑優(yōu)化問題行之有效的一種方法。文獻(xiàn)[1]給出了求解非凸規(guī)劃問題的凝聚同倫內(nèi)點(diǎn)方法；文獻(xiàn)[2-5]討論了可行域在相應(yīng)條件下約束序列極大極小問題的凝聚同倫內(nèi)點(diǎn)法；文獻(xiàn)[6]研究了改進(jìn)的凝聚約束同倫方法；文獻(xiàn)[7]把凝聚同倫內(nèi)點(diǎn)方法推廣到求解帶有不等式約束的凸多目標(biāo)優(yōu)化問題，文中在此基礎(chǔ)上研究更一般的情形，即同時帶有等式和不等式約束的凸多目標(biāo)優(yōu)化問題。

考慮下述一般多目標(biāo)規(guī)劃(MOP)問題

(1)

其中

文中采用下列記號：

P={1,2,…,p}，M={1,2,…,m}，L={1,2,…,l}；

Ω={x∈Rn|gi(x)≤0,hj(x)=0;i∈M,j∈L}表示可行集；

Ω0={x∈Rn|gi(x)<0,hj(x)=0;i∈M,j∈L}表示嚴(yán)格可行集；

I(x)={i∈{1,2,…,m}|gi(x)=0}表示積極指標(biāo)集；

?Ω=ΩΩ0表示可行集邊界。

令

易見，不等式約束集合{x∈Rn|gi(x)≤0,i∈M}與{x∈Rn|g(x)≤0}等價。于是問題(1)等價轉(zhuǎn)化為如下單個不等式約束問題：

(2)

定義凝聚函數(shù)

t>0

則問題(2)轉(zhuǎn)化為下面的光滑優(yōu)化問題

(3)

令

文中基本假設(shè)：

(C1)f,gi,i∈M為三次連續(xù)可微凸函數(shù),hj,j∈L為線性函數(shù)；

(C2)Ω0非空有界連通集；

(C3)對?x∈Ω，向量組(▽gi(x),▽hj(x)|i∈I(x),j∈L)線性無關(guān)；

引理1 假設(shè)條件(C1)成立，則g(x,θ t)也是三次連續(xù)可微凸函數(shù)，且g(x)≤g(x,θ t)≤g(x)+θ tlnm。

標(biāo)注1:由引理1知，當(dāng)t→0+時，問題(3)的解即為問題(2)的解，從而為問題(1)的解。

引理2

0

引理3

假設(shè)條件(C1),(C2)成立，則1)對?θ∈(0,1]，t∈(0,1]有Ωθ(t)?Ω;

引理4

假設(shè)條件(C1)～(C4)成立，則1)存在θ∈(0,1]，使得對?t∈(0,1]，對?x∈Ωθ(t)，向量組(▽xg(x,θ t),▽hj(x)|j∈L)線性無關(guān)，即

引理1～引理4的證明可參見文獻(xiàn)[3]。

1 主要結(jié)果

對于問題(3)利用線性加權(quán)法將其轉(zhuǎn)化為如下n+p個變量的非線性規(guī)劃問題

(4)

定義1[8]設(shè)x∈Ω,如果不存在y∈Ω,使f(y)≤f(x)(或f(y)

定義2[8]如果(x*,λ*)是問題(4)的最優(yōu)解，則稱x*是問題(3)的最小弱有效解。

(5)

稱(x,λ)是問題(4)的K-K-T點(diǎn)，(y,z,ζ,h)是問題(4)的Lagrange乘子。

當(dāng)t→0+時，方程(5)的K-K-T點(diǎn)收斂于問題(4)的最優(yōu)解，即為問題(1)的最小弱有效解。

為求解(5)構(gòu)造同倫方程:

(6)

其中

當(dāng)t=1時，同倫方程(6)變?yōu)?/p>

(7)

當(dāng)t→0時，方程(6)的解為方程(5)的K-K-T點(diǎn)，即為問題(1)的最小弱有效解。

證明 用H′(w,w(0),t)記為H的jacobi陣，則

(8)

其中

事實(shí)上，由同倫方程(6)中的

下證Γw(0)是有界曲線。若Γw(0)無界，則存在序列{(w(k),tk)}?Γw(0)，有

由假設(shè)(C2)及Λ++的定義及t∈(0,1],存在子列{(w(k),tk)},不妨設(shè)其本身，k→+∞,有x(k)→x*∈Ω，λ(k)→λ*∈Λ+，tk→t*∈[0,1],‖(y(k),z(k),ζ(k),h(k)‖→+∞。

下面證明‖(y(k),z(k),ζ(k),h(k))‖→+∞是不可能的。

‖h(k)‖→+∞,‖ζ(k)‖→+∞的不可能性證明見文獻(xiàn)[1]。

1)下面證明若z無界，則‖z(k)‖→+∞(k→∞)，由式(6)的第一個方程得

取極限(k→+∞)，得

(9)

若式(9)成立，則其極限必存在,記

2)下面證明{y(k)}有界:

﹙Ⅰ﹚當(dāng)t*=1時，由式(6)的第一個方程有

(10)

(Ⅱ)當(dāng)0≤t*<1時，由式(6)的第一個方程，有

(11)

當(dāng)取k→+∞的極限時，式(11)左端極限的第一、三、四部分是有限的，而第二部分無窮大，矛盾。所以{y(k)}有界。

由以上討論知‖w(k)‖→/ +∞,即Γw(0)是有界的。

2 算法收斂性

特別地，如果Γw(0)是有限的，(w*,0)是Γw(0)的另一端點(diǎn)，則w*是K-K-T方程的一個解。

是非奇異的，Γw(0)只能微分同胚于區(qū)間(0,1]，設(shè)(w*,t*)是Γw(0)當(dāng)t→0+的極限點(diǎn),則有下列可能情形：

用Γw(0)的弧長s參數(shù)化該曲線，即存在連續(xù)可微函數(shù)w(s),t(s),使得

(12)

微分式(12),得定理4。

定理4 同倫路徑Γw(0)由下面的常微分方程初值問題確定

(13)

并且如果有t(s*)=0,則w*=(x(s*),λ(s*),y(s*),z(s*),ζ(s*),h(s*))T是K-K-T方程的解。

3 結(jié) 語

多目標(biāo)優(yōu)化問題是近30年來迅速發(fā)展起來的一門新興學(xué)科,主要研究在某種意義下多個指標(biāo)同時達(dá)到最優(yōu)的問題。由于所涉及到的多個指標(biāo)并不是獨(dú)立的，它們往往是通過決策變量耦合在一起且處于相互競爭、相互沖突的狀態(tài)，同時所涉及到的函數(shù)大多是不光滑的，由此帶來的復(fù)雜性使得對多目標(biāo)問題進(jìn)行優(yōu)化變得十分困難。文中在已有研究結(jié)果的基礎(chǔ)上，實(shí)現(xiàn)了凝聚同倫內(nèi)點(diǎn)方法求解一類非光滑凸多目標(biāo)優(yōu)化問題的最小弱有效解，擴(kuò)大了凝聚同倫內(nèi)點(diǎn)方法的適用范圍。

[1] 劉慶懷.解非凸規(guī)劃問題的組合同倫內(nèi)點(diǎn)法[D]:[博士學(xué)位論文].長春:吉林大學(xué),1999.

[2] YU Bo, LIU Guo-xin, FENG Guo-chen, et al. The aggretate homotopy method for constrained sequential max-min problem[J]. Northeast. Math.,2003,19(4)：287-290.

[3] 金鑒祿，譚佳偉，賀莉，等.一般非線性規(guī)劃問題的凝聚同倫內(nèi)點(diǎn)方法[J].吉林大學(xué)學(xué)報,2011,49(6)：1044-1052.

[4] 金鑒祿，王秀玉，賀莉，等.約束序列極大極小問題的凝聚同倫內(nèi)點(diǎn)方法[J].應(yīng)用數(shù)學(xué)學(xué)報,2010,33(5)：792-804.

[5] 張春陽，張國霜，李卓識，等.正獨(dú)立映射的判定及其在非凸優(yōu)化中的應(yīng)用[J].長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，31(1)：111-114.

[6] 蘇猛龍，趙立芹，呂顯瑞.改進(jìn)的凝聚約束同倫方法求解一類非線性最優(yōu)化問題[J].吉林大學(xué)學(xué)報：理學(xué)版，2008，46(6)：1094-1096.

[7] 楊軼華,趙立芹,呂顯瑞,等.多目標(biāo)凸規(guī)劃凝聚同倫內(nèi)點(diǎn)算法[J].吉林大學(xué)學(xué)報:理學(xué)版,2006,44(6)：883-887.

[8] 林銼云, 董加禮.多目標(biāo)優(yōu)化的方法與理論[M].長春:吉林教育出版社,1992.

[9] Allgower E L. Numerical continuation methods: an introducation[M]. New York: Springer-Verlag,1990.

Aggregate homotopy interior-point method for general multiobjective programming

HE Li1, GUO Xu1, WEN Yan-hong2, DAI Jia-xuan1

(1.School of Basic Sciences, Changchun University of Technology, Changchun 130012， China;2.Changchun Vocational Institute of Technology, Changchun 130033， China)

Inequality constraint conditions after equivalent transformation is smooth approximated by means of aggregate function, and then the multi-objective function is transferred into a single objective function with linear weighing. We get the minimal weak efficient solution for the multi-objective optimization problem via the aggregate homotopy method, and prove that it is globally convergent.

multi-objective optimization; aggregate function; homotopy method.

2014-03-12

國家自然科學(xué)基金資助項(xiàng)目(10771020); 吉林省自然科學(xué)基金資助項(xiàng)目(20130101061JC)

賀 莉(1970-)，女，漢族，吉林圖們?nèi)?，長春工業(yè)大學(xué)副教授，碩士，主要從事最優(yōu)化理論與算法研究,E-mail:heli_xu@126.com.

O 221

A

1674-1374(2014)06-0601-06