多目标优化问题近似解的非线性标量化刻画

李小燕,李美术,高 英

(重庆师范大学数学科学学院,重庆 401331)

1 引言

多目标优化问题中,如何定义最优解是首要问题.目前研究的解的概念主要有:有效解,弱有效解和各种真有效解的概念.关于这些解的存在性,最优性条件和对偶等理论是多目标优化理论研究的主要内容.但这些解存在性条件较强,通常需要对可行集增加某种意义下的凸性或紧性条件.大量研究表明,在非紧条件下,近似解有可能存在.因此,在非紧条件下研究近似解成为了多目标优化问题研究的又一重要方向.近几十年来,一些学者提出了各种不同的近似解的概念,并进行了进一步的研究.1979年,Kutateladze[1]首先提出了近似解的概念.1984年,Loridan[2]引进了多目标优化问题 ε-有效解的概念.随后,一些学者又提出了几种近似解的概念(如White[3],Helbig[4]).2006年,Guti´errez等人[5,6]利用co-radiant集定义了多目标优化问题的一种新的近似解,该近似解推广并统一了先前给出的诸多近似解的概念(如Kutateladze[1],White[3],Helbig[4]).受文献[5,6]中研究工作的启发,高英等人[7,8]在Benson真有效解的基础上,利用co-radiant集提出了一种近似真有效解的概念.

求解多目标优化问题一个重要途径是将多目标优化问题转化为数值优化问题,这种转化方法称为标量化方法.标量化主要分为线性标量化和非线性标量化.线性标量化主要是在凸性和一些广义凸性条件下利用凸集分离定理或择一定理进行刻画.非线性标量化主要是通过一些特殊的非线性函数,在非凸分离定理的基础上进行研究.近年来,对有效解,弱有效解和各种真有效解的标量化研究可参见文献[9–15],关于多目标优化问题各种近似解的标量化研究可参见文献[16–20].但利用范数研究多目标优化问题各种近似解的非线性标量化的成果并不多见.因此本文受文献[7–9,17]的启发,利用范数考虑多目标优化问题近似有效解和近似真有效解的非线性标量化刻画,并举例说明主要结果.

2 预备知识

令Rn为n维欧氏空间,Rn+为其非负卦限.设C⊂Rn,intC表示C的内部,clC表示C的闭包.若C∩(−C)⊂{0},则称C 为点集.任取x,y∈Rn,记

定义2.1[9]设S⊂Rn,S的回收锥S+定义为

考虑如下的多目标优化问题

定义2.3[5,7]设ε∈R,且ε≧0,x∈X,C⊂Rp为co-radiant点集.

(i)称为(MOP)问题关于C的ε-有效解,若

(ii)称为(MOP)问题关于C的ε-真有效解,若

记(MOP)问题关于C 的ε-有效解和ε-真有效解之集分别为E(f,C,ε)和P(f,C,ε).

Rp中的l∞-范数和lα-范数分别定义为

其中

),其中=inf{yi:yi为y∈Y的第i个分量},i=1,···,p.若满足则称为Y的理想点.

设||·||为Rp中的某种范数,为Y=f(X)的理想点.考虑如下的非线性标量化问题:

定义2.4设ε≧0,∈X,α∈[1,∞).

(i)称为(SP)问题关于||·||∞的ε-最优解,若

(ii)称为(SP)问题关于||·||α的ε-最优解,若记 (SP)问题关于 ||·||∞和 ||·||α的 ε-最优解之集分别为 A∞(f,ε)和 Aα(f,ε).

3 主要结果

本节利用||·||1范数和||·||∞范数得到多目标优化问题近似有效解和近似真有效解的标量化结果.若无特别说明,本节总假设C⊂Rp+为co-radiant点集且0/∈clC.

为了证明的方便,假设由||·||1范数的定义,||y1+y2||1≦||y1||1+||y2||1.若y1,y2∈Rp+,则满足等式关系这是因为

本文在很多地方用到这一结论.

定理 3.1设 ε≧ 0,0＜ β ＜ d||·||1(0,C),则

(i)A1(f,εβ)⊂ E(f,C,ε);

(ii)若 Y+C(ε)为闭集,则 A1(f,εβ)⊂ P(f,C,ε),

