凸函数与凸规划

凸函数与凸规划单变量凸函数在讨论一般线性空间上的凸函数以前，先在这节中讨论区间上的单变量凸函数.设Rba),(为实数轴上的开区间，.ba函数Rbaf),(:称为),(ba上的凸函数，如果].1,0[),,(,),()1()())1((212121baxxxfxfxxf(2.1.1)如果不等号是严格的，则称f在),(ba上是严格凸函数.如果g在),(ba上是凸函数，则称g在),(ba上是凹函数.此外，(2.1.1)等价于,)()(11niiiniiixfxf.1],1,0[,,),,(,,111niinnbaxx命题2.1.1f为),(ba上的凸函数等价于下列条件的任何一个：i)),,(,),,(,211221xxxxxbaxx,)()()()(2211xxxfxfxxxfxf(2.1.2)即左差商不大于右差商.ii)),,(,),,(,211221xxxxxbaxx,)()()()(121211xxxfxfxxxfxf(2.1.3)即右差商当自变量差分减小时是不增的.iii)),,(,),,(,211221xxxxxbaxx,)()()()(222121xxxfxfxxxfxf(2.1.4)即左差商当自变量差分减小时是不减的.iv),,)()(),(yxyxyfxfyxF作为x或y的函数，在),(ba上不减.证明设,)1(21xxx则(2.1.2)等价于,))(1()()()()()(122211xxxfxfxxxfxf即).()()1())1(()(2121xfxfxxfxf(2.1.3)、(2.1.4)的证明类似，iv)只是i)~iii)的统一叙述.命题2.1.2设f为),(ba上的凸函数，则f在),(ba上处处左、右可导，从而处处连续.其左、右导数f、f满足：,),,(,2121xxbaxx).()()()()()(22121211xfxfxxxfxfxfxf(2.1.5)证明事实上，由(2.1.2)与(2.1.3)可知，当12xxx时，有.)()()()(inf)()(lim)(121222222222xxxfxfxxxfxfxxxfxfxfxxxxxx(2.1.6)同样，由(2.1.2)与(2.1.4)可知，当21xxx时，有.)()()()(sup)()(lim)(121211111111xxxfxfxxxfxfxxxfxfxfxxxxxx(2.1.7)由1x、2x的任意性，(2.1.6)和(2.1.7)同时也指出了f在),(ba中处处左、右可导.再由(2.1.2)—(2.1.4)易证，当21xx时，有下式成立：).()()()(;)()()()(111212121222xfxfxxxfxfxxxfxfxfxf命题2.1.2的逆也成立，其证明需要下面推广的中值定理：引理2.1.3设),(ba上的连续函数f处处有右导数.f则).(sup)()()(inf2),(1212),(2121xfxxxfxfxfxxxxxx定理2.1.4f是),(ba上的凸函数的充要条件为f在),(ba处处左、右可导，且满足),,(,2121xxxx,21xx).()()()()()(22121211xfxfxxxfxfxfxf(2.1.5)证明必要性就是命题2.1.2，充分性则由条件(2.1.5)和引理2.1.3立刻得到.推论1若f在),(ba上可导，则f是),(ba上的凸函数的充要条件为)(xf在),(ba上不减.推论2若f在),(ba上二阶可导，则f是),(ba上的凸函数的充要条件为,0)(xf).,(bax推论3若f是),(ba上的凸函数，则f在),(ba上不可导的点至多可数.证明因f是),(ba上的凸函数，故它在),(ba处处左、右可导.若f在),(,21baxx不可导，,21xx则由(2.1.5)式显见，开区间)),(),((11xfxf))(),((22xfxf不相交.在这样的开区间内任取一有理数，则由有理数可数推知这样的开区间至多可数，进而f在),(ba上不可导的点至多可数.注1将上面论证中的不等号“”改为严格不等号“”，即可相应地得到一系列有关严格凸函数的结果.注2直接用定义判断一个函数是否为凸函数通常是比较困难的，对于光滑函数，用定理2.1.4的推论1和2来判断则是相当简便的.在应用中，通常是用导数来肯定函数的凸性.反过来，它必定满足凸性不等式.利用这种办法，我们可以证明一些不太容易直接证明的不等式.例如：,xy当,1),0(x时，有.0)1(2xy由推论2，它是),0(上的凸函数.因此，下面的不等式成立：,)(1111nnnnxxxx.1],1,0[,,,0,,111nnnxx特别，取每个,1ni有,)(11nxxnxxnn.0,,1nxx推论3虽然凸函数除了至多可数个点以外，处处可导，但它的导数却可以在一个处处稠密集上不存在.例如，设}{nr为R上有理数的全体，,,2,1,0nn.1nn令,)(xrnnxg.Rx,)()(0xdttgxf.Rx由于g为递增函数，故f为凸函数.但f在所有有理点都不存在导数.由于这样的函数存在，我们一般无法讨论凸函数的二阶导数.然而，А.Д.Александров（1936）指出，凸函数几乎处处存在二阶逼近，即).[([)(!2)(~)(!1)()()(20200000xxoxxxfxxxfxfxf于是，也可以说，凸函数几乎处处有上式意义下的“二阶导数”).(~0xf在这一节的昀后，我们将函数的凸性与图像空间的凸集联系起来.设,),(:Rbaf称图像空间2R中的集合})(),,(:),{(:epi2yxfbaxRyxf为f的上图（epigraph）.命题2.1.5f在),(ba上凸等价于fepi是2R中的凸集.证明设f为),(ba上的凸函数，.epi),(),,(2211fyxyx则),,(,21baxx,)(11yxf.)(22yxf由(2.1.1)，)()()1())1((2121xfxfxxf],1,0[,)1(21yy即,epi))1(,)1((),(),)(1(21212211fyyxxyxyx],1,0[这表明fepi是凸集.反之，设fepi是凸集.对于任何),,(,21baxx显然有)),(,(11xfx))(,(22xfxfepi（fepi定义式中“”取到“”）.因此，],1,0[))()()1(,)1((2121xfxfxx)1())(,(11xfx))(,(22xfx.epif按fepi定义式，有)()()1())1((2121xfxfxxf，].1,0[即f为凸函数.命题2.1.6设f为),(ba上的凸函数，则),,(0bax,R使得).,(),()()(00baxxxxfxf证明因f在),(ba上凸，故fepi是凸集.由fepi和集合代数内部的定义可知，.)epi())(,(00ifxfx注意到,epi2Rf故.)epi(if于是可用凸集分离定理1.4.8，,),(*221R使得.)epi(),(),(020121ifyxxfxyx因y可以任意大，故只有.02进一步，还有.02事实上，假设,02则对,0.)epi())(,(00ifxfx将此代入上面的分离不等式得到,0)(0001xx这是不可能的.令,:21由上面的分离不等式得到.)epi(),(),()(00ifyxxxxfy令)(xfy得到).,(),()()(00baxxxxfxf由命题的证明可见，这里的就是凸集fepi在点))(,(00xfx处的承托直线的斜率.我们已经看到，),(ba上的凸函数f具有很好的分析性质：处处连续，处处左、右可导.那么，一个自然的问题是：在可导点和不可导点（一定是左、右导数存在，但不相等）会有什么样的统一性质？为此，我们给出“次微分”概念.集合)},(),()()(:{:)(000baxxxxfxfRxf称为f在),(0bax的次微分.如果,)(0xf则称f在0x处次可微，若),(0xf称为f在0x处的次梯度.命题2.1.6表明，对于),(ba上的凸函数f，它在),(ba上是处处次可微的.这就正面回答了我们刚才提出的问题.进一步，还有如下的结果：命题2.1.7设f是),(ba上的凸函数，则).,()],(),([)(0000baxxfxfxf证明先证“”：设)].(),([00xfxf当0xx时，由(2.1.5)有;)()()(000xfxxxfxf当0xx时，仍由(2.1.5)有,)()()(000xfxxxfxf综合起来就是),,(),()()(00baxxxxfxf即).(0xf再证“”：设).(0xf按定义，有).,(),()()(00baxxxxfxf当0xx时，由上式推出;)()(00xxxfxf当0xx时，则推出.)()(00xxxfxf对这两个不等式分别取右、左极限得到)(0xf和,)(0xf即)].(),([00xfxf命题2.1.7说明，次微分概念可以作为导数概念的推广.事实上，若凸函数f在0x处可导，则)(0xf为单元集)},({0xf其次梯度就是通常的导数，否则)(0xf是一个“真正的”闭区间)].(),([00xfxf后面，我们要将这一概念推广到一般情形.昀后，我们还要指出，(2.1.1)也可以作为闭区间],[ba上的凸函数的定义.这时，在],[ba的内部),(ba上，前面的所有结论都保持不变；但在端点，凸函数不但可以没有单侧导数，甚至可以不连续.不过，凸函数的不连续不会“太不连续”，容易证明，它一定在端点上半连续，即满足),()(suplimafxfax).()(suplimbfxfbx线性空间上的凸函数这一节讨论线性空间上的凸函数.由于线性空间只有代数结构，我们不能在其中讨论收敛性及与其相关的凸函数的连续性和可微性，因而上一节中有关单变量凸函数的大部分性质都只能在引进拓扑结构后的线性空间（即下一章的拓扑线性空间）中才能推广.本节所论及的只是凸函数的“代数性质”.设K为线性空间X中的一个凸集.我们可以用两种办法定义函数RKf:的凸性.直接定义：如果,,21Kxx],1,0[).()()1())1((2121xfxfxxf(2.2.1)则称f是K上的凸函数.间接定义：称f是K上的凸函数，如果,,21Kxx))(()(121xxtxftg是]1,0[上的凸函数.同上一节类似，可以定义严格凸函数和凹函数.并且(2.2.1)也等价于更一般的不等式：,,,1Kxxn],1,0[,,1n,11nii.)()(11niniiiiixfxf(2.2.2)线性空间上的凸函数同样联系着图像空间RX的一个凸集，为此，依然引进“上图”的概念：集合})(,:),{(:epi