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

李金燕,金 星,賀 莉*

(1.長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院，吉林 長(zhǎng)春 130012;2.長(zhǎng)春醫(yī)學(xué)高等?？茖W(xué)校 藥學(xué)系，吉林 長(zhǎng)春 130031)

?

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

李金燕1,金 星2,賀 莉1*

(1.長(zhǎng)春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院，吉林 長(zhǎng)春 130012;2.長(zhǎng)春醫(yī)學(xué)高等?？茖W(xué)校 藥學(xué)系，吉林 長(zhǎng)春 130031)

給出一類非凸區(qū)域的擬法錐構(gòu)造方法,并在該可行域上建立多目標(biāo)優(yōu)化問題的KKT點(diǎn)組合同倫方程,證明了同倫算法的整體收斂性,數(shù)值例子說明此方法是可行和有效的。

多目標(biāo)規(guī)劃; 擬法錐條件; 同倫方法

0 引 言

同倫方法是求解優(yōu)化問題的一種重要算法[1-4]。目前,利用同倫內(nèi)點(diǎn)法求解一般凸多目標(biāo)規(guī)劃的最小弱有效解已有很多成果[5-7],但在實(shí)際生活中很多關(guān)于多目標(biāo)規(guī)劃問題的可行域都是非凸的[8],對(duì)于不同的非凸區(qū)域,需要滿足一定的邊界條件。當(dāng)可行域滿足擬法錐條件時(shí),構(gòu)造相應(yīng)的正獨(dú)立映射函數(shù)至關(guān)重要[9],文獻(xiàn)[8]并沒有給出具體的構(gòu)造方法。事實(shí)上,非凸區(qū)域的擬法錐構(gòu)造并沒有統(tǒng)一的方法,只能針對(duì)具體的某一類進(jìn)行研究。文獻(xiàn)[10]介紹了一類部分反向凸約束區(qū)域的擬法錐構(gòu)造問題,文獻(xiàn)[11]給出了由球體和分片線性函數(shù)構(gòu)成的非凸區(qū)域的擬法錐構(gòu)造。文中在文獻(xiàn)[10-11]的基礎(chǔ)上針對(duì)“N”型非凸區(qū)域給出擬法錐構(gòu)造,并在該可行域上用同倫算法求解多目標(biāo)優(yōu)化問題。

文中考慮如下的多目標(biāo)優(yōu)化問題:

(1)

文中使用如下記號(hào):

式中：﹟B1(x)——指標(biāo)集B1(x)的元素個(gè)數(shù);

﹟B2(x)——指標(biāo)集B2(x)的元素個(gè)數(shù);

對(duì)于(VP),考慮如下的非凸規(guī)劃問題:

引理1 (VP1)的最優(yōu)解一定是(VP)的弱有效解。

顯然(VP1)是一個(gè)含有n+p個(gè)變量的非凸規(guī)劃問題,(VP1)的KKT方程為:

(3)

引理2[10]

2)?x∈?Ωs(s∈M),有{x+l。

文中做如下基本假設(shè):

(C1)Ω是有界連通集,且Ω0非空;

(C2)?Ω是正獨(dú)立的,即?x∈?Ω,gs(x)(s∈B1(x)),hjk(x)((j,k)∈B2(x))線性正獨(dú)立。

1 正獨(dú)立映射及擬法錐條件

對(duì)于問題(2),構(gòu)建關(guān)于約束梯度的正獨(dú)立映射如下:

(4)

下面給出映射(4)關(guān)于約束梯度正獨(dú)立的引理。

定理1 由式(4)定義的映射{ηs(x),ηjk(x)}關(guān)于{gs(x),hjk(x)}(s∈M,j∈P,k∈K)是正獨(dú)立的，即?x∈?Ω,若

(5)

必有ys=αs=yjk=αjk=0。

令

作超平面

對(duì)?a>0,令

則

所以Hjk(z(2))>0。

因?yàn)?/p>

所以

所以z(1),z(2),z(3)在Hjk(x)的同一側(cè),即Con{,是尖凸錐。

定理2(擬法錐條件) 定理1中構(gòu)造的正獨(dú)立映射{ηs(x),ηjk(x)},(s∈M,j∈P,k∈K),對(duì)?x∈?Ω有

(7)

所以

故有

得證。

2 同倫方程及收斂性

對(duì)于式(3)構(gòu)造同倫方程如下:

(8)

其中，

當(dāng)t=1時(shí),同倫方程(8)有唯一解

當(dāng)t=0時(shí),式(8)變?yōu)?VP1)的KKT系統(tǒng)(3),因此同倫方程(8)的解就是(VP1)的KKT系統(tǒng)(3)的解，令

