凸集基本概念、函數(shù)計(jì)算和凸優(yōu)化初步方法

1、凸集基本概念、函數(shù)計(jì)算和凸優(yōu)化初步方法2主要內(nèi)容凸集基本概念凸集保凸運(yùn)算分割超平面支撐超平面凸函數(shù)基本概念上境圖Jensen不等式凸函數(shù)保凸運(yùn)算凸優(yōu)化一般提法對(duì)偶函數(shù)鞍點(diǎn)解釋用對(duì)偶求解最小二乘問題強(qiáng)對(duì)偶KKT條件3思考凸集和凸函數(shù)y=x2是凸函數(shù)，函數(shù)圖像上位于y=x2上方的區(qū)域構(gòu)成凸集。凸函數(shù)圖像的上方區(qū)域，一定是凸集；一個(gè)函數(shù)圖像的上方區(qū)域?yàn)橥辜?，則該函數(shù)是凸函數(shù)。稍后給出上述表述的形式化定義。因此，學(xué)習(xí)凸優(yōu)化，考察凸函數(shù)，先從凸集及其性質(zhì)開始。4凸集集合C內(nèi)任意兩點(diǎn)間的線段均在集合C內(nèi)，則稱集合C為凸集。5凸集6超平面和半空間超平面hyperplane半空間halfspace7超平面和半

2、空間8多面體多面體有限個(gè)半空間和超平面的交集。仿射集(如超平面、直線)、射線、線段、半空間都是多面體。多面體是凸集。此外：有界的多面體有時(shí)稱作多胞形(polytope)。注：該定義略混亂，不同文獻(xiàn)的含義不同。9多面體10保持凸性的運(yùn)算集合交運(yùn)算思考：如何證明？(提示：根據(jù)定義)仿射變換函數(shù)f=Ax+b的形式，稱函數(shù)是仿射的：即線性函數(shù)加常數(shù)的形式透視變換投射變換(線性分式變換)11集合交運(yùn)算：半空間的交12仿射變換仿射變換伸縮、平移、投影若f是仿射變換，若S為凸集，則f(S)為凸集；若f(S)為凸集，則S為凸集。13透視變換透視函數(shù)對(duì)向量進(jìn)行伸縮(規(guī)范化)，使得最后一維的分量為1并舍棄之。透視

3、的直觀意義小孔成像14透視變換的保凸性凸集的透視變換仍然是凸集。思考：反過來，若某集合的透視變換是凸集，這個(gè)集合一定是凸集嗎？15投射函數(shù)(線性分式函數(shù))投射函數(shù)是透視函數(shù)和仿射函數(shù)的復(fù)合。g為仿射函數(shù)：定義f為線性分式函數(shù)若c=0,d0，則f即為普通的仿射函數(shù)。16分割超平面設(shè)C和D為兩不相交的凸集，則存在超平面P，P可以將C和D分離。注意上式中可以取等號(hào)：所以：逆命題：“若兩個(gè)凸集C和D的分割超平面存在，C和D不相交”為假命題。加強(qiáng)條件：若兩個(gè)凸集至少有一個(gè)是開集，那么當(dāng)且僅當(dāng)存在分割超平面，它們不相交。17分割超平面18分割超平面的構(gòu)造兩個(gè)集合的距離，定義為兩個(gè)集合間元素的最短距離。做集

4、合C和集合D最短線段的垂直平分線。19支撐超平面設(shè)集合C，x0為C邊界上的點(diǎn)。若存在a0，滿足對(duì)任意xC，都有 成立，則稱超平面 為集合C在點(diǎn)x0處的支撐超平面。凸集邊界上任意一點(diǎn)，均存在支撐超平面。反之，若一個(gè)閉的非中空（內(nèi)部點(diǎn)不為空）集合，在邊界上的任意一點(diǎn)存在支撐超平面，則該集合為凸集。20思考如何定義兩個(gè)集合的“最優(yōu)”分割超平面？找到集合“邊界”上的若干點(diǎn)，以這些點(diǎn)為“基礎(chǔ)”計(jì)算超平面的方向；以兩個(gè)集合邊界上的這些點(diǎn)的平均作為超平面的“截距”支持向量：support vector若兩個(gè)集合有部分相交，如何定義超平面，使得兩個(gè)集合“盡量”分開？注：上述“集合”不一定是凸集，可能是由若干離

