一般多目標優化問題的凝聚同倫內點算法

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

(1.長春工業大學 基礎科學學院， 吉林 長春 130012;2.長春職業技術學院， 吉林 長春 130033)

一般多目標優化問題的凝聚同倫內點算法

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

(1.長春工業大學 基礎科學學院， 吉林 長春 130012;2.長春職業技術學院， 吉林 長春 130033)

用凝聚函數把等價轉化后的不等式約束條件進行光滑逼近，對目標函數進行線性加權轉化成單目標函數，然后利用組合同倫內點方法求解多目標優化問題的最小弱有效解，并證明該方法是整體收斂的。

多目標規劃; 凝聚函數; 同倫方法

0 引 言

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

考慮下述一般多目標規劃(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}表示嚴格可行集；

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

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

令

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

(2)

定義凝聚函數

t>0

則問題(2)轉化為下面的光滑優化問題

(3)

令

文中基本假設：

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

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

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

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

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

引理2

0

引理3

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

引理4

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

引理1～引理4的證明可參見文獻[3]。

1 主要結果

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

(4)

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

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

(5)

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

當t→0+時，方程(5)的K-K-T點收斂于問題(4)的最優解，即為問題(1)的最小弱有效解。

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

(6)

其中

當t=1時，同倫方程(6)變為

(7)

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

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

(8)

其中

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

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

由假設(C2)及Λ++的定義及t∈(0,1],存在子列{(w(k),tk)},不妨設其本身，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)‖→+∞的不可能性證明見文獻[1]。

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

取極限(k→+∞)，得

(9)

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

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

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

(10)

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

(11)

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

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

2 算法收斂性

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

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

用Γw(0)的弧長s參數化該曲線，即存在連續可微函數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 結 語

多目標優化問題是近30年來迅速發展起來的一門新興學科,主要研究在某種意義下多個指標同時達到最優的問題。由于所涉及到的多個指標并不是獨立的，它們往往是通過決策變量耦合在一起且處于相互競爭、相互沖突的狀態，同時所涉及到的函數大多是不光滑的，由此帶來的復雜性使得對多目標問題進行優化變得十分困難。文中在已有研究結果的基礎上，實現了凝聚同倫內點方法求解一類非光滑凸多目標優化問題的最小弱有效解，擴大了凝聚同倫內點方法的適用范圍。

[1] 劉慶懷.解非凸規劃問題的組合同倫內點法[D]:[博士學位論文].長春:吉林大學,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] 金鑒祿，譚佳偉，賀莉，等.一般非線性規劃問題的凝聚同倫內點方法[J].吉林大學學報,2011,49(6)：1044-1052.

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

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

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

[7] 楊軼華,趙立芹,呂顯瑞,等.多目標凸規劃凝聚同倫內點算法[J].吉林大學學報:理學版,2006,44(6)：883-887.

[8] 林銼云, 董加禮.多目標優化的方法與理論[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

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

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

O 221

A

1674-1374(2014)06-0601-06