最優(yōu)化模型與算法-基于Python實(shí)現(xiàn) 課件全套 第1-6章 凸集合-凸優(yōu)化算法

凸集合最優(yōu)化模型與算法——基于Python實(shí)現(xiàn)第一章01仿射集、凸集和凸錐直線與線段是我們熟悉的幾何對(duì)象。如何對(duì)其定義呢？我們沿用解析幾何的思想，給出直線與線段的概念。設(shè)

為空間

中的兩個(gè)點(diǎn)，那么具有下列形式的點(diǎn)

(1.1.1)

構(gòu)成一條過

和

的直線。參數(shù)

對(duì)應(yīng)

，

對(duì)應(yīng)

。參數(shù)

的值在0和1之間變動(dòng)，

的軌跡構(gòu)成了

和

之間的(閉)線段。的表示形式給出了直線的另一種解釋，如圖1.1.1所示：是基點(diǎn)(對(duì)應(yīng))和方向(由指向)乘以參數(shù)的和。因此，給出了在由向方向上的位置。當(dāng)由0增加到1時(shí)，點(diǎn)相應(yīng)地由移動(dòng)到。如果，點(diǎn)在為端點(diǎn)的射線上。圖1.1.1直線的幾何解釋1.1.1直線與線段設(shè)集合，如果過中任意兩個(gè)不同點(diǎn)的直線仍然在集合中，則稱集合是仿射集。也就是說，是仿射的等價(jià)于：對(duì)于任意及，有即仿射集中任意兩點(diǎn)的系數(shù)之和為1的線性組合仍包含在中。明顯地，直線與平面都是仿射集。仿射集合的概念也可以擴(kuò)展到多個(gè)點(diǎn)的情況。如果

我們稱具有

形式的點(diǎn)為

的仿射組合。利用仿射集合的定義(即仿射集合包含其中任意兩點(diǎn)的仿射組合)，我們可以歸納出以下結(jié)論：一個(gè)仿射集包含其中任意點(diǎn)的仿射組合，即如果是一個(gè)仿射集，并且那么仍然在中。1.1.2仿射集特別地，如果一個(gè)仿射集經(jīng)過原點(diǎn)，那么稱該集合為子空間，即如果是一個(gè)仿射集并且，則集合(1.1.3)是一個(gè)子空間。子空間的一個(gè)重要性質(zhì)是關(guān)于加法和數(shù)乘是封閉的。為說明這一點(diǎn)，設(shè)，

，則有

。因?yàn)?/p>

是仿射的，且

，所以(1.1.4)。由，可知。因此仿射集合

可以表示為(1.1.5)即一個(gè)子空間加上一個(gè)偏移向量。與仿射集相關(guān)聯(lián)的子空間與的選取無關(guān)，所以可以是中的任意一點(diǎn)。我們定義仿射集的維數(shù)為子空間的維數(shù)，其中是中的任意元素。1.1.2仿射集下面給出仿射集的一個(gè)例子。例

1.1.1線性方程組的解集?？紤]線性方程組的解集，其中，，則是一個(gè)仿射集。為證明這點(diǎn)，設(shè)，，即則對(duì)于任意，有(1.1.6)這表明任意的仿射組合也在中，并且與仿射集相關(guān)聯(lián)的子空間就是的零空間。既然線性方程組的解集是空間中的一個(gè)仿射集，那么空間中的任意仿射集是否都可以表示為某個(gè)線性方程組的解集？如果該命題成立，那么我們便得到了空間中仿射集的代數(shù)描述。該命題是成立的，證明可參見[2]定理1.3。設(shè)是兩個(gè)不同的點(diǎn)，那么包含和的最小的仿射集是什么？答案是由和所確定的直線。這個(gè)問題蘊(yùn)含著仿射包的概念。由集合中的點(diǎn)的所有仿射組合組成的集合稱為的仿射包，記為(1.1.7)仿射包是包含的最小的仿射集合：如果是滿足的仿射集合，那么。1.1.2仿射集如果集合的仿射維數(shù)小于n，那么這個(gè)集合的仿射集合。集合相對(duì)于的內(nèi)部稱為集合相對(duì)內(nèi)部，記為，即(1.1.8)

其中，即半徑為r，中心為x并由范數(shù)定義的球(這里的可以是任意范數(shù)，并且所有范數(shù)定義了相同的相對(duì)內(nèi)部)。進(jìn)一步可以定義集合的相對(duì)邊界為，此處表示的閉包。集合的仿射包的維數(shù)稱為集合的仿射維數(shù)。仿射維數(shù)在凸分析及凸優(yōu)化中非常有用，然而它與經(jīng)典維數(shù)的定義不一致。例如，上的單位圓環(huán)的仿射包是全空間，所以其仿射維數(shù)為2。但在其他大多數(shù)維數(shù)的定義下，上的單位圓環(huán)的維數(shù)為1。1.1.3仿射維數(shù)與相對(duì)內(nèi)部例1.1.2考慮中位于平面的一個(gè)正方形：(1.1.9)其仿射包為-平面，即的內(nèi)部為空，但其相對(duì)內(nèi)部為(1.1.10)的邊界是其自身，而相對(duì)邊界是(1.1.11)1.1.3仿射維數(shù)與相對(duì)內(nèi)部上一小節(jié)介紹的仿射集是一類特殊的凸集合。下面介紹一般的凸集合的概念。如果集合中任意兩點(diǎn)間的線段仍然在中，則稱集合為凸集合，即對(duì)任意和滿足的都有

(1.1.12)直觀地理解，如果集合中的每一點(diǎn)都可以被其他點(diǎn)沿著它們之間一條“無阻礙”的路徑看見，那么這個(gè)集合就是凸集合。“無阻礙”是指整條路徑都在集合中。由于仿射集包含穿過集合中任意不同兩點(diǎn)的整條直線，任意不同兩點(diǎn)間的線段自然也在集合中。因而仿射集是凸集合。1.1.4凸集合圖1.1.2一些簡單凸集和非凸集1.1.4凸集合圖1.1.2

顯示了

空間中一些簡單的凸集合和非凸集合。其中，左邊的菱形集合，包括它的邊界是凸集合，中間的心形集合不是凸集合，因?yàn)榧现酗@示為點(diǎn)的兩點(diǎn)之間的線段不包含在集合中，右邊的正方形包含一些邊界點(diǎn)而不包含其他邊界點(diǎn)，不是凸集合。我們稱點(diǎn)

為點(diǎn)

的一個(gè)凸組合，其中

并

。與仿射集合類似，一個(gè)集合是凸集合等價(jià)于集合包含其中所有點(diǎn)的凸組合。點(diǎn)的凸組合可以看做它們的加權(quán)平均，

代表

的權(quán)重。設(shè)

是兩個(gè)不同的點(diǎn)，那么包含