(9)

(10)

證明類似于文獻(xiàn)[5]。

由于H(w(0),1)解是唯一的,故情況1)不成立。若情況2)成立,必存在子列(w(k),tk)∈Γw(0),使得gso(x(k))→0(存在某個(gè)1≤so≤2)或hjoko(x(k))→0(存在某個(gè)(jo,ko),1≤j0≤2,1≤k0≤n),‖y(k)‖→或‖‖→,這與引理4矛盾,所以情形2)不成立,故僅有情形3)成立。顯然是式(8)的一個(gè)解,這就證明了存在性。如果Γw(0)是有限的,此極限點(diǎn)是Γw(0)的另一個(gè)端點(diǎn),記為,則得到是式(8)的一個(gè)解。

3 算法及數(shù)值例子

如果用Γw(0)上曲線的弧長(zhǎng)u作為該曲線的同倫參數(shù),即存在連續(xù)可微函數(shù)w(u),t(u),使得

(11)

由微分式(11)得:

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

(12)

如果有t(u*)=0,則w*是KKT方程的解。

例子:

計(jì)算結(jié)果見表1。

表1 計(jì)算結(jié)果

[1] 林正華,李勇,于波.一般非線性規(guī)劃的組合同倫內(nèi)點(diǎn)法[J].應(yīng)用數(shù)學(xué)與計(jì)算學(xué)報(bào),1996,80:209-224.

[2] 劉國新,馮果忱,于波.解序列極大極小問題的凝聚同倫方法[J].吉林大學(xué)學(xué)報(bào):理學(xué)版,2003,41(2):155-156.

[3] 于波,馮果忱,張紹梁.非凸非線性規(guī)劃的凝聚約束同倫算法[J].非線性分析,2001,45:839-847.

[4] Lin Z H,Zhu D L,Sheng Z P. Finding a minimal efficient solution of a convex multiobjective program [J]. Optim Theory Appl.,2003,118(3):587-600.

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

[6] Shang Y F,YU B. A constraints shifting homotopy method for convex multiobjective programming [J]. Compute and Appl. Math.,2011,236(5):640-646.

[7] 賀莉,譚佳偉,陳嘉,等.混合約束多目標(biāo)優(yōu)化問題的凝聚同倫內(nèi)點(diǎn)方法[J].吉林大學(xué)學(xué)報(bào):理學(xué)版,2014,52(2):212-218.

[8] 楊軼華,趙立芹,呂顯瑞,等.求多目標(biāo)擬錐條件下最小弱有效解的同倫內(nèi)點(diǎn)算法[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版,2007,45(1):35-38.

[9] 張春陽，張國霜，李卓識(shí)，等.正獨(dú)立映射的判定及其在非凸優(yōu)化中的應(yīng)用[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010,31(1)：111-114.

[10] 高云峰,劉慶懷.一類部分反向凸約束優(yōu)化問題的組合同倫方程[J].吉林大學(xué)學(xué)報(bào),2008,11:1110-1112.

[11] 李洪偉,劉慶懷.一類復(fù)雜非凸區(qū)域的擬法錐構(gòu)造方法及其在非凸規(guī)劃求解中的應(yīng)用[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2009(5):400-412.

Homotopy method for a class of non-convex multiobjective programming problems

LI Jinyan1,JIN Xing2，HE Li1*

(1.School of Basic Science,Changchun University of Technology,Changchun 130012，China;2.Phamacy Department,Changchun Medical College,Changchun 130031，China)

We give a method to construct the quasi-normal cone in a class of non-convex regions in which the combined K-K-T points homotopy equation of the multi-objective programming problem is built up. It is proved that the method is with global convergence property by means of numerical examples.

multi-objective programming; quasi-normal cone condition; homotopy method.

2016-04-30

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

李金燕(1990-)，女，漢族，山西臨汾人，長(zhǎng)春工業(yè)大學(xué)碩士研究生，主要從事最優(yōu)化理論與算法方向研究,E-mail:jinyan_yiyi@126.com. *通訊作者：賀 莉(1970-)，女，漢族，吉林圖們?nèi)耍L(zhǎng)春工業(yè)大學(xué)教授，碩士，主要從事最優(yōu)化理論與算法方向研究,E-mail:heli_xu@126.com.

10.15923/j.cnki.cn22-1382/t.2016.5.02

O 221.6

A

1674-1374(2016)05-0422-06