擬凸函數(shù)的近似次微分及其在多目標優(yōu)化問題中的應用*

史小波，高 英

（重慶師范大學 數(shù)學科學學院，重慶 401331）

引 言

凸性在優(yōu)化問題中有著廣泛的應用，但在實際問題的研究中，我們遇到的函數(shù)或者集合大多數(shù)是非凸的.于是研究凸性的各種推廣形式具有重要的意義.20 世紀60 年代以來，凸函數(shù)的概念已被推廣到不同類型的廣義凸函數(shù)，例如擬凸函數(shù)[1]、E-凸函數(shù)[2]等.擬凸函數(shù)作為一類特殊的廣義凸函數(shù)，在非凸優(yōu)化中有著廣泛的應用[3-4].De Finetti 和Fenchel 在文獻[5-6]中首次給出了擬凸函數(shù)的定義.1965年，Mangasarian[1]首次引進偽凸的概念并給出擬凸函數(shù)和偽凸函數(shù)的若干性質(zhì).隨后，楊新民等[7-9]進一步給出擬凸函數(shù)的性質(zhì)及其在優(yōu)化理論中的應用.

對于凸函數(shù)來說，次微分和近似次微分[10]是給出凸優(yōu)化問題最優(yōu)性條件的基本工具.因此，如何引進擬凸函數(shù)的次微分是研究擬凸優(yōu)化問題最優(yōu)性條件的首要問題.20 世紀70 年代以來，文獻[11-14]先后引進了Greenberg-Pierskalla 次微分、星型次微分、Gutiérrez 次微分、Plastria 次微分并給出了一些性質(zhì).隨后，Penot 在文獻[15-16]中首次給出這四種次微分之間的關系并給出了一些推廣性質(zhì).有了這些次微分的概念及基本性質(zhì)，一些學者開始利用這些次微分給出擬凸數(shù)值優(yōu)化問題的最優(yōu)性條件[17-19].2019 年，陳瑞婷等[20]給出了擬凸意義下的近似次微分以及近似解的概念，并給出了擬凸多目標優(yōu)化問題近似解的最優(yōu)性條件.

本文在文獻[10,20]的基礎上，得到了擬凸函數(shù)新的近似次微分的概念，研究其與已有次微分之間的關系及性質(zhì)，并將其應用到擬凸多目標優(yōu)化問題中.最后，給出近似有效解、近似真有效解的概念，利用新的近似次微 分得到擬凸優(yōu)化問題近似解的最優(yōu)性條件.

1 預備知識

定義1[10]設f:Rn→R，若對于任意的x1,x2∈Rn和λ ∈[0,1]，有

f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2),

則稱f為Rn上的凸函數(shù).

定義2[9]設f:Rn→R，若對于任意的x1,x2∈Rn和λ ∈[0,1]，有

f(λx1+(1-λ)x2)≤max{f(x1),f(x2)},

則稱f為Rn上的擬凸函數(shù).

給定λ ∈R，f對應于λ的水平集與嚴格水平集定義為

S≤f(λ)={x∈Rn|f(x)≤λ},

S＜f(λ)={x∈Rn|f(x)＜λ}.

針對擬凸函數(shù)，文獻[11-14]引進了如下次微分的概念.

定義3[11-14]設f為擬凸函數(shù)，x0∈Rn,f在x0處的Greenberg-Pierskalla 次微分定義為

x*0∈?*f(x0)??〈x*0,x-x0〉＜0,?x∈[f＜f(x0)];

星型次微分定義為

x*0∈??f(x0)??〈x*0,x-x0〉≤0,?x∈[f＜f(x0)];

Gutiérrez 次微分定義為

x*0∈?≤f(x0)??〈x*0,x-x0〉≤f(x)-f(x0),?x∈[f≤f(x0)];

Plastria 下次微分定義為

x*0∈?＜f(x0)??〈x*0,x-x0〉≤f(x)-f(x0),?x∈[f＜f(x0)].

注12000年，Penot 在文獻[15]中給出了四種次微分之間的關系：

?≤f(x0)??＜f(x0)??*f(x0)???f(x0).

2019 年，文獻[20]針對擬凸函數(shù)給出了近似水平集和近似次微分的概念.

設ε ≥0，擬凸函數(shù)f的近似水平集與嚴格近似水平集可以表示為