和

的最小的凸集是什么？答案是以

和

為端點(diǎn)的線段。這個(gè)問題蘊(yùn)含著凸包的概念。集合

的凸包，記為

，定義如下：(1.1.13)顧名思義，凸包是凸集合，它是包含集合的最小的凸集。也就是說，如果是包含的凸集，那么。圖1.1.3展示了凸包的概念，其中左邊的六邊形(含內(nèi)部)是十五個(gè)點(diǎn)的凸包，右邊的腎形集合也是非凸集，其凸包是腎形集合(連同內(nèi)部)和陰影部分共同構(gòu)成的集合。1.1.4凸集合圖1.1.3

中兩個(gè)集合的凸包010203041.1.4凸集合凸集合的概念可以推廣到包括無限級(jí)數(shù)、積分以及一般形式的概率分布。假設(shè)

，滿足(1.1.14)并且，其中為凸集。那么，如果級(jí)數(shù)收斂，我們有(1.1.15)假設(shè)對(duì)所有滿足，并且，其中是凸集。那么，如果下面的積分存在，我們就有(1.1.16)最一般的情況，設(shè)

是凸集，

是隨機(jī)變量，并且

的概率為1，那么

。事實(shí)上，這一形式包含了前述的特殊情況。例如，假設(shè)隨機(jī)變量

只在

和

中取值，其概率分別是

和

其中

。于是，

，

即退化為兩個(gè)點(diǎn)的凸組合。1.1.5凸錐考慮從原點(diǎn)出發(fā)，經(jīng)過某一定點(diǎn)x的射線。它具有一項(xiàng)重要的特性，即對(duì)任意

，

依然包含于該射線中。這一例子蘊(yùn)含著錐的概念。如果對(duì)于任意

和

都有

，稱集合

是錐。如果集合

是錐，并且是凸集合，則稱

為凸錐，即對(duì)于任意

和

，都有(1.1.17)在幾何上，具有此類形式的點(diǎn)構(gòu)成了二維的扇形，如圖1.1.4所示，這個(gè)扇形以0為頂點(diǎn)，邊是過和的射線，包含所有具有形如的點(diǎn)，其中。圖1.1.4二維扇形1.1.5凸錐具有

形式的點(diǎn)稱為

的錐組合(或非負(fù)線性組合)。如果

均屬于凸錐

，那么，

的每一個(gè)錐組合也在

中。實(shí)際上，集合

是凸錐的充要條件，是它包含其元素的所有錐組合。集合中元素的所有錐組合的集合稱為集合的錐包，即

(1.1.18)集合的錐包是包含的最小的凸錐。圖1.1.5展示了兩個(gè)集合的錐包，左邊的集合由若干離散的點(diǎn)構(gòu)成，右邊的集合是一個(gè)腎形區(qū)域。圖1.1.5錐包02凸函數(shù)的示例1.2.1超平面和半空間超平面三維歐氏空間

中的一個(gè)平面可以表示為

，

其中

，

R。推廣至維n維歐氏空間

便得到了超平面的概念。超平面是具有下面形式的集合(1.2.1)其中，且。超平面是關(guān)于x的非平凡線性方程的解空間，因此是一個(gè)仿射集。幾何上，超平面可以解釋為與給定向量a的內(nèi)積為常數(shù)的點(diǎn)的集合，也可以看成法線方向?yàn)閍的超平面。常數(shù)決定了平面從原點(diǎn)的偏移量?？梢詫⒊矫姹硎境上旅娴男问?1.2.2)其中是超平面上任意滿足的點(diǎn)。進(jìn)一步，可以表示為(1.2.3)這里表示的正交補(bǔ)，即與正交的向量的集合(1.2.4)從上式可知，超平面由偏移加上所有正交于法向量的向量構(gòu)成。1.2.1超平面和半空間半空間一個(gè)超平面將

劃分為兩個(gè)半空間。閉的半空間是具有下列形式的集合，

(1.2.5)它是一個(gè)非平凡的線性不等式的解空間，其中

。半空間是凸的，但不是仿射的。半空間(1.2.5)也可表示為

(1.2.6)其中

是相應(yīng)超平面上的任意一點(diǎn)，即

滿足

，表達(dá)式(1.2.6)有明顯的幾何解釋：半空間由

加上任意與(向外的)法向量

呈鈍角(或直角)的向量組成。半空間(1.2.5)的邊界是超平面

。集合

是半空間

的內(nèi)部，稱為開半空間。1.2.2歐氏球和橢球歐氏球

中的空間歐氏球(簡稱球)具有下面的形式(1.2.7)其中，表示歐幾里得范數(shù)，即。向量是球心，標(biāo)量為半徑。由距離球心距離不超過的所有點(diǎn)組成。歐氏球的另一個(gè)常見的表達(dá)式為(1.2.8)歐氏球是凸集，即如果，并且，那么

(1.2.9)歐氏球?qū)?yīng)于歐幾里得范數(shù)。如果將歐幾里得范數(shù)進(jìn)行拓展，相應(yīng)地可得到歐氏球的拓展—橢球。橢球橢球是凸集合，是歐氏球的拓展，具有如下形式(1.2.10)其中，即是對(duì)稱正定矩陣。向量為橢球的中心。橢球的半軸長度為，這里為的特征值。球可以看成時(shí)的橢球。橢球另一個(gè)常用的表示形式是(1.2.11)其中是對(duì)稱正定陣。取，則表達(dá)式等價(jià)于(1.2.10)式。當(dāng)式(1.2.11)中的矩陣為對(duì)稱半正定矩陣，且為奇異矩陣時(shí)，集合(1.2.11)稱為退化的橢球，其仿射維數(shù)等于的秩。退化的橢球也是凸的。非退化的橢球聯(lián)系于一個(gè)新的范數(shù)，那任意一個(gè)范數(shù)是否也對(duì)應(yīng)一個(gè)幾何對(duì)象“球”呢？答案是肯定的，這便是范數(shù)球。1.2.2歐氏球和橢球設(shè)

為

空間的某一范數(shù)，則以為半徑，

為球心的

集合稱為范數(shù)球。明顯地，范數(shù)球是凸的?？臻g的每一個(gè)范數(shù)實(shí)際上還對(duì)應(yīng)一個(gè)錐。集合(1.2.12)稱為關(guān)于范數(shù)的范數(shù)錐。明顯地，它是一個(gè)凸錐。1.2.3范數(shù)球和范數(shù)錐1.2.4多面體上面的小節(jié)介紹了多面體和超平面的概念，再由交運(yùn)算便可以得到多面體。有限個(gè)線性等式和不等式的解集稱為多面體，即

