拟凸变分不等式近似解与拟凸优化问题近似解的关系

陈瑞婷,徐智会

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

拟凸变分不等式近似解与拟凸优化问题近似解的关系

陈瑞婷,徐智会

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

利用已有的拟凸函数四种次微分,引进拟凸函数的四种近似次微分,给出拟凸变分不等式问题,研究了拟凸变分不等式的近似解与拟凸优化问题近似解之间的充分条件与必要条件,并给出相应例题予以说明.

拟凸函数;次微分;近似次微分;变分不等式;近似最优解

变分不等式是数学规划的一个重要研究领域,它与力学、微分方程、控制理论、数学经济、最优化理论、对策理论、非线性规划等理论和应用学科有着广泛的联系并有重要的应用.自20世纪60年代,变分不等式和相补问题的基本理论被提出和创立以来,经过许多数学家的杰出工作,变分不等式及其相关问题的理论和应用取得重要进展,日臻完善[1-7].其中在最优化理论中,凸性假设被广泛使用,但在实际问题的研究中,所研究的函数或集合大多数是非凸的.自20世纪60年代以来,凸函数的概念已被推广到不同类型的广义凸函数,例如:拟凸函数[8],E-凸函数[9].1965年,Mangasarian[8]引进拟凸和伪凸函数的概念并研究其性质.随后,很多学者研究了拟凸函数性质及最优性条件[10-14].

变分不等式是解决优化问题的一个有效工具.近年来,一些学者在研究优化问题时发现优化问题的最优性条件可以通过变分不等式进行刻画,见文献[15-19].Yang和Zheng[20]研究了一个点是变分不等式近似解的充分必要条件.特别的,近年来,针对拟凸数值优化问题研究较多[21-23],但利用次微分给出变分不等式问题的解相对较少,因此本文在文献[11]的基础上研究拟凸变分不等式的解与拟凸优化问题近似最优解之间的联系.

1 预备知识

设X为赋范向量空间,S⊂X为凸子集.

定义1[24]若f∶S→R,满足:∀x1,x2∈S,∀λ∈[0，1]，f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2),

则称f为S上的凸函数.

定义2[24]若f∶S→R,满足:∀x1,x2∈S,∀λ∈[0，1]，f(λx1+(1-λ)x2)≤max{f(x1),f(x2)},

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

本文考虑拟凸优化问题: (P)minf(x)x∈S

其中:可行集S为闭凸集,f是S上的拟凸函数.设x0∈S,下面给出目标函数f的水平集和次微分的概念.

设x0∈S,f∶X→R的下水平集为:[f≤f(x0)]∶={x∈X∶f(x)≤f(x0)}.

严格下水平集为:[flt;f(x0)]∶={x∈X∶f(x)lt;f(x0)}.

定义3[25]设f∶X→R,且存在常数K,使得对任意的x1,x2∈X满足如下条件:

|f(x1)-f(x2)≤K|x1-x2|

那么称f(x)在X上是Lipschitz连续的.

定义4[25]设x0∈S,凸函数f∶X→R在x0处次微分定义为:

定义5[11]设x0∈F,拟凸函数f∶X→R在x0处的Greenberg-Pierskalla次微分定义为:

存在,则称f在点x0处是Gteaux可微的.

注1 由定义可知:∂≤f(x0)⊆∂lt;f(x0)⊆∂*f(x0)⊆∂⊗f(x0),并且当f在[flt;f(x0)]上上半连续时,有∂⊗f(x0)=∂*f(x0)∪{0}，参见文献[11].

定义7 设ε≥0,x0∈S,若f(x0)-ε≤f(x),∀x∈S,称x0为问题(P)的ε-最优解.针对于问题(P)的近似最优解,首先定义拟凸函数f的近似水平集和近似次微分.

定义8 设ε≥0,x0∈S,f∶X→R的ε-下水平集为:[f≤f(x0)-ε]∶={x∈X∶f(x)≤f(x0)-ε}

严格ε-下水平集为:[flt;f(x0)-ε]∶={x∈X∶f(x)lt;f(x0)-ε}

定义9 设ε≥0,x0∈S,拟凸函数f∶X→R在x0处的两种ε-次微分定义为:

定义10 设ε≥0,x0∈S,拟凸函数f∶X→R在x0处的ε-下次微分定义如下:

显然该次微分是闭的.比之更弱的ε-次微分为:

定义12 设δgt;0,x0∈S,f∶X→R,若存在x0的一个邻域U(x0,δ),使得x0为f在U(x0,δ)上的ε-最优解,则称x0为f在X上的局部ε-最优解.

