何 非，商玉鳳

(空軍航空大學(xué) 基礎(chǔ)基地基礎(chǔ)部，吉林 長(zhǎng)春 130022)

解多目標(biāo)規(guī)劃最小弱有效解的動(dòng)約束組合同倫方法

何 非，商玉鳳

(空軍航空大學(xué) 基礎(chǔ)基地基礎(chǔ)部，吉林 長(zhǎng)春 130022)

給出了解無(wú)界集上凸多目標(biāo)規(guī)劃問題最小弱有效解的動(dòng)約束組合同倫方法，并證明了同倫路徑的存在性和大范圍收斂性。

多目標(biāo)規(guī)劃;凸規(guī)劃;同倫算法;弱有效解;有效解

0引言

其中Ω={x∈Rn|g(x)=(g1(x)，…，gm(x))T＜0}稱為可行集，

Ω={x∈Rn|g(x)=(g1(x)，…，gm(x))T≤0}為嚴(yán)格可行集，

I(x)={i|gi(x)=0}為緊指標(biāo)集。

定義1［1］設(shè)x*∈Ω，如果不存在x∈Ω，使得

則說(shuō)x*是(VP)的有效解(或弱有效解)。

定理1［1］假設(shè)fj(x)，gi(x)為凸函數(shù)(i=1，…，m)，(j=1，…，p)，且在∈Ω處可微，≥0(或＞0)。如果存在∈Rm+，使得(滿足條件：

考慮如下的多目標(biāo)規(guī)劃問題：

多目標(biāo)規(guī)劃問題的求解，一般都是通過(guò)主要目標(biāo)法等形式轉(zhuǎn)化為單目標(biāo)規(guī)劃來(lái)求解。文獻(xiàn)［2］(亦見文獻(xiàn)［3～6］)中，提出了解非凸Brouwer不動(dòng)點(diǎn)問題和非凸規(guī)劃問題組合同倫內(nèi)點(diǎn)法，并在此條件下證明了同倫路徑的存在性和大范圍收斂性。利用組合同倫內(nèi)點(diǎn)法，文獻(xiàn)［7］給出了解多目標(biāo)規(guī)劃的直接算法。但該方法要求初始點(diǎn)為可行集的內(nèi)點(diǎn)。文獻(xiàn)［8］中給出了解凸規(guī)劃問題的動(dòng)邊界組合同倫方法，該方法不要求可行集有界，初始點(diǎn)也不再限制為可行集內(nèi)點(diǎn)。本文給出了解多目標(biāo)規(guī)劃問題的最小弱有效解的動(dòng)約束組合同倫方法，同樣不要求可行集有界以及初始點(diǎn)不限制為可行集內(nèi)點(diǎn)。

1 假設(shè)條件及同倫方程的構(gòu)造方法

在本文中總使用如下假設(shè)。

假設(shè)條件1

(A1)f，g∈Cl(l＞2)且為凸函數(shù);

(A2)Ω0非空;

為求解(1)構(gòu)造動(dòng)約束組合同倫方程

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

則同倫方程有唯一的解

當(dāng)t=0時(shí)，同倫方程(2)變?yōu)榉匠?1)。

為方便作如下記號(hào)：

對(duì)于給定的w(0)，將同倫方程(2)寫為Hw(0)(w，t)，并記它的的零點(diǎn)集記為H-1w(0)(0)，即

命題1［9］設(shè)qi(x)(i=，1，…，l)是凸函數(shù)，且存在x∈Ωq。那么Ω0q非空的充要條件是：?x∈?Ωq，{▽qi(x)，i∈Iq(x)}是正獨(dú)立的。

即

其中

下面我們證明在一定條件下同倫方程(2)的零點(diǎn)集包含一條起始于(w(0)，1)的有界光滑曲線，當(dāng)t→0時(shí)，曲線的另一端的極限點(diǎn)的(x，y)-分量(x*，y*)為問題(1)的解。

2 同倫路徑的存在性及有界性

引理1 如果假設(shè)條件1成立，映射H由(2)定義.則對(duì)幾乎所有的，0是

Hw(0)的正則值，并且H-1(0)包含一條起始于(w(0)，1)的光滑曲線，記為Γ。證明 對(duì)任意的w(0)∈Rn×Rm++×Λ++×RP