(1.2.13)可見，多面體是有限個(gè)半空間和超平面的交集?？梢允褂镁o湊表達(dá)式(1.2.14)來表示(1.2.5)式。其中(1.2.15)此處的表示上的分量不等式，即表示。上面小節(jié)中介紹了若干空間中凸集合的例子。下面的例子給出了矩陣空間中的一個(gè)凸集合。用表示對(duì)稱矩陣的集合，即(1.2.16)這是一個(gè)維數(shù)為的向量空間。我們用表示對(duì)稱半正定矩陣的集合，即(1.2.17)用表示對(duì)稱正定矩陣的集合，即(1.2.18)這些符號(hào)與相對(duì)應(yīng)，即表示非負(fù)實(shí)數(shù)，而表示正實(shí)數(shù)。集合是一個(gè)凸錐：如果并且，那么。依據(jù)半正定矩陣的定義可以直接驗(yàn)證這個(gè)結(jié)論：對(duì)于任意，如果并且

，那么，我們有(1.2.19)1.2.5半正定錐03保持凸性的運(yùn)算交集運(yùn)算保持凸性：如果和是凸集，那么也是凸集。這個(gè)性質(zhì)可以擴(kuò)展到無窮個(gè)集合的交集：定理1.3.1如果對(duì)于任意，都是凸的，那么也是凸集。特別地，子空間、仿射集合和凸錐對(duì)于任意交運(yùn)算也是封閉的。舉一個(gè)簡單的例子，多面體是半空間和超平面(它們都是凸集)的交集，因而是凸的。例1.3.1半正定錐可以表示為(1.3.1)對(duì)于任意是關(guān)于的(不恒等于零的)線性函數(shù)，因此集合(1.3.2)實(shí)際上就是中的半空間。由此可見，半正定錐是無窮個(gè)半空間的交集，因此是凸集合。1.3.1交集一個(gè)凸集合在何種變換之下可以依然保持凸性。這樣的變換有多種，應(yīng)用最廣泛的是仿射變換。定理1.3.2如果是一個(gè)線性變換和常數(shù)的和，則稱函數(shù)是仿射變換。即具有的形式，其中。假設(shè)是凸集合，并且函數(shù)是仿射變換，那么，在下的像集(1.3.3)也是凸集合。類似地，如果是仿射函數(shù)，那么在下的原像(1.3.4)也是凸集合。1.3.2仿射變換(4)部分和。下面的集合稱為的部分和：(1.3.8)其中，。當(dāng)m=0時(shí)，部分和退化為和的交集；當(dāng)n=0時(shí)，部分和等于?？梢则?yàn)證，兩個(gè)凸集合的部分和仍是凸集合。下面僅驗(yàn)證(3)中集合的和的凸性。的凸性可以直接通過凸集合的定義證明。此外，還可以通過下面的方法證明這個(gè)結(jié)論：如果和是凸集合，那么其直積(也稱為Cartesian乘積)(1.3.9)也是凸集。例1.3.2此例給出若干凸集合在仿射變換下的像集(1)伸縮和平移。如果是凸集，并且那么集合和是凸集合，其中(1.3.5)(2)一個(gè)凸集合向它的某幾個(gè)坐標(biāo)的投影仍是凸集合，即如果是凸集合，那么(1.3.6)也是凸集合。(3)兩個(gè)集合的和定義為(1.3.7)如果和是凸集，那么也是凸集合。1.3.2仿射變換這個(gè)集合在仿射變換下的像是。這種證明手法具有代表性，請(qǐng)讀者自行構(gòu)造恰當(dāng)?shù)姆律渥儞Q，證明其余的集合的凸性。實(shí)際上，許多重要的凸集合都可以使用上面的方法來驗(yàn)證其凸性。舉例如下。例1.3.3多面體多面體是凸集合。因?yàn)樗梢员硎緸榉秦?fù)象限和原點(diǎn)的Cartesian乘積在仿射函數(shù)下的原像，即(1.3.10)例1.3.4線性矩陣不等式的解。條件(1.3.11)稱為關(guān)于x的線性矩陣不等式(LMI)，其中，。線性矩陣不等式的解是凸集合。事實(shí)上，它是半正定錐在仿射映射下的原像。例1.3.5雙曲錐。集合(1.3.12)是凸集，其中。因?yàn)樗嵌A錐(1.3.13)在仿射函數(shù)下的原像。1.3.2仿射變換04支撐超平面1.4支撐超平面前面介紹的凸集合的概念是借助凸集合內(nèi)的點(diǎn)進(jìn)行刻畫的，另外，凸集合還可以從外部借助支撐超平面來刻畫。同時(shí)，支撐超平面與下一章要介紹的凸函數(shù)的次微分聯(lián)系緊密。設(shè)，是其邊界上的一點(diǎn)，即(1.4.1)如果，并且對(duì)任意滿足，那么稱超平面為集合在點(diǎn)處的支撐超平面，即與集合被超平面分離。其幾何解釋如圖1.4.1所示：超平面與相切于點(diǎn)，而且半空間包含。圖1.4.1超平面

在

處支撐1.4支撐超平面一個(gè)基本的結(jié)論是支撐超平面定理：對(duì)于任意非空的凸集和任意，在處存在的支撐超平面。支撐超平面定理的證明本質(zhì)上依賴于凸集合分離定理。有興趣的讀者可以參見文獻(xiàn)[2]中推論11.6.2。一件引人注意的事情是支撐超平面定理的逆命題。當(dāng)集合滿足一定條件時(shí)，支撐超平面定理的逆命題也成立：如果一個(gè)集合是閉的，具有非空內(nèi)部，并且其邊界上每個(gè)點(diǎn)均存在支撐超平面，那么它是凸集合。該命題給出了凸集的另一種刻畫方式。05對(duì)偶錐許多數(shù)學(xué)運(yùn)算及幾何形體都是成對(duì)出現(xiàn)的。例如，加法和減法互為逆運(yùn)算，指數(shù)和對(duì)數(shù)互為反函數(shù)。前文介紹的凸錐也是成對(duì)出現(xiàn)的，這便是本節(jié)要介紹的對(duì)偶錐。令為一個(gè)錐。集合被稱為的對(duì)偶錐。顧名思義，是一個(gè)錐，即使原來的錐不是凸的，也總是凸的。幾何上，當(dāng)且僅當(dāng)是支撐原點(diǎn)的超平面的法線。如圖1.5.1所示，左圖中，法線向內(nèi)的半空間包含錐，所以。右圖中，法線向內(nèi)的半空間不包含，所以。1.5對(duì)偶錐圖1.5.1對(duì)偶錐1.5對(duì)偶錐下面給出幾個(gè)常見的錐的對(duì)偶錐。例1.5.1子空間是一個(gè)錐。它的對(duì)偶錐是其正交補(bǔ)例1.5.2非負(fù)卦限。錐的對(duì)偶錐是它本身(1.5.1)我們稱這種錐為自對(duì)偶錐。例1.5.3半正定錐。記對(duì)稱矩陣的集合為，我們使用其標(biāo)準(zhǔn)內(nèi)積半正定錐是自對(duì)偶的，即對(duì)于任意的，(1.5.2)下面，我們證明這一結(jié)論。假設(shè)，那么存在使(1.5.3)因此，正半定矩陣滿足，由此可知。假設(shè)，我們可以利用特征值分解將分解為，其中特征值。于是，我們有(1.5.4)例1.5.4范數(shù)錐的對(duì)偶。令為定義在上的范數(shù)。與之相關(guān)的錐的對(duì)偶錐由其對(duì)偶范數(shù)定義，(1.5.5)這里的對(duì)偶范數(shù)。請(qǐng)讀者依據(jù)對(duì)偶錐的定義嘗試給出證明。上面給出了若干對(duì)偶錐的例子，我們指出對(duì)偶錐滿足一些基本的性質(zhì)：是閉凸錐?？蓪?dǎo)出是的凸包的閉包。因此，如果是閉凸錐，則。除了本小節(jié)介紹的對(duì)偶錐的定義之外，文獻(xiàn)中有多種類似的“對(duì)偶錐”的定義，如文獻(xiàn)[2]中第14節(jié)定義的極錐。1.5對(duì)偶錐謝謝觀看凸函數(shù)最優(yōu)化模型與算法——基于Python實(shí)現(xiàn)第二章01凸函數(shù)的定義和例子一些常見的初等函數(shù)，如一元函數(shù)

