拟凸优化问题近似解的最优性条件

徐智会， 陈瑞婷， 高 英

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

凸性在最优性理论、数理经济和工程技术中有极其重要的作用．自20世纪60年代以来，凸函数的概念已被推广到不同类型的广义凸函数，并在广义凸性条件下，研究其最优性和对偶理论［1－20］，例如拟凸函数［1］和 E－凸函数［2］等．其中，拟凸函数作为一类特殊的广义凸函数，在经济学领域中有着广泛的应用．Mangasrian［1］提出拟凸和伪凸的概念并研究其性质．杨新民等［3－5］介绍了拟凸函数的某些特殊性质．对于凸函数来说，次微分是给出凸优化问题最优性条件的基本工具，这方面的结果已经非常成熟．针对拟凸函数，文献［1］介绍了 Greenberg－Pierskalla次微分、星型次微分、Gutiérrez次微分和Plastria次微分的概念，并研究了它们的性质．在此次微分的基础上，很多学者开始研究拟凸优化问题解的最优性条件［7－12］．但拟凸优化问题近似解的最优性条件研究至今并未涉及．注意到最优化问题近似解理论研究的重要性，本文在拟凸函数4种次微分的基础上，提出拟凸函数4种近似次微分的概念，从而利用近似次微分给出拟凸数值优化问题近似解的最优性必要和充分条件．

1 预备知识

则称f为S上的凸函数．

定义 1．2［5］若 f(x)在 S 上满足x，x∈S，

12

则称f为S上的拟凸函数．

本文考虑如下拟凸优化问题

严格下水平集为

定义 1．3［19］当f为凸函数时，次微分定义为

定义 1．4［6］拟凸函数 f:SR，在 x处的

0Greenberg－Pierskalla次微分定义为

星型次微分定义为

Gutiérrez次微分定义为

Plastria下次微分定义为

由定义可知

并且当f在［f＜f(x0)］上是上半连续时，有

定义 1．5［19］集合C在x0处的法锥定义为

定义 1．6 设 ε≥0，x0∈S，若 f(x0)－ε≤f(x)，x∈S，称 x0为问题(1)的 ε－近似解．

定义 1．7 设 δ＞0，ε≥0，x0∈S，f:X→R，若存在 x0的一个邻域内 U(x0，δ)，使得 x0为 f在U(x0，δ)上的ε－近似解，则称x0为f在X上的局部ε－近似解．

为了给出问题(1)近似解的最优性条件，定义拟凸函数f的近似水平集和近似次微分的概念．

定义 1．8 设 ε≥0，x0∈S，f的近似下水平集为

严格近似下水平集为

定义 1．9 设 ε≥0，x0∈S，拟凸函数 f的 2种近似次微分定义为

注 1．1 当［f＜f(x0)－ε］=Ø时，规定*εf(x0)=X*．

定义 1．10［10］设 ε≥0，集合 C 在 x0处的近似法锥定义为

当集合C=［f＜f(x0)－ε］时，○＊εf(x0)=Nε(C，x0)．对应于定义 1．4 中的＜f(x0)和≤f(x0)，可定义如下近似次微分．

由定义可知

当ε=0时，上述4种次微分分别可退化到定义1．4中4种次微分，且(2)式可退化为文献［8］中的如下关系

当 ε＞0时，有

注1．2 在文献［8］中给出结论，当f是凸函数时，若x0不是f在X上的最优解，且 R+(dom f－x0)=X，则有*f(x0)=(0，+∞ )f(x0)，即y∈*f(x0)，存在 λ∈(0，+∞)，y1∈f(x0)，有 y=λy1．对于给出的拟凸函数的近似次微分*εf(x0)和凸函数的 ε－次微分εf(x0)，当 ε＞0时，在无任何条件下，关系式(0，+∞)εf(x0)∈*εf(x0)成立，事实上，对任意的 t＞0，x0∈X，x0*∈εf(x0)，由定义有

故对任意的 x∈［f＜f(x0)－ε］有

即tx*0∈*εf(x0)，故(0，+∞)εf(x0)∈*εf(x0)．但反包含关系在条件x0不是f在X上的最优解，且R+(dom f－x0)=X 下，*εf(x0)∈(0，+∞)ε×f(x0)也不一定成立，见如下例子．

2

注 1．3 与注1．2说明类似，有再结合(2)式有

注 1．4 当 ε=0 时，有 R+＜f(x0)=*f(x0)［6］，但当 ε＞0 时，只能保证 R+ε＜f(x0)∈*εf(x0)．事实上，因为对任意的y0*∈＜εf(x0)，由定义有

从而对任意的t≥0有

故ty0*∈*εf(x0)，即 R+＜εf(x0)∈*εf(x0)．但反包含关系不一定成立．例如 f(x)=x，取 x0=0，ε=1时有

引理 1．1［7］设A、B 是 X 中的非空凸子集，若A∩B=Ø，则存在超平面分离A和B．

2 拟凸优化问题的最优性条件

本节在给出近似水平集与近似次微分的基础上，给出问题(1)近似解的最优性条件．

定理 2．1 设 x0∈S，ε≥0，若