引理1[27]设A，B是X中的非空凸子集,intA≠ø,若intA∩B=ø,则存在超平面分离intA和B.

2 拟凸变分不等式近似解与拟凸优化问题近似解的关系

考虑如下变分不等式问题：

定理1 设ε≥0,x0是(VIAP1)的解,且〈ξ,x-x0〉⊄[-ε,ε],∀x∈S,则x0为问题(P)的ε-最优解.

因此ξ∈-Nε(x0,S).

下证x0为问题(P)上的近似最优解.

反证,设x0不是问题(P)的近似最优解,则存在x∈S,使得:f(x)lt;f(x0)-ε.

又因为ξ∈-Nε(S,x0)，故有:〈ξ,x-x0〉≥-ε.

从而有〈ξ,x-x0〉⊆[-ε,ε],与定理条件矛盾,因此x0为问题(P)的ε-最优解.

推论1 若x0是(VIAP3)的解,且〈ξ,x-x0〉⊄[-ε,ε],∀x∈S,则x0为问题(P)的ε-最优解.

推论2 若x0是(VIAP4)的解,且〈ξ,x-x0〉⊄[-ε,ε],∀x∈S,则x0为问题(P)的ε-最优解.

推论3 设ε≥0,x0∈S,f在[f≤f(x0)-ε]内是上半连续的,f在x0处Gteaux可微且〈f′(x0),x-x0〉≥-ε,∀x∈S,〈f′(x0),x-x0〉⊄[-ε,ε],∀x∈S,则x0为问题(P)的ε-最优解.

注5 定理1、推论1和推论2的逆命题不一定成立,见如下例子.

取x0=0时,显然x0=0是问题(P)的ε-最优解.

定理2 设ε≥0,x0是问题(P)的ε-最优解,但x0不是f在全空间X上的局部ε-最优解.若f在[flt;f(x0)-ε]内上半连续,则x0是(VIAP2)的解.

证明令G=[flt;f(x0)-ε].x0是问题(P)的ε-最优解,则f(x)≥f(x0)-ε,∀x∈S.显然S∩G=ø,又由f的拟凸性及f在[flt;f(x0)-ε]内上半连续,知G为开凸集,S也为凸集.由凸集分离定理,存在ξ∈X*,r∈R,使得

〈ξ,w-x0〉≥r≥〈ξ,u-x0〉,∀w∈S,∀u∈G.

(1)

故有:ξ∈(-Nε(S,x0)).

从而结论成立,故x0是(VIAP2)的解.

例3说明x0不是全空间X上的局部近似最优解这一条件必不可少.

取x0=0时,显然x0是问题(P)的ε-最优解,且是全空间R上的局部ε-最优解.

要使〈ξ，x〉≥-ε,∀x∈S成立,ξ只能取零,这与结论矛盾.

定理3 设ε≥0,x0∈S,f是在射线上连续的拟凸函数,f在X上的局部ε-最优解是全局ε-最优解,令inff(S)gt;inff(X)+ε,且f在[f≤inff(S)-ε]上Lipschitz连续,则下列结论等价;

1)x0是(VIAP3)的解；2)x0是(VIAP4)的解.

任取x∈[flt;f(x0)-ε],由上式可知,只需证明:当f(x)=f(x0)-ε时,有：〈ξ，x-x0〉≤f(x)-f(x0)+ε.

事实上,由条件inff(S)gt;inff(X)+ε可知x0不是f在全空间X上的全局ε-最优解,从而由条件可知x0不是f在全空间X上的局部ε-最优解.取xn→x,使得f(xn)lt;f(x0)-ε,则有：〈ξ，xn-x0〉≤f(x)-f(x0)+ε.

因为f在[flt;inff(S)+ε]上是上半连续的,故上式两端取极限得：

〈ξ，x-x0〉≤f(x)-f(x0)+ε.∀x∈[f≤f(x0)+ε]，

[1] FACCHINEI F,PANG J S.Finite-dimensional variational inequalities and complementarity problems[M].Springer,2003.

[2] YANG X Q.Vector variational inequality and vector pseudolinear optimization[J].Journal of Optimization Theory and Applications,1997,95(3):729-734.

[3] FERRIS M C,PANG J S.Engineering and economic applications of complementarity problems[J].Siam Review,1997,39(4):669-713.

[4] KOJIMA M,MEGIDDO N,NOMA T,et al.A unified approach to interior Point Algorithms for Linear Complementarity Problems[M].Springer Berlin Heidelberg,1991.

