线性规划 凸集凸函数

线性规划凸集和凸函数凸集和凸函数在非线性规划的理论中具有重要作用，下面给出凸集和凸函数的一些基本知识。定义1设，若对D中任意两点与，连接与的线段仍属于D；换言之，对，∈D，∈[0,1]恒有+(1-)∈D则称D为凸集。+(1-)称为和的凸组合。nRD)1(x)2(x)1(x)2(x)1(x)2(xa)1(xa)2(xa)1(xaa)2(x)1(x)2(x例(i)超平面为凸集。{}b==xPxTH定义为(ii)半空间为凸集。{}b=-xPxTH定义为{}(iii)射线为凸集，其中d为给定的非零向量，为定点。0,)0(+==lldxxxL)0(x(iv)超球是凸集。xr(v)欧式空间是凸集，规定空集是凸集nR凸集的性质有限个凸集的交集仍然是凸集。设是凸集，则是凸集。12,,,kDDD12kDDD设是凸集，则是凸集。D{|,}DyyxxDbb==凸集的和集仍然是凸集。设是凸集，则是凸集。12,DD1212{|,,}DDyyxzxDzD+==+推论：设是凸集，，则也是凸集，其中。iD1kiiiDb=iRb1,2,,ik=定义3极点（顶点）：设D是凸集,若D中的点x不能成为D中任何线段上的内点，则称x为凸集D的极点。设D为凸集，X∈D,若X不能用X(1)∈D,X(2)∈D两点的一个凸组合表示为X=αX(1)+(1-α)X(2),其中0α1，则称X为D的一个极点。kii=1=1定义2.凸组合：设X(1)，X(2)，…，X(k)是n维欧式空间中的k个点，若存在μ1,μ2,…,μk满足0≤μi≤1,(i=1,2,…,k),使X=μ1X(1)+μ2X(2)+…μkX(k)，则称X为X(1)，X(2)，…，X(k)的凸组合。多边形的顶点是凸集的极点（顶点）。圆周上的点都是凸集的极点（顶点）。定义4设D为R中非空凸集，若对，∈D，∈(0,1)恒有n)1(x)2(xaf[+(1-)]≤+(1-)f(*))1(xa)2(xa)()1(xfaa)()2(x则称为D上的凸函数；进一步，若≠时，(*)式仅〝〞成立,则称为D上严格凸函数。)(xf)1(x)2(x)(xf对凸的一元函数的几何意义为：在曲线上任取两点P1(x1,),P2(x2,)弦位于弧之上（见图）。)(xf)(1xf(x2)f21PP21PPx1x2x(x,y)p1p2)(xf凹函数，严格凹函数+(1-)-a)(1xfa)(2xf])1([21xxfaa-+=2221)1(xxaa-+221])1([xxaa-+-=2221)1(xxaa-+-])1(2)1([21222212xxxxaaaa-+-+=212221)1(2)1()1(xxxxaaaaaa---+-=(1-)aa)2(212221xxxx-+=(1-)aa(x1-x2)≥02∴+(1-)≥a)(1xfa)(2xf])1([21xxfaa-+所以，=x是R上凸函数。)(xf2例如，对=x，因x1,x2∈R，∈(0,1))(xfa2例：证明线性函数是上的凸函数。nR1122()Tnnfxcxcxcxcx==+++同理可证线性函数也是上的凹函数。()Tfxcx=nR凸函数的性质性质1设f1,f2为定义在凸集D上的凸函数，为非负实数，则f1,f1+f2也是D上凸函数。ll性质2设D是R中一个凸集，f是定义在D上的一个凸函数，则f在D的内部连续。n性质4：f(x)是凸集D上的凹函数的充要条件是-f(x)是D上的凸函数。性质3设D是中一个非空凸集，f是定义在D上的一个凸函数，则水平集是凸集。{}aa=)(,xxxfDDnRa)(xfx定理1：设f(x)定义在凸集D上，，令则,xyD()((1)),[0,1]tftxtyt=+-（i)f(x)是凸集D上的凸函数的充要条件是是[0，1]上的凸函数。（ii)设，若是[0，1]上的严格凸函数，则f(x)是凸集D上的严格凸函数。xy()t()t凸函数的判断n设函数存在一阶偏导数，x∈R，向量)(xf)(xf=Tnxfxfxf,,,21为在点x处的梯度。)(xf…定义设函数存在二阶偏导数，x∈R，则称矩阵)(xfn2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxfLLL为在点x处的Hesse矩阵。)(xf)(2xf=………)||(||21||)(||202000000popxfppxfxfpxfpopxfxfpxfTTT+++=+++=+多元函数Taylor展开：定理2(一阶条件）：设D是R中非空开凸集,是定义在D上的可微函数,则是凸函数的充要条件为x,y∈D,有n)(xf)(xf)(yf≥+(y-x))(xfT)(xf而是D上严格凸函数为x,y∈D,x≠y,上式仅〝〞成立。)(xfxf(x)定理3（二阶条件）：设D是R中非空开凸集,是定义在D上的二次可微函数,则是凸函数的充要条件为对x∈D,≥0,即Hesse矩阵半正定。n)(xf)(xf)(2xf)(2xf若x∈D,0，即Hesse矩阵正定，则为严格凸函数。)(2xf)(xf例：证明函数是上的凸函数。22212()Tnfxxxxxx==+++nR若规划===ljhmigtsfji,,2,1,0)(,,2,1,0)(..)(minxxx……中,和-为凸函数,是线性函数,则上述问题为求凸规划。)(xf)(xig)(xih定义6:凸规划设D为凸集,是定义在D上的凸函数，则称规划问题为凸规划。min()xDfx()fxnR凸规划是非线性规划中的一种重要特殊情形，它具有很好的性质。定理4：（1)凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。(2)如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。