定義4[20]設f為擬凸函數(shù)，ε ≥0,x0∈Rn，f在x0處的幾種近似次微分定義為

注2文獻[20]指出，當時，以上四種近似次微分有如下關系：

?≤εf(x0)??＜εf(x0)??*εf(x0)???εf(x0).

次微分與對應的近似次微分的關系為

?≤f(x0)??≤εf(x0), ?＜f(x0)??＜εf(x0),

?*f(x0)??*εf(x0), ??f(x0)???εf(x0),

且ε=0時，近似次微分退化為精確的次微分.

定義5[10]設函數(shù)f:S?Rn→R，對任意的x∈S，存在一個正數(shù)L,δ，使得

|f(x1)-f(x2)| ≤L‖x1-x2‖,?x1,x2∈B(x,δ),

則稱f為S上的局部Lipschitz 函數(shù).

定義6[10]設f為Rn上的局部Lipschitz 函數(shù)，f(x)在點x處關于方向d∈Rn的廣義方向?qū)?shù)定義為

f在點x處的Clarke 次微分定義為

?Cf(x)={ξ ∈Rn:fo(x;v)≥ξTv,?v∈Rn}.

若f為Rn上的凸函數(shù)，則Clarke 次微分退化為凸意義下的次微分：

?f(x0)={ξ ∈Rn|ξT(x-x0)≤f(x)-f(x0),?x∈Rn}.

文獻[10]針對凸函數(shù)給出了如下近似次微分的概念.

定義7[10]設f為Rn上的凸函數(shù)，ε ≥0,f在點x0點的ε次微分定義為

?εf(x0)={ξ ∈Rn|〈ξ,x-x0〉 ≤f(x)-f(x0)+ε,?x∈Rn}.

Clarke 次微分是針對局部Lipschitz 連續(xù)函數(shù)給出的.顯然，擬凸不一定連續(xù).從而，也不一定是局部Lipschitz連續(xù).下面給出一個例子說明擬凸連續(xù)函數(shù)也不一定是局部Lipschitz 連續(xù)的.

例1設f(x)=x∈[0,+∞)，則f(x)在[0,+∞)上為擬凸連續(xù)函數(shù).

由定義顯然有f(x)在[0,+∞)上為擬凸連續(xù)函數(shù).下面說明f(x)在x=0處不是局部Lipschitz 連續(xù)的.事實上，對任意的L＞0,δ ＞0，特別取當n充分大時，xn,yn∈O(0,δ)∩[0,+∞)且

|f(xn)-f(yn)|＞L|xn-yn|,

即

從 而f(x)不是局部Lipschitz 連續(xù)的.

2 擬凸函數(shù)的近似次微分

本節(jié)針對擬凸函數(shù)f:Rn→R，在定義4 的基礎上，提出如下近似次微分的概念，并研究其性質(zhì).

定義8設ε ≥0,x0∈Rn,f在x0處的ε-下次微分定義為

由定義可知，定義4 中的近似次微分包含于定義8 中的近似次微分，但反包含不一定成立，見例2.

例2考慮擬凸函數(shù)

取x0=0, ε=2，則定義4 中的近似次微分?≤εf(x0)=(-∞,0]，而定義8中的近似次微分?≤εf(x0)={0}.

在實際應用中，存在一些擬凸函數(shù)，其精確的次微分可能為空集，而改進后的近似次微分不一定非空，見例3.

例3考慮擬凸函數(shù)

取x0=0, ε=2，

?＜f(x0)=?≤f(x0)=?,?≤εf(x0)=[1,+∞).

而對于某些擬凸函數(shù)來說，定義4 中的近似水平集有可能為空集，而本文定義的水平集不一定非空，見例4.

例4考慮擬凸函數(shù)

取x0=0, ε=2，則定義4 中的近似水平集x∈?,而定義8中的水平集x∈(-2,+∞)，此時，

f(x)?≤εf(x0)

注3 當為局部Lipschitz 連續(xù)時，Clarke 次微分不一定包含在，見例5.

例5設f(x)=x3,x∈R，則f(x)為擬凸局部Lipschitz 連續(xù)函數(shù).特別取x0=0, ε=1，則?Cf(x0)={0},?≤εf(x0)=?.

下面，我們研究了近似次微分的一些性質(zhì).

ε ≥0,x0∈Rn?≤εf(x0)

