多目標(biāo)優(yōu)化問(wèn)題的同倫方法

王秀玉, 徐維華, 姜興武, 戴嘉軒

(1.長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院, 長(zhǎng)春 130012; 2.長(zhǎng)春理工大學(xué) 理學(xué)院, 長(zhǎng)春 130022;3.吉林工商學(xué)院 基礎(chǔ)部, 長(zhǎng)春 130062)

(1-μk)[f(x(k))λ(k)+gi(x(k))]+μk(x(k)-x(0))=0.(9)

多目標(biāo)優(yōu)化問(wèn)題的同倫方法

王秀玉1, 徐維華2, 姜興武3, 戴嘉軒1

(1.長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院, 長(zhǎng)春 130012; 2.長(zhǎng)春理工大學(xué) 理學(xué)院, 長(zhǎng)春 130022;
3.吉林工商學(xué)院 基礎(chǔ)部, 長(zhǎng)春 130062)

用組合同倫方法求解帶有不等式約束的多目標(biāo)優(yōu)化問(wèn)題, 該同倫方法不要求可行域滿足法錐條件, 且目標(biāo)函數(shù)權(quán)重向量的初始值是非可行的.在上述條件下, 給出了同倫路徑的存在性、有界性和收斂性的證明.

多目標(biāo)優(yōu)化問(wèn)題; 同倫算法; 同倫路徑

考慮如下多目標(biāo)優(yōu)化問(wèn)題:

其中:x∈n;M={1,2,…,m};L={1,2,…,p};f=(f1,f2,…,fp)T:n→p,g=(g1,g2,…,gm)T:n→m均為充分光滑的向量值函數(shù).

文獻(xiàn)[1-4]對(duì)單目標(biāo)的優(yōu)化問(wèn)題構(gòu)造了組合同倫方法, 求解單目標(biāo)問(wèn)題的K-K-T點(diǎn), 顯示了同倫方法在求解優(yōu)化問(wèn)題中的優(yōu)勢(shì).然而, 運(yùn)用文獻(xiàn)[1-4]中的組合同倫方法求解優(yōu)化問(wèn)題, 均需要可行域滿足各類(lèi)法錐條件, 從而使上述組合同倫方法的應(yīng)用范圍受到較大限制.

多目標(biāo)優(yōu)化問(wèn)題應(yīng)用廣泛, 文獻(xiàn)[5]將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題, 建立了一種組合同倫方程, 對(duì)多目標(biāo)問(wèn)題的K-K-T點(diǎn)進(jìn)行了求解, 將文獻(xiàn)[1-4]的組合同倫方法推廣到求解多目標(biāo)優(yōu)化問(wèn)題, 但目標(biāo)函數(shù)的權(quán)重保持不變.文獻(xiàn)[6-8]改善了文獻(xiàn)[5]的不足, 分別對(duì)可行域滿足法錐條件、擬法錐及弱法錐條件時(shí), 多目標(biāo)問(wèn)題K-K-T點(diǎn)的存在性和有界性進(jìn)行了研究.文獻(xiàn)[9]對(duì)凸多目標(biāo)優(yōu)化問(wèn)題構(gòu)造了動(dòng)約束同倫方法, 并改進(jìn)了權(quán)重向量為常向量的不足.但當(dāng)可行域不滿足任何法錐條件時(shí), 如何運(yùn)用文獻(xiàn)[5-8]中的同倫方法求解多目標(biāo)問(wèn)題的K-K-T點(diǎn), 目前尚未見(jiàn)文獻(xiàn)報(bào)道.本文考慮只含有不等式約束的多目標(biāo)規(guī)劃問(wèn)題, 且可行域不必滿足任何法錐條件, 建立了同倫方程, 既克服了目標(biāo)函數(shù)權(quán)重向量不變的不足, 又避免了法錐條件帶來(lái)的局限性, 給出了同倫路徑的存在性、有界性及收斂性證明.

1 同倫方程的構(gòu)造及同倫路徑的存在性

設(shè)x≥0(x>0)表示向量x的每個(gè)分量均為非負(fù)(正)數(shù),f表示向量值函數(shù)f:n→n的Jacobi矩陣,h表示數(shù)量值函數(shù)h:n→的梯度, 其中n表示n維歐氏空間.

對(duì)問(wèn)題(MOP), 本文對(duì)可行域?qū)嵭型獗平绞? 使用下列符號(hào): 0≤α<+∞為任意的非負(fù)常數(shù);Ωα={x∈n|gi(x)≤α,i∈M}為關(guān)于α的可行域n|gi(x)<α,i∈M}為關(guān)于α的嚴(yán)格可行域表示Ωα的邊界;Iα(x)={i|gi(x)=α,i∈M}表示點(diǎn)x∈Ωα的積極約束.當(dāng)α=0時(shí),Ω0即為多目標(biāo)問(wèn)題的可行域.

為求解問(wèn)題(MOP), 做如下假設(shè):

(H1)f(x),gi(x)(i∈M)是Cl(l≥3)函數(shù);

(H3) ?x∈?Ωα, {gi(x)|i∈Iα(x)}是正線性獨(dú)立的,gi(x)=0,yi≥0?yi=0.

其中:Y=diag(y1,y2,…,ym);e=(1,1,…,1)T;ω=(x,y,λ).

當(dāng)μ=1時(shí), 式(1)有唯一解ω(0)=(x(0),y(0),λ(0)); 當(dāng)μ=0時(shí), 式(1)為

此即為多目標(biāo)優(yōu)化問(wèn)題的K-K-T方程.顯然H(ω(0),ω(0),1)=0.對(duì)給定的(x(0),y(0),λ(0)), 同倫方程(1)的左邊H(ω,ω(0),μ)也記為Hω(0)(ω,μ), 并記