5、散點(diǎn)組成。若一組集合為(x,1)，另一組集合為(x,2)，則為機(jī)器學(xué)習(xí)中的分類問題。21凸函數(shù)若函數(shù)f的定義域domf為凸集，且滿足22一階可微若f一階可微，則函數(shù)f為凸函數(shù)當(dāng)前僅當(dāng)f的定義域domf為凸集，且23進(jìn)一步的思考結(jié)合凸函數(shù)圖像和支撐超平面理解該問題對(duì)于凸函數(shù)，其一階Taylor近似本質(zhì)上是該函數(shù)的全局下估計(jì)。反之，如果一個(gè)函數(shù)的一階Taylor近似總是起全局下估計(jì)，則該函數(shù)是凸函數(shù)。該不等式說明從一個(gè)函數(shù)的局部信息，可以得到一定程度的全局信息。24二階可微若函數(shù)f二階可微，則函數(shù)f為凸函數(shù)當(dāng)前僅當(dāng)dom為凸集，且若f是一元函數(shù)，上式表示二階導(dǎo)大于等于0若f是多元函數(shù)，上式表示二階

6、導(dǎo)Hessian矩陣半正定。25凸函數(shù)舉例26上境圖函數(shù)f的圖像定義為：函數(shù)f的上境圖(epigraph)定義為：27凸函數(shù)與凸集一個(gè)函數(shù)是凸函數(shù)，當(dāng)且僅當(dāng)其上境圖是凸集。思考：如何證明？(提示：定義)進(jìn)一步，一個(gè)函數(shù)是凹函數(shù)，當(dāng)且僅當(dāng)其亞圖(hypograph)是凸集。28Jensen不等式：若f是凸函數(shù)基本Jensen不等式若則若則29 Jensen不等式是幾乎所有不等式的基礎(chǔ)利用f(E(x)E(f(x)，(f是凸函數(shù))，證明下式D0利用y=-logx是凸函數(shù)，證明：提示：任取a,b0，帶入基本Jensen不等式30保持函數(shù)凸性的算子凸函數(shù)的非負(fù)加權(quán)和凸函數(shù)與仿射函數(shù)的復(fù)合凸函數(shù)的逐點(diǎn)最大

7、值、逐點(diǎn)上確界31凸函數(shù)的逐點(diǎn)最大值f1,f2均為凸函數(shù)，定義函數(shù)f：則函數(shù)f為凸函數(shù)。32思考逐點(diǎn)上確界和上境圖的關(guān)系一系列函數(shù)逐點(diǎn)上確界函數(shù)對(duì)應(yīng)著這些函數(shù)上境圖的交集。直觀例子Oxy平面上隨意畫N條直線(直線是凸的雖然直線也是凹的)，在每個(gè)x處取這些直線的最大的點(diǎn)，則構(gòu)成的新函數(shù)是凸函數(shù)；同時(shí)：N條直線逐點(diǎn)求下界，是凹函數(shù)；在Lagrange對(duì)偶函數(shù)中會(huì)用到該結(jié)論。33凸優(yōu)化優(yōu)化問題的基本形式34優(yōu)化問題的基本形式優(yōu)化問題的域可行點(diǎn)(解)(feasible)xD，且滿足約束條件可行域(可解集)所有可行點(diǎn)的集合最優(yōu)化值最優(yōu)化解35凸優(yōu)化問題的基本形式fi(x)(0i m)為凸函數(shù)，hj(x)

8、(1i p)為仿射函數(shù)凸優(yōu)化問題的重要性質(zhì)可行域?yàn)橥辜植孔顑?yōu)解即為全局最優(yōu)解36對(duì)偶問題一般優(yōu)化問題的Lagrange乘子法Lagrange函數(shù)對(duì)固定的x，Lagrange函數(shù)L(x,v)為關(guān)于和v的仿射函數(shù)37Lagrange對(duì)偶函數(shù)(dual function)Lagrange對(duì)偶函數(shù)若沒有下確界，定義：根據(jù)定義，顯然有：對(duì)0，v，若原優(yōu)化問題有最優(yōu)值p*，則進(jìn)一步：Lagrange對(duì)偶函數(shù)為凹函數(shù)。38左側(cè)為原函數(shù)，右側(cè)為對(duì)偶函數(shù)39鞍點(diǎn)解釋為表述方便，假設(shè)沒有等式約束，只考慮不等式約束，結(jié)論可方便的擴(kuò)展到等式約束。假設(shè)x0不可行，即存在某些i，使得fi(x)0。則選擇 ，對(duì)于其他乘子，假設(shè)x0可行，則有fi(x)0,(i=1,2,.,m),選擇有：40鞍點(diǎn)：最優(yōu)點(diǎn)而原問題是：從而，原問題的本質(zhì)為：而對(duì)偶問題，是求對(duì)偶函數(shù)的最大值，即：而：41證明：對(duì)于任意的(x,y)domf42線性方程的最小二乘問題原問題Lagrange函數(shù)Lagrange對(duì)偶函數(shù)對(duì)L求x的偏導(dǎo)，帶入L，得到g對(duì)g求v的偏導(dǎo)，求g的極大值，作為原問題的最小值43