1、最优化理论与算法2，凸分析与凸函数2.凸集与凸函数2.1 凸集与锥凸集与锥(1)(2)(1)(2)(1)(2)(1)(2),0,1,2.1 (1-)(1-)nSnxxSxxSSxxxDfx设 为 维欧氏空间中的一个集合。若对任意两点及每个实数有则称 为。称为和的凸集凸组合。2.凸集与凸函数-,:2.1TTTTTHx p xpnpHx p xHx p xHx p xHx p x 为凸集，其中 为 维列向量，为实数。此外 下面相对于法向量 的半空间都是凸集 正的闭半空间 负的闭半空间正的开半空间 负的开半空平面间例超2.凸集与凸函数x0 xx-x0px0 xx-x0p(0)(0)02.2 Lx x
2、xddx 集合，为凸集，其中 为给定的例非零向量，为定点。(0)(0),0Lx xxdx 集合称为,为射线射线的顶点2.凸集与凸函数11111,.,1,1,.,.,.,2.2mmniimimmmxxR imxxxxDf 给定 个向量以及满足的非负实数称向量 为的 凸组合.11111,2,.,.,.,1,0,1,.,2.1.nmnmmmiiiSSmxxxxR ihSmT +集合是凸集,当且仅当 包含其中任意有限个元素的凸组合,即对任意的有其中运用定义不难验证如下命题：2.凸集与凸函数n12SSE2,1,.设 和为中两个凸集是题实数命则11S x xS 1,为凸集。122SS，为凸集12123SS
3、SS(1)(2)(1)(2)，=x+xx,x为凸集12124SSSS(1)(2)(1)(2)，=x-xx,x为凸集,2.3.nC TDfconv TCTTC 集合的是指所有包含 的凸集的交集 记为 凸包为凸集 2.凸集与凸函数0101,.,.,mnmixxxxxxmx 有限点集的凸包称为。若,仿射无关时，对应的凸包称为。向量 称为该单多胞形维单纯形纯形的顶点。多面体多面体(polyhedral set)是有限闭半空间的交.(可表为 Axb).x4x3x2x1x5xy2.凸集与凸函数,.2.4nCxCxCCCDfC 设有集合若对每一点当 取任何非负数时，都有称 为又若 为凸集，则称 为锥凸锥ii
4、,.,0,i1,2,.,23.k (1)(2)(k)k(i)i=1，向量集的所有非负线性组合构成的集合例.为凸锥。2.2S n若集合S为凸集，则它的闭包命题也是凸集。多面集 x|Ax0也是凸锥，称为多面锥多面锥。2.凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)=x|0,xS是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间约定约定:非空集合非空集合S生成的凸锥生成的凸锥,是指可以表示成是指可以表示成S中有限中有限个元素的非负线性组合个元素的非负线性组合(称为凸锥组合称为凸锥组合)的所有点所构成的所有点所
5、构成的集合的集合,记为记为coneS.若若S凸凸,则则coneS=K(S)02.凸集与凸函数Df 2.5 非空凸集中的点 x 称为极点极点,若 x=x1+(1-)x2,(0,1),x1,x2 S,则 x=x1=x2.换言之,x不能表示成S中两个不同点的凸组合.x4x3x2x1x5xySx由上可知,任何有界凸集中任一点都可表成极点的凸组合.2.凸集与凸函数Def 2.6.设非空凸集SRn,Rn中向量d 0 称为S的一个一个回收方回收方向向(方向方向),若对每一 xS,R(x.d)=x+d|0 S.S的所有方向构成的尖锥称为S的回收锥,记为0+S 方向d1和d2 称为S的两个不同的方向不同的方向,
6、若对任意0,都有 d1d2；方向d称为S的极方向extreme direction,若 d=d1+(1-)d2,(0,1),d1,d2 是S的两个方向,则有 d=d1=d2.换言之d不能表成它的两个不同方向的凸锥组合x0 x0ddd2.凸集与凸函数1221TTT S(x,x)x|x|(0,1)45(1,1)(1,1)2 4集合凡是与向量夹角的向量都是它的方向。，是其仅有的例.两个极方向Sx Axb,x0,d,dS2d0A0.5d 设是非零向量。证明 是 的方向且例.(Th23P 若多面体 的极点 极方向)存在的话,则极点(极方向)的数目一.定有限.2.凸集与凸函数 表示定理表示定理Th2.4
7、若多面体若多面体P=xRn|Axb,r(A)=n则则:(1)P的极点集是非空的有限集合的极点集是非空的有限集合,记为记为x kkK则则j(2)记记P的极方向集为的极方向集为d jJ(约定约定P不存在极方向时不存在极方向时J=)|1,0,0,kjkjkjk Kj Jnkkjk KPconv xkKcone djJxxdxkKjJ (3)指标集指标集J是空集当且仅当是空集当且仅当P是有界集合是有界集合,即多胞形即多胞形.2.凸集与凸函数表示定理直观描述表示定理直观描述:设 X 为非空多面体.则存在有限个极点 x1,xk,k0.进一步,存在有限个极方向 d1,dl,l0 当且仅当 X 无界.进而,x
8、X 的充要条件是 x 可以表为 x1,xk 的凸组合和d1,dl的非负线性组合(凸锥组合).xyx1x2x3d1d20推论推论2.1 若多面体若多面体S=x|Ax=b,x0非空非空,则则S必有极点必有极点.2.2 凸集分离定理凸集分离定理2.凸集与凸函数121212121212121212,.,()2.7|,0,nTTTTSSHx p xxSp xxSp xHSSSSHHSSSHSHHSSSHx p xSHHSDfS ，设 和是中两个非空集合，为超平面。若对有，分对于有（或情形恰好相反），则称超平面集合和若则称 正常分离 和。若则称严格分离 和。若则称分离和离强。2.凸集与凸函数(),0,()
9、0()0()08,2.nnTTTSppDxSSHx pxxSHx pxxHx pxxSxSSfHHx ，设，若或者则称 是 在 处的，若则称 为 在 处的支撑超平面正常支撑超平面。nx SSES,Th2.5infx设 为中的闭凸集，yS,则存在唯一的点x使得 y-xy-dist,)2.9inf (2.4)nx SDfSy Sxn设非空，y,则点y与集合S之间的距离dist(y,S)定义为（y-证明：令2.凸集与凸函数(k)(k)(k)x,xS,yxr.于是,由下确界定义知,存在序列使得x Sinfxr0y-22(k)(m)(k)(m)222(k)(m)(k)(m)xx(xy)(xy)2 xy2
10、 xy(xy)(xy)(k)(k)xxS.x先证存在极限只须证为柯西数列。所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.凸集与凸函数2(k)(m)22(k)(m)22(k)(m)222(k)2(m)2(xx)2 xy2 xy4y22 xy2 xy4r2(xyr)2(xyr)0(k,m)下证明唯一性2.凸集与凸函数xS,xyxyr.1S2111xyxyr,222111rxyxyr222yx(yx)|yx|yx|11,yS,设有由 为凸集，有（x+x）S,由 Schwartz 不等式y-（x+x）再由 的定义y-（x+x）因否则导出矛盾。2.凸集与凸函数TTTTTTSyS,Hx|p
11、 xHyp y,p xxS.p yyS p yp x,xS.设 为闭凸集，为超平面。分离点若则，令，则 与 分离可表为2.7(),00,nTTThSySpxSp yp x 设为中的闭凸集，则存在及实数，使得对点有。2.6.,(2.4)(-)()0nTThSySxSy xxx设的非空闭凸集，则点为极小化问题的最优解当且仅当2.凸集与凸函数xpX(i)(x-)(y-)0 对任意 xX.(ii)令 p=y-，=p p.Txxxyx 证明提纲x SxS,|y-x|=inf|y-x|由此可得2.凸集与凸函数222222(1)xx()x(1)x,yxy(x(1)x)yx(xx)yxxx2(yx)(xx)在
12、连线如图 上取一点则2xx2(yx)(xx)002(yx)(xx)0(yx)(xx)0，则 即 2.凸集与凸函数 Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理TTTT2p(yx)p(yxxx)p(yx)p(xx)=(yx)(xx)（）nTT2.1CS,p y0p x推论设 为中的非空闭凸锥集，yC,则存在p(0)使得证明2.凸集与凸函数nTTTh2.8 S()clS,p yp x 设为中的凸集，yS,则存在p0，使得对点x有。jjjjj(k)(k)(k)(k)(k)(k)T(k)(k)T(k)(k)(k)(
13、k)(k)TT(k)TTjySy,yclSyy.y2.7,p,xclS,pypx.pp,p.pypx,xclS.xclSk,p yp x,xclS 使得对每一，由定理存在单位向量使得成立因为序列有界，存在收敛子列其极限为单位向量 显然固定，令得。推论2.2：设S为Rn 中的非空集合，yS,则存在非零向量p，使对xclS,pT(x-y)02.凸集与凸函数n1212TT1212Th2.9.S,S()SSinf p x xS Supp x xSSS+-设为中的凸集,=,则存在p0使 (换言之，存在超平面H,使得H,H)。21(2)(1)(1)(2)12SSS z zxx,xS,xS证明：令2.凸集与
14、凸函数12T(1)T(2)(1)(2)12SSS8 p xp x,xS,xS12T由于 和是非空凸集，因此 是非空凸集。由于SS=,则零元素0S。根据定理2.的推论，存在非零向量p，使得对每一个zS，成立p z0，即2.凸集与凸函数1211212122.10.,(),00inf nTTThS SSSSHSSpp x xSSup p x xS 设中的闭凸集有界，则存在超平面 强分离 和，即存在，使 21SSS 12证明提纲：令，则S是非空的凸集，SS=0S。先证S是闭集，再根据Th2.7立明 作为凸集分离定理的应用，下面介绍两个择一定理：Farkas定理和Gordan定理，它们在最优化理论中是很
15、有用的。2.凸集与凸函数2.3 择一定理择一定理2.1100,0.TTFarkasAmncnAxc xA yc y定理（定理）设 为矩阵，为 维向量，则，有解的充要条件是，无解2.凸集与凸函数 0000,00 1 1 (2)0 00200TTTTTTTTTAxc xxAxc xA yc yyA ycxy Axc xyAxy Axc xc x证明：先证必要性。设，有解，即存在，使且。现在证明无解。用反证法。设存在，使（）将（）式两端转置，并右乘，得到由于，因此，从而由（）得到与的假设矛盾。2.凸集与凸函数,000,0(3)2.70,(4)045TTTTTTTA yc yAxc xSz zA y
16、yScSxzSx cx zsx cx z 再证充分性。设无解，证明，有解。令 则 为闭凸集。由假设，根据定理，存在非零向量 及数，使得对每一点成立 由于，根据（），必有 （）TTTTS c xy Ax(6)6c x0(7)c x6(7)(8)T上式两端转置，并考虑到集合 的定义，有在式（）中，令y=0，得到 由于为某个确定的数，y0，y的分量可取得任意大，因此由（）又可得出 Ax0(8)由和知非零向量x是Ax0，c x0的解。2.凸集与凸函数2.凸集与凸函数2.11A00m nnnTAcAxxc x 定理（Farkas置换定理）设，则c为 的行向量的凸锥组合，即cconeA对任意满足的向量，都
17、有。T 设A为m n矩阵，那么，Ax0有解的充要条件是不存在非零向量y0，使A y=0.2.12 定理（Gordan定理）0,0,0.TmTGaleAmnbmAxbA wwwb w推论（置换定理）设 为矩阵，为 维向量，则线性系统有解对任意满足，的向量都有2.凸集与凸函数 0TTTT证明:先证必要性。设Ax0有解，即存在x，使Ax0，我们来证明不存在非零向量y0,使A y=0。设某个非零向量y，使A y=0，即 y A=0（1）上式两端右乘x得到y Ax（2）在式（2）中，由假设Ax0，因此y的诸分量不可能全为非负数，即y0不成立。2.凸集与凸函数 (3)(4)TTn12再证充分性。设不存在非
18、零向量y0，使A y=0，来证明Ax0有解。我们来证明它的等价命题，即证若Ax0无解，则存在非零向量y0，使A y=0。设Ax0无解。令 S=zz=Ax,xE以及S=zz0TTT2.8 y Axy z(5)y z0z0,y0 12n2由于Ax0无解，因此SS。根据定理，存在非零向量y，使得对所有xE 及zS，成立特别地，当x=0时有（6）由于它的分量可取任何负数，因此由式（6）知（7）2.凸集与凸函数T(5)0,y Ax0(8)x0 y=0 nTTTT在式中，令z得到对每个xE 均有令A y,代入(8),则-A y，因此A（9）由式（7）和（9）可知存在非零向量y0，使A y=0。2.凸集与凸
19、函数2.凸集与凸函数2.4 2.4 凸函数凸函数Df2.10 设SRn是非空凸集,函数f:SR,若对任意x1,x2S,和每一(0,1)都有 f(x1+(1-)x2)f(x1)+(1-)f(x2)则称f是S上的凸函数凸函数.若上面的不等式对于xy严格成立,则称f是S上的严格凸函数严格凸函数.若-f是S上的凸函数,则称f是S上的凹函数凹函数.若-f是S上的严格凸函数,则称f是S上的严格凹函数严格凹函数.2.4.1 基本性质基本性质2.2.凸集与凸函数Th2.13 设 f 是一凸函数，则对任意的xRn 和d(0)Rn，f在x处沿方向d的方向导数存在。2.凸集与凸函数21111122211222121
20、20,()()()()()(1)()(1)()()()()()fgf xdgf xdfxdxf xdf xf xdf xf xdf x 证：令是凸函数，故即2.凸集与凸函数1212()(0)()(0)()()()(0)()0(),0,0,(0)()()()ggggf xdf xggGggggg 即 由此知差商是的非减函数，又也是凸的 对有2.凸集与凸函数0()()()(0)()0()()()()liminf(,)og ogggGf xdf xf xdf xDf x d 即由此知在有下界，从而极限存在，且从而存在命题2.3 设f是定义在凸集S上的凸函数，则(1)所有凸函数f的集合关于凸锥组合运算
21、是封闭的,即(a)实数0，则f也是定义在S上的凸函数(b)设f1和f2是定义在凸集S上的凸函数，则f1+f2也是定义在S上的凸函数2.凸集与凸函数(2)函数f在开集intS内是连续的.(3)函数f的水平集L(f,)=x|xS,f(x),R 和上镜图epi(f)=(x,y)|xS,yR,yf(x)都是凸集2.2.凸集与凸函数设设S 为为Rn中的非空凸集中的非空凸集,则则 f(x)是凸的当且仅当上镜图是凸的当且仅当上镜图 epif=(x,y)|xS,yR,yf(x)是凸集是凸集 对上镜图事实上我们有如下定理112212112212121212121122121120 1111111fx yxyep
22、ifx xS yf xyf xyyf xf xfxxxxyyx yxyepifepifx xSxf xx 证明设 凸 则对有对是凸集 取则:),(,),(,),(),().(,)()()()()(),(),()(,)()(,),(,(),(,211221212 0 11 11f xepi fxf xxf xepi ff xf xfxx 则对从而()(,),(,()()(,(),()()()().2.凸集与凸函数定理2.14 设SRn为一非空凸集，f是定义在S上的凸函数，则f在S上的局部极小点是整体极小点，且极小点的集合为凸集。2.凸集与凸函数xxN(x)x|xx,0 xSN(x),f(x)f(
23、x)证明：设 是f在S上的局部极小点，则存在 的 邻域使得对每个成立2.凸集与凸函数()().01(1,(1)()(1)()(1)(1()xxSf xf xxxSfxxf xxf xxxxSNxxf 反证法，若 不是整体极小点，则存在于是，)f()f(x*)+f(x*)(x-x*),任意 xS.:(1)01(1)()(1)(),01,(+()(x)()()ffy-xf y-f xf xyxff yf x 证明必要性:设 是凸函数，于是对，有 因此 对l2.4.2 凸函数的判别凸函数的判别2.凸集与凸函数1212T11T22T12121(1)()()+()(),()()+()(),()+(1)(
24、)()+()(1),()(+(1:x,xS,xxx,f xf xf xx-xf xf xf xx-xf xf xf xf xxx-xf xfx充分性 任取令则 于是2-)xT0(x)()()(),fy-xf yf x 令得 2.凸集与凸函数Th 2.16*.设S 是 Rn a上的非空开凸集,f(x)为 S 到 R上的可微函上的可微函数数.则 f(x)是凸函数当且仅当任意的 x1,x2 S,有 (f(x2)-f(x1)(x2-x1)0.类似的,f 严格凸当且仅当对任意相异的 x1,x2 S,(f(x2)-f(x1)(x2-x1)0.1212212211212121:),()()()(-)()()
25、()(-)()-()(-)0TTTfx xSf xf xf xxxf xf xf xxxf xf xxx证设凸我们有相加得1221211211121121),()()()(-),(*)(1-),(0,1).()-()(-)0,(1-)()-()(-)0 ()-()(-)0.(*),TTTTx xSf xf xf xxxxxxf xf xx xf xf xxxf xf xxx 让由中值定理其中 由假设 即有 由21121 ()()()(-),2.16,Tf xf xf xxxThf有由凸2.凸集与凸函数2.凸集与凸函数Def 2.11.设 S 是Rn 上的非空开集,f(x)f(x):SR 的函数
26、 则 f(x)在点x*int(S)称为二次可微的,若存在向量f(x*),和 nn(Hessian)矩阵 H(x*),及函数:Rn R 使得对所有的 xS,f(x)=f(x*)+f(x*)(x-x*)+0.5(x-x*)H(x*)(x-x*)+|x-x*|(x-x*)其中 lim (x-x*)=0.2x*x*xx*Th 2.17 设S 是 Rn a上的非空开凸集,f(x)为 S 到 R上的二次可上的二次可微函数微函数.则(1)f(x)是凸函数当且仅当S上每一点的Hessian矩阵是半正定的.(2)f(x)是严格凸函数当且仅当S上每一点的Hessian矩阵是正定的.凸规划2.凸集与凸函数ijijij min f(x)s.t.g(x)0,i1,2,.,m h(x)0,j1,2,.,lf(x)g(x)(x)g(x)0,i1,2,.,m h(x)0,j1,2,.,l是凸函数，是凹函数，h是线性函数。可行域S=x
