一類多目標(biāo)優(yōu)化問題的凝聚同倫算法

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

(長春工業(yè)大學(xué)基礎(chǔ)科學(xué)學(xué)院，吉林 長春 130012)

?

一類多目標(biāo)優(yōu)化問題的凝聚同倫算法

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

(長春工業(yè)大學(xué)基礎(chǔ)科學(xué)學(xué)院，吉林 長春 130012)

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

多目標(biāo)優(yōu)化；凝聚函數(shù)；同倫內(nèi)點(diǎn)方法

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

本文考慮一般多目標(biāo)規(guī)劃問題(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ù)可微向量值函數(shù).引入以下符號：

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

令

(2)

(3)

1　預(yù)備知識

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

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

本文假設(shè)：

上式是假設(shè)條件(A3)的特殊情形，因此本文廣義弱擬法錐條件下求解多目標(biāo)優(yōu)化問題擴(kuò)大了凝聚同倫內(nèi)點(diǎn)方法的使用范圍.

由于問題(3)是非光滑多目標(biāo)優(yōu)化問題，我們利用如下凝聚函數(shù)進(jìn)行光滑化.

(4)

顯然， 當(dāng)t→0+時，問題(4)的解為多目標(biāo)優(yōu)化問題(1)的解.

其中

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

則

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

(5)

其中

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

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

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

(6)

相應(yīng)的KKT方程為：

(7)

稱(x，λ)是MOP問題的KKT點(diǎn)，(y，u，v，h)是MOP問題的Lagrange乘子.對于凸多目標(biāo)規(guī)劃問題，其解可以通過求解KKT系統(tǒng)得到.對于非凸多目標(biāo)規(guī)劃問題，得到的是MOP問題的KKT點(diǎn).

為求解KKT系統(tǒng)，構(gòu)造如下組合同倫方程:

(8)

當(dāng)t=1時，同倫方程(8)變?yōu)?/p>

(9)

當(dāng)t→0+時，方程(8)的解為KKT系統(tǒng)的解，即為問題(1)的KKT點(diǎn).

(10)

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

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

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

上式兩邊取極限得

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

由方程(8)第一式有

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

(10)

(11)

用Γw(0)的弧長s參數(shù)化該曲線，存在連續(xù)可微函數(shù)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，F(xiàn)ENG G C，ZHAGN S L. The aggregate constraint homotopy method for nonconvex nonlinear programming[J]. Nonlinear Analysis，2001，45：839-847.

[5]劉慶懷，林正華. 求解多目標(biāo)規(guī)劃最小弱有效解的同倫內(nèi)點(diǎn)方法[J]. 應(yīng)用數(shù)學(xué)學(xué)報，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]金鑒祿，王秀玉，賀莉等.約束序列極大極小問題的凝聚同倫內(nèi)點(diǎn)方法[J]. 應(yīng)用數(shù)學(xué)學(xué)報，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]楊軼華，趙立芹，呂顯瑞等. 多目標(biāo)凸規(guī)劃凝聚同倫內(nèi)點(diǎn)算法[J]. 吉林大學(xué)學(xué)報(理學(xué)版)，2006，44(6)：883-887.

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

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

(責(zé)任編輯：李亞軍)

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

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

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

O 221[學(xué)科代碼]110·74

A

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