其中E為單位矩陣.由μ∈(0,1], 有

2 同倫路徑的有界性和收斂性

證明: 由同倫方程(1)的第二個(gè)方程可知, 若點(diǎn)(x,y,λ,μ)∈Γw(0), 則有

由同倫方程(1)的第三個(gè)方程可知

由式(4)可得

即

若Γω(0)無(wú)界, 則存在序列(x(k),y(k),λ(k),μk)∈Γω(0), 當(dāng)k→∞時(shí), 滿足‖(x(k),y(k),λ(k),μk)‖→∞.由上述證明知{λ(k)}有界.

又由同倫方程(1)的第二個(gè)式子得

x(k)→x(*),λ(k)→λ(*),μk→μ*, ‖y(k)‖→∞.

若μk→1, 則由式(7)得y(k)→y(0), 這與y(k)的無(wú)界性矛盾, 因此有μk→/1, i.e.,μ*≠1.由式(8)得

即x(*)∈Ωμ*/(1-μ*).顯然I?I(x(*)).由同倫方程(1)得

(1-μk)[f(x(k))λ(k)+gi(x(k))]+μk(x(k)-x(0))=0.(9)

即

（11）

式(11)與假設(shè)(H3)矛盾.

證明: 參考文獻(xiàn)[7]中定理3的證明.由引理1和引理2知Γw(0)為有界光滑曲線.由一維流形分類(lèi)定理知Γw(0)或者微分同胚于單位圓周, 或者微分同胚于單位區(qū)間(0,1].注意到

及

1)μ*∈[0,1),x(*)∈Ωμ*/(1-μ*),λ(*)∈Λ+, ‖y(*)‖→∞;

3)μ*=1,λ(*)∈Λ+,x(*)=x(0),y(*)=y(0);

[1]YU Bo, FENG Guochen, ZHANG Shaoliang.The Aggregate Constraint Homotopy Method for Nonconvex Nonlinear Programming [J].Nonlinear Analysis: Theory Methods & Applications, 2001, 45(1): 839-847.

[2]YU Bo.A Combined Homotopy Infeasible Interior Point Method for Nonconvex Programming [J].Pacific J Optim, 2012, 8(1): 89-101.

[3]LIU Qinghuai, YU Bo, FENG Guochen.An Interior Point Path-Following Method for Nonconvex Programming with Quasi Normal Cone Condition [J].Advances in Mathematics, 2000, 29(4): 381-382.

[4]蔡志丹, 趙立芹, 蘇孟龍.組合同倫內(nèi)點(diǎn)算法求解一類(lèi)非凸無(wú)界優(yōu)化問(wèn)題 [J].吉林大學(xué)學(xué)報(bào): 理學(xué)版, 2013, 51(6): 1073-1076.(CAI Zhidan, ZHAO Liqin, SU Menglong.Combined Homotopy Interior Point Algorithm for a Class of Unbounded Non-convex Optimization Problems [J].Journal of Jilin University: Science Edition, 2013, 51(6): 1073-1076.)

[5]Song W, Yao G M.Homotopy Method for a General Multiobjective Programming Problem [J].Journal of Optimization Theory and Applications, 2008, 138(1): 139-153.

[6]趙雪, 張春陽(yáng), 張樹(shù)功.弱擬法錐條件下解多目標(biāo)規(guī)劃問(wèn)題的同倫方法 [J].吉林大學(xué)學(xué)報(bào): 理學(xué)版, 2012, 50(4): 663-666.(ZHAO Xue, ZHANG Chunyang, ZHANG Shugong.Homotopy Method for Solving Multiobjective Programming Problem under Weak Quasi-normal Cone Condition [J].Journal of Jilin University: Science Edition, 2012, 50(4): 663-666.)

[7]ZHAO Xue, ZHANG Shugong, LIU Qinghuai.Homotopy Interior-Point Method for a General Multiobjective Programming Problem [J/OL].Journal of Applied Mathematics, 2012, doi: 10.1155/2012/497345.

[8]Zhao X, Zhang S G, Yang Y T, et al.Homotopy Method for a General Multiobjective Programming Problem under Generalized Quasinormal Cone Condition [J/OL].Abstract & Applied Analysis, 2012, doi:10.1155/2012/591612.

[9]SHANG Yufeng, YU Bo.A Constraint Shifting Homotopy Method for Convex Multi-objective Programming [J].Journal of Computational and Applied Mathematics, 2011, 236(5): 640-646.

HomotopyMethodforMultiobjectiveProgrammingProblems

WANG Xiuyu1, XU Weihua2, JIANG Xingwu3, DAI Jiaxuan1
(1.SchoolofBasicScience,ChangchunUniversityofTechnology,Changchun130012,China;
2.SchoolofScience,ChangchunUniversityofScienceandTechnology,Changchun130022,China;
3.DepartmentofBase,JilinBusinessandTechnologyCollege,Changchun130062,China)

The combined homotopy method was constructed for solving multiobjective programming problem with inequalities constraints.This method does not need that the feasible region satisfies the normal condition.And the initial weight vector of the objective function is infeasible.The existence, boundedness and convergence of the homotopy path were proved under the above mentioned conditions.

multiobjective programming problem; homotopy method; homotopy path

2013-12-03.

王秀玉(1965—), 女, 漢族, 碩士, 副教授, 從事最優(yōu)化理論與算法的研究, E-mail: wangxiuyu.000@163.com.

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào): 10771020)和吉林省自然科學(xué)基金(批準(zhǔn)號(hào): 201215128; 20101597).

O221.2

A

1671-5489(2014)06-1176-05

10.13413/j.cnki.jdxblxb.2014.06.13

趙立芹)