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

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

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

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

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

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

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

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

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

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

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

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

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

對問題(MOP), 本文對可行域?qū)嵭型獗平绞? 使用下列符號: 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時,Ω0即為多目標(biāo)問題的可行域.

為求解問題(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時, 式(1)有唯一解ω(0)=(x(0),y(0),λ(0)); 當(dāng)μ=0時, 式(1)為

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

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

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

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

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

由式(4)可得

即

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

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

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

若μk→1, 則由式(7)得y(k)→y(0), 這與y(k)的無界性矛盾, 因此有μ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)為有界光滑曲線.由一維流形分類定理知Γ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)算法求解一類非凸無界優(yōu)化問題 [J].吉林大學(xué)學(xué)報: 理學(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]趙雪, 張春陽, 張樹功.弱擬法錐條件下解多目標(biāo)規(guī)劃問題的同倫方法 [J].吉林大學(xué)學(xué)報: 理學(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.

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

O221.2

A

1671-5489(2014)06-1176-05

10.13413/j.cnki.jdxblxb.2014.06.13

趙立芹)