定理1設，則為閉凸集.

{x*n}??≤εf(x0)limn→∞x*n=x*x*∈?≤εf(x0)

證明首先證明閉性，任取，若，下面證明.

x*n∈?≤εf(x0)x∈[f≤f(x0)]

由可知，對任意的，有

limn→∞x*n=x*

又由可知

這表明x*∈?≤εf(x0)，從而?≤εf(x0)是閉集.

下面再證明凸性.任取ξ1, ξ2∈?≤εf(x0)，由定義可知

〈ξ1,x-x0〉 ≤f(x)-f(x0)+ε,

〈ξ2,x-x0〉 ≤f(x)-f(x0)+ε.

任取λ ∈[0,1]，有

λ〈ξ1,x-x0〉 ≤λ(f(x)-f(x0))+λε,

(1-λ)〈ξ2,x-x0〉 ≤(1-λ)(f(x)-f(x0))+(1-λ)ε.

將上式相加得

〈λξ1+(1-λ)ξ2,x-x0〉 ≤f(x)-f(x0)+ε.

即

λξ1+(1-λ)ξ2∈?≤εf(x),

故?≤εf(x0)為凸集.

綜上所述，?≤εf(x0)為閉凸集.

定理2設x0∈Rn, 0 ＜ε1＜ε2，則?≤ε1f(x0)??≤ε2f(x0).

證明任取ξ ∈?≤ε1f(x0)，對于任意的x∈[f≤f(x)]，有

〈ξ,x-x0〉 ≤f(x)-f(x0)+ε1.

由ε1＜ε2可知

〈ξ,x-x0〉 ≤f(x)-f(x0)+ε2.

這表明ξ ∈?≤ε2f(x0).再由ξ的任意性可知

?≤ε1f(x0)??≤ε2f(x0).

定理3設x0∈Rn，對任意的ε ＞0，有

證明首先證明其中n∈Z+.由定義顯然有

令n→+∞，則有

〈ξ,x-x0〉≤f(x)-f(x0),?x∈[f≤f(x0)].

從而ξ ∈?≤f(x0).再由ξ的任意性可知故

與凸意義下的近似次微分類似，下述結(jié)論成立.

x0∈Rn,

定理4設則有

(ⅰ) ?≤εg(x0)=?≤εf(x0)，其中g(x)=f(x)+C,C為常數(shù)；

(ⅱ) ?≤εg(x0)=其中g(x)=af(x)，a＞0；

(ⅲ) ?≤εg(x+x0)=?≤εf(x0)，其中g(x)=f(x-x0)，f(x)為單調(diào)函數(shù)；

(ⅳ) ?≤εf(x0)+{α}??≤εg(x0)，其中g(x)=f(x)+αTx，α ∈Rn+，g(x)為單調(diào)遞增函數(shù).

定理5設ε1,ε2≥0, ε1+ε2≤ε，對任意x0∈Rn，若Lf1(x0)=Lf2(x0)，有

證明任取ξ1∈?≤ε1f1(x0), ξ2∈?≤ε2f2(x0)，由定義可知，對任意的x∈Lf1(x0)，有

〈ξ1,x-x0〉 ≤f1(x)-f1(x0)+ε1,

〈ξ2,x-x0〉 ≤f2(x)-f2(x0)+ε2.

兩式相加得

〈ξ1+ξ2,x-x0〉 ≤f1(x)+f2(x)-(f1(x0)+f2(x0))+ε1+ε2.

令ξ=ξ1+ξ2，有

〈ξ,x-x0〉=f1(x)+f2(x)-(f1(x0)+f2(x0))+ε1+ε2≤

f1(x)+f2(x)-(f1(x0)+f2(x0))+ε.

從而ξ ∈?≤ε(f1(x0)+f2(x0))，即包含關系成立.

注4定理中Lf1(x0)=Lf2(x0)條件必不可少.

例6考慮函數(shù)

f1(x)=x,f2(x)=x2,

取x0=0, ε=1，則Lf1(x0)=(-∞,0],Lf2(x0)={0},Lf1+f2(x0)=[-1,0].

由定義有

?≤εf1(x0)=[1,+∞), ?≤εf2(x0)=R,

{?≤εf1(x0)+?≤εf2(x0)}=R,

然而

?≤ε(f1(x0)+f2(x0))=[-1,+∞).

