第二章最优化-线性规划.

第二章线性规划2§2.1凸集与凸函数3凸集定义2.1.1设集合DRn,若对于任意点x,y∈D,及实数aa1,都有ax+(1-a)y∈D,则称集合D为凸集.常见的凸集:单点集{x},空集,整个欧式空间Rn,超平面H={x∈Rn|a1x1+a2x2+…anxn=b}，半空间H+={x∈Rn|a1x1+a2x2+…anxn≥b}，实心圆，实心球，实心长方体等都是凸集。4凸集从直观上看，没有凹入部分，或没有空洞的是凸集。几何解释为：集合D中任两点连线上的每一点仍在D中，则D为凸集。5凸集的例例2.1.2超球||x||≤r为凸集证明设x,y为超球中任意两点,≤a≤1,则有||ax+(1-a)y||≤a||x||+(1-a)||y||≤ar+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.6凸集的性质(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j∈J)是凸集,则它们的交集D={x|x∈Dj,j∈J}是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD={y|y=bx,x∈D}.7凸集的性质(iii)设D1,D2是凸集,则D1与D2的和集D1+D2={y|y=x+z,x∈D1,z∈D2}是凸集.注:和集与并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T|x∈R}表示x轴上的点,D2={(0,y)T|y∈R},表示y轴上的点.则D1∪D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集8推论凸集的线性组合是凸集.11,kii1kiiixx定义2.1.2设xi∈Rn,i=1,…,k,实数i0,则称为x1,x2,…,xk的凸组合.容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.两点的凸组合三点的凸组合多点的凸组合9极点定义2.1.3设D为凸集,x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得x=ay+(1-a)z则称x为D的极点.凸集极点凸集极点10极点例D={x∈Rn|||x||≤a}(a0),则||x||=a上的点均为极点证明:设||x||=a,若存在y,z∈D及a∈(0,1),使得x=ay+(1-a)z.则a2=||x||2≤a2||y||2+(1-a)2||z||2+2a(1-a)||y||||z||≤a2不等式取等号,必须||y||=||z||=a,容易证明y=z=x,根据定义可知,x为极点.11凸函数定义2.1.4设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,及任意的a∈[0,1]都有f(ax+(1-a)y)≤af(x)+(1-a)f(y)则称函数f(x)为凸集D上的凸函数.12凸函数定义2.1.5设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,x≠y,及任意的a∈(0,1)都有f(ax+(1-a)y)af(x)+(1-a)f(y)则称函数f(x)为凸集D上的严格凸函数.将上述定义中的不等式反向,可以得到凹函数和严格凹函数的定义.13凸函数的例例2.1.3设f(x)=(x–1)2,试证明f(x)在(–∞,+∞)上是严格凸函数.证明:设x,y∈R,且x≠y,a(0,1)都有f(ax+(1-a)y)-(af(x)+(1-a)f(y))=(ax+(1-a)y-1)2-a(x-1)2-(1-a)(y-1)2=–a(1-a)(x-y)20因此f(x)在(–∞,+∞)上是严格凸函数.14凸函数的几何性质对一元函数f(x),在几何上af(x1)+(1-a)f(x2)(0≤a≤1)表示连接(x1,f(x1)),(x2,f(x2))的线段,f(ax1+(1-a)x2)表示在点ax1+(1-a)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一结论对于多元函数也是成立的,而且是充要条件,即有下面的定理.15凸函数的性质(i)设f(x)是凸集DRn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数.(ii)设f1(x),f2(x)是凸集DRn上的凸函数,实数m0,则f1(x)+mf2(x)也是D上的凸函数.(iii)设f(x)是凸集DRn上的凸函数,b为实数,则水平集S(f,b)={x|x∈D,f(x)≤b}是凸集.下面的图形给出了凸函数f(x,y)=x4+3x2+y4+y2+xy的等值线(f(x,y)=2,4,6,8,10,12)的图形.可以看出水平集为凸集.16凸函数的性质-1.5-1-0.500.511.5-2-101217凸函数的判断定理2.1.1设f(x)定义在凸集DRn上,x,y∈D.令F(t)=f(tx+(1-t)y),t∈[0,1],则该定理的几何意义是:凸函数上任意两点之间的部分是一段向下凸的弧线.(i)f(x)是凸集D上的凸函数的充要条件是对任意的x,y∈D,一元函数F(t)为[0,1]上的凸函数.(ii)f(x)是凸集D上的严格凸函数的充要条件是对任意的x,y∈D(x≠y),一元函数F(t)为[0,1]上的严格凸函数.18凸函数的判断19一阶条件定理2.1.2(一阶条件)设在凸集DRn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y∈D,都有f(y)≥f(x)+f(x)T(y-x)定理2.1.3(一阶条件)设在凸集DRn上f(x)可微,则f(x)在D上为严格凸函数的充要条件是对任意的x,y∈D,x≠y,都有f(y)f(x)+f(x)T(y-x)20二阶条件设在开凸集DRn上f(x)可微,则(i)f(x)是D内的凸函数的充要条件为,在D内任一点x处,f(x)的Hesse矩阵G(x)半正定,其中22221211222222122222212()()nnnnnfffxxxxxfffGxfxxxxxxfffxxxxx(ii)若在D内G(x)正定,则f(x)在D内是严格凸函数.21凸规划定义2.1.6设DRn为凸集,则f(x)为D上的凸函数,则称规划问题minf(x)s.t.x∈D为凸规划问题.定理2.1.5(i)凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.(ii)若f(x)是DRn上的严格凸函数,且凸规划问题minf(x)s.t.x∈D的整体极小点存在,则整体极小点唯一.22§2.2线性规划的标准型与基本概念23线性规划的一般形式min(max)c1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxn≥(或≤,=)b1a21x1+a22x2+···+a2nxn(或≤,=)b2······am1x1+am2x2+···+amnxn(或≤,=)bmx1,x2,···,xn≥024线性规划的标准型minc1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2······am1x1+am2x2+···+amnxn=bmx1,x2,···,xn≥0其中bi≥0.在标准形式中目标函数一律改为最大化或最小化，此处我们统一为最小化，约束条件（非负约束条件除外）一律化成等式，且要求其右端项大于等于零。25矩阵-向量形式的标准型mincTx(LP)s.t.Ax=bx≥0其中c=(c1,c2,···,cn)T,x=(x1,x2,···,xn)T,b=(b1,b2,···,bm)T111212122212nnmmmnaaaaaaAaaac:价格向量A:约束矩阵b:右端向量26矩阵-向量形式的标准型记A=(p1,p2,···,pn),其中pj=(a1j,a2j,···,amj)T,线性规划(LP)又可以表示为1012min()..,,,,TnjjjjcxLPstxpbxjn27线性规划解的情况满足约束条件的向量x是可行解,全体可行解构成可行域D.D≠F时但目标函数无下界时,称线性规划(LP)无界或无最优解;D=F时,称线性规划无可行解;D≠F时若目标函数有下界,可以证明线性规划(LP)必有最优解.28可行域为凸集定理2.2.1线性规划问题mincTx(LP)s.t.Ax=bx≥0的可行域D为凸集.证明任取x,y∈D,则有Ax=b,x≥0,Ay=b,y≥0对任意的a∈[0,1],设z=ax+(1-a)y,则z≥0,且Az=A(ax+(1-a)y)=aAx+(1-a)Ay=ab+(1-a)b=b因此z∈DD为凸集.29一般形式转化为标准型(i)极大极小maxf(x)min–f(x)(ii)若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量——称为松弛变量，将不等式改为等式。如1231234238238xxxxxxx(iii)若约束条件是大于等于型，则在该约束条件不等式左边减去一个新变量——称为剩余变量，将不等式改为等式。如1231234238238xxxxxxx30一般形式转化为标准型(iv)若某个约束方程右端项，则在约束方程两端乘以（-1），不等号改变方向，然后再将不等式化为等式。0ib(v)若变量xj无非负约束，则引入非负变量xj’≥0,xj’’≥0,令xj=xj’-xj”.31例将线性规划miny=2x1-x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1-x2+2x3=5x1,x2≥0,x3是自由变量化为标准型解:令x3=x3’-x3’’,得到标准型miny=2x1-x2-3x3’+3x3’’s.t.x1+x2+x3’-x3’’+x4=7x1-x2+x3’-x3’’-x5=2-3x1-x2+2x3’-2x3’’=5x1,x2,x3’,x3’’,x4,x5≥032例将线性规划maxy=250x1+350x2s.t.5x1+6x2≥2508x1+6x2≤30010x1+20x2=-700x1≥0,x2≤0化为标准型解:令x2’=-x2,得到标准型min-y=-250x1+350x2’s.t.5x1-6x2’-x3=2508x1-6x2’+x4=300-10x1+20x2’=700x1≥0,x2’≥0,x3≥0,x4≥033基本概念设约束矩阵A的秩为m(行满秩),且m≤n,则A中必存在m阶非奇异子阵B,不妨设B=(p1,p2,···,pm)称B为线性规划问题(LP)的一个基矩阵,或称为基,基矩阵中的列向量称为基向量,对应的决策变量称为基变量,其余变量称为非基变量.34基本概念在约束方程组取定基矩阵B=(p1,p2,···,pm)之后,令非基变量均为0,得到的方程组p1x1+p2x2+···+pmxm=b有唯一解,这样得到约束方程组的一个解向量x=(x1,x2,···xm)T通过这种方法得到的满足约束方程组的解称为基矩阵B对应的基解.35基本概念如果基解又满足非负条件,则称之为基可行解.此时的基B称为可行基.基可行解中非零分量的个数不会超过m,若基可行解中非零分量的个数恰为m,称此基可行解为非退化的基可行解,否则称为退化的基可行解.若一个线性规划的所有基可行解都是非退化的,称此线性规划是非退化的.mnC线性规划(LP)的基解个数不会超过36例考虑线性规划min2x1-x2s.t.x1+x2+x3=5-x1-x2+x4=02x1+2x2+x5=22x1,x2,x3,x4,x5≥0该线性规划有5个变量,3个约束,最多个基解.事实上,该线性规划只有7个基解(p1,p2线性相关)下面列出7个基解及对应的基(p1,p3,p4),(11,0,-6,11,0)T不可行(p1,p3,p5),(0,0,5,0,22)T退化(p1,p4,p5),(5,0,0,5,12)T非退化(p2,p3,p4),(0,11,-6,11,0)T不可行(p2,p3,p5),(0,0,5,0,22)T退化(p2,p4,p5),(0,5,0,5,12)T非退化(p