最优化模型与算法——基于Python实现教案全套渐令ch01凸集合---ch06凸优化算法.docx

第一章凸集合1 .(1)证明一个集合是凸集当且仅当它与任意直线的交是凸的。(2)证明一个集合是仿射的，当且仅当它与任意直线的交是仿射的。两个点分别为A和B,即L=A,B°对于SL中的两个点C和D,我们需要证明连接C和D的线段上的所有点也属于SLo由于SL是直线L与集合S的交集，因此C和D必须同时属于L和S。由于S是凸集，连接A和B的线段上的点都属于S,换句话说，线段AB上的任意一点都属于S。由于C和D同时属于线段AB,所以连接C和D的线段上的点也都属于线段ABo因此，连接C和D的线段上的点既属于S又属于L,即它们属于SL。所以，SL是凸的。(必要性)假设集合S与任意直线的交都是凸的。我们需要证明S本身是凸的。假设S中的两个点E和F,我们需要证明连接E和F的线段上的所有点也属于Se考虑直线EF,由于S与直线EF的交集是凸的，所以连接E和F的线段上的点也都属于S。因此，S是凸的。综上所述，一个集合是凸集当且仅当它与任意直线的交是凸的。接下来，我们来证明一个集合是仿射的当且仅当它与任意直线的交是仿射的。(2)证明：(充分性)假设集合S是仿射集。我们需要证明，对于任意直线L与S的交集SL,SL也是仿射的。假设直线L的两个点分别为A和B,即L=A,B°对于SL中的任意两个点C和D,我们需要证明连接C和D的线段上的所有点以及C和D本身都属于SL由于SL是直线L与集合S的交集，因此C和D必须同时属于L和So由于S是仿射集，连接A和B的线段上的所有点以及A和B本身都属于S0由于C和D同时属于线段AB,因此连接C和D的线段上的所有点以及C和D本身也都属于线段AB。所以，连接C和D的线段上的所有点以及C和D本身都属于L和S,即它们属于SL因此，SL是仿射的。(必要性)假设集合S与任意直线的交都是仿射的。我们需要证明S本身是仿射的。假设S中的任意两个点E和F,我们需要证明连接E和F的线段上的所有点以及E和F本身都属于S。考虑直线EF,由于S与直线EF的交集是仿射的，所以连接E和F的线段上的所有点以及E和F本身都属于So因此，S是仿射的。综上所述，一个集合是仿射的当且仅当它与任意直线的交是仿射的。2 .(1)设C是R"中的凸集合，A是从R”到Ir的线性变换。证明：集合AC=AxxC是凸集合。(2)设。是R，”中的凸集合，A是从R到Rw的线性变换.证明：集合A-,D=xAxD是凸集合。(1)要证明集合AC=AxWC是凸集，我们需要证明对于任意两个元素AX和Ay属于AC,以及任意介于O和1之间的权重值t,tAx+(l-t)Ay也属于ACo设AX=A(Xl)和Ay=A(x2),其中xl和x2分别是集合C中的两个元素。根据C是凸集的定义，对于任意介于0和1之间的权重值t,txl+(l-t)x2也属于C。由于A是线性变换，我们有A(txl+(1-t)x2)=tA(xl)+(l-t)A(x2)=tAx+(l-t)Ayo因此，我们得出结论，tAx+(l-t)Ay属于AC。由此可见，集合AC对于任意的Ax和Ay,以及介于0和1之间的权重值t,满足凸集的定义。因此，集合AC=AxxC是凸集。(2)为了证明集合ATD=xAWD)是凸集，我们需要证明对于任意两个元素xl和x2属于,D,以及任意介于。和1之间的权重值t,t*xl+(l-及*x2也属于A'D。假设xl和x2属于A"D,即AXl和Ax2属于D。由于D是凸集，对于任意介于0和1之间的权重值t,t*Axl+(l-t)*Ax2也属于Do考虑Al(t*Axl+(l-t)Ax2)=A,(tAxl)+,(l-t)x2)=t,(xl)+(l-t)1(Ax2)=txl+(l-t)*x2因此，我们得出结论,t*xl+(l-t)*x2属于ATDo由此可见，集合ATD对于任意的xl和x2,以及介于。和1之间的权重值t,满足凸集的定义。因此，集合ATD=AxD是凸集。3 .两个平行的超平面xwR"X=伪和xwRI/x=%之间的距离是多少?对于平行的超平面xWRnax=b1l1WRnax=b2,其中a为法向量，b1和b为常数。两个平行超平面之间的距离可以通过计算其中一个超平面上的任意点到另一个超平面的垂直距离来得到。设超平面6Rra-x=b1)上的一点为x。，则它到超平面xR1a-x=b的垂直距离为：d=(ax(11b2)/a其中，aXcrbzl表示aX减去b2的绝对值，Ilall表示a的EUClidearI范数(即向量a的长度)。因此两个平行超平面(xRnarx=b1和(xRnlax=b2之间的距离为d=(a0-b2)a|,其中X。是其中一个超平面上的任意点。4 .给定向量IV,i,其中/是有限或无限的指标集。证明：集合K=(xR,(x,)OZ)是凸锥，并写出K的极锥Ko要证明集合K=WRn,b<O,ViI是凸锥，我们需要满足以下两个条件：对于任意的Xi和X2B于K,以及任意的非负权重值J和(2，都有tiXi+jx痈于Ko对于任意的X属于K,以及任意的非负标量t,都有tx属于K。首先，考虑条件1。对于任意的Xi和X弱于K,并且对于任意的非负权重值J和t2,我们有:t1x1+t2x2,b=t1xb+t2x2.b由于x1,b<O且x2>b<0,我们可以得出:txhb+t2x2,b<0因此，t1X1+t2xJ国于Ko接下来，考虑条件2。对于任意的X属于K,并且对于任意的非负标量t,我们有：tx,b)=tx,b由于x,b<O,我们可以得出：tx,b)<0因此，tx属于K。综上所述，集合K=xRr合x,b<O,iI是一个凸锥。接下来，我们来描述K的极锥。极锥由满足以下条件的向量X构成：1. (x,bO,其中b是给定的向量。2. x,b=0的充分必要条件是X是K的边界点。因此，K的极锥由满足条件x,bWO的向量X构成，并且当x,b=O时，X为K的边界点。5 .证明：概率单纯形尸=<(P,Pk)Kgpk=l,Pk2。卜是凸集合。要证明概率单纯形P=(PlP,p)Rngpk=l,pk>O)是凸集合，我们需要满足以下条件：对于任意的P,q属于P，以及任意的非负权重值I和5，都有tp+lzQ属于P。对于任意的P属于P,以及任意的非负标量t,都有Ip属于P。首先，考虑条件1。对于任意的P=(Pi,P2»,P)和q=(q,Q2,q)属于P，以及任意的非负权重值J和t2,我们有：(t1pk+t2qk)=t1pk+t2qk=t1+tz=l因此，tP+lzq属于P。接下来，考虑条件2。对于任意的P=(Pi,p2,p)属于P,以及任意的非负标量t,我们有：tPk=tPk=t因此，tp属于P。综上所述，我们证明了概率单纯形P=(pi,p2,p)ERnEpk=l,Pk>0是凸集合。6 .证明如果航和S?是IVIX中的凸集，那么它们的部分和(1.6. 2)S=(x,J+y2)xeR,yy2Rn,(x,ji)Si,(x,j2)S2也是凸的。要证明如果Sl和S混Rn中的凸集，那么它们的部分和S=(x,yd-y2)xRn,yby2Rn,(x,yi)Sh(x,y2)七S2)也是凸的。为了证明S是凸集，我们需要验证以下两个条件：1 .对于任意的(X1»Yi+Yi2)和(x2tYz+Yzz)属于s,以及任意的非负权重值J和都有t1(xy1+丫12)+t2(X2>Yz,y22)属十SO2 .对于任意的(x,y+y12)属于S,以及任意的非负标量t,都有t(x,y+y12)属于S。首先，考虑条件Io对于任意的(x1,y+y12)和(x2,y2+y22)属于S,以及任意的非负权重值t1和t2,我们有：ti(x,y+y12)+t2(x2.Yz+Yz?)=(tx1+t2xa(t1y1+t2y2)+(t1y12÷t2yz2)由于S和S提凸集，我们知道(x1,y1)S,(x2,y2)S2o根据凸集的定义,我们得出：(t1x1+t2X2,t1y1+t2y2)S1(t1x1+t2X2,t1y12+t2y22)三S2因此，(t1x1+t2x2,(t1y+t2y2)+(t1y12+t2y22)属于So这证明了条件1成立。接下来，考虑条件2。对于任意的(x,y+y12)属于S,以及任意的非负标量t,我们有：t(x,y+y2)=(tx,ty+ty12)由于Sl和S2凸集,我们知道(x,y)S和(x,y知S2°根据凸集的定义,我们得出：(tx,ty)S1(tx,ty12)S2因此，(tx,ty+ty12)属于S。这证明了条件2成立。综上所述，根据条件1和条件2,我们可以得出结论：S=(x,yi+y2)xRn,yi,y2Rn,(x,yi)S1,(x,y2)S2)是凸集。7 .可逆的线性分式函数。令RnfRn为线性分式函数f(x)=+,domf=xIc,X+<Z>0(1.6.3)(cX+d)设矩阵=k(1.6.4)ca非奇异。证明了可逆并且尸也是一个线性分式映射。利用A,b,c和d显式地给出rI及其定义域的表达式。略。8 .支撑超平面。(a)将闭凸集xR2x2e*')表示为半空间的交集。(b)令C=xeR""Wl表示R"空间中的单位L范数球，并令£为C的边界上的点，显式地写出集合<3在£处的支撑超平面。(a)要将闭凸集S=(xR2X>e2表示为半空间的交集，我们首先需要确定支撑超平面。支撑超平面是一个超平面，它恰好与集合的边界相切，并将集合划分为两个部分。对于集合S=xR2IX>e2,其中e是一个给定的正数，我们可以找到一个支撑超平面来表示它。考虑到X>e2,我们可以通过选择超平面X=e2来构造这个支撑超平面。注意到这个超平面满足以下条件：对于任意X£S,都有X2e?,因此X在超平面上方。对于任意X0S,都有X<e2,因此X在超平面下方。因此，我们可以将闭凸集S表示为半空间的交集：S=xR2IXe2o(b)集合C=x即Ilxll<1表示Rn空间中的单位J-范数球，其中X是C的边界上的点。要找到集合C在X处的支撑超平面，我们需要找到一个超平面，它恰好与C的边界在点X处相切，并将C划分为两个部分。对于单位c范数球C,我们可以发现支撑超平面位于每个坐标轴上的平面上。具体地，在点X=x1,x2j.,X处的支撑超平面可以写作以下形式：Xl=÷1,X2=±1,，X=±1这些平面分别与C的边界上的点X相切，并将C划分为两个半球，其中一个位于超平面上方，另一个位于超平面下方。因此，集合C在点X处的支撑超平面可以表示为x1=+1,x2=±1,.,X=÷lo注意这是一个包含2n个超平面的联合，每个超平面都由一个坐标轴确定。9 .考虑平面上的两个不相交的闭凸集C1=xR21x2=0),C2=R21X2,x1>0o(1)对于凸集合GCqR",若存在bRpR,使得C1,x2C2(1.6.5)则称凸集合G和G可以被严格分离。上面两个不相交的闭凸集合能被严格分离吗？(2)计算上面两个闭凸集的和C+C2,集合G+C2是闭集