等，具有共同的形態(tài)，即函數(shù)曲線凸向下方，具有這種形態(tài)的函數(shù)稱為凸函數(shù)。定義2.1.1函數(shù)

是凸的，如果

是凸集，且對(duì)于任意

和任意

，有

(2.1.1)

則稱

為凸函數(shù)。圖2.1.1凸函數(shù)示意圖從幾何上看，上述不等式意味著連接點(diǎn)

和

之間的線段，在函數(shù)

的圖像上方(如圖2.1.1所示)。如果(2.1.1)式中的不等式當(dāng)

以及

時(shí)嚴(yán)格成立，那么稱函數(shù)

是嚴(yán)格凸的。如果

是凸的，那么我們稱函數(shù)

為凹的；如果

是嚴(yán)格凸的，那么稱函數(shù)

為嚴(yán)格凹的。2.1.1凸函數(shù)的概念對(duì)于仿射函數(shù)，不等式(2.1.1)總成立，因此所有的仿射函數(shù)是既凸又凹的。反之，若某個(gè)函數(shù)是既凸又凹的，則它是仿射函數(shù)。函數(shù)是凸的，當(dāng)且僅當(dāng)該函數(shù)在與其定義域相交的任何直線上都是凸的。換言之，函數(shù)

是凸的，當(dāng)且僅當(dāng)對(duì)于任意

和任意向量

，函數(shù)

在其定義域

中是凸的。這個(gè)性質(zhì)非常有用，因?yàn)樗菰S我們將函數(shù)限制在直線上來判斷其是否是凸函數(shù)。2.1.1凸函數(shù)的概念通?？梢远x凸函數(shù)在定義域外的值為

，從而將這個(gè)凸函數(shù)延拓至全空間

。如果

是凸函數(shù)，那么我們定義它的值拓展函數(shù)

如下：(2.1.2)值拓展函數(shù)是定義在全空間上的，取值集合為。我們也可以從值拓展函數(shù)的定義中確定原函數(shù)的定義域，即。這種拓展可以簡化符號(hào)描述，我們不需要明確描述定義域或者每次提到時(shí)都限定“對(duì)所有的”。以基本不等式(2.1.1)為例，對(duì)值拓展函數(shù)可以描述為：對(duì)任意和，以及，有(2.1.3)(當(dāng)或時(shí)不等式總成立)當(dāng)然此時(shí)我們應(yīng)當(dāng)利用擴(kuò)展運(yùn)算來理解這個(gè)不等式。若和都在內(nèi)，上述不等式即為不等式(2.1.1)，如果有任何一個(gè)在外，上述不等式的右端為，不等式仍然成立。值拓展函數(shù)2.1.1凸函數(shù)的概念再看一個(gè)例子，設(shè)

和

是

上的兩個(gè)凸函數(shù)，逐點(diǎn)和函數(shù)

的定義域?yàn)?/p>

，對(duì)于任意

有

。利用值拓展函數(shù)我們可以簡單地描述為，對(duì)于任意

，

，其中，函數(shù)

的定義域被自動(dòng)定義為

，因?yàn)楫?dāng)

或者

時(shí)，

。在有些文獻(xiàn)中，凸函數(shù)的值域被拓展為

。在這種情況下，如果一個(gè)凸函數(shù)取不到

，并且它能取有限值，那么稱這樣的凸函數(shù)為恰當(dāng)凸函數(shù)。本書如果沒有特別聲明，所提到的凸函數(shù)均指恰當(dāng)凸函數(shù)。在不造成歧義的情況下，本書將用同樣的符號(hào)來表示一個(gè)凸函數(shù)及其值拓展函數(shù)，即假設(shè)所有的凸函數(shù)都隱含地被拓展了，也就是在定義域外都被定義為?！啊?.1.1凸函數(shù)的概念例2.1.1凸集的示性函數(shù)。設(shè)是一個(gè)凸集，考慮凸函數(shù)其定義域?yàn)?，?duì)于所有的，。換言之，此函數(shù)在集合上取值為零，其延拓函數(shù)可以描述如下(2.1.4)凸函數(shù)被稱作集合的示性函數(shù)。利用示性函數(shù)，可以更加方便地描述問題。例如，對(duì)于在集合上極小化函數(shù)(假設(shè)其定義在整個(gè)空間)的問題，可以給出等價(jià)地描述為：在上極小化函數(shù)。上面介紹了凸函數(shù)的概念及其值拓展函數(shù)。對(duì)于某一特定的函數(shù)，如何判斷其是否是凸函數(shù)呢。下面我們分別假定函數(shù)是一階可微和二階可微的，對(duì)其進(jìn)行分析，分別給出函數(shù)是凸函數(shù)的一階條件和二階條件。“”2.1.1凸函數(shù)的概念定理2.1.1(一階凸性條件)假設(shè)

可微(即其梯度

在開集

內(nèi)處處存在)，則函數(shù)

是凸函數(shù)的充要條件是

內(nèi)是凸集且對(duì)于任意

內(nèi)下式成立

(2.1.5)

