最優(yōu)化模型與算法-基于Python實(shí)現(xiàn) 教案 ch02 凸函數(shù)

凸函數(shù)1．證明下列函數(shù)為凸函數(shù)(1)一元函數(shù) (2.5.1)其中，。(2)定義在上的幾何平均函數(shù) (2.5.2)略。2．已知函數(shù)為定義在上的凸函數(shù)，函數(shù) (2.5.3)證明：函數(shù)為上的凸函數(shù)．要證明函數(shù)f(x)=eg(x)-1是定義在Rn上的凸函數(shù)，需要判斷其二階導(dǎo)數(shù)是否非負(fù)。首先計(jì)算f(x)的一階和二階導(dǎo)數(shù)：f'(x)=8egzf"(a)=64egz由于函數(shù)s(x)是定義在Rn上的凸函數(shù)，即s"(x)≥0對(duì)于所有x∈R成立?，F(xiàn)在我們來(lái)研究函數(shù)f"(x)的符號(hào)。對(duì)于所有x∈R,有cgr>0。因此，f"(x)=64egx>0,即二階導(dǎo)數(shù)恒大于零。根據(jù)凸函數(shù)的定義，如果一個(gè)函數(shù)的二階導(dǎo)數(shù)恒大于等于零，則該函數(shù)是凸函數(shù)。因此，函數(shù)f(x)是定義在Rn上的凸函數(shù)。3．已知二元函數(shù)為處處有限的凸函數(shù)，設(shè)一元函數(shù)定義為 (2.5.4)證明：函數(shù)為凸函數(shù)。根據(jù)式子(2.5.4),我們有：g(x)=infyf(x這表示g(x)是函數(shù)f(z,y)在變量y上的下確界。由于f(x,y)是處處有限的凸函數(shù)，那么對(duì)于固定的x,函數(shù)f(x,y)關(guān)于y是凸函數(shù)。因此，對(duì)于任意的x1,x2和0≤θ≤1,我們有：f(x1,y)≥θf(wàn)(x1,y)+(1-θ)f(x2,y)取y1為使得θf(wàn)(x1,y1)+(1-θ)f(x2,y1)達(dá)到下確界g(x1)的值，即θf(wàn)(x1,y1)+(1-θ)f(x2,y1)=g(x1)。同樣，取y2為使得θf(wàn)(x1,y2)+(1-θ)f(x2,y2)達(dá)到下確界g(x2)的值，即θf(wàn)(x1,32)+(1-θ)f(x2,y2)=g(x2)。由于f(x,y)是凸函數(shù)，我們有：f(θx1+(1-θ)x2,θy1+(1-θ)y2)≤θf(wàn)(x1,y1)+(1-θ)f(x2,y2)取下確界得到：9(θx1+(1-θ)x2)≤θg(x1)+(1-θ)g(x2)因此，函數(shù)g(x)是凸函數(shù)。4．設(shè)函數(shù)為凸函數(shù)，證明函數(shù)的下卷積函數(shù) (2.5.5)為凸函數(shù)。要證明函數(shù)f(x)是凸函數(shù)，我們需要證明對(duì)于任意的x1,x2和0≤θ≤1,有f(θx1+(1-θ)x2)≤θf(wàn)(x1)+(1-θ)f(x2)。首先，我們來(lái)研究函數(shù)f(x)的定義。根據(jù)式子(2.5.5),我們有：f(x)=(f1*f2)(x)-inf{f1(x1)+f2(x2)|x1+2=x}這表示f(x)是函數(shù)f1(a1)+f2(x2)取下確界(infimum)時(shí)的差值。由于f1和f2均為凸函數(shù)，我們知道對(duì)于任意的x1,x2和0≤θ≤1,有：f1(θx1+(1-θ)x2)≤θf(wàn)i(x1)+(1-θ)f1(x2)f2(θx1+(1-θ)x2)≤θf(wàn)2(x1)+(1-θ)f2(x2)對(duì)于第一項(xiàng)(f1*f2)(x),我們可以使用Jensen不等式來(lái)處理。由于f1和f2均為凸函數(shù)，我們有：(f1*f2)(θx1+(1-θ)x2)≤θ(f1*f2)(x1)+(1-θ)(f1*f2)(x2)現(xiàn)在，我們來(lái)研究第二項(xiàng)inf{f1(x1)+f2(x2)|x1+x2=x}。我們要證明：inf{f1(θx1+(1-θ)x2)+f2(θx1+(1-θ)x2)|z1+x2=θx1+(1-θ)x2}≥θinf{f1(x1)+f2(x2)|c1+x2=x1}+(1-θ)inf{f1(x1)+f2(x2)|x1+2=2}也就是要證明：inf{f1(x1)+f2(x2)|x1+x2=x}≥θinf{f(x1)+f2(x2)|x1+x2=x1}+(1-θ)inf{f1(x1)+f2(x2)|x1+x2=2}根據(jù)下確界的性質(zhì)，左邊的下確界大于等于右邊的下確界，因此上述不等式成立。綜上所述，我們得到：f(θx1+(1-θ)x2)=(f1*f2)(θx1+(1-θ)x2)-inf{f1(θx1+(1-θ)x2)+f2(θx1+(1-θ)x2)|x1+x2=θx1+(1-θ)x2}≤θ(f1*f2)(a1)+(1-θ)(f1*f2)(a2)-θinf{f1(x1)+f2(x2)|x1+x2=x1}-(1-θ)inf{f1(x1)+f2(x2)|x1+x=x2}進(jìn)一步化簡(jiǎn)得到：≤θ[(f1*f2)(x1)-inf{f1(x1)+f2(x2)|x1+x2=x1}]+(1-θ)[(f1*f2)(x2)-inf{f1(x1)+f2(x2)|x1+x2=x2}]根據(jù)函數(shù)f(x)的定義，可以將上述不等式進(jìn)一步簡(jiǎn)化為：=θf(wàn)(x1)+(1-θ)f(x2)因此，我們證明了對(duì)于任意的x1,x2和0≤θ≤1,有f(θx1+(1-θ)x2)≤θf(wàn)(x1)+(1-θ)f(x2)。因此，函數(shù)f(x)是凸函數(shù)。凸性的二階條件。設(shè)函數(shù)，其中是中的凸集合且是開集，函數(shù)二階連續(xù)可微．證明：是集合上的凸函數(shù)當(dāng)且僅當(dāng)對(duì)任意的，半正定。略。6．分片線性凸函數(shù)的表示。函數(shù)，其定義域?yàn)椋环Q為分片線性函數(shù)，如果存在的一個(gè)劃分 (2.5.6)其中，且對(duì)任意，intint；以及一系列仿射函數(shù)使得對(duì)有，證明若是凸函數(shù)，有。略。7．函數(shù)的凸包。函數(shù)的凸包(或凸包絡(luò))定義為 (2.5.7)幾何上，函數(shù)的上圖是的上圖的凸包。證明如果函數(shù)是凸函數(shù)，且對(duì)所有有，則對(duì)所有有。略。8．推導(dǎo)下列函數(shù)的共軛函數(shù)。(a)二次函數(shù)， (2.5.8)其中為階對(duì)稱正定矩陣，，(b)一元函數(shù) (2.5.9)(c)函數(shù)， (2.5.10)(d)定義在上的冪函數(shù)，其中。如果呢？略。設(shè)為非空凸集合，距離函數(shù)，設(shè)函數(shù)，，證明：，其中，表示函數(shù)的下卷積函數(shù)，并求的共軛函數(shù)．的共軛函數(shù)為10．給定函數(shù)，其定義域?yàn)椤ＷC明的共軛函數(shù)為 (2.5.11)提示：函數(shù)的梯度為。略。11．集合的支撐函數(shù)我們知道集合的支撐函數(shù)定義為。在前文我們?cè)C明是凸函數(shù)。(a)凸集合為平面上-范數(shù)對(duì)應(yīng)的1-范數(shù)單位圓： (2.5.12)計(jì)算支撐函數(shù)。(b)證明。(c)證明。(d)證明。(e)設(shè)是閉凸集。證明的充要條件是，對(duì)任意有 (2.5.13)略。12．已知凸集合，為集合上的指示函數(shù)，，二元函數(shù)定義為 (2.5.14)設(shè)函數(shù)是由生成的正齊次凸函數(shù)，即。該正齊次凸函數(shù)稱為對(duì)應(yīng)于凸集合的度規(guī)函數(shù)，計(jì)算度規(guī)函數(shù)。略。13．計(jì)算下列函數(shù)的處的次微分：(1) (2.5.15)(2) (2.5.16)(3) (2.5.17)(4)