拟凸函数的近似次微分及其在多目标优化问题中的应用*

史小波，高 英

（重庆师范大学 数学科学学院，重庆 401331）

引 言

凸性在优化问题中有着广泛的应用，但在实际问题的研究中，我们遇到的函数或者集合大多数是非凸的.于是研究凸性的各种推广形式具有重要的意义.20 世纪60 年代以来，凸函数的概念已被推广到不同类型的广义凸函数，例如拟凸函数[1]、E-凸函数[2]等.拟凸函数作为一类特殊的广义凸函数，在非凸优化中有着广泛的应用[3-4].De Finetti 和Fenchel 在文献[5-6]中首次给出了拟凸函数的定义.1965年，Mangasarian[1]首次引进伪凸的概念并给出拟凸函数和伪凸函数的若干性质.随后，杨新民等[7-9]进一步给出拟凸函数的性质及其在优化理论中的应用.

对于凸函数来说，次微分和近似次微分[10]是给出凸优化问题最优性条件的基本工具.因此，如何引进拟凸函数的次微分是研究拟凸优化问题最优性条件的首要问题.20 世纪70 年代以来，文献[11-14]先后引进了Greenberg-Pierskalla 次微分、星型次微分、Gutiérrez 次微分、Plastria 次微分并给出了一些性质.随后，Penot 在文献[15-16]中首次给出这四种次微分之间的关系并给出了一些推广性质.有了这些次微分的概念及基本性质，一些学者开始利用这些次微分给出拟凸数值优化问题的最优性条件[17-19].2019 年，陈瑞婷等[20]给出了拟凸意义下的近似次微分以及近似解的概念，并给出了拟凸多目标优化问题近似解的最优性条件.

本文在文献[10,20]的基础上，得到了拟凸函数新的近似次微分的概念，研究其与已有次微分之间的关系及性质，并将其应用到拟凸多目标优化问题中.最后，给出近似有效解、近似真有效解的概念，利用新的近似次微 分得到拟凸优化问题近似解的最优性条件.

1 预备知识

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

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

则称f为Rn上的凸函数.

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

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

则称f为Rn上的拟凸函数.

给定λ ∈R，f对应于λ的水平集与严格水平集定义为

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

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

针对拟凸函数，文献[11-14]引进了如下次微分的概念.

定义3[11-14]设f为拟凸函数，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]针对拟凸函数给出了近似水平集和近似次微分的概念.

设ε ≥0，拟凸函数f的近似水平集与严格近似水平集可以表示为

定义4[20]设f为拟凸函数，ε ≥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]设函数f:S⊆Rn→R，对任意的x∈S，存在一个正数L,δ，使得

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

则称f为S上的局部Lipschitz 函数.

定义6[10]设f为Rn上的局部Lipschitz 函数，f(x)在点x处关于方向d∈Rn的广义方向导数定义为

f在点x处的Clarke 次微分定义为

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

若f为Rn上的凸函数，则Clarke 次微分退化为凸意义下的次微分：

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

文献[10]针对凸函数给出了如下近似次微分的概念.

定义7[10]设f为Rn上的凸函数，ε ≥0,f在点x0点的ε次微分定义为

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

Clarke 次微分是针对局部Lipschitz 连续函数给出的.显然，拟凸不一定连续.从而，也不一定是局部Lipschitz连续.下面给出一个例子说明拟凸连续函数也不一定是局部Lipschitz 连续的.

例1设f(x)=x∈[0,+∞)，则f(x)在[0,+∞)上为拟凸连续函数.

由定义显然有f(x)在[0,+∞)上为拟凸连续函数.下面说明f(x)在x=0处不是局部Lipschitz 连续的.事实上，对任意的L＞0,δ ＞0，特别取当n充分大时，xn,yn∈O(0,δ)∩[0,+∞)且

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

即

从 而f(x)不是局部Lipschitz 连续的.

2 拟凸函数的近似次微分

本节针对拟凸函数f:Rn→R，在定义4 的基础上，提出如下近似次微分的概念，并研究其性质.

定义8设ε ≥0,x0∈Rn,f在x0处的ε-下次微分定义为

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

例2考虑拟凸函数

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

在实际应用中，存在一些拟凸函数，其精确的次微分可能为空集，而改进后的近似次微分不一定非空，见例3.

例3考虑拟凸函数

取x0=0, ε=2，

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

而对于某些拟凸函数来说，定义4 中的近似水平集有可能为空集，而本文定义的水平集不一定非空，见例4.

例4考虑拟凸函数

取x0=0, ε=2，则定义4 中的近似水平集x∈∅,而定义8中的水平集x∈(-2,+∞)，此时，

f(x)∂≤εf(x0)

注3 当为局部Lipschitz 连续时，Clarke 次微分不一定包含在，见例5.

例5设f(x)=x3,x∈R，则f(x)为拟凸局部Lipschitz 连续函数.特别取x0=0, ε=1，则∂Cf(x0)={0},∂≤εf(x0)=∅.

下面，我们研究了近似次微分的一些性质.

ε ≥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).再由ξ的任意性可知故

与凸意义下的近似次微分类似，下述结论成立.

x0∈Rn,

定理4设则有

(ⅰ) ∂≤εg(x0)=∂≤εf(x0)，其中g(x)=f(x)+C,C为常数；

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

(ⅲ) ∂≤εg(x+x0)=∂≤εf(x0)，其中g(x)=f(x-x0)，f(x)为单调函数；

(ⅳ) ∂≤εf(x0)+{α}⊂∂≤εg(x0)，其中g(x)=f(x)+αTx，α ∈Rn+，g(x)为单调递增函数.

定理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考虑函数

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 拟凸多目标优化问题近似解的最优性条件

本节考虑如下的多目标优化问题(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为拟凸函数，利用第2 节中的近似次微分给出MOP 的近似解的最优性条件.

定义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 的ε-有效解，

(ⅱ) 存在常数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类似，容易得出以下结论.

定理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]并没有给出近似真有效解的最优性条件，下面利用近似次微分给出MOP 近似真有效解的最优性条件.

定理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)的ε-最优解.

4 结 论

本文在已有拟凸函数的近似次微分基础上，对次微分定义进行了改进，给出了其与已有次微分之间的关系及一系列性质，如凸性闭性等，并通过实例说明其合理性.随后，利用新的近似次微分给出拟凸单目标优化问题的近似最优解，拟凸多目标优化问题的近似有效解、近似真有效解的刻画.