如圖2.1.2所示，上述不等式意味著凸函數(shù)的函數(shù)圖像將位于定義域內(nèi)任意一點(diǎn)切線的上方。由得出的仿射函數(shù)即為函數(shù)在點(diǎn)附近Taylor近似。不等式(2.1.5)表明，對(duì)于一個(gè)凸函數(shù)，其一階Taylor近似實(shí)質(zhì)上是原函數(shù)的一個(gè)全局下估計(jì)。反之，如果某個(gè)函數(shù)的一階Taylor近似總是其全局下估計(jì)，那么這個(gè)函數(shù)是凸的。圖2.1.2凸函數(shù)的一階條件2.1.1凸函數(shù)的概念不等式(2.1.5)說明從一個(gè)凸函數(shù)的局部信息，即它在某點(diǎn)的函數(shù)值及梯度，我們可以得到一些全局信息(如它的全局下估計(jì))。這也許是凸函數(shù)的最重要的信息，由此可以解釋凸函數(shù)以及凸優(yōu)化問題的一些非常重要的性質(zhì)。下面是一個(gè)簡單的例子，由不等式(2.1.5)可以知道，如果

那么對(duì)于所有的

，存在

，即

是函數(shù)

的全局極小點(diǎn)。另一個(gè)著名的例子是第6章中介紹的在線凸優(yōu)化算法，其遺憾界的估計(jì)本質(zhì)上依賴于不等式(2.1.5)。嚴(yán)格凸性同樣可以由一階條件刻畫：函數(shù)

嚴(yán)格凸的充要條件是

是凸集且對(duì)任意

，有

(2.1.6)對(duì)于凹函數(shù)，亦存在與之對(duì)應(yīng)的一階條件：函數(shù)

是凹函數(shù)的充要條件是

是凸集且對(duì)于任意

，有下式成立

(2.1.7)2.1.1凸函數(shù)的概念下面考慮定理2.1.1的證明。證明思路充分利用凸函數(shù)的性質(zhì)：函數(shù)

是凸函數(shù)當(dāng)且僅當(dāng)函數(shù)限定在定義域內(nèi)任意一條直線上是凸的。因此，首先證明函數(shù)

是一元的情況時(shí)，命題成立，再將函數(shù)

為n元函數(shù)的情形化歸為一元函數(shù)。證明：為了證明(2.1.5)，先考慮

的情況。我們證明可微函數(shù)

是凸函數(shù)的充要條件是對(duì)

內(nèi)的任意

和

有

(2.1.8)首先假設(shè)

是凸函數(shù)，且

。因?yàn)?/p>

是凸集(某個(gè)區(qū)間)，對(duì)于任意

我們有

。由函數(shù)

的凸性可得

(2.1.9)

將上式兩端同除t可得

(2.1.10)

令t→0，可以得到不等式(2.1.8)。為了證明充分性，假設(shè)對(duì)

(某個(gè)區(qū)間)內(nèi)的任意

和

，函數(shù)滿足不等式(2.1.8)。選擇任意

且

。令

。兩次應(yīng)用不等式可得

(2.1.11)將第一個(gè)不等式乘以

，第二個(gè)不等式乘以

，并將二者相加可得

(2.1.12)從而說明了函數(shù)是凸的。2.1.1凸函數(shù)的概念現(xiàn)在來證明一般情況，即

。設(shè)

，考慮過這兩點(diǎn)的直線上的函數(shù)

，即函數(shù)

，此函數(shù)對(duì)

求導(dǎo)可得

。首先假設(shè)函數(shù)

是凸的，則函數(shù)

是凸的，由前面的討論可得

，即

(2.1.13)再假設(shè)此不等式對(duì)于任意和均成立。因此，若以及，我們得到(2.1.14)即，說明函數(shù)是凸的。證畢?，F(xiàn)在假設(shè)函數(shù)二階可微，不妨假設(shè)函數(shù)為一元函數(shù)，則對(duì)于開集內(nèi)的任意一點(diǎn)，它的二階導(dǎo)數(shù)存在，考慮函數(shù)的凸性是否可用二階導(dǎo)數(shù)刻畫?？紤]簡單的一元二次函數(shù)的情形：此時(shí)函數(shù)為凸函數(shù)當(dāng)且僅當(dāng)函數(shù)曲線開口向上，即。此外，若函數(shù)退化為一次函數(shù)，即時(shí)，則函數(shù)仍為凸函數(shù)。綜上所述，對(duì)于一元二次函數(shù)，若允許二次項(xiàng)的系數(shù)退化，則為凸函數(shù)當(dāng)且僅當(dāng)對(duì)任意，。這一結(jié)論對(duì)于一般的二階可微函數(shù)是否成立？下面的定理給出了肯定的回答。2.1.1凸函數(shù)的概念定理2.1.2假設(shè)函數(shù)

二階可微，即對(duì)于開集

內(nèi)的任意一點(diǎn)，它的Hessian矩陣或者二階導(dǎo)數(shù)

存在，則函數(shù)

是凸函數(shù)的充要條件是其Hessian矩陣是半正定陣，即對(duì)于所有的

有

(2.1.15)

對(duì)于上的函數(shù)，上式可以簡化為(是凸的，即一個(gè)區(qū)間)，此條件說明函數(shù)的導(dǎo)數(shù)是非減的。條件從幾何上可以理解為函數(shù)圖像在點(diǎn)x處具有正的曲率。關(guān)于二階條件的證明作為習(xí)題留給讀者完成。類似地，函數(shù)

是凹函數(shù)的充要條件是

是凸集且對(duì)于任意

，有

。嚴(yán)格凸的條件可以由二階條件刻畫。如果對(duì)于任意的

有

，則函數(shù)

嚴(yán)格凸。但逆命題不一定成立，例如，函數(shù)

，其表達(dá)式為

，它是嚴(yán)格凸的，但在

處，二階導(dǎo)數(shù)為零。2.1.1凸函數(shù)的概念添加標(biāo)題例2.1.2二次函數(shù)。考慮二次函數(shù)

，其定義域?yàn)?/p>

，其表達(dá)式為

(2.1.16)其中

。因?yàn)閷?duì)于任意

，所以函數(shù)

是凸的，當(dāng)且僅當(dāng)

。對(duì)于二次函數(shù)，嚴(yán)格凸比較容易表達(dá)，函數(shù)

是嚴(yán)格凸的，當(dāng)且僅當(dāng)

(函數(shù)是嚴(yán)格凹的當(dāng)且僅當(dāng)

)。在判斷函數(shù)的凸性和凹性時(shí)，不管是一階條件還是二階條件，

是凸集這個(gè)前提條件必須滿足的。例如，考慮函數(shù)

，其定義域?yàn)?/p>

，對(duì)于所有

均滿足

，但是函數(shù)