由 此可見R ?[-1,+∞).因此該條件必不可少.

3 擬凸多目標優(yōu)化問題近似解的最優(yōu)性條件

本節(jié)考慮如下的多目標優(yōu)化問題(MOP)：

minf(x),s.t.x∈S,

其中，S?Rn為凸集，f(x)=(f1(x),f2(x),···,fm(x))T,fi:S→R,i=1,2,···,m為擬凸函數(shù)，利用第2 節(jié)中的近似次微分給出MOP 的近似解的最優(yōu)性條件.

定義9[18]設ε≥0,x0∈S，則S在x0處的法錐定義為

N(S,x0)={x*0∈Rn:〈x*0,x-x0〉≤0,?x∈S}.

S在x0處的ε-法錐定義為

Nε(S,x0)={x*0∈Rn:〈x*0,x-x0〉≤ε,?x∈S}.

定義10[20]設ε=(ε1,ε2,···,εm)T≥0,x0∈S，

(ⅰ) 若不存在x∈S，使得fi(x)＜fi(x0)-εi,?i∈{1,2,···,m}，則稱x0為MOP 的ε-弱有效解.

(ⅱ) 若不存在x∈S，使得

fi(x)≤fi(x0)-εi,?i∈{1,2,···,m},

fj(x)＜fj(x0)-εj,?j∈{1,2,···,m},

則稱x0為MOP 的ε-有效解.

定義11[21]設ε=(ε1,ε2,···,εm)T≥0,x0∈S，若

(ⅰ)x0是MOP 的ε-有效解，

(ⅱ) 存在常數(shù)M＞0，使得對任意的i∈{1,2,···,m}和x∈S，滿足fi(x)＜fi(x0)-εi，存在j∈{1,2,···,m}{i}滿足fj(x0)＜fj(x)+εj，且

則稱x0為MOP 的ε-真有效解.

與文獻[20]中定理 2.2類似，容易得出以下結(jié)論.

定理6設x0∈S, ε=(ε1,ε2,···,εm)T≥0.λi≥0,i∈{1,2,···,m},，若存在(-N?(S,x0))，滿足〈x*0,x-x0〉?[-?,?], ?x∈S{x0}，則x0是MOP 的ε-有效解.

注意到，文獻[20]并沒有給出近似真有效解的最優(yōu)性條件，下面利用近似次微分給出MOP 近似真有效解的最優(yōu)性條件.

定理7設x0∈S, ε=(ε1,ε2,···,εm)T≥0.λi＞0,i∈{1,2,···,m},，若存在(-N?(S,x0){0})，滿足〈x*0,x-x0〉?(-?,?),?x∈S{x0}，則x0是MOP 的ε-真有效解.

證明首先，由定理6得出x0為MOP 的ε-有效解，下面證明x0是MOP 的ε-真有效解.

反證，假設x0不是ε-真有效解，則對任意的M＞0，存在滿足fi(x)＜fi(x0)-εi的x∈S{x0},i∈{1,2,···,m}使得對任意滿足fj(x0)＜fj(x)+εj的j∈{1,2,···,m}{i}有

由λi＞0得

λi(fi(x0)-fi(x)-εi)＞(m-1)λj(fj(x0)-fj(x)+εj).

整理得

λi fi(x0)+(m-1)λj fj(x0)＞λi fi(x)+(m-1)λj fj(x)+λiεi+(m-1)λjεj.

即

從而

即

〈x*0,x-x0〉＜?,

又由于x*0∈-N?(S,x0)，從而有

〈x*0,x-x0〉＞-?.

這與〈x*0,x-x0〉?(-?,?), ?x∈S{x0}相矛盾，故x0是MOP 的ε-真有效解.□

推論1設MOP 中m=1,S=Rn, ε ≥0，若0 ∈?≤εf(x0)，則x0為minx∈Rn f(x)的ε-最優(yōu)解.

4 結(jié) 論

本文在已有擬凸函數(shù)的近似次微分基礎上，對次微分定義進行了改進，給出了其與已有次微分之間的關系及一系列性質(zhì)，如凸性閉性等，并通過實例說明其合理性.隨后，利用新的近似次微分給出擬凸單目標優(yōu)化問題的近似最優(yōu)解，擬凸多目標優(yōu)化問題的近似有效解、近似真有效解的刻畫.