[5] RAN B,BOYCE D E.Discrete Optimal Control,Mathematical Programming and Variational Inequality Problems[M].Dynamic Urban Transportation Network Models.Springer Berlin Heidelberg,1994:53-82.

[6] CHEN G Q,CAO B.A new NCP-function for box constrained variational inequalities and a related Newton-type method[J].Mathematica Numerica Sinica,2002(1):91-104.

[7] BERNSTEIN D.Network economics:A variational inequality approach,by anna nagurney[J].Advances in Computational Economics,1993,1:3-44.

[8] MANGASARIAN O L.Pseudo functions[J].Journal of the Society for Industrial and Applied Mathematics,1965,3(2):23-32.

[9] DUCA D I,LUPA L.On the E-epigraph of an E-convex function[J].Journal of Optimization Theory and Applications,2006,129(2):341-348.

[10] PENOT J P.What is quasiconvex analysis?[J].Optimization,2000,47(1/2):35-110.

[11] PENOT J P.Characterization of solution sets of quasiconvex programs[J].Journal of Optimization Theory and Applications,2003,117(3):627-636.

[12] NAUYEN T H L,PENOT J P.Optimality conditions for quasiconvex programs[J].Siam Journal on Optimization,2006,17(2):500-510.

[13] PENOT J P,ZALINESCU C.Elements of quasiconvex subdifferential calculus[J].Journal of Convex Analysis,2000,7(2):243-269.

[14] PENOT J P.Characterization of Solution Sets of Quasiconvex Programs[J].Journal of Optimization Theory and Applications,2003,117(3):627-636.

[15] YANG X Q,GOH C J.On vector variational inequalities:application to vector equilibria[J].Journal of Optimization Theory and Applications,1997,95(2):431-443.

[16] KINDERLEHRER D,STAMPACCHIA G.An Introduction to Variational Inequalities and their Applications[M].Academic Press,1980.

[17] LEE G M,KIM D S,LEE B S,et al.Vector variational inequality as a tool for studying vector optimization problems[J].Nonlinear Anal,1998,34:745-765.

[18] MISHRA S K,WANG S Y.Vector varational like inequalities and nonsmooth vector optimization problems[J].Nonlinear Anal,2006,64:1939-1945.

[19] YANG X Q.Vector varational inequality and vector pseudolinear optimization[J].J Optim Theory Appl,1997,95:729-734.

[20] YANG X Q,ZHENG X Y.Approximate solutions and opmality conditions of vector variational inequalities in Bamach spaces[J].J Glob Optim,2008,40:455-462.

[21] 孙菊贺.锥约束变分不等式问题的数值方法的研究[D].大连：大连理工大学,2008.

[22] 曾云辉.变分不等式的数值解法研究[D].西安：西北大学,1999.

[23] 胡淑娟,王希营,丁方允.关于变分不等式问题近似解的数值证明[J].计算力学学报,2006,23(1):40-45.

[24] 杨新民,戎卫东.广义凸性及其应用[M].北京：科学出版社,2016.

[25] 胡毓达,孟志青.凸分析与非光滑分析[M].上海：上海科学技术出版社,2000.

[26] GAO Y,YANG X M，LEE H W J.Optimality conditions for approximate solutions in multiobjective optimization problems[J].Journal of Inequalities and Applications.2010,article ID 620928,17 pages.

[27] YOSHIKAZU SAWARAGI,HIROTAKA NAKAYAMA,TETSUZO TANINO.Theory of multiobjective optimization[M].Academic Press,1985.

责任编辑：高山

TheRelationsbetweenApproximateSolutionofQuasiconvexVariationalInequalitiesandApproximateSolutionofQuasiconvexOptimizationProblem

CHEN Ruiting,XU Zhihui

(School of Mathematics Sciences,Chongqing Normal University,Chongqing 401331,China)

In this paper,we introduce four kinds of approximate subdifferential of quasiconvex function by using known four kinds of subdifferential of quasiconvex function,and give quasiconvex variational inequality problems.We study the sufficient conditions and necessary conditions between the quasiconvex variational inequality and quasiconvex optimization problems,and give the corresponding examples to illustrate.

quasiconvex function;subdifferential;approximate subdifferential;variational inequalities;approximate optimal solutions

2017-08-08.

国家自然科学基金项目(11201511);重庆市科委项目(cstc2015jcyjA00005);重庆市教委项目(KJ1500309).

陈瑞婷(1994-),女,硕士生,主要从事最优化理论与方法的研究.

1008-8423(2017)04-0390-04

10.13501/j.cnki.42-1569/n.2017.12.008

O221.6

A