其中 d||·||1(0,C)为 0 到 C 的距离,即 d||·||1(0,C)=inf{||c||1:c ∈ C}.

证设则由定义2.4有

(i)当 ε＞0时,若∈/E(f,C,ε),则存在使得从而存在c1∈C⊂R+p,使得.因此由为Y的理想点,则即.因此,由||·||1范数的性质可得

这与(3.1)式矛盾.因此∈E(f,C,ε).

当ε=0时,若/∈E(f,C,0),则存在从而存在因此

这与(3.1)式矛盾.因此∈E(f,C,0).

综上,(i)成立.

(ii)当ε＞0时,若则存在非零向量

从而存在

若 {βk}有界.不失一般性,假设 βk→ β0,则 β0≧ 0.若 β0=0,由 C ⊂ Rp+有因此则从而这与c∈C(ε)矛盾.若 β0＞0,则由 Y+C(ε)为闭集有

从而存在y0∈Y,d0∈C使得则由||·||1范数的性质可得

这与(3.1)式矛盾.

若{βk}无界,不失一般性,假设当k→∞时,βk→+∞,则其中,dk∈C⊂Rp+,∀k.即∀γ＞0,存在自然数Kγ,当k＞Kγ时,有则

从而.因此存在k∗使得事实上,若对任意的,则存在＞0,使得

令则对存在自然数Kȳ,使得当k＞Kȳ时这与(3.2)式矛盾.因此,结合||·||1范数的定义可得

当ε=0时,利用ε＞0的证明思路,结合(i)中ε=0的情况,可得结论.从而(ii)成立.

注 3.1(i)定理中的 0 ＜ β ＜ d||·||1(0,C)必不可少.若 β =d||·||1(0,C),则 A1(f,εβ)⊆E(f,C,ε)不一定成立.见例3.1.

(ii)定理中的两种反包含关系不一定成立.事实上,对任意的0＜ β＜ d||·||1(0,C),E(f,C,ε)⊆ clA1(f,εβ),P(f,C,ε)⊆ clA1(f,εβ)都不一定成立.见例 3.1.

(iii)文献[9]利用||·||α(α∈[1,∞))给出了精确的有效解和真有效解的非线性标量化结果.但对近似解来说,定理中的结果对其它范数不一定成立.如||·||∞范数和||·||2范数.见例3.2.

例3.1令X=R2+,C={(x1,x2)T:x1≥0,x2≥0,x1+x2≥1},f:X→R2,f(x)=x,则Y=f(X)=R2+的理想点之集为R2−且d||·||1(0,C)=1.令ε=1,则

E(f,C,1)的图象如图1所示.

若 β =d||·||1(0,C)=1, 则

显然,A1(f,εβ)E(f,C,ε),

图1

图2

特别取β=0.9时,A1(f,0.9)的图象如图2所示.显然,clA1(f,β),∀0＜β＜1.这说明定理3.1中的两种反包含关系不一定成立.

例3.2令

取则

这说明定理3.1的结果对||·||∞范数和||·||2范数不一定成立.

令

∀µ ∈ Λ++,α ∈ [1,∞),y=(y1,···,yp)T∈ Rp+,y 的 (µ,α)范数定义为的 (µ,∞)范数定义为其中 µ ⊙ y=(µ1y1,···,µpyp)T.记

推论3.1在定理3.1的条件下,对任意的µ∈Λ++,有

(i)(f,εβ) ⊂ E(f,C,ε);

(ii)若 Y+C(ε)为闭集,则

证与定理3.1的证明类似.

注3.2当ε=0且C(0)∪{0}=Rp+时,推论3.1中的条件和结果退化到文献[9]中的定理3.4.8中的特殊情形.

由例3.2知,若定理3.1中的范数改为||·||∞范数,结果不一定成立.对||·||∞范数有如下的标量化结果.

定理3.2设ε＞0,C⊂intRp+为co-radiant点集.若

则

(i)A∞(f,∈)⊂ E(f,C,ε);

(ii)若 Y+C(ε)为闭集,则 A∞(f,∈)⊂ P(f,C,ε).

证设则

(i)若则存在从而存在c0∈C,使得因此

这与(3.3)式矛盾.因此∈E(f,C,ε).

(ii)若则存在非零向量从而存在{βk}⊂R+{0},{yk}⊂Y,{ck}⊂C(ε),使得其中c∈C(ε).