并不是凸函數(shù)。2.1.1凸函數(shù)的概念前文已經(jīng)提到所有的線性函數(shù)和仿射函數(shù)均為凸函數(shù)(同時(shí)也是凹函數(shù))，并描述了凸和凹的二次函數(shù)。下面給出更多的凸函數(shù)和凹函數(shù)的例子。首先考慮—元函數(shù)，其自變量記為x。例2.1.3一元凸函數(shù)指數(shù)函數(shù)。對(duì)任意

，函數(shù)

在

上是凸的。冪函數(shù)。當(dāng)

或

時(shí)，

在

上是凸函數(shù)，當(dāng)

，

在

上是凹函數(shù)。絕對(duì)值冪函數(shù)。當(dāng)

時(shí)，函數(shù)

在

上是凸函數(shù)。對(duì)數(shù)函數(shù)。函數(shù)

在

上是凹函數(shù)。負(fù)熵函數(shù)。函數(shù)

在其定義域上是凸函數(shù)。定義域?yàn)?/p>

或者

，當(dāng)

時(shí)定義函數(shù)值為0。我們可以通過基本不等式(2.1.1)或者二階導(dǎo)數(shù)半正定或半負(fù)定來判斷上述函數(shù)是凸的或是凹的。以函數(shù)

為例，其導(dǎo)數(shù)和二階導(dǎo)數(shù)分別為

(2.1.17)因此對(duì)于

，有

。所以負(fù)熵函數(shù)是嚴(yán)格凸的。2.1.2凸函數(shù)的例子下面我們給出

上的一些凸函數(shù)的例子。例2.1.4n元凸函數(shù)。范數(shù)。

上的任意范數(shù)均為凸函數(shù)。最大值函數(shù)。函數(shù)

在

上是凸函數(shù)。二次一次線性分式函數(shù)。

，其定義域?yàn)?/p>

(2.1.18)

該函數(shù)是凸函數(shù)，函數(shù)圖像如圖2.1.3所示：圖2.1.3

的圖像2.1.2凸函數(shù)的例子指數(shù)和的對(duì)數(shù)。函數(shù)在是凸函數(shù)。這個(gè)函數(shù)可以看成最大值函數(shù)的解析近似函數(shù)，因?yàn)閷?duì)任意x，下面的不等式成立(2.1.19)第二個(gè)不等式中當(dāng)x的所有分量都相等時(shí)是緊的。圖2.1.4描述了時(shí)函數(shù)的圖像幾何平均值。幾何平均值函數(shù)在定義域上是凹函數(shù)。對(duì)數(shù)行列式。函數(shù)在定義域是凹函數(shù)。

判斷上述函數(shù)的凸性(或者凹性)有多種途徑，可以直接驗(yàn)證不等式是否成立，亦可以驗(yàn)證其Hessian矩陣是否半正定，或者可以將函數(shù)轉(zhuǎn)換到與其定義域相交的任意直線上，通過得到的一元函數(shù)判斷原函數(shù)的凸性。2.1.2凸函數(shù)的例子圖2.1.4

的圖像直觀地說，如果一個(gè)函數(shù)比線性函數(shù)增長得快，那么它就是強(qiáng)凸函數(shù)。為了給出一個(gè)精確的定義，回想一下對(duì)于凸函數(shù)

，在任意點(diǎn)

，我們可以找到一個(gè)線性函數(shù)(切線)，它在

處等于

，在其他任何點(diǎn)不超過

。如果

嚴(yán)格位于切線的上方，且函數(shù)

與切線的差滿足下述數(shù)量關(guān)系，則

是強(qiáng)凸的。強(qiáng)凸函數(shù)定義如下。定義2.1.2函數(shù)

關(guān)于范數(shù)

在

上是

-強(qiáng)凸的，如果任何

，有

(2.1.20)

強(qiáng)凸函數(shù)的示意圖，如圖2.1.5所示，其中函數(shù)

與其在

處切線的距離至少為

。圖2.1.5強(qiáng)凸函數(shù)2.1.3強(qiáng)凸性強(qiáng)凸函數(shù)的一個(gè)重要性質(zhì)如下。定理2.1.3設(shè)

為非空凸集，函數(shù)

關(guān)于范數(shù)

在

上是

-強(qiáng)凸的，

，則對(duì)所有

有

。證明：首先假設(shè)

是可微的，

是在

的內(nèi)部，即

，根據(jù)強(qiáng)凸的定義，有

。

若

在

的邊界上，仍然有對(duì)所有的

，

(否則

就不是最優(yōu)的，我們可以向

方向移動(dòng)以降低

的值)。因此，目標(biāo)不等式依然成立。最后，給出

不可微條件下的證明。將

的定義域延拓到全空間，設(shè)

滿足

如果

，否則

。因此，有

。由于

是一個(gè)恰當(dāng)凸函數(shù)，所以有

。通過使用

的強(qiáng)凸性可推出目標(biāo)不等式。證畢。如果函數(shù)

是二次可微的，則容易驗(yàn)證

強(qiáng)凸的條件是對(duì)所有

，

，其中

是

在

