《最优化模型与算法——基于Python实现教案全套渐令ch01凸集合---ch06凸优化算法.docx》由会员分享，可在线阅读，更多相关《最优化模型与算法——基于Python实现教案全套渐令ch01凸集合---ch06凸优化算法.docx（28页珍藏版）》请在课桌文档上搜索。
1、第一章凸集合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与任意直线的交都是凸的。我们需要证明
2、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必须同时属于
3、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是仿射的。综上所述，一个集合是仿射的当且仅当它与任意直线的交是仿射的。
4、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)=tA
5、x+(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也属于AD。假设xl和x2属于AD,即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(Ax
6、2)=txl+(l-t)*x2因此，我们得出结论,t*xl+(l-t)*x2属于ATDo由此可见，集合ATD对于任意的xl和x2,以及介于。和1之间的权重值t,满足凸集的定义。因此，集合ATD=AxD是凸集。3 .两个平行的超平面xwRX=伪和xwRI/x=%之间的距离是多少?对于平行的超平面xWRnax=b1l1WRnax=b2,其中a为法向量，b1和b为常数。两个平行超平面之间的距离可以通过计算其中一个超平面上的任意点到另一个超平面的垂直距离来得到。设超平面6Rra-x=b1)上的一点为x。，则它到超平面xR1a-x=b的垂直距离为：d=(ax(11b2)/a其中，aXcrbzl表示aX减
7、去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,bO,ViI是凸锥，我们需要满足以下两个条件：对于任意的Xi和X2B于K,以及任意的非负权重值J和(2，都有tiXi+jx痈于Ko对于任意的X属于K,以及任意的非负标量t,都有tx属于K。首先，考虑条件1。对于任意的Xi和X弱于K,并且对于任意的非负权重
8、值J和t2,我们有:t1x1+t2x2,b=t1xb+t2x2.b由于x1,bb0,我们可以得出:txhb+t2x2,b0因此，t1X1+t2xJ国于Ko接下来，考虑条件2。对于任意的X属于K,并且对于任意的非负标量t,我们有：tx,b)=tx,b由于x,bO,我们可以得出：tx,b)0因此，tx属于K。综上所述，集合K=xRr合x,bO,iI是一个凸锥。接下来，我们来描述K的极锥。极锥由满足以下条件的向量X构成：1. (x,bO,其中b是给定的向量。2. x,b=0的充分必要条件是X是K的边界点。因此，K的极锥由满足条件x,bWO的向量X构成，并且当x,b=O时，X为K的边界点。5 .证明：
9、概率单纯形尸=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,Pk0是凸集合。6
10、 .证明如果航和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 .对于任意的(X1Yi+Yi2)和(x2tYz+Yzz)属于s,以及任意的非负权重值J和都有t1(xy1+丫12)+t2(X2Yz,y22)属十SO2 .对于任意的(x,y+y12)属于S,以及任意的非负标量t,都有t(x,y+y12)属于S。首先，考虑条
11、件Io对于任意的(x1,y+y12)和(x2,y2+y22)属于S,以及任意的非负权重值t1和t2,我们有：ti(x,y+y12)+t2(x2.Yz+Yz?)=(tx1+t2xa(t1y1+t2y2)+(t1y12t2yz2)由于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,我们
12、有：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+0(1.6.3)(cX+d)设矩阵=k(1.6.4)ca非奇异。证明了可逆并且尸也是一个线性分式映射。利用A,b,c和d显式地给出rI及其定义域的
13、表达式。略。8 .支撑超平面。(a)将闭凸集xR2x2e*)表示为半空间的交集。(b)令C=xeRWl表示R空间中的单位L范数球，并令为C的边界上的点，显式地写出集合e2表示为半空间的交集，我们首先需要确定支撑超平面。支撑超平面是一个超平面，它恰好与集合的边界相切，并将集合划分为两个部分。对于集合S=xR2IXe2,其中e是一个给定的正数，我们可以找到一个支撑超平面来表示它。考虑到Xe2,我们可以通过选择超平面X=e2来构造这个支撑超平面。注意到这个超平面满足以下条件：对于任意XS,都有X2e?,因此X在超平面上方。对于任意X0S,都有Xe2,因此X在超平面下方。因此，我们可以将闭凸集S表示为
14、半空间的交集：S=xR2IXe2o(b)集合C=x即Ilxll0o(1)对于凸集合GCqR,若存在bRpR,使得C1,x2C2(1.6.5)则称凸集合G和G可以被严格分离。上面两个不相交的闭凸集合能被严格分离吗？(2)计算上面两个闭凸集的和C+C2,集合G+C2是闭集合吗？略。10 .支撑函数。集合CUR的支撑函数定义为(1.6. 6)Sc(j)=sup(yxxC)我们允许Sc(y)取值为+8。令C=xeRhx1W1表示R空间中的单位范数球，求相应的支撑函数Sc(y)。对于集合C=xRrlx+W2X2I+.+IyX根据绝对值的性质,我们可以将上述式子最大化,将每个i的符号与对应的yi符号相同。
15、也就是说，如果yi和i同号，则i对最大化y,x有正向贡献，否则没有贡献。因此,我们可以得到：Sc(y)=supy,xxCSc(y)=supy,x|x1现在我们需要找到满足IxIKl的所有向量X,它们都在单位Ll范数球内。这等价于以下条件：-1x11-121.1X1我们需要尽可能地最大化y,使其成为支撑函数的值。为了最大化y,x,我们需要选择i的符号和yi的符号相同。因此，我们得到：Sc(y)=sup(y,X|-1xi=,我们需要证明两个方向的包含关系：K包含于K,并且K包含于K首先，我们证明K*包含于Ko假设yK*,我们需要证明yKo根据对偶锥的定义，K的元素y满足以下条件：y,x0,对于所有
16、XK由于K是一个闭凸锥，因此对于任意的XK和任意的正实数t,tx也属于Ko由此可得：y,(tx)=ty,x0,对于所有XK和任意的正实数t考虑到y,(tx)=t(y,x),我们可以得出结论：y,x0,对于所有XeK和任意的正实数t这意味着y是K的一个元素。因此，我们得出结论：K*包含于Ko接下来，我们证明K包含于K假设XK,我们需要证明XK根据闭凸锥的定义，K的元素X满足以下条件：y,x0,对于所有yeK这意味着对于任意的yK*,y,x力Oo因此，根据对偶锥的定义，X属于K因此，我们得出结论：K包含于K综上所述，根据包含关系的证明，我们可以得出结论：如果K是闭凸锥，则K*=Ko第二章凸函数1
17、.证明下列函数/为凸函数一元函数2N+1,x0+8,XWO（25.1）定义在r上的几何平均函数fM=-(11xiY(25.2)略。2 .已知函数以制为定义在R上的凸函数，函数f(x)=e(253)证明：函数/(X)为R上的凸函数.要证明函数f(x)=eg(x)T是定义在Rn上的凸函数，需要判断其二阶导数是否非负。首先计算f(x)的一阶和二阶导数：f,(x)=8egzf(a)=64egz由于函数S(X)是定义在Rn上的凸函数，即s(x)20对于所有XWR成立。现在我们来研究函数f”(x)的符号。对于所有xR,有cgr0因此，(x)=64egx0,即二阶导数恒大于零。根据凸函数的定义，如果一个函数
18、的二阶导数恒大于等于零，则该函数是凸函数。因此，函数f(x)是定义在Rn上的凸函数。3 .已知二元函数/为处处有限的凸函数，设一元函数且定义为sw=infU.y)(254)证明：函数g*)为凸函数。根据式子(2.5.4),我们有：g(x)=Vf(x,y)这表示g()是函数f(z,y)在变量y上的下确界。由于f(,y)是处处有限的凸函数，那么对于固定的X,函数f(,y)关于y是凸函数。因此，对于任意的xl,x2和OW8Wl,我们有:f(xl,y)2。f(xl,y)+(l-)f(x2,y)取yl为使得Of(Xl,yl)+(l-0)f(x2,yl)达到下确界g(xl)的值,即Of(xl,yl)+(1
19、-)f(x2fyl)=g(xl)O同样，取y2为使得0f(xl,y2)+(l-0)f(x2,y2)达到下确界g(x2)的值,即f(xl,32)+(1-)f(x2,y2)=g(x2)o由于f(x,y)是凸函数，我们有：f(0xl+(l-0)x2,yl+(l-)y2)f(l,yl)+(l-)f(2,y2)取下确界得到：9(0xl+(l-)x2)0g(xl)+(l-)g(x2)因此，函数g(x)是凸函数。4 .设函数九人：R-R为凸函数，证明函数几力的下卷积函数f()=(ZX)=inHZ()+(z)IX1+X2=)(2.5.5)为凸函数。要证明函数f(x)是凸函数,我们需要证明对于任意的xl,x2和
20、OWeWl,有f(xl+(l-)x2)f(xl)+(l-)f(x2)o首先,我们来研究函数f(x)的定义。根据式子5.5),我们有：f(x)=(fl*f2)(x)-inffl(xl)+f2(x2)|xl+2=x这表示f(x)是函数fl表D+f2(x2)取下确界(infimum)时的差值。由于fl和f2均为凸函数，我们知道对于任意的xl,x2和01,有：fl(xl+(l-)x2)fi(xl)+(l-)fl(x2)f2(xl(l-)x2)f2(xl)+(l-)f2(x2)对于第一项(fl*f2)(x),我们可以使用Jensen不等式来处理。由于11和f2均为凸函数，我们有：(fl*f2)(0xl+
21、(l-)x2)(fl*f2)(xl)+(l-)(fl*f2)(x2)现在，我们来研究第二项inffl(xl)+f2(x2)xl+x2=x0我们要证明：inffl(0xl+(l-)x2)+f2(xl+(l-)x2)Izl+x2=xl+(l-0)x220inffl(xl)+f2(x2)cl+x2=xl+(l-)inff1(xl)+f2(x2)|xl+2=2也就是要证明：inff1(xl)+f2(x2)xl+x2=x2inff(xl)+f2(x2)xl+x2=xl+(1-)inffl(xl)+f2(x2)xl+x2=2根据下确界的性质,左边的下确界大于等于右边的下确界，因此上述不等式成立。综上所述，
22、我们得到：f(xl+(l-)x2)=(fl*f2)(xl+(l-)x2)-inffl(xl+(l-)x2)+f2(xl+(l-)x2)Ixl+x2=xl+(l-)x2(fl*f2)(al)+(l-)(fl*f2)(a2)-inffl(xl)+f2(x2)Ixl+x2=xl-(l-)inffl(xl)+f2(x2)Ixl+x=x2进一步化简得到：W(fl*f2)(xl)-inffl(xl)+f2(x2)xl+x2=xl+(l-)(fl*f2)(x2)-inff1(x1)+f2(x2)xl+x2=x2根据函数f(x)的定义，可以将上述不等式进一步简化为：=0f(xl)+(l-0)f(x2)因此,我
23、们证明了对于任意的xl,x20l,Wf(0xl+(l-)x2)f(xl)+(l-)f(x2)0因此,函数f(x)是凸函数。5 .凸性的二阶条件。设函数/(x)9R,其中C是R中的凸集合且是开集，函数/二阶连续可微.证明：/是集合C上的凸函数当且仅当对任意的XeC,(X)半正定。6 .分片线性凸函数的表示。函数八RTR,其定义域为dof=R,被称为分片线性函数，如果存在R的一个划分R”=%打XL(2.5.6)其中产,且对任意i,intX-intX=;以及一系列仿射函数qb+MHX+使得对xX,有/(x)=qT+4,证明若/是凸函数，有f(x)=maxax+b.,a!x+b,)O略。7 .函数的凸
24、包。函数六RfR的凸包(或凸包络)定义为(x)=inf/1(x,r)convepif&5.7)几何上，函数月的上图是/的上图的凸包。证明如果函数人是凸函数，且对所有X有(x)w(x),则对所有X有(X)Wg(X)。略。8 .推导下列函数的共辗函数。二次函数广RR,N=HoHEHa(2.5.8)其中。为阶对称正定矩阵，,wR,asR一元函数/3=国+1(2.5.9)ZXiIn务若丐0,/=L,，2耳=1八町j=lil(C)函数R,(o,-o,l+否则(2.5.10)(d)定义在R+上的鬲函数/()=N,其中1。如果+4可行集：1 .直线4xl+x2=22 .直线x.+3x2=13 .点(0,0)
25、请注意，由于第三个约束等式与第二个约束等式相同，它们在平面上重合。绘制出这些直线和点后，可行集将位于这些曲线和点之间。具体来说，可行集将位于由这些曲线和点围成的区域内部。S2(a)最优解集是(TL11)最优值是W52(b)最优解集是(77,77)最优值是S2(c)最优解集是(K,77)104最优值是言2 .调用Python包cvxopt求解二次规划minimize(1/2)xPx+qrx+rsubejectto-1x,l,f=1,2,3(37的最优解K其中22.014.52512-212176-2612进一步证明近似满足最优性条件。3 .处理凸等式约束。凸优化问题只能含有线性等式约束。但是，在
26、一些特殊的情况下，有可能处理凸等式约束函数，即具有(2=形式的约束，其中人是凸函数。我们将在这个问题中研究这一思想。考虑优化问题minimizesubeject tofoMj(x)0,=l,m 7. 3)MX)-0其中工和人是定义域为Rn的凸函数。除非是仿射的，这不是一个凸优化问题。考虑相关的问题minimize(x)subejecttofi(x)0,/=1,其中，凸等式约束已经被放松为凸不等式。当然，这个问题是凸的。假设我们可以保证凸问题(3.7.4)的任意最优解,都有(/)二,即不等式MX)0在解处总是起作用的。那么，我们可以通过求解凸问题(3.7.4)来求解(非凸)问题(3.73)0说明
27、下标，满足 )关于，单调递增 九j”关于。非减 关于与单调递减时就会发生这种情况。4 .考虑Lasso模型ArM(3.7.5)其中，AR-,bR0m人将其转化为等价的线性规划问题，设置A,的数值并编程求解等价的线性规划问题得到Lasso模型的解。要编程求解这个等价的线性规划问题，你可以使用线性规划库，如Python中的scipy.optimize.Iinprog或MATLAB中的Iinprog函数。根据具体的编程语言和库的要求,你需要将问题转化为相应的输入格式，并调用相应的函数来求解。5 .设有若干二分类问题的观测样本(号J)LRx+LT,考虑线性支持向量机模型：2R纲f+c%ii2闫(3,7
28、.6)其中，OO为参数，/(4%w,=max(0,lf(篦毛+与)为样本点(4为)的经验损失,对应于Hinge损失函数Q)=max(O,l),函数武制=*+力为判别函数。(1)下载通用的二分类数据集，并对样本特征进行标准化处理；将线性支持向量机模型化为凸二次规划模型，并调用通用的二次规划软件包求解；使用模型训练得到的判别函数对样本点进行分类，计算分类准确率。、略。6 .考虑下面的QCQP问题minimize(1/2)x1Px+qlx+rsubjecttox1x1(377)其中PS,证明最优解=TP+M)-%4=maxR,又是非线性等式qT(P+)-2q=l的最大解。7 .将下面的管道流量问题建
29、模为几何规划：温度为T（高于环境温度）的加热液体在固定长度且圆形截面半径为的管道中流动。管道周围有一层厚度为M的保温层，以减少通过管壁的热量损失，卬-L本问题的设计变量为7，卬。热量损失（近似）与/成比例，因此在固定的寿命内，损失的能量成本为%7m管壁厚度一定，其成本与总材料近似成正比，为W绝缘材料的成本也近似与总绝缘材料成比例，即。3叫（卬，）。总成本是这三种成本之和。沿管道向下的热流完全是由于液体的流动，流动速度一定，即。4力;常数S都是正数，变量7也是正数。现在的问题是：受总成本上限Ci和约束条件的限制，最大限度地提高管道的总流量。工,而WTWi皿，加”WrWGIaK,吗而卬W%tr,w
30、O.lr（37.8）将问题建模为几何规划的一般步骤如下：（1）确定目标函数（2）确定约束条件（3）确定变量类型及取值范围根据问题描述，我们可以得到以下信息：（1）目标：最大化管道的总流量（2）约束：a.总成本不能超过一个上限。b.管道外层半径不能超过一个给定值。c.液体在管道中的速度不超过一个给定值。d.管道剩余空间应保证绝缘材料和管道壁厚度的要求。（3）变量类型及取值范围：a.管道内径，为常数。b.管道壁厚度，为常数。c.管道外层半径，为变量，取值范围为管道内径，给定最大值。d.绝缘材料厚度，为变量，取值范围为0,管道外层半径-管道内径。e.流体速度，为常数。设管道外层半径为，绝缘材料厚度为
31、。那么，管道总长度为，管道壁与绝缘层之外半径为O绝缘材料和管道壁厚度需满足以下条件：绝缘材料厚度不得小于0绝缘材料和管道壁厚度之和不能超过管道外层半径与管道内径之差将目标函数、约束条件及变量类型总结如下：（1）目标函数：最大化管道总流量（2）约束：总成本不能超过一个上限。管道外层半径不能超过一个给定值。液体在管道中的速度不超过一个给定值。管道剩余空间应保证绝缘材料和管道壁厚度的要求。（3）变量类型及取值范围：管道内径，为常数。管道壁厚度，为常数。管道外层半径，为变量，取值范围为管道内径，给定最大值。绝缘材料厚度，为变量，取值范围为0,管道外层半径-管道内径。流体速度，为常数。第四章对偶理论1
32、.考虑如下优化问题minimizex-2x+subjectto(x-I)(X-5)0(451)其中变量XGR。分析原问题，给出可行集、最优值以及最优解。画出目标函数关于X的图像，并在图像上画出可行集、最优值以及最优解。画出4=0.2时，Lagrange函数La关于X的图像，验证下界性质：三呼对九成立。推导并画出Lagrange对偶函数8。(1)找出可行集：要使约束条件成立，需要满足(x-D(-5)W0.这意味着X的取值范围为l,5o求解最优值：我们需要找到在可行集内使目标函数最小的点。首先，我们可以计算目标函数的导数：f,(x)=2-2o将其置零求解：2-2=0,得到x=l.检查临界点和可行集
33、边界上的目标函数值：当x=l时,f(x)=I2-2(1)+I=Oo确定最优解：目标函数在x=l处取得最小值，满足约束条件(xT)(-5)W0因此，可行集为1,5,最优值为f(x)=O,在x=l处取得最小值。综上所述，原问题的可行集为1,5,最优值为0,在x=l处取得最优解。(2)略。2 .考虑如下凸分段线性函数最小化问题minimizemax(a：x+bi),-1-m(4.5.2)其中变量xR。考虑等式问题minimizemaxyij1.m(4. 5. 3)subjecttoafx+bi=yz,z=l,rn其中变量*tR”,yeR推导出Lagrange对偶问题。将分段线性问题(4.5.1)表述
34、为LP问题并写出LP问题的对偶问题。将LP对偶与中所求得的对偶问题联系起来。(1)略。(2)略。3 .设有若干二分类问题的观测样本(4y)3=R+1I,考虑线性支持向量机模型：12min-w+CV/(x/，x-；v,Z)(4. 5. 4)HeRd./;eR2Jr=l其中，C0为参数，k*w)=max(Uf(wX+勿)为样本点(“J的经验损失，对应于Hinge损失函数3=max1),函数y(x)=wx+b为判别函数。将线性支持向量机模型化为凸二次规划模型，并写出该规划模型的对偶问题；结合凸二次规划模型的最优性条件，说明哪些样本对模型起作用，哪些不起作用.(1)将线性支持向量机模型化为凸二次规划模
35、型，并写出该规划模型的对偶问题：我们可以将线性支持向量机模型写成如下的凸二次规划形式：minimize1/2|w|2+Ci=lmisubjecttoyi(w,xi+b)21-i,i=1,2,.,mi0,i=l,2,.,m其中，变量为wR4,bR,i0,i=l,2,.,m0的样本点)，变量为aH,n为样本数。注意，这是一个凸二次规划问题，而且这个问题的解又可以用来求解原始问题中的最优解。(2)结合凸二次规划模型的最优性条件，说明哪些样本对模型起作用，哪些不起作用。根据凸二次规划模型的最优性条件，我们可以得出以下结论：对于所有的正常样本(即yi=+1的样本)，当其对应的Lagrange乘子ai0时，它们将成为决策边界上的支持向量。对于所有的负样本(即yi=-1的样本)，当其对应的Lagrange乘子iO时，它们也将成为决策边界上的支持向量。对于那些满足O11i,假设模型有唯一解，证明该模型的最优解关于是分片线性的。略。6 .考虑QCQP问题minimize(jcj2+a)-4subjectto(xl-1)2+(x2-1)24(457)其中变量XW写出最优点/和最优值写出KKT条件。求解L