且〈y0*，x－x0〉［－ε，ε］，x∈Sx0，则 x0为问题(1)上的ε－近似解．

证明 设x0不是问题(1)的ε－近似解，则存在x∈Sx0，使得f(x) ＜ f(x0)－ ε，故由y*0∈*εf(x0)有〈y*0，x － x0〉＜ ε，又因为 y*0∈－Nε(S，x0)，故有〈y*0，x－x0〉≥－ε，从而有

这与条件矛盾．因此x0为问题(1)上的ε－近似解．推论 2．1 设 x0∈S，ε≥0，若任意的

有〈y0*，x－x0〉［－ε，ε］，x∈Sx0，则 x0是问题(1)的ε－近似解．

由定理2．1得x0是问题(1)的ε－近似解．

推论 2．2 设 x0∈S，ε≥0，f在［f＜f(x0)－ε］上是上半连续函数，若

使得〈y*0，x－x0〉［－ε，ε］，x∈Sx0，则 x0是问题(1)的ε－近似解．

证明 与定理2．1的证明类似．

推论 2．3 设 x0∈S，ε≥0，f在［f≤f(x0)－ε］上是上半连续函数，若

使得〈y*0，x－x0〉［－ε，ε］，x∈Sx0，则 x0是问题(1)的ε－近似解．

由推论2．2得x0是问题(1)的ε－近似解．

注 2．5 定理 2．1、推论 2．1～2．3 的逆命题不一定成立，见如下例子．

下面符合定理 2．1、推论 2．1～2．3 中的〈y*0，x－x0〉［－1，1］:

但是定理 2．1、推论 2．1～2．3 中的逆命题并不一定成立．取x0=0，ε=1时，经计算得x0是问题(1)的ε－近似解．下面不满足定理 2．1、推论 2．1～2．3 中的〈y0*，x－x0〉［－ε，ε］:

定理2．2 设 ε≥0，x0是问题(1)的 ε－近似解，但x0不是f在全空间X上的局部ε－近似解，f在［f＜f(x0)－ε］是上半连续的，则存在 y*0∈X{0}，使得

证明 令G=［f＜f(x0)－ε］，x0是问题(1)的ε－近似解，则．显然 S∩G=Ø，又由f的拟凸性及 f在是上半连续的，知 G为开凸集，S也为凸集．由引理1．1可知，存在y0*∈X*{0}，r∈R，使得

在(3)式右端取 ω=x0，则〈y0*，μ－x0〉≤r≤0≤ε，μ∈G，这表明y*0∈*εf(x0)．

另一方面，x0不是f在全空间X上的局部ε－近似解，存在{μn}G，使得 μn→x0．由(3)式左边可知，再由 μn→x0可知r≥0，所以r=0．从而(3)式右端退化为

即〈－y0*，ω－x0〉≤0≤ε，则 y*0∈(－Nε(S，x0))．结合前面结果有y*0∈*εf(x0) ∩ (－ Nε(S，x0))．

下面的例子说明x0不是f在全空间X上的局部ε－近似解这一条件必不可少．

S=R，取 x0=0，ε=，则x是f在S上的近似解，f

0也是在全空间X上的局部 ε－近似解，且 f在［f＜f(x0)－ε］是上半连续的．经计算

推论 2．4 设 x0∈S，ε≥0，f在［f＜f(x0)－ε］上是上半连续，f在 x0处 G－可微，若对x∈Sx0，有－f'(x0)∈－Nε(S，x0)且〈－f'(x0)，x－x0〉［－ε，ε］，则x0是问题(1)上的ε－近似解．

证明 显然－f'(x0)∈○＊εf(x0)，于是满足推论2．1 的条件，证毕．

定理 2．3 设 ε≥0，x0∈S，f在 X 上的局部ε－近似解是全局 ε－近似解．令 inf(S)＞inf(X)+ε，f在［f＜inf(S)－ε］上是上半连续的，则≤εf(x0)=＜εf(x0)．

＜f (x0)∈≤εf(x0)．对任意的 y*0∈＜εf(x0)，由定义得

任取 x∈［f≤f(x0)－ε］，由上式可知，只需证明:当f(x)=f(x0)－ε时有

事实上，由条件inf(S)＞inf(X)+ε可知，x0不是f在X上的全局ε－近似解，从而由条件可知x0不是f在X 上的局部 ε－近似解．取 xn→x，使得 f(xn)＜f(x0)－ε，则有

因为f在［f＜inf(S)－ε］上是上半连续的，故上式两端取极限得

综上可知 y*0∈≤εf(x0)．证毕．

当ε＞0时，以上结论不能推广到ε－近似解．事实上，在例 2．2 中，S0=［－1，0］，取 C=S=［－1，1］，则 C∩S0=［－1，0］．当 x0=0 时，有

当 x1=－1时，有

这表明，对于 x0，x1∈C∩S0，

3 结论

本文针对拟凸函数给出了4种近似次微分的概念，研究了它们之间的关系．利用近似次微分给出了拟凸优化问题近似解的必要和充分条件，并通过实例说明其合理性．在本文基础上，还可以将拟凸数值优化问题推广到多目标拟凸优化问题，利用近似次微分研究近似弱有效解、近似有效解的充分必要条件和对偶理论．