處的Hessian矩陣。2.1.3強(qiáng)凸性例2.1.5(歐式正則化項(xiàng))函數(shù)關(guān)于范數(shù)是1-強(qiáng)凸的。要說明這一點(diǎn)，只需注意到在任意點(diǎn)處的Hessian矩陣是單位矩陣。以下定理給出了強(qiáng)凸函數(shù)其他有用的性質(zhì)，其證明可以依據(jù)強(qiáng)凸的定義得到。定理2.1.4如果是上關(guān)于某個(gè)范數(shù)1-強(qiáng)凸的，那么是關(guān)于同一個(gè)范數(shù)是-強(qiáng)凸函數(shù)。此外，如果是的凸子集，則在上也是1-強(qiáng)凸的。2.1.3強(qiáng)凸性凸函數(shù)自然地誘導(dǎo)出若干凸集合。常用的有下水平集和上圖。下水平集定義2.1.3函數(shù)的下水平集定義為。對(duì)于任意的，凸函數(shù)的下水平集仍然是凸集合。證明可以由凸集的定義直接得到：如果，則有，因此對(duì)任意，即。反之，逆命題未必成立：一個(gè)函數(shù)的所有下水平集都是凸集合，但函數(shù)本身未必是凸函數(shù)。例如，在上不是凸的(實(shí)際上，它嚴(yán)格是凹的)，但是其所有下水平集都是凸的。如果是凹函數(shù)，則由給出的上水平集是凸集。下水平集的性質(zhì)可以用來判斷集合的凸性，若某個(gè)集合可以描述為一個(gè)凸函數(shù)的下水平集，或者一個(gè)凹函數(shù)的上水平集，則它是凸集合。上圖定義2.1.4函數(shù)的圖像定義為(2.1.21)它是空間的一個(gè)子集。函數(shù)的上圖定義為(2.1.22)它也是空間的一個(gè)子集。是“之上”的意思，所以上圖的英文epigraph是“在函數(shù)圖像之上＂的意思。圖2.1.5的陰影部分是函數(shù)的上圖，深顏色的下邊界是函數(shù)的圖像。2.1.4其他凸集合和凸不等式凸集和凸函數(shù)的聯(lián)系可以通過上圖來建立，如下面的定理所述：定理2.1.5—個(gè)函數(shù)是凸函數(shù)，當(dāng)且僅當(dāng)其上圖是凸集；一個(gè)函數(shù)是凹函數(shù)，當(dāng)且僅當(dāng)其亞圖(2.1.23)是凸集。該結(jié)論的證明可以參見文獻(xiàn)[1]中的定理5.3。此結(jié)論雖然直觀上較為自然，卻具有重要的價(jià)值。它在凸集(幾何對(duì)象)和凸函數(shù)(分析學(xué)研究對(duì)象)之間建立了一座橋梁。作為一個(gè)例子，考慮關(guān)于可微凸函數(shù)滿足的不等式：(2.1.24)其中函數(shù)是凸的，。我們可以利用epi從幾何角度理解上述基本不等式。如果epi，有(2.1.25)上式可以等價(jià)地描述為(2.1.26)如圖2.1.7所示，向量定義了函數(shù)在點(diǎn)處上圖epi的一個(gè)支撐超平面。圖2.1.6函數(shù)的上圖圖2.1.7上圖的支撐超平面2.1.4其他凸集合和凸不等式Jensen不等式及其擴(kuò)展凸函數(shù)所滿足的基本不等式：對(duì)于任意，有(2.1.27)有時(shí)也稱作Jensen不等式。此不等式可以擴(kuò)展至更多點(diǎn)的凸組合。如果函數(shù)是凸函數(shù)，且，則下式成立(2.1.28)此不等式可以擴(kuò)展至無窮項(xiàng)和、積分以及期望。例如，如果在上且，則當(dāng)相應(yīng)的積分存在時(shí)，下式成立(2.1.29)擴(kuò)展到更一般的情況，我們可以采用支撐集屬于的任意概率測度。如果是隨機(jī)變量，事件發(fā)生的概率為1，函數(shù)是凸函數(shù)，當(dāng)相應(yīng)的期望存在時(shí)，我們有(2.1.30)設(shè)隨機(jī)變量的可能取值為，相應(yīng)地取值概率為(2.1.31)則由一般不等式(2.1.31)可以得到基本不等式(2.1.1)。上述所有不等式均被稱為Jensen不等式，而實(shí)際上最初由Jensen提出的不等式相當(dāng)簡單。對(duì)于任意有(2.1.32)請(qǐng)讀者思考，上述不等式如果對(duì)于任意成立，是否與(2.1.28)式等價(jià)？2.1.4其他凸集合和凸不等式02保持凸性的運(yùn)算01020304上一節(jié)，我們已經(jīng)了解了若干具體的凸函數(shù)，為了研究或構(gòu)造多種多樣的凸函數(shù)，基本的方法是使用保持函數(shù)凸性的運(yùn)算。非負(fù)加權(quán)求和顯然，如果函數(shù)

是凸函數(shù)且

，則函數(shù)

也是凸函數(shù)。如果函數(shù)

和

都是凸函數(shù)，則它們的和

也是凸函數(shù)。將非負(fù)伸縮以及求和運(yùn)算結(jié)合起來，可以看出，凸函數(shù)的集合本身是一個(gè)凸錐，凸函數(shù)的非負(fù)加權(quán)組和仍然是凸函數(shù)，即函數(shù)

(2.2.1)是凸函數(shù)。類似地，凹函數(shù)的非負(fù)加權(quán)求和仍然是凹函數(shù)。嚴(yán)格凸函數(shù)的非負(fù)，非零加權(quán)組和是嚴(yán)格凸函數(shù)。這個(gè)性質(zhì)可以擴(kuò)展至無限項(xiàng)的求和以及積分的情形。例如，如果固定任意

，函數(shù)

關(guān)于

是凸函數(shù)，且對(duì)任意

有

，若下式中的積分存在，則函數(shù)

(2.2.2)關(guān)于

是凸函數(shù)。我們可以很容易驗(yàn)證非負(fù)伸縮變換以及求和運(yùn)算是保持凸性的運(yùn)算，可以使用上圖作具體結(jié)論。例如，如果

且

是凸函數(shù)，我們有

(2.2.3)因?yàn)橥辜ㄟ^線性變換得到的像仍然是凸集，所以

是凸集。2.2保持凸性的運(yùn)算復(fù)合仿射映射假設(shè)函數(shù)

，以及

，定義

為

(2.2.4)

其中

若函數(shù)

是凸函數(shù)，則函數(shù)

是凸函數(shù)；如果函數(shù)

是凹函數(shù)，那么函數(shù)

是凹函數(shù)。逐點(diǎn)最大和逐點(diǎn)上確界假設(shè)函數(shù)

，

均為凸函數(shù)，則

和

均為凸集合。因此，

也是凸集合，這個(gè)凸集合正是函數(shù)

和

的逐點(diǎn)最大值函數(shù)

的上圖。因此，由定理2.1.5得到如下結(jié)論。定理2.2.1如果函數(shù)

和

均為凸函數(shù)，則二者的逐點(diǎn)最大值函數(shù)

有

(2.2.5)仍然是凸函數(shù)，其定義域?yàn)?/p>

。2.2保持凸性的運(yùn)算下面依據(jù)凸函數(shù)的定義給出證明。證明：任取

以及

，有

從而說明了函數(shù)的凸性。證畢。(2.2.6)同樣可以證明，如果函數(shù)為凸函數(shù)，則它們的逐點(diǎn)最大函數(shù)有(2.2.7)仍然是凸函數(shù)。特別地，(2.2.8)定義了一個(gè)分片線性(實(shí)際上是仿射)函數(shù)，它具有L個(gè)或者更少的子區(qū)域，因?yàn)樗且幌盗蟹律浜瘮?shù)的逐點(diǎn)最大值函數(shù)，所以它是凸函數(shù)。2.2保持凸性的運(yùn)算如下例所示，基于定理2.2.1，可以驗(yàn)證一些重要的函數(shù)的凸性。例2.2.1最大個(gè)分量之和。對(duì)于任意，用表示中第大的分量，即將的分量按照降序進(jìn)行排列得到下式(2.2.9)則對(duì)的最大的個(gè)分量進(jìn)行求和所得到的函數(shù)(2.2.10)是凸函數(shù)。事實(shí)上，此函數(shù)可以表述為(2.2.11)即從的分量中選取個(gè)不同分量進(jìn)行求和的所有可能組合的最大值。因?yàn)楹瘮?shù)是個(gè)線性函數(shù)的逐點(diǎn)最大，所以是凸函數(shù)。“”2.2保持凸性的運(yùn)算逐點(diǎn)最大的性質(zhì)可以擴(kuò)展至無限個(gè)凸函數(shù)的逐點(diǎn)上確界，如下面的定理所述。定理2.2.2如果對(duì)于任意，函數(shù)關(guān)于都是凸的，則函數(shù)(2.2.12)關(guān)于也是凸的。此時(shí)，函數(shù)的定義域?yàn)?2.2.13)從上圖的角度理解，一系列函數(shù)的逐點(diǎn)上確界函數(shù)對(duì)應(yīng)著這些函數(shù)上圖的交集：對(duì)于函數(shù)，我們有(2.2.14)由定理1.3.1知，是凸集合，再由定理2.1.5知，函數(shù)是凸函數(shù)。例2.2.2集合的支撐函數(shù)。令集合，且，定義集合的支撐函數(shù)為(2.2.15)自然地，函數(shù)的定義域?yàn)?/p>

