凹函数的共轭

凹函数的共轭 第25卷第4期 2004年8月 大连大学 J0URNAL0FDALlANUNIVERSITY V01.25No4 Aug.2004 凹函数的共轭 刚家泰 刘自新,张成, (大连大学信息工程学院,辽宁大连116622) 摘要:在数学规划的对偶理论中,函数及其共轭函数在解决某些实际问题时发挥着 利用二 重要的作用, 者的关系,我们可以把涉及某一函数的问题转化为与其共轭函数有关的对偶问题加以解决.有关凸函数及 其共轭函数的理论,在文献[3]中有较为详尽的论述,本文着重介绍凹函数及其共轭函数的相关理论,这 些理论在对偶凸规划中同样发挥着重要作用. 关键词:凹函数;共轭凹函数;共轭集 中图分类号:o221.2文献标识码:A文章编号:1008—2395i2004)04—0006—05 Conjugateofconcavefunction UUZi—xin,ZHANGCheng,GANGJia—tai (CollegeofInformationEngineering,DalianUniversity,Dalian116622,China) Abstract:InthetheoryofduMi~aboutMathematicalprogramming,functionanditsconjugat efunctionplayan importantroleintheresolvingofsomepracticalproblems,withtheirrelation,weCal1.transfo rmaproblemofa functionintoaproblemofitsconjugatefunction,SOthatweCallsolveiteasily.Thetheoryofco nvexfunctionand itsconjugatefunctionhavebeendiscussedin[3].Inthispaper,wemainlytalkaboutthetheory ofconcavefunc. tionanditsconjugatefunction,thesetheoryisimportanteitherinthedualityofconvexprogra mming. Keywords:concavefunction;conjugateofconcavefunction;conjugatesets 在凸规划的对偶理论中,凸函数,凸函数的共轭函数及其与凸函数,凸集的关系是非常重要的理论 基础,这些关系及其推广,可参考文献[1,2]ManfredWalk在文献[3]中对凸函数及凸函数的共轭也有 较为详尽的阐述,在有些情况下,我们也常常在凹函数的框架下讨论凸规划问题,正是在这样的背景下, 本文讨论了凹函数,凹函数的共轭及其关系,这些结果可以很容易地推广到拓扑向量空间中. 设g是一个定义在凸集D尺上的凹函数,即对任意,ED,AE(O,1),有g((1一A)+Ax)? (1一A)g()+Ag(X)我们考察集合 [g,D]={(,)ER×DI?g()}(1) 如果g是一个闭凹函数,则[g,D]是包含在尺"中的闭凸集.由于通过一个闭凸集的每一个边界点 至少有一个切超平面,利用这个性质,我们不但可以用点(,)描述[g,D],而且也可以通过所有的切 超平面来描述它,这就是我们定义包含所有这些超平面的[g,D]的相应对偶集[g,D]的原因. 定义1所有非垂直的超平面的集合 H={(,)ERXRI<(一1,a),(z,)>一=0} 对任意的(,)E[g,D]满足性质 <(一1,a),(,)>一?0 称为[g,D]的相应对偶集,记为[g,D]. 向量(一1,a)垂直于H,为切超平面在垂直坐标轴上的截距,我们把(,a)等同于超平面,则[g, 收稿日期:2003.11.17 作者简介:刘自新(1969一),男,副教授 第4期刘自新等:凹函数的共轭7 D]可理解为R"中的一个子集.从几何观点看,属于[g,D]的所有超平面完全位于凸集[g,D]的上 方,所以元素(,n)?[g,D]当且仅当对任何?D,我们有 ?<口,>一g() 从而7?in—fl<n,>一g()}= 是使(,n)?[g,D]的最大数,对任何7?y-的实数7,元素(7,n)?[g,D]. 令D={n?R,in—fl<n,>一g()}>一..},在D上定义函数 g(n)==in— f{<?,>一g()} 如果n?D,则显然所有满足7<的超平面(7,n)?[g,D],D包含[g,D]中所有具有方向 向量(一1,n)的超平面,由此我们可以用 [g,D]={(,n)?R×Dl?g(n)}(2) 表示[g,D]的共轭集,我们称g为g的共轭凹函数. 命题2设D是一个包含内点的闭凸集,g为定义在D上的闭凹函数,则D是一非空凸集,g是以 D为定义域的闭凹函数. 证明:因为g是闭的,所以[g,D]也是闭的. 由于过[g,D]的每个边界点有一个切超平面,因此,如果.是D的内点,则在[g,D]上存在一个过 点(g(.),.)的切超平面,且这个切超平面不是垂直的,所以它属于[g,D],即D?. 下证D的凸性和g的凹性. 考察点n=Aa+(1一A)nn,n?D且0?A?1,我们有 inf{<口,>一g()}=infl<Aa+(1一A)口,>一g()}? Ain— fl<n,>一g()}+(1一A)infl<n,>一g()} 因此n?D即D是凸的,上面的不等式也意味着g(n)?Ag(n)+(1一A)g(n),这说明 g是一个凹函数. 最后我们证明g是闭的. 令{n}是D的内点序列,收敛于n,则对V?D g(口)?<口,>一g() 从而imsupg(口)?. 1irasup{<口,>一g()}=<口,>一g()V?D 所以imsupg(n)?infl<n,>一g()}=g(n) 另一方面,由于凹函数在任何内点连续,从而有. 1irasupg(n)?g(n),因此imsupg(n)= g(n),即g是闭的. 由于g是定义在D上的闭凹函数,由(1)[g,D]={(7,n)?R×Dl7?g(n)}是凸的, 闭的,这个结果连同(2)意味着[g,D]=[g,D]. 下面我们考察凹函数g与其共轭凹函数g的关系. 设.是D的内点,(g(.),.)是凸集[g,D]的边界点,则在[g,D]上过(g(.),.)存在一个切超 平面,这个切超平面可以用数对(7,n.)表示,显然它是共轭集[g,D]的一个元素,关于这个切超平面, 我们有 <n" ,>一g()?7?D 且<n.,.>一g(x.)=7 由这些关系,立即有 g(口o):i婴f{<口0,>一g(x)}=<口0,0>一g(x0)=7 从而 g(x0)+g(口0)=<口0,>(3) 8大连大学第25卷 因为g(n.)=,所以[g,D]上过边界点(g(.),.)的切超平面可以用[g,D]上过边界点 (g(n.),n.)的切超平面表示,反之,[g,D]上过边界点(g(n.),n.)的切超平面也可以用[g,D]上过 边界点(g(.),..)的切超平面表示.我们称数对(n.,.)为凹共轭点对. 定理3设(n.,.)为关于凹函数g及其共轭凹函数g'的--x,/共轭点,如果n.?D及.?D为 内点,且存在邻域6(n.)D及6(")D使g和g分别在该邻域内严格凹,则n.与.的对应是 唯一的,且[g,D]上过(g(),的切超平面和[g,D]上过(g(n.),n.)的相应切超平面唯一定 义. 证明:假设切超平面(g(n.),n.)过(g(.),.)和(g(),)且.,,由[g,D]的凸性,对0? A?1. (g(),)=A(g(),.)+(1一A)(g(),)?[g,D] 从而(g(),)属于切超平面(g(n.),n),因此(g(),)是[g,D]的边界点,因此,当.?? 时,函数g是线性的,这与假设存在一个邻域6(.)D使g在6(.)中严格凹矛盾.由于定理的结 论是对称的,定理得证. 命题4如果g是一个定义在闭凸集D上的闭凹函数,则 [g,D]=[g,D]:[g,D] 证明:首先证明[g,D][g,D] 对任何元素(,)?[g,D],由g的定义,对所有n?D g(fI)?<n,>一g() 因为?g(),因此 ?<n,>一g(n)n?D(4) 从而?inf{<n,>一g(n)}:(g)()(5) 则我们可以把[g,D]表示为如下形式: [g,D]={(,)?RxDI?(g)()} 且D={?RIinf{<n,>一g(n)}>一?} 由(4),又寸VD也有?D且女口果(,)?[g,D]贝0由(5)(,)?[g,D'],因此DD'' 且[g,D][g,D]'. 下面我们证明,如果(.,.)[g,D],则(.,.)[g,D]. 如果(.,.)[g,D],则由于[g,D]是闭的,从而点(.,.)与[g,D]有正距离,这意味着([g, D],{(.,.)})>0,由分离定理,存在一个超平面(y,n)严格分离[g,D]与(.,.),对这个超平面, 我们有 <(一1,n),(,)>一y>0V(,)?[g,D](6) 且<(一1,?),(0,.)>一y<0(7) 由(6),对V?D)<<?,>一y,相应地y?infl<?,>一g()}=g(?),这意味着超 平面(y,n)属于[g',D]. 另一方面,由y?g'(?)及(7),0><?,.>一y?<?,.>一g(?),因此,(0,.)不可能是 [g',D]'的元素,这就证明了定理. 设g,g是定义在凸集D,D:上的闭凹函数,则[g,D],[g,D]是闭凸集,设[g,D],[, D2]是相应的共轭集,我们定义 T=[g1.,D]+[g,D]={(y,?)?R}y=y1+y2; ?=n+?;(y,?')?[g',D],i=1,2} 令表示的闭包. 命题5设g,g是定义在D,D上的闭凹函数,如果D=DnD?,则对定义在D上的凹函 第4期刘自新等:凹函数的共轭9 数g()=g()+g(),有 [g,D]=T=[g,D] 其中D:+DD'D:+Di 且g(n)=sup{gl(n)+g2(n)I=n+n;n'?D,i=1,2} 这个命题说明对Vn=n+n?D+D2,总有g(n)?gl(n)+g2(n). 证明:这个命题的证明分三步: (i)T[g,D]; (ii)[g,D]=; (iii)T=[g,D]. (i)设(y,n)=(yl+y2,n+n)?T,则对所有?DlnD2, yl?g(n)?<n,>一gl() y2?g2(n)?<n,>一g2() 将两个不等式相加得 y=y1+y2?<n+n,>一g1()一g2()=<n,>一g() 因此?inf{<n,>一g()}=g(n)D1nD 从而元素(y,n)=(y+y:,n=n+n)?[g,D],因此[g,D]',又因函数g()=g() +g()是闭的,因此凸集[g,D]是闭的且[g,D]. (ii)由命题4,[g,D]一=[g,D],由定义1,(OL,)?T当且仅当对任何(y,n)=(y+y,n +n)?T,我们有 0?<(一1,),(y,乜)>一=<乜+以,>一l—2一O/ 这个不等式显然等价于 OL?<n,>一g(n)+<n,>一g2(n)Vn'?D,:1,2 因此我们有 OL?inf{<?,>一g1"(n)+inf{<n,>一g2(n)} ncui 由于g一:g,i=1,2,故 OL?gl()+g2()=g()?DlnD2 因此若(OL,X)?T贝U(OL,)?[g,D],即 [g,D](8) 由共轭集的定义,(8)意味着 [g,D]T一(9) (,n)?T一当且仅当任何(OL,)?T,我们有 0?<(一l,n),(OL,)>一y=一OL+<n,>一y 县p?<n,>一OL 这个不等式等价于 y?<n,>一g()=<n,>,gl()一g2()V?DlnD2=D 从而y?inft<n,>一g()}:g(n) 因此,若(y,n)?T一,则(y,n)?[g,D]即一[g,D],这个结果与(9)一起意味着T一: [g,D],因[g,D]是闭的,所以一也是闭的. 此外,因是闭凸集,T一=T,由(i),TT[g,D]=T一. 如果我们用这种包含关系和变换两次,得 一T一=T[g,D]…=[g,D]=T一 因此,T:[g,D]=T一.(下转第18页) 18大连大学第25卷 究,得到了很有意义的结果,到目前理论上还无法解释的很清楚.不过当时的实验与现在的不同,气泡是 毫米量级的,不是用声压驱动,而是用力学方法拉开气泡然后气泡收缩,闭合时发光一次.遗憾的是他们 也没能介绍到国外. 的研究工作因当时的特殊国情无法继续深入进行, 3声致发光的应用前景 与多数基础研究类似,声致发光现象的研究离实际应用还有一段距离,但有些应用是许多人期 待的. (1)由于气泡内可能达到高温,高压的极端条件,人们企图找到能控制极端条件的方法,以期达到 热核反应条件; (2)气泡发光有很准确的周期规律,与驱动声场频率同步,而且每次发光脉冲很窄(100ps左右), 可以用来做便宜的窄脉冲光源或用来计时; (3)气泡内极端条件可用来加速化学反应. 另一方面,从前两节介绍不难看出在声致发光的研究中,涉及声学,光学,化学,量子物理,热学与统 计物理等基础理论以及实验技术等,对于大学物理系高年级学生或研究生参加这个课题的研究等于来 到实习所学知识的天然试验场.总之,声致发光现象的研究正期待更多更有意义的应用前景. 参考文献: [1]GREENLANDPT.Sonoluminescence[J].ContemporaryPhysics.1999. [2]YOUNGJB,eta1.Lineemissioninsirtgle—bubblesonoluminescence[J].Phys.Rev.Lett.,2001 .-4-----6--+---6--+---6-…--6---6-一+一+一--+一一--6----6----6-?.-4-----6---4-----6----6----6----6-"--6----6---6----6---4-_--6----6----6----6- 一+--4-- (上接第9页) (iii)考察g和,如果这两个共轭函数是闭的,则g是闭的,因此[g,D]是闭凸集. 设(,a)是中的元素,则 7=7+72?gl*(a)+g(a)?{inf{g(a)+g(a)la= a+aVa'?D,i=1,2}=g(0) 我们也有[g,D]. 这意味着[g,D],因[g,D]是闭集, 为证明逆关系,我们考察元素(7,a)?[g',D'],7?g(a). 假设(7,a)T,a=a+aVa'?D,=1,2,如果令y=gl(a),72=7一gl(a),贝071+ 72=7,因(7,a)T,故 72=7一g(a)>g2(a) 因此 y?inf{gl(a)+g(a)fa=a+aVa'?D,i:1,2}:g(a) 因此,对所有(7,a)?[g,D]而(7,.a)T,有(7,a)=(g(a),a),这表示这些元素是[g, D]的边界点,因此,(y,a)?T导致[g,D],故T=[g,D]. 参考文献: [1]FENCHELW.OnConjugateConvexfunctions[J].Can.J.Math.,1949,(1):73—77. [2]KARLINS.AgeneralizationofBmwe~fixedpointtheorem[J].DukeMath.J.,1941,(8):4 57—459. [3]MANFREDWALK.TheoryofDualityinMathematicalProgramming[M].Jena,Germa n:DemocraticRepubhc,1989.41—54 [4]M阿佛里耳非线性规划一分析与方法(上册)[M].李元熹等译.上海:上海科学技 术出版社,1982.101—105.