最優(yōu)化模型與算法-基于Python實現(xiàn) 教案 ch01 凸集合

第一章凸集合1．（1）證明一個集合是凸集當(dāng)且僅當(dāng)它與任意直線的交是凸的。（2）證明一個集合是仿射的，當(dāng)且僅當(dāng)它與任意直線的交是仿射的。兩個點分別為A和B，即L={A,B}。對于SL中的兩個點C和D，我們需要證明連接C和D的線段上的所有點也屬于SL。由于SL是直線L與集合S的交集，因此C和D必須同時屬于L和S。由于S是凸集，連接A和B的線段上的點都屬于S，換句話說，線段AB上的任意一點都屬于S。由于C和D同時屬于線段AB，所以連接C和D的線段上的點也都屬于線段AB。因此，連接C和D的線段上的點既屬于S又屬于L，即它們屬于SL。所以，SL是凸的。（必要性）假設(shè)集合S與任意直線的交都是凸的。我們需要證明S本身是凸的。假設(shè)S中的兩個點E和F，我們需要證明連接E和F的線段上的所有點也屬于S?？紤]直線EF，由于S與直線EF的交集是凸的，所以連接E和F的線段上的點也都屬于S。因此，S是凸的。綜上所述，一個集合是凸集當(dāng)且僅當(dāng)它與任意直線的交是凸的。接下來，我們來證明一個集合是仿射的當(dāng)且僅當(dāng)它與任意直線的交是仿射的。證明：（充分性）假設(shè)集合S是仿射集。我們需要證明，對于任意直線L與S的交集SL，SL也是仿射的。假設(shè)直線L的兩個點分別為A和B，即L={A,B}。對于SL中的任意兩個點C和D，我們需要證明連接C和D的線段上的所有點以及C和D本身都屬于SL。由于SL是直線L與集合S的交集，因此C和D必須同時屬于L和S。由于S是仿射集，連接A和B的線段上的所有點以及A和B本身都屬于S。由于C和D同時屬于線段AB，因此連接C和D的線段上的所有點以及C和D本身也都屬于線段AB。所以，連接C和D的線段上的所有點以及C和D本身都屬于L和S，即它們屬于SL。因此，SL是仿射的。（必要性）假設(shè)集合S與任意直線的交都是仿射的。我們需要證明S本身是仿射的。假設(shè)S中的任意兩個點E和F，我們需要證明連接E和F的線段上的所有點以及E和F本身都屬于S。考慮直線EF，由于S與直線EF的交集是仿射的，所以連接E和F的線段上的所有點以及E和F本身都屬于S。因此，S是仿射的。綜上所述，一個集合是仿射的當(dāng)且僅當(dāng)它與任意直線的交是仿射的。2．(1)設(shè)是中的凸集合，是從到的線性變換。證明：集合是凸集合。(2)設(shè)是中的凸集合，是從到的線性變換．證明：集合是凸集合。（1）要證明集合AC={Ax|x∈C}是凸集，我們需要證明對于任意兩個元素Ax和Ay屬于AC，以及任意介于0和1之間的權(quán)重值t，tAx+(1-t)Ay也屬于AC。設(shè)Ax=A(x1)和Ay=A(x2)，其中x1和x2分別是集合C中的兩個元素。根據(jù)C是凸集的定義，對于任意介于0和1之間的權(quán)重值t，tx1+(1-t)x2也屬于C。由于A是線性變換，我們有A(tx1+(1-t)x2)=tA(x1)+(1-t)A(x2)=tAx+(1-t)Ay。因此，我們得出結(jié)論，tAx+(1-t)Ay屬于AC。由此可見，集合AC對于任意的Ax和Ay，以及介于0和1之間的權(quán)重值t，滿足凸集的定義。因此，集合AC={Ax|x∈C}是凸集。（2）為了證明集合A?1D={x|Ax∈D}是凸集，我們需要證明對于任意兩個元素x1和x2屬于A?1D，以及任意介于0和1之間的權(quán)重值t，t*x1+(1-t)*x2也屬于A?1D。假設(shè)x1和x2屬于A?1D，即Ax1和Ax2屬于D。由于D是凸集，對于任意介于0和1之間的權(quán)重值t，t*Ax1+(1-t)*Ax2也屬于D?？紤]A?1(t*Ax1+(1-t)Ax2)=A?1(tAx1)+A?1((1-t)Ax2)=tA?1(Ax1)+(1-t)A?1(Ax2)=tx1+(1-t)*x2因此，我們得出結(jié)論，t*x1+(1-t)*x2屬于A?1D。由此可見，集合A?1D對于任意的x1和x2，以及介于0和1之間的權(quán)重值t，滿足凸集的定義。因此，集合A?1D={x|Ax∈D}是凸集。3．兩個平行的超平面和之間的距離是多少？對于平行的超平面{x∈R?|a·x=b?}和{x∈R?|a·x=b?}，其中a為法向量，b?和b?為常數(shù)。兩個平行超平面之間的距離可以通過計算其中一個超平面上的任意點到另一個超平面的垂直距離來得到。設(shè)超平面{x∈R?|a·x=b?}上的一點為x?，則它到超平面{x∈R?|a·x=b?}的垂直距離為：d=(|a·x?-b?|)/||a||其中，|a·x?-b?|表示a·x?減去b?的絕對值，||a||表示a的Euclidean范數(shù)（即向量a的長度）。因此，兩個平行超平面{x∈R?|a·x=b?}和{x∈R?|a·x=b?}之間的距離為d=(|a·x?-b?|)/||a||，其中x?是其中一個超平面上的任意點。4．給定向量，，其中是有限或無限的指標(biāo)集。證明：集合 (1.6.1)是凸錐，并寫出的極錐。要證明集合K={x∈R?|{x,b}<0,?i∈I}是凸錐，我們需要滿足以下兩個條件：對于任意的x?和x?屬于K，以及任意的非負(fù)權(quán)重值t?和t?，都有t?x?+t?x?屬于K。對于任意的x屬于K，以及任意的非負(fù)標(biāo)量t，都有tx屬于K。首先，考慮條件1。對于任意的x?和x?屬于K，并且對于任意的非負(fù)權(quán)重值t?和t?，我們有：{t?x?+t?x?,b}=t?{x?,b}+t?{x?,b}由于{x?,b}<0且{x?,b}<0，我們可以得出：t?{x?,b}+t?{x?,b}<0因此，t?x?+t?x?屬于K。接下來，考慮條件2。對于任意的x屬于K，并且對于任意的非負(fù)標(biāo)量t，我們有：{tx,b}=t{x,b}由于{x,b}<0，我們可以得出：t{x,b}<0因此，tx屬于K。綜上所述，集合K={x∈R?|{x,b}<0,?i∈I}是一個凸錐。接下來，我們來描述K的極錐。極錐由滿足以下條件的向量x構(gòu)成：1.{x,b}≤0，其中b是給定的向量。2.{x,b}=0的充分必要條件是x是K的邊界點。因此，K的極錐由滿足條件{x,b}≤0的向量x構(gòu)成，并且當(dāng){x,b}=0時，x為K的邊界點。5．證明：概率單純形。要證明概率單純形P={(p?,p?,…,p?)∈R?|∑pk=1,pk>0}是凸集合，我們需要滿足以下條件：對于任意的p,q屬于P，以及任意的非負(fù)權(quán)重值t?和t?，都有t?p+t?q屬于P。對于任意的p屬于P，以及任意的非負(fù)標(biāo)量t，都有tp屬于P。首先，考慮條件1。對于任意的p=(p?,p?,…,p?)和q=(q?,q?,…,q?)屬于P，以及任意的非負(fù)權(quán)重值t?和t?，我們有：∑(t?pk+t?qk)=t?∑pk+t?∑qk=t?+t?=1因此，t?p+t?q屬于P。接下來，考慮條件2。對于任意的p=(p?,p?,…,p?)屬于P，以及任意的非負(fù)標(biāo)量t，我們有：∑tpk=t∑pk=t因此，tp屬于P。綜上所述，我們證明了概率單純形P={(p?,p?,…,p?)∈R?|∑pk=1,pk>0}是凸集合。6．證明如果和是中的凸集，那么它們的部分和 (1.6.2)也是凸的。要證明如果S?和S?是R?中的凸集，那么它們的部分和S={(x,y?+y?)|x∈R?,y?,y?∈R?,(x,y?)∈S?,(x,y?)∈S?}也是凸的。為了證明S是凸集，我們需要驗證以下兩個條件：1.對于任意的(x?,y?+y??)和(x?,y?+y??)屬于S，以及任意的非負(fù)權(quán)重值t?和t?，都有t?(x?,y?+y??)+t?(x?,y?+y??)屬于S。2.對于任意的(x,y+y??)屬于S，以及任意的非負(fù)標(biāo)量t，都有t(x,y+y??)屬于S。首先，考慮條件1。對于任意的(x?,y?+y??)和(x?,y?+y??)屬于S，以及任意的非負(fù)權(quán)重值t?和t?，我們有：t?(x?,y?+y??)+t?(x?,y?+y??)=(t?x?+t?x?,(t?y?+t?y?)+(t?y??+t?y??))由于S?和S?是凸集，我們知道(x?,y?)∈S?，(x?,y?)∈S?。根據(jù)凸集的定義，我們得出：(t?x?+t?x?,t?y?+t?y?)∈S?(t?x?+t?x?,t?y??+t?y??)∈S?因此，(t?x?+t?x?,(t?y?+t?y?)+(t?y??+t?y??))屬于S。這證明了條件1成立。接下來，考慮條件2。對于任意的(x,y+y??)屬于S，以及任意的非負(fù)標(biāo)量t，我們有：t(x,y+y??)=(tx,ty+ty??)由于S?和S?是凸集，我們知道(x,y)∈S?和(x,y??)∈S?。根據(jù)凸集的定義，我們得出：(tx,ty)∈S?(tx,ty??)∈S?因此，(tx,ty+ty??)屬于S。這證明了條件2成立。綜上所述，根據(jù)條件1和條件2，我們可以得出結(jié)論：S={(x,y?+y?)|x∈R?,y?,y?∈R?,(x,y?)∈S?,(x,y?)∈S?}是凸集。7．可逆的線性分式函數(shù)。令為線性分式函數(shù) (1.6.3)設(shè)矩陣 (1.6.4)非奇異。證明可逆并且也是一個線性分式映射。利用和顯式地給出及其定義域的表達(dá)式。略。8．支撐超平面。(a)將閉凸集表示為半空間的交集。(b)令表示空間中的單位范數(shù)球，并令為的邊界上的點，顯式地寫出集合在處的支撐超平面。(a)要將閉凸集S={x∈R2|x>e2}表示為半空間的交集，我們首先需要確定支撐超平面。支撐超平面是一個超平面，它恰好與集合的邊界相切，并將集合劃分為兩個部分。對于集合S={x∈R2|x>e2}，其中e是一個給定的正數(shù)，我們可以找到一個支撐超平面來表示它?？紤]到x>e2，我們可以通過選擇超平面x=e2來構(gòu)造這個支撐超平面。注意到這個超平面滿足以下條件：對于任意x∈S，都有x≥e2，因此x在超平面上方。對于任意x?S，都有x<e2，因此x在超平面下方。因此，我們可以將閉凸集S表示為半空間的交集：S={x∈R2|x≥e2}。(b)集合C={x∈R?|||x||<1}表示R?空間中的單位c?-范數(shù)球，其中x是C的邊界上的點。要找到集合C在x處的支撐超平面，我們需要找到一個超平面，它恰好與C的邊界在點x處相切，并將C劃分為兩個部分。對于單位c?-范數(shù)球C，我們可以發(fā)現(xiàn)支撐超平面位于每個坐標(biāo)軸上的平面上。具體地，在點x=[x?,x?,...,x?]處的支撐超平面可以寫作以下形式：x?=±1,x?=±1,...,x?=±1這些平面分別與C的邊界上的點x相切，并將C劃分為兩個半球，其中一個位于超平面上方，另一個位于超平面下方。因此，集合C在點x處的支撐超平面可以表示為x?=±1,x?=±1,...,x?=±1。注意這是一個包含2?個超平面的聯(lián)合，每個超平面都由一個坐標(biāo)軸確定。9.考慮平面上的兩個不相交的閉凸集。(1)對于凸集合，若存在，使得 (1.6.5)則稱凸集合和可以被嚴(yán)格分離。上面兩個不相交的閉凸集合能被嚴(yán)格分離嗎？計算上面兩個閉凸集的和，集合是閉集合嗎?略。10．支撐函數(shù)。集合的支撐函數(shù)定義為 (1.6.6)我們允許取值為。令表示空間中的單位范數(shù)球，求相應(yīng)的支撐函數(shù)。對于集合C={x∈R?|||x||<1}，其中||x||表示L?范數(shù)。我們需要求對于任意的y∈R?，支撐函數(shù)Sc(y)。定義支撐函數(shù)Sc(y)為：Sc(y)=sup{y1x|x∈C}考慮到L?范數(shù)是所有絕對值之和，我們可以得到：||x||=|x?|+|x?|+...+|x?|因此，我們需要將方程y1x表示為絕對值之和：y1x=|y?x?|+|y?x?|+...+|y?x?|根據(jù)絕對值的性質(zhì)，我們可以將上述式子最大化，將每個xi的符號與對應(yīng)的yi符號相同。也就是說，如果yi和xi同號，則xi對最大化y1x有正向貢獻(xiàn)，否則沒有貢獻(xiàn)。因此，我們可以得到：Sc(y)=sup{|y1x||x∈C}Sc(y)=sup{|y1x||||x||<1}現(xiàn)在我們需要找到滿足||x||<1的所有向量x，它們都在單位L?范數(shù)球內(nèi)。這等價于以下條件：-1<x?<1-1<x?<1...-1<x?<1我們需要盡可能地最大化|y1x|，使其成為支撐函數(shù)的值。為了最大化|y1x|，我們需要選擇xi的符號和yi的符號相同。因此，我們得到：Sc(y)=sup{y1x|-1<xi<1,i=1,2,...,n}Sc(y)=||y||?因此，單位L?范數(shù)球C的支撐函數(shù)為：Sc(y)=||y||?這是y的所有分量絕對值之和。11．階數(shù)時的半正定矩陣構(gòu)成的錐。對于階數(shù)，用矩陣系數(shù)和普通不等式給出半正定錐的顯式表示。為表示時中的元素，請用下面的符號略。12．證明：如果是閉凸錐，則。要證明如果K是閉凸錐，則K^*=K，我們需要證明兩個方向的包含關(guān)系：K^*包含于K，并且K包含于K^*。首先，我們證明K^*包含于K。假設(shè)y∈K^*，我們需要證明y∈K。根據(jù)對偶錐的定義，K^*的元素y滿足以下條件：y1x≥0，對于所有x∈K由于K是一個閉凸錐，因此對于任意的x∈K和任意的正實數(shù)t，tx也屬于K。由此可得：y1(tx)=ty1x≥0，對于所有x∈K和任意的