解多目標規劃最小弱有效解的動約束組合同倫方法

何 非，商玉鳳

(空軍航空大學 基礎基地基礎部，吉林 長春 130022)

解多目標規劃最小弱有效解的動約束組合同倫方法

何 非，商玉鳳

(空軍航空大學 基礎基地基礎部，吉林 長春 130022)

給出了解無界集上凸多目標規劃問題最小弱有效解的動約束組合同倫方法，并證明了同倫路徑的存在性和大范圍收斂性。

多目標規劃;凸規劃;同倫算法;弱有效解;有效解

0引言

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

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

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

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

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

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

考慮如下的多目標規劃問題：

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

1 假設條件及同倫方程的構造方法

在本文中總使用如下假設。

假設條件1

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

(A2)Ω0非空;

為求解(1)構造動約束組合同倫方程

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

則同倫方程有唯一的解

當t=0時，同倫方程(2)變為方程(1)。

為方便作如下記號：

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

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

即

其中

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

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

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

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

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

其中

這樣我們有

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

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

改寫方程(5)為

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

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

于是

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

3 同倫路徑的收斂性

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

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

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

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

(1)hk→∞。

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

結合(13-14)兩式

得到

當k→∞時，右端極限存在且為有限值，因此hk→+∞。

當t*＜1時，

當t*=1時，

這是不可能的。

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

當t*=1時，由方程(10)式，

改寫(16)為

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

而由已知條件

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

當t*＜1時，將(17)式整理為

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

［1］ 林銼云，董加禮.多目標優化的方法與理論［M］.長春：吉林教育出版社，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.，Feng，G.C..A combined homotopy interior method for convex programming problem［J］.Appl.Math.Comput.，1997，84：193-211.

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

［8］ 商玉鳳，于波.凸規劃問題的動邊界組合同倫方法及其收斂性［J］.吉林大學學報：理學版，2006，44：311-315.

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

責任編輯：鐘 聲

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-)，女，吉林遼源人，助教，碩士，主要從事最優化理論與算法研究。