一類非凸多目標優化問題的同倫算法

李金燕,金 星,賀 莉*

(1.長春工業大學 基礎科學學院，吉林 長春 130012;2.長春醫學高等專科學校 藥學系，吉林 長春 130031)

?

一類非凸多目標優化問題的同倫算法

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

(1.長春工業大學 基礎科學學院，吉林 長春 130012;2.長春醫學高等專科學校 藥學系，吉林 長春 130031)

給出一類非凸區域的擬法錐構造方法,并在該可行域上建立多目標優化問題的KKT點組合同倫方程,證明了同倫算法的整體收斂性,數值例子說明此方法是可行和有效的。

多目標規劃; 擬法錐條件; 同倫方法

0 引 言

同倫方法是求解優化問題的一種重要算法[1-4]。目前,利用同倫內點法求解一般凸多目標規劃的最小弱有效解已有很多成果[5-7],但在實際生活中很多關于多目標規劃問題的可行域都是非凸的[8],對于不同的非凸區域,需要滿足一定的邊界條件。當可行域滿足擬法錐條件時,構造相應的正獨立映射函數至關重要[9],文獻[8]并沒有給出具體的構造方法。事實上,非凸區域的擬法錐構造并沒有統一的方法,只能針對具體的某一類進行研究。文獻[10]介紹了一類部分反向凸約束區域的擬法錐構造問題,文獻[11]給出了由球體和分片線性函數構成的非凸區域的擬法錐構造。文中在文獻[10-11]的基礎上針對“N”型非凸區域給出擬法錐構造,并在該可行域上用同倫算法求解多目標優化問題。

文中考慮如下的多目標優化問題:

(1)

文中使用如下記號:

式中：﹟B1(x)——指標集B1(x)的元素個數;

﹟B2(x)——指標集B2(x)的元素個數;

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

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

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

(3)

引理2[10]

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

文中做如下基本假設:

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

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

1 正獨立映射及擬法錐條件

對于問題(2),構建關于約束梯度的正獨立映射如下:

(4)

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

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

(5)

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

令

作超平面

對?a>0,令

則

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

因為

所以

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

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

(7)

所以

故有

得證。

2 同倫方程及收斂性

對于式(3)構造同倫方程如下:

(8)

其中，

當t=1時,同倫方程(8)有唯一解

當t=0時,式(8)變為(VP1)的KKT系統(3),因此同倫方程(8)的解就是(VP1)的KKT系統(3)的解，令

(9)

(10)

證明類似于文獻[5]。

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

3 算法及數值例子

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

(11)

由微分式(11)得:

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

(12)

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

例子:

計算結果見表1。

表1 計算結果

[1] 林正華,李勇,于波.一般非線性規劃的組合同倫內點法[J].應用數學與計算學報,1996,80:209-224.

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

[3] 于波,馮果忱,張紹梁.非凸非線性規劃的凝聚約束同倫算法[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] 劉慶懷,林正華.求解多目標規劃最小弱有效解的同倫內點方法[J].應用數學學報,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] 賀莉,譚佳偉,陳嘉,等.混合約束多目標優化問題的凝聚同倫內點方法[J].吉林大學學報:理學版,2014,52(2):212-218.

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

[9] 張春陽，張國霜，李卓識，等.正獨立映射的判定及其在非凸優化中的應用[J].長春工業大學學報：自然科學版，2010,31(1)：111-114.

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

[11] 李洪偉,劉慶懷.一類復雜非凸區域的擬法錐構造方法及其在非凸規劃求解中的應用[J].應用數學學報,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

吉林省自然科學基金資助項目(20130101061JC)

李金燕(1990-)，女，漢族，山西臨汾人，長春工業大學碩士研究生，主要從事最優化理論與算法方向研究,E-mail:jinyan_yiyi@126.com. *通訊作者：賀 莉(1970-)，女，漢族，吉林圖們人，長春工業大學教授，碩士，主要從事最優化理論與算法方向研究,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