++×{0}，和T∈(0，1］，

其中

這樣我們有

是行滿秩的，即0是H(w，w(0)，t)的正則值。由參數(shù)化的Sard定理得，對(duì)幾乎所有的w(0)，0是Hw(0)(w，t)的正則值，又由逆映像定理及Hw(0)(w(0)，1)=0包含一條通過(guò)(w(0)，1)的光滑曲線，記為Γ。

引理2 設(shè)如果假設(shè)條件1、2成立，映射H由(2)定義，則曲線Γ當(dāng)t→0時(shí)極限點(diǎn)的x-分量有界。證明 假設(shè)存在Γ上的點(diǎn)列{(x(k)，y(k)，λ(k)，ξ(k)，hk，tk)}+∞k=1，滿足當(dāng)k→+∞時(shí)，‖x(k)‖→+∞。由是Γ上的點(diǎn)列，則有

改寫方程(5)為

由g(x(k))為凸函數(shù)，有

在(7)式兩端同時(shí)右乘y(k)，再結(jié)合(4)，我們得到

于是

將(9)代入(6)，得成立，這同假設(shè)條件2矛盾。

3 同倫路徑的收斂性

定理1 設(shè)fi，gj∈Cl(l＞2)(i=1，…，p)，(j=1，…，m)，假設(shè)條件1，2成立，映射H由(2)定義，則對(duì)幾乎所有的，同倫方程的零點(diǎn)集(0)必包含一條經(jīng)過(guò)點(diǎn)(w(0)，1)的有界光滑曲線Γ，其另一端的極限點(diǎn)的(x，y)-分量(x*，y*)是(1)的解。

證明 由引理1我們知道存在一條經(jīng)過(guò)(w(0)，1)的光滑曲線Γ.設(shè)(w*，t*)是曲線Γ的另一端的極限點(diǎn)，則存在點(diǎn)列滿足

且(w(k)，tk)→(w*，t*)，由引理2得到當(dāng)k→+∞時(shí)，‖x(k)‖→+∞，我們記x(k)的極限值為x*.由(14)我們得到0≤λ(k)i≤1(i=1，…，p)，從而‖λ(k)‖→ +∞，并記λ(k)的極限值為λ*。

下面我們證明(hk，ξ(k)，y(k))→+∞，分別討論如下。

(1)hk→∞。

在(14)式的左右兩端同乘λ(k)，則有

結(jié)合(13-14)兩式

得到

當(dāng)k→∞時(shí)，右端極限存在且為有限值，因此hk→+∞。

當(dāng)t*＜1時(shí)，

當(dāng)t*=1時(shí)，

這是不可能的。

(3)‖y(k)‖→ +∞。

當(dāng)t*=1時(shí)，由方程(10)式，

改寫(16)為

若vj=0，?j∈I(x*，1)，當(dāng)k→+∞時(shí)，方程(17)為

而由已知條件

得到x*≠x(0)，這樣vj≥0，(j∈I(x*，1))且不全為零。

當(dāng)t*＜1時(shí)，將(17)式整理為

這與命題1矛盾.綜上可知當(dāng)k→+∞時(shí)，曲線Γ是有界曲線，定理得證。

［1］ 林銼云，董加禮.多目標(biāo)優(yōu)化的方法與理論［M］.長(zhǎng)春：吉林教育出版社，1992.

［2］ Yu，B.，Lin，Z..Homotopy method for a class nonconvex Brouwer fixed point problems［J］.Appl.Math.Comput.，1996，74：65-77.

［3］ Feng，G.C.，Lin，Z.，Yu，B.Existence of an interior pathway of a Kraus-Kuhn-Tucker point of a nonlinear programming problem［J］.Nonlinear Analysis Theory Methods Applications，1998，32：761-768.

［4］ Feng，G.C.，Yu，B.Combined homotopy interior point method for nonlinear programming problems［J］.Lecture Notes in Num.Anal.，1995，14：9-16.

［5］ Lin，Z.H.，Li，Y.，Yu，B.A combined homotopy interior method for general nonlinear programming problems［J］.Appl.Math.Comput.，1996，80：209-224.

［6］ Lin，Z.H.，Yu，B.，F(xiàn)eng，G.C..A combined homotopy interior method for convex programming problem［J］.Appl.Math.Comput.，1997，84：193-211.

［7］ 劉慶懷，林正華.求解多目標(biāo)規(guī)劃最小弱有效解的同倫內(nèi)點(diǎn)方法［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2000，23：188-195.

［8］ 商玉鳳，于波.凸規(guī)劃問題的動(dòng)邊界組合同倫方法及其收斂性［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，2006，44：311-315.

［9］ Rockefellar，T.Convex Analysis［M］.Princeton：Princeton University Press，2000.

責(zé)任編輯：鐘 聲

Dynamic constraint combination homotopy method for minimal weak efficient solutions to multi-objective programming

HE Fei，SHANG Yu-feng
(Fundamental Department of Flight Training Base，Air Force Aviation University，Changchun 130022，China)

This article gives the dynamic constraint combination homotopy method for minimal weak efficient solutions to convex multiobjective programming problems on unbounded sets and proves the existence and convergence of the homotopy path.

multi-objective programming;convex programming;homotopy algorithm;weak efficient solution;efficient solution

O221.2

A

1009-3907(2010)08-0021-06

2010-06-05

何非(1982-)，女，吉林遼源人，助教，碩士，主要從事最優(yōu)化理論與算法研究。