。對(duì)于任意是的線性函數(shù)，是一系列線性函數(shù)的逐點(diǎn)上確界函數(shù)，因此是凸函數(shù)。2.2保持凸性的運(yùn)算復(fù)合運(yùn)算除上面介紹的保持凸性的運(yùn)算之外，實(shí)踐中應(yīng)用最廣泛的函數(shù)運(yùn)算可能是函數(shù)的復(fù)合運(yùn)算。因此，我們特別關(guān)心復(fù)合運(yùn)算在何種條件之下能保持函數(shù)的凸性。給定函數(shù)以及，定義復(fù)合函數(shù)為(2.2.16)我們考慮當(dāng)函數(shù)是凸函數(shù)或凹函數(shù)時(shí)，函數(shù)和應(yīng)滿足的條件。首先考慮的情況，即。僅考慮的情況(事實(shí)上，將函數(shù)限定在與其定義域相交的任意直線上得到的函數(shù)決定了原函數(shù)的凸性)。為了找出復(fù)合規(guī)律，首先假設(shè)函數(shù)和是二次可微的，且。在上述假設(shè)下，函數(shù)是凸的等價(jià)于對(duì)所有的。復(fù)合函數(shù)的二階導(dǎo)數(shù)為(2.2.17)假設(shè)函數(shù)是凸函數(shù)，函數(shù)是凸函數(shù)且非減(即且)，從式(2.2.17)可以得出，即函數(shù)是凸函數(shù)。2.2保持凸性的運(yùn)算類似地，由式(2.2.17)可以得出如下結(jié)論。定理2.2.2給定函數(shù)以及，考慮復(fù)合函數(shù)則有(1)如果是凸函數(shù)且非減，是凸函數(shù)，則是凸函數(shù)，(2)如果是凸函數(shù)且非增，是凹函數(shù)，則是凸函數(shù)。請(qǐng)讀者思考：如果是凹函數(shù)且是單調(diào)函數(shù)，則函數(shù)應(yīng)具備怎樣的條件，才能使函數(shù)是凹函數(shù)？作為本節(jié)的結(jié)束，我們指出函數(shù)之間的一些常見的運(yùn)算未必保持凸性。例如，減法運(yùn)算。設(shè)函數(shù)為凸函數(shù)，則未必是凸函數(shù)。稱為DC(Differenceofconvexfunctions)函數(shù)，是一類重要的非凸函數(shù)。在第5章中將介紹極小化DC函數(shù)的最優(yōu)化算法。2.2保持凸性的運(yùn)算03共軛函數(shù)2.3.1共軛函數(shù)的概念定義2.3.1設(shè)函數(shù)

，則函數(shù)

(2.3.1)稱為函數(shù)

的共軛函數(shù)。明顯地，

是凸函數(shù)，這是因?yàn)樗且幌盗嘘P(guān)于

的凸函數(shù)(實(shí)際上是仿射函數(shù))的逐點(diǎn)上確界。無論

是否是凸函數(shù)，

都是凸函數(shù)。注意到當(dāng)

是凸函數(shù)時(shí)，下標(biāo)

可以去掉，這是因?yàn)楦鶕?jù)之前關(guān)于函數(shù)延拓的定義，有

。我們從一些簡單的例子開始探尋共軛函數(shù)的一些規(guī)律。在此基礎(chǔ)上我們可以得到很多常見凸函數(shù)的共軛函數(shù)的解析形式。例2.3.1考慮上一些凸函數(shù)的共軛函數(shù)。(1)仿射函數(shù)。，作為的函數(shù)，當(dāng)且僅當(dāng)，即為常數(shù)時(shí)，有界。因此，共軛函數(shù)的定義域?yàn)閱吸c(diǎn)集，且。(2)負(fù)對(duì)數(shù)函數(shù)。，定義域?yàn)?。?dāng)時(shí)，函數(shù)無上界，當(dāng)時(shí)，在處函數(shù)達(dá)到最大值。因此，定義域?yàn)?，共軛函?shù)為。(3)指數(shù)函數(shù)。，當(dāng)時(shí)，函數(shù)無界。當(dāng)時(shí)，函數(shù)在處達(dá)到最大值。因此，當(dāng)時(shí)，。綜合起來，(我們規(guī)定)。(4)負(fù)熵函數(shù)。，定義域?yàn)?同上面討論，)。對(duì)所有，函數(shù)關(guān)于在上有上界，因此。在處，函數(shù)達(dá)到最大值。因此。2.3.1共軛函數(shù)的概念(5)嚴(yán)格凸的二次函數(shù)?？紤]函數(shù)。對(duì)所有的，關(guān)于的函數(shù)都有上界并在處達(dá)到最大值，因此(2.3.2)例2.3.2對(duì)數(shù)-行列式。我們考慮上定義的函數(shù)。其共軛函數(shù)定義為(2.3.3)其中，是上的標(biāo)準(zhǔn)內(nèi)積。首先我們說明只有當(dāng)時(shí)，才有上界。如果，則有特征向量，且對(duì)應(yīng)的特征值。令有(2.3.4)當(dāng)時(shí)，上式無界。接下來考慮的情形。為了求最大值，令對(duì)的偏導(dǎo)為零，則(2.3.5)得(是正定的)。因此，其定義域?yàn)椤＠?.3.3示性函數(shù)。設(shè)是某個(gè)集合(不一定是凸集)的示性函數(shù)，即當(dāng)，時(shí)，。示性函數(shù)的共軛函數(shù)為(2.3.6)它是集合的支撐函數(shù)。2.3.1共軛函數(shù)的概念共軛理論可理解為下面類型的“最佳”不等式。(2.3.7)其中和是從到的函數(shù)，令表示對(duì)此不等式有效的所有函數(shù)對(duì)的集合，“最佳”對(duì)是指中的不等式不能被收緊的函數(shù)對(duì)，即如果，并且