多目標優化問題的同倫方法

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

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

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

多目標優化問題的同倫方法

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

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

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

多目標優化問題; 同倫算法; 同倫路徑

考慮如下多目標優化問題:

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

文獻[1-4]對單目標的優化問題構造了組合同倫方法, 求解單目標問題的K-K-T點, 顯示了同倫方法在求解優化問題中的優勢.然而, 運用文獻[1-4]中的組合同倫方法求解優化問題, 均需要可行域滿足各類法錐條件, 從而使上述組合同倫方法的應用范圍受到較大限制.

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

1 同倫方程的構造及同倫路徑的存在性

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

對問題(MOP), 本文對可行域實行外逼近方式, 使用下列符號: 0≤α<+∞為任意的非負常數;Ωα={x∈n|gi(x)≤α,i∈M}為關于α的可行域n|gi(x)<α,i∈M}為關于α的嚴格可行域表示Ωα的邊界;Iα(x)={i|gi(x)=α,i∈M}表示點x∈Ωα的積極約束.當α=0時,Ω0即為多目標問題的可行域.

為求解問題(MOP), 做如下假設:

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

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

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

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

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

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

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

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

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

由式(4)可得

即

若Γω(0)無界, 則存在序列(x(k),y(k),λ(k),μk)∈Γω(0), 當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)與假設(H3)矛盾.

證明: 參考文獻[7]中定理3的證明.由引理1和引理2知Γw(0)為有界光滑曲線.由一維流形分類定理知Γw(0)或者微分同胚于單位圓周, 或者微分同胚于單位區間(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]蔡志丹, 趙立芹, 蘇孟龍.組合同倫內點算法求解一類非凸無界優化問題 [J].吉林大學學報: 理學版, 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]趙雪, 張春陽, 張樹功.弱擬法錐條件下解多目標規劃問題的同倫方法 [J].吉林大學學報: 理學版, 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—), 女, 漢族, 碩士, 副教授, 從事最優化理論與算法的研究, E-mail: wangxiuyu.000@163.com.

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

O221.2

A

1671-5489(2014)06-1176-05

10.13413/j.cnki.jdxblxb.2014.06.13

趙立芹)