若{βk}有界,假设βk→β0.由定理3.1(ii)的证明知β00.因此为闭集,有从而存在 y1∈ Y,d1∈ C,使得由c∈C(ε),C⊂intRp+可得c的每个分量都大于0.因此

这与(3.3)式矛盾.

若{βk}无界,类似定理3.1(ii)的证明,存在k∗使得.因此

这与(3.3)式矛盾.综上

注3.3若Y+C(0)为闭集,类似可证A∞(f,0)⊂P(f,C,0).

定理3.3设ε≧0.若Y+Rp+为闭集,则

证由Y+Rp+为闭集,易证满足

则有界,不妨假设由Y+Rp+为闭集有∈Y+Rp+,即存在x1∈X,f(x1)=y1∈Y,d1∈Rp+,使得

先证因此

再证.事实上,若则存在使得由0clC知d20,从而又因为

推论3.2在定理3.3的条件下,对任意的

证与定理3.3的证明类似.

注3.4当ε=0且C(0)∪{0}=时,推论3.2中的条件和结果退化到文献[9]中的定理3.4.9(i).

参考文献

[1]Kutateladze S S.Convex ε-programming[J].Soviet Math.Doklady,1979,20(2):390–393.

[2]Loridan P.ε-solutions in vector minimization problems[J].J.Optim.The.Appl.,1984,43(2):265–276.

[3]White D J.Epsilon efficiency[J].J.Optim.The.Appl.,1986,49:319–337.

[4]Helbig S.One new concept for ε-efficiency[R].Talk at Optimization Days,1992.

[5]Guti´errez C,Jim´enez B,Novo V.A uni fied approach and optimality conditions for approximate solutions of vector optimization problems[J].SIAM J.Optim.,2006,17(3):688–710.

[6]Guti´errez C,Jim´enez B,Novo V.On approximate efficiency in multiobjective programming[J].Math.Meth.Oper.Res.,2006,64(1):165–185.

[7]Gao Y,Yang X M,Teo K L.Optimality conditions for approximate solutions of vector optimization problems[J].J.Indus.Mgt.Optim.,2011,7(2):483–496.

[8]Gao Y,Hou S H,Yang X M.Existence and optimality conditions for approximate solutions to vector optimization problems[J].J.Optim.The.Appl.,2012,152:97–120.

[9]Sawaragi Y,Nakayama H,Tanino T.Theory of multiobjective optimization[M].Japan:Dpt.Appl.Math.Konan Univ.,1985.

[10]Kaliszewski I.A theorem on nonconvex functions and its application to vector optimization[J].European J.Oper.Res.,1995,80:439–449.

[11]Beldiman M,Panaitescu E,Dogaru L.Approximate quasi efficient solutions in multiobjective optimization[J].Bull Math.Soc.Math.Roumanie Tome,2008,51(2):109–121.

[12]Rastegar N,Khorram E.A combined scalarizing method for multiobjective programming problems[J].European J.Oper.Res.,2014,236:229–237.

[13]李小燕,高英.多目标优化问题Proximal真有效解的最优性条件[J].应用数学和力学,2015,36(6):668–676.

[14]Zheng X Y.Scalarization of Henig proper efficient points in a normed space[J].J.Optim.The.Appl.,2000,105(1):233–247.

[15]杨丰梅,龚循华.C#-单调范数与Henig有效点的切比雪夫标量化[J].系统科学与数学,2002,22(3):334–342.

[16]岳瑞雪,高英.多目标优化问题(ε,)-拟近似解的非线性标量化[J].数学杂志,2016,36(3):615–626.

[17]Guti´errez C,Huerga L,Novo V.Scalarization and saddle points of approximate proper solutions in nearly subconvexlike vector optimization problems[J].J.Math.Anal.Appl.,2012,389:1046–1058.

[18]高英.多面体集下多目标优化问题近似解的若干性质[J].运筹学学报,2013,17(2):48–52.

[19]Flores-Baz´an F,Hern´andez E.A uni fied vector optimization problem:complete scalarizations and applications[J].Optim.,2011,60(12):1399–1419.

[20]郭辉.向量优化问题(C,ε)-弱有效解的一个非线性标量化性质[J].运筹学学报,2015,19(2):105–110.