一類多目標優化問題的凝聚同倫算法

賀　莉，李　娜，劉慶懷，王秀玉

(長春工業大學基礎科學學院，吉林 長春 130012)

?

一類多目標優化問題的凝聚同倫算法

賀莉，李娜，劉慶懷，王秀玉

(長春工業大學基礎科學學院，吉林 長春 130012)

利用凝聚同倫算法求解一類帶有等式約束和不等式約束的多目標優化問題.首先用凝聚函數對等價轉化后的不等式約束條件進行光滑逼近，然后給出相應的組合同倫方程，在廣義弱擬法錐條件下，證明其解幾乎處處收斂于該類多目標優化問題的KKT點.

多目標優化；凝聚函數；同倫內點方法

凝聚函數方法的思想起源于1979年Kreisselmeier和Steinhauser[1]得到的研究成果，20世紀80年代這種思想被廣泛地應用于結構優化和工程設計等領域.[2-3]2000年于波等[4]把凝聚函數的思想與組合同倫內點方法結合起來，提出了凝聚約束同倫方法，并指出這種方法的主要優點在于大大降低了同倫路徑數值跟蹤時線性系統的維數，縮小了問題的求解規模.此后很多學者進行了深入研究，在解決極大極小問題、非線性規劃問題和互補問題等方面取得了一些重要結果.[5-7]文獻[8]給出了含有不等式約束的非線性規劃問題的改進凝聚約束同倫方法，文獻[9]把凝聚約束同倫內點方法推廣到只帶有等式約束的凸多目標優化問題.本文在文獻[8-10]的基礎上，通過引入正不相關概念，給出較弱廣義弱擬法錐條件，在較弱的假設條件下，研究了一類既含有等式約束又含有不等式約束的多目標優化問題.

本文考慮一般多目標規劃問題(MOP)

minf(x)，

s.t.gi(x)≤0，i∈M，

hj(x)=0，j∈L.

(1)

其中：x∈Rn；M={1，2，…，m}；L={1，2，…，l}；f=(f1，f2，…，fp)T：Rn→Rp；g=(g1，g2，…，gm)T：Rn→Rm；h=(h1，h2，…，hl)T：Rn→Rl；f，g，h均為三次連續可微向量值函數.引入以下符號：

Ω={x∈Rn|gi(x)<0，hj(x)=0，i∈M，j∈L} 表示嚴格可行集.

令

(2)

(3)

1　預備知識

定義1如果存在二次連續可微映射ηi(x，zi)：Rn+1→Rn(i=1，2，…，m)，?x∈Ω滿足：

(1)ηi(x，0)=0，i∈M；

本文假設：

上式是假設條件(A3)的特殊情形，因此本文廣義弱擬法錐條件下求解多目標優化問題擴大了凝聚同倫內點方法的使用范圍.

由于問題(3)是非光滑多目標優化問題，我們利用如下凝聚函數進行光滑化.

(4)

顯然， 當t→0+時，問題(4)的解為多目標優化問題(1)的解.

其中

引理3[4]假設條件(A1)成立，則：

則

y=0，z=0，uj=0，j∈L.

(5)

其中

這與假設(A3)矛盾，命題得證.

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

為求解問題(4)，利用線性加權法將其轉化為如下n+p個變量的非線性規劃問題：

(6)

相應的KKT方程為：

(7)

稱(x，λ)是MOP問題的KKT點，(y，u，v，h)是MOP問題的Lagrange乘子.對于凸多目標規劃問題，其解可以通過求解KKT系統得到.對于非凸多目標規劃問題，得到的是MOP問題的KKT點.

為求解KKT系統，構造如下組合同倫方程:

(8)

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

(9)

當t→0+時，方程(8)的解為KKT系統的解，即為問題(1)的KKT點.

(10)

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

(1) 當h(k)→∞，v(k)→∞時的不可能性證明見文獻[5].

(2) 若u無界，則‖u(k)‖→∞(k→∞)，由方程(8)第一式有

上式兩邊取極限得

上式若成立，則其極限必存在，記

由方程(8)第一式有

η(x(k)，θtk，tk(1-tk)(y(k))2)+

(10)

(11)

用Γw(0)的弧長s參數化該曲線，存在連續可微函數w(s)，t(s)， 滿足

Hw(0)(w(s)，t(s))=0，t(0)=1，w(0)=w(0).

微分上式有：

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

t(0)=1;

w(0)=w(0).

且如果有t(s*)=0，則w*=(x(s*)，λ(s*)，y(s*)，u(s*)，v(s*)，h(s*))T是KKT方程的解.

[1]KREISSELMEIER G，STEINHAUSER R. Systematic control design by optimizing a performance index:Proceedings of the IFAC Symposium[C]. Switzerland：Zürich，1979.

[2]BARTHELEMY J F M，CHANG K J，ROGERS J L. Shuttle solid rocket booster bolted field joint shape optimization.[J]. Spaceraft and Rockets，1998，25：117-124.

[3]HAJELA P，Techniques in optimum structural synthesis with static and dynamic construints[D]. Palo Alto：Stanford University，1982.

[4]YU BO，FENG G C，ZHAGN S L. The aggregate constraint homotopy method for nonconvex nonlinear programming[J]. Nonlinear Analysis，2001，45：839-847.

[5]劉慶懷，林正華. 求解多目標規劃最小弱有效解的同倫內點方法[J]. 應用數學學報，2000，23(2)：188-195.

[6]LIU GUOXIN. Aggregaye homotopy methods for solving sequential max-min problems，complementarity problems and variational inequalities[D].Changchun：Jilin University，2003.

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

[8]SU MENGLONG，YU BO，WANG JIAN. Solving nonconvex nonlinear programming problems via a new aggregate constraint homotopy method[J]. Nonlinear Analysis，2010，73：2558-2565.

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

[10]術洪亮，張春陽. 求解非凸優化問題的一種連續化方法[J].東北師大學報(自然科學版)，2012，44(3)：31-34.

[11]ALLGOWER E L. Numerical continuation methods：an introducation[M]. New York：Springer-Verlag，1990：114-115.

(責任編輯：李亞軍)

Aggregate homotopy method for a class of multiobjective programming problem

HE Li，LI Na，LIU Qing-huai，WANG Xiu-yu

(School of Basic Science，Changchun University of Technology，Changchun 130012，China)

The aggregate homotopy method was used to solve a class of multiobjective programming problem with both equality and inequality constraints. The inequality contraints were deformed and smoothly approximated by aggregate functions. A general weak quasi-normal cone condition was defined in the feasible region and the corresponding homotopy equation was given. For almost all points in the feasible region，it converged to the KKT point of the multi-objective programming problem.

multiobjective optimization；aggregate function；homotopy method

1000-1832(2016)03-0041-07

2015-04-07

國家自然科學基金資助項目(51278065)；吉林省自然科學基金資助項目(20130101061JC).

賀莉(1970—)，女，碩士，教授，主要從事最優化理論與算法研究.

O 221[學科代碼]110·74

A

[DOI]10.16163/j.cnki.22-1123/n.2016.03.009