凸優(yōu)化理論

第一章凸集

1、仿射集

1.1.定義：任意以及都有；

直觀上，如果兩點(diǎn)在仿射集內(nèi)，那么通過任意兩點(diǎn)的直線位于其

內(nèi)；

1.2、仿射集的關(guān)聯(lián)子空間：

如果是仿射集，且，則集合是一個子空間（關(guān)于加法和數(shù)乘封

閉），因此仿射集可以表示為一個子空間加上一個偏移，，可以是C中

任意一點(diǎn)；定義C的維數(shù)為子空間V的維數(shù)（向量基的個數(shù)）；

1.3、線性方程組的解集：

等價(jià)于仿射集且其關(guān)聯(lián)的子空間是就是的的零空間即；

1.4、仿射組合：

如果，稱為的仿射組合；

如果是仿射集，，且，那么；

集合C是仿射集集合包含其中任意點(diǎn)的仿射組合；

1.5、仿射包：

集合C中的點(diǎn)的所有仿射組合組成的集合記為C的仿射包

,；仿射包是包含的最小的仿射集合；

1.6、仿射維數(shù)：

集合仿射維數(shù)為其仿射包維數(shù)，即仿射包相關(guān)聯(lián)子空間的維數(shù)，即

是其子空間最大線性無關(guān)基；

如果集合的仿射維數(shù)小于n,那么這個集合在仿射集合中；

1.7、集合相對內(nèi)部：

定義為的內(nèi)部，記為，即；

集合內(nèi)部：由其內(nèi)點(diǎn)構(gòu)成，內(nèi)點(diǎn)為；

1.8、集合的相對邊界：

集合C的相對邊界定義為，為C的閉包；

集合C的邊界定義為；

-------------------------------------------------------------------------2凸集：

如果，，，都有；

直觀上，如果兩點(diǎn)在凸集內(nèi)，則兩點(diǎn)間的線段也在凸集內(nèi)"方射

集是凸集；

2.1、凸組合：

如果，，，稱為的凸組合；

點(diǎn)的凸組合可以看做他們的混合或加權(quán)平均，代表混合時所占的

份數(shù)。

如果點(diǎn)在凸集內(nèi)，則它們的凸組合仍在凸集內(nèi)；

C是凸集集合包含其中所有點(diǎn)的凸組合；

2.2、集合的凸包：

集合C中所有點(diǎn)的凸組合，；

C的凸包是包含C的最小凸集;

2.3、無窮級數(shù)的凸組合：

假設(shè)，，，并且........為凸集，

那么若下面的級數(shù)收斂，那么

2.4、積分的凸組合：

假設(shè)對所有滿足，并且，其中為凸集，

那么如果下面積分存在，貝I」：；

2.5、概率的凸組合：

假設(shè)x是隨機(jī)變量，為凸集，并且的概率為，那么；

3錐：如果對于任意和，都有，稱集合C為維;

直觀上如果點(diǎn)在錐中，那么以原點(diǎn)為端點(diǎn)過該點(diǎn)的射線在錐中；

3.1、凸錐：

集合C是錐，并且是凸的，則稱C為凸錐，即對于任意，和，，

都有

直觀上，如果兩點(diǎn)在凸錐中，那么以原點(diǎn)為端點(diǎn)，以過兩點(diǎn)的兩

條射線為邊界的扇形面在凸錐中；

3.2、錐組合:

具有，形式的點(diǎn)稱為的錐組合（或^負(fù)線性組合）；

如果均屬于凸推C,那么的每一個推組合也在C中;

集合C是凸推它包含其元素的所有推組合；

3.3、錐包:

集合C的錐包是C中所有元素的錐組合的集合；

凸集

的例子：

空集、單點(diǎn)集、全集都是的仿射子集；

線段是凸的，但不是仿射的；

射線是凸的，不是仿射的，不是錐（除非端點(diǎn)是零點(diǎn)）；

直線是仿射的，自然是凸的；如果通過零點(diǎn)，則是錐，并且是凸

錐；

子空間是仿射的、凸錐（滿足對加法、數(shù)乘封閉、含零元）；

超平面：

,其中，且；，，在超平面上；

閉的半空間：

非平凡線性不等式的解空間，，半空間是凸的，但不是仿射的，

也不是錐；

半空間邊界、內(nèi)部：、；

Euclid球：

歐幾里得球是凸集：；橢球：

橢球是凸集：，對稱正定矩陣，決定橢球從各個方向擴(kuò)展的幅度；

半軸長度有給出；正半定矩陣；若為奇異矩陣，橢球退化，即

一些維度上半軸長為零，這時其仿射維數(shù)等于A的秩，退化的橢

球也是凸的；

范數(shù)球、范數(shù)錐：

它們是凸集，范數(shù)錐：，；如二階錐（二次錐）；------------

-----------------------------------------------------4.多面體：

有限個線性等式和不等式的解集：，，；

因此多面體是有限個半空間和超平面的交集；

仿射集合（如子空間、超平面、直線）、射線、線段、半空間都

是多面體；

多面體是凸集；有界多面體也稱為多胞形〈二、有限集合的凸包；

多面體可以表示為，

,b、d為向量;

4.1、單純形（一種多面體）：點(diǎn)描述法

設(shè)k+1個點(diǎn)，，仿射獨(dú)立，即，，，線性獨(dú)立，那么這些點(diǎn)決定

了一個單純形：，，，，這個集合的仿射維數(shù)（它的仿射閉包的維

數(shù)），即是，空間的維數(shù)，顯然它的一個基就是，，，即集合的仿射

維數(shù)為k;

單純形是凸集、并且是多面體，一般稱k維單純形（k+1個仿射

獨(dú)立點(diǎn)生成的凸包）；

4.2、常見的單純形：

1維單純形是一條空間線段（1個基向量，2個空間點(diǎn)）；

2維單純形是一個空間三角形（含其內(nèi)部）（2個基向量，3個空

間點(diǎn)）；

3維單純形是一個四面體（3個基向量，4個空間點(diǎn)）；

4.3、單位單純形：

由零向量0和單位向量，，決定的n維單純形，

它可以表示為滿足下列條件的向量的集合：；

4.4、概率單純形：

由單位向量，，決定的n-1維單純形，它是滿足下列條件的向量

集合：；

概率單純形中的每個向量對應(yīng)于隨機(jī)變量n個取值對應(yīng)的一個概

率分布，可理解為第i個元素的概率；4.5、單純形的多面體描述法

C是單純形，充要條件是，對于某些，，有；

/其中，，，，，，

顯然，B的秩為k;因此存在非奇異矩陣，使得，一則：，，，，

III

顯然：且且目

；這里A的選擇與，，有關(guān)；

4.6、多面體：凸包描述法

有限集合，，的凸包是：，，，是一個有界多面體，但是無法用

線性不等式和不等式的集合將其表示；

凸包表達(dá)式的一個擴(kuò)展：，一其意義是，，的凸包加上，，的錐

包，定義了一個多面體，反之每個多面體也都可以表示為此類形式；

仿射集是凸集；多面體是凸集；仿射集是多面體；

單純形（特殊多面體）是凸集，可以給出線性等式和不等式表示；

多面體（使用線性等式和不等式組定義）等價(jià)于凸包，無法給出

線性等式和不等式表示；

有限集的凸包是有界多面體，無法給出線性等式和不等式表示；

5.保凸運(yùn)算：用以從凸集構(gòu)造出其他凸集；

5.1、求交集：無窮多個凸集的交是凸集；

5.2、仿射映射：，且若S是凸的，那么是凸的；反之成立"申縮、

平移、投影是仿射映射；凸集的和、直積是凸的，凸集的投影是凸的，

凸集的部分和是凸的；

注意：，也是仿射函數(shù)；

線性矩陣不等式的解：，是凸集；

雙曲錐：,是凸集；

5.3、透視映射：，，定義域?yàn)?，如果C是凸集，那么是凸集；

反之成立；

5.4、線性分式映射：是仿射的，其中并且

，那么：，是線性分式（投射）函數(shù),定義域

.P是透視函數(shù)；同樣象與原象的凸性可以互推；

線性分式映射的應(yīng)用：條件概率，設(shè)u和v是分別在，，和，，

中取值的隨機(jī)變量，并且

表示概率。那么條件概率由下式給出：，f可以通過一個線性分式映

射從聯(lián)合分布凸集P（維向量集合，每一個向量是一個聯(lián)合分布）到

條彳牛概率分布凸集（維向量集合，每一個向量是一個條件分布）；

------------------------------------------------------------------------------6分離

與支撐超平面：

重要的想法：用超平面或仿射函數(shù)（仿射集）將兩個不相交的凸

集分離開來！

6.1、超平面分離定理：

假設(shè)C和D是兩個不相交的凸集,即，那么存在和b使得對于所有

有，對于所有有；超平面稱為集合C和D的分離超平面；

*假設(shè)C和D的歐式距離即，，并且

存在達(dá)到這個最小距離，這些條件是可以被滿足的，如當(dāng)C和D

是閉的并且其中之一是有界的。定義：,因此仿射函數(shù)分離了C和D,

且與連接c和d之間的線段相垂直并且穿過其中點(diǎn)。

1）仿射集與凸集的分離：仿射集等價(jià)于線性等式組，即多個超平

面交集；凸集等價(jià)于線性等式組和線性不

等式組的交集，即多個超平面、半空間交集兩成的多面體；

設(shè)C是凸集,而D是仿射的，即，其中。設(shè)C和D不相交，則存

在使得和，對與所有均成立。

2）超平面嚴(yán)格分離：

如果對于任意有，并且對于任意，有；

一般情況不相交的凸集并不一定能夠被超平面嚴(yán)格分離，即使集

合是閉集；

3）點(diǎn)和閉凸集的嚴(yán)格分離：

6.2、超平面分離逆定理：（分離超平面的存在表面C和D不相

交）不成立

任何兩個凸集，如果其中至少有一個是開集，那么當(dāng)且僅當(dāng)存在

分離超平面時，它們不相交；換句話說，如果它們都是閉集，逆定理

可能是不成立的；

***************************************************************

************************嚴(yán)格線性不等式的擇一定理：嚴(yán)格線性不等

式,無解的充要條件是兩個凸集

不相交，即存在，使得，，，；這兩個線性不等式僅有一個成立；

************************

6.3、支撐超平面定理

設(shè)而是其邊界上的一點(diǎn)，即，如果，并且對任意滿足，那么稱超

平面為集合C在點(diǎn)處的支撐超平面；

對于任意非空的凸集C和任意，在處存在C的支撐超平面；

如果C的內(nèi)部非空，即是上面所述；如果C內(nèi)部是空集，那么C

必處于小于n維的一個仿射集合中，并且任意包含這個仿射集合的超

平面一定包含C和，這是一個平凡的支撐超平面，如

，支撐超平面為；

6.4、支撐超平面逆定理

如果一個集合是閉的，具有非空內(nèi)部，并且其邊界上每個點(diǎn)均存

在支撐超平面，那么它是凸的；

7廣義

不等式：

7.1、正常錐：錐，要求如下

K是凸的（兩點(diǎn)連線封閉）；

K是閉的（集合是閉集）；----------需要在距離空間中

K是實(shí)的（具有非空內(nèi)部）；--------需要在距離空間中

K是尖的（不包含直線，）；

正常錐可以用來定義廣義不等式，即上的偏序關(guān)系。

上偏序關(guān)系：；

上嚴(yán)格偏序關(guān)系：；

上的偏序關(guān)系、嚴(yán)格偏序關(guān)系就是

7.2、一些例子

非負(fù)象限是正常錐，向量間的偏序關(guān)系等價(jià)于所有分量間的偏序

關(guān)系；

半正定錐是中的正常錐，相應(yīng)的廣義不等式就是矩陣不等式，兩

個半正定矩陣間的偏序關(guān)系等價(jià)于矩陣差為半正定矩陣，兩個半正定

矩陣間的嚴(yán)格偏序關(guān)系等價(jià)于矩陣差為正定矩陣；半正定矩陣的內(nèi)部

有正定矩陣組成；

[0,1]上非負(fù)的多項(xiàng)式錐：K定義如下，

向量c;

7.3、廣義不等式性質(zhì)：

偏序性質(zhì)：對加法保序；具有傳遞性；對非負(fù)乘數(shù)保序；自反；

反對稱；對極限運(yùn)算保序；不具有全序性；

7.4、最小兀與極小兀

最小元：如果對于每個，都有，稱是S的最小元;是最小元；表示

可以與相比，并大于等于的所有元素；要求全部可比，在Rn上意味

著其他元素的各個分量都大于等于該元素的分量，在半正定錐上意味

著相減后差仍是半正定推；

極小元：如果，，那么，稱x為S的極小元；沒有要求全部可比，

在Rn上意味著只要求可比的元素中不存在各個分量都小于該元素的

相應(yīng)分量的元素，在半正定錐上意味著相減后差不是半正定錐，注意

不同極小元之間不可比；

是最小元，表示可以與x相比并且大于或等于（偏序意義上）x的

所有元素；

是極小元，表示可以與X相比并且小于或等于（偏序意義上）X的

所有元素；需要明確偏序關(guān)系的實(shí)際意義以及定義集合s的具體規(guī)則；

-------------------------------------------------------------8.對偶推與廣義不等式

8.1、（錐的）對偶錐:

令K為一個錐，集合稱為K的對偶錐，且是凸錐，即使K不是凸

錐；

直觀上，當(dāng)且僅當(dāng)是K在原點(diǎn)的一個支撐超平面的法線；K的對

偶錐是由其在原點(diǎn)的所有支撐超平面的反向法線組成的錐；

8.2、對偶錐的一些例子

子空間（加法、數(shù)乘封閉，含零元）的對偶錐：子空間的對偶錐是其

正交補(bǔ)，子空間是凸錐但不是正常錐，因?yàn)楹本€；

非負(fù)象限的對偶推：錐的對偶是它本身，；

半正定錐的對偶錐：在集合上，使用標(biāo)準(zhǔn)內(nèi)積

；半正定錐是自對偶的，即對于任意的

/

;（注意把矩陣看成向量）；

范數(shù)推的對偶：，由對偶范數(shù)定義，，，其中對偶范數(shù)由給出；

對偶錐滿足一些性質(zhì)：

是閉凸錐；

f

如果K有非空內(nèi)部（K是實(shí)的），那么是尖的；

如果K的閉包是尖的，那么有非空內(nèi)部；

是K的凸包的閉包，如果K是凸和閉的，則；

8.3、廣義不等式的對偶：

假設(shè)凸錐是正常錐，因此可以導(dǎo)出一個廣義不等式。其對偶推也

是正常的，所以也能導(dǎo)出一個廣義不等式。稱為的對偶；

（1）相關(guān)性質(zhì)：

當(dāng)且僅當(dāng)對于任意，有；

當(dāng)且僅當(dāng)對于任意和，有；

K是正常推，則也是正常錐；

***************************************************************

************************線性嚴(yán)格廣義不等式&圣__定理?

設(shè)是正常推，對于嚴(yán)格廣義不等式，其中，要么它是可行的，要

么存在使得I

，使得，，是可行的；

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

************************8.4、對偶不等式定義的最小出口極小元:

用對偶廣義不等式來刻畫（可能非凸），關(guān)于正常錐K導(dǎo)出的廣

義不等式的最小元和極小元；

最小元的對偶性質(zhì)：x是S上關(guān)于廣義不等式的最小元的充要條件

是，對于所有,x是在上極小化的唯一最優(yōu)解；

極小元的對偶性質(zhì)：

如果，并且x在上極小化，那么x是極小的；反之不成立，S上的

極小元x可以對彳丑可都不是上極小化的解；當(dāng)S是凸集是，逆定理成

立；

半正

定錐:

,是凸錐；上的半正定錐：

I

正定矩陣：特征值全為正；各階順序主子式為正；合同于單位矩

陣；

說明：1）是維向量空間，是的子空間；

2）是的以為法向量正半空間，它是凸錐；顯然

是無數(shù)個正半空間的交集，因此也是凸錐，即對于任意，的所有

X構(gòu)成的集合是凸的，它就是半正定僚；

3）凸集在中針對的是向量，在中針對的是矩陣；

4）中的正常錐是向量的集合，而中正常錐是矩陣的集合；

半正

定錐是中的正常錐，相應(yīng)的廣義不等式就是矩陣不等式，兩個半正定

矩陣間的偏序關(guān)系等價(jià)于矩陣差為半正定矩陣，兩個半正定矩陣間的

嚴(yán)格偏序關(guān)系等價(jià)于矩陣差為正定矩陣；半正定矩陣的內(nèi)部有正定矩

陣組成；

；半正定錐是自對偶的，即對于任意的半正定錐的對偶錐：在集

合上，使用標(biāo)準(zhǔn)內(nèi)積

;（注意把矩陣看成向量）；

第二章凸函數(shù)

-------------------------------------------------------1凸

函數(shù)

1.1.定義：是凸的，如果domf是凸集,且對于任意和任意，有

嚴(yán)格凸函數(shù)：如果當(dāng)以及時嚴(yán)格成立；

凸函數(shù)性質(zhì)：

仿射函數(shù)（包括線性函數(shù)）是既凸又凹的；

1.2、函數(shù)是凸的,當(dāng)且僅當(dāng)其在與其定義域相交的任何直線上都

是凸的；

函數(shù)f是凸的，當(dāng)且僅當(dāng)對于任意和任意向量v,函數(shù)是凸的（其

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

1.3、拓展值延伸：

如果f是凸函數(shù)，定義它的拓展延伸

1.4、凸集的示性函數(shù)：

設(shè)是一個凸集，考慮凸函數(shù)，其定義域?yàn)镃,對于所有的，有。

其擴(kuò)展值延伸函數(shù)

在C外為無窮大；

在集合C上極小化函數(shù)f等價(jià)于在上極小化函數(shù)；

1.5、一階條件：

假設(shè)f可微（即其梯度在開集定義域內(nèi)處處存在），則函數(shù)f是凸

函數(shù)的充要條件是定義域是凸集且對于任意，下式成立；（對于定義域

內(nèi)不相等的任意x,y等號不成立，稱為嚴(yán)格凸性），上式得出的仿射函

數(shù)即為函數(shù)f在點(diǎn)x附近的一階泰勒近似；

凸函數(shù)一階條件解釋：

如果，有；

上式可以描述為：，；

可以解釋為以為法向量的超平面在邊界點(diǎn)，支撐著；

1.6、二階條件：

假設(shè)函數(shù)f二階可微，即對于開集domf內(nèi)的任意一點(diǎn)，它的

hessian矩陣或二階導(dǎo)存在，則函數(shù)f是凸函數(shù)的充要條件是，其

hessian矩陣是半定矩陣：即對于所有的,有；

幾何意義上，函數(shù)圖像在x處具有正（向上）的曲率；

1.7.常用凸函數(shù)

二次函數(shù)：

二次函數(shù)，其定義域?yàn)橥辜浔磉_(dá)式為，其中，

，。顯然，所以函數(shù)f是凸的當(dāng)且僅當(dāng)P半正定；

其它R上凸函數(shù)例子：

指數(shù)函數(shù)；幕函數(shù)（底數(shù)大于1或?yàn)樨?fù)數(shù)，定義域?yàn)榉秦?fù)實(shí)數(shù)）；絕

對值募函數(shù)（指數(shù)大于等于1時）；

對數(shù)函數(shù)；負(fù)燧函數(shù)；

其它Rn上凸函數(shù)例子：

線性函數(shù)；仿射函數(shù)；范數(shù)；

最大值函數(shù):........為分量；

二次-線性分式函數(shù):，其中x為實(shí)數(shù)，y為非負(fù)實(shí)數(shù)；

指數(shù)和的對數(shù)凸函數(shù)：，，，為分量；

幾何平均凹函數(shù)：，，，，為分量；

對數(shù)-行列式凹函數(shù)：，；

矩陣分式函數(shù)：

矩陣分式函數(shù)，，在定義域上是凸的；

1.8、下水平集：

凸函數(shù)的下水平集定義為：；

對于任意，凸函數(shù)的下水平集仍然是凸集；反之不成立；

上水平集：

凹函數(shù)的上水平集定義為：；

對于任意，凹函數(shù)的上水平集仍然是凸集；反之不成立；

1.9、圖像：

函數(shù)的圖像定義為，，它是空間的一個子集。

上鏡圖：

函數(shù)的上鏡圖定義為一它也是空間的一個子集；

上鏡圖作用：

凸函數(shù)的很多結(jié)果可以從幾何的角度利用上鏡圖并結(jié)合凸集的一

些結(jié)論來證明或理解；

1.10、凸集和凸函數(shù)的聯(lián)系：

一個函數(shù)是凸函數(shù)，當(dāng)且僅當(dāng)其上鏡圖是凸集；

一個函數(shù)是凹函數(shù)，當(dāng)且僅當(dāng)其亞圖是凸集；

不等式及其擴(kuò)展：

l.llxJensen

對于凸函數(shù),基本不等式有時也稱為Jensen不等式。

擴(kuò)展到多個點(diǎn)：

，其中........且；考慮凸集時，此不等式可以擴(kuò)展至無窮項(xiàng)

和、積分、期望；

擴(kuò)展到積分：如果在上且,則當(dāng)相應(yīng)的積分存在時，下式成

立:；

擴(kuò)展到概率：如果x是隨機(jī)變量，事件發(fā)生的概率為1,函數(shù)f是

凸函數(shù)，當(dāng)相應(yīng)的期望存在時，我們有;（把事件x的概率視為）

作用：通過將Jensen不等式應(yīng)用于合適的凸函數(shù)可以得到很多著

名的不等式；如Holder不等式；

-------------------------------------------------------------------------------2、保

凸運(yùn)算

2.1、非負(fù)加權(quán)求和：

凸函數(shù)的非負(fù)加權(quán)求和仍然是凸函數(shù)，它構(gòu)成的凸函數(shù)的集合本

身是凸錐；

凹函數(shù)的非負(fù)加權(quán)求和仍然是凹函數(shù)，它構(gòu)成的凹函數(shù)的集合本

身是凸錐；

如果固定任意，函數(shù)關(guān)于x是凸函數(shù)，且對于任意，有，則函數(shù)g:

關(guān)于x的凸函數(shù)（若積分存在）。

2.2、復(fù)合仿射映射：

假設(shè)函數(shù)，以及，定義為，其中

;如果f是凸函數(shù)，則g是凸函數(shù)，如果函數(shù)f是凹函數(shù)，則g是

凹函數(shù)；

2.3、逐點(diǎn)最大和逐點(diǎn)上確界：

如果函數(shù)、均為凸函數(shù)，則二者的逐點(diǎn)最大函數(shù)f：,f是凸函數(shù),

其定義域?yàn)閮蓚€函數(shù)的交集；可以擴(kuò)展到多個點(diǎn)的逐點(diǎn)最大函數(shù)；

(1)分片線性函數(shù)：

函數(shù)定義了一個分片線性(實(shí)際上是仿射)函數(shù)，，(具有L個

或者更少的子區(qū)域)，是凸函數(shù)；反之成立；

(2)最大r個分量之和：

對于任意，用表示x中第i大的分量，即將x的分量按照非升序進(jìn)

行排列得到下式：，則對x的最大r個分量進(jìn)行求和所得到的函數(shù)是凸

函數(shù)；

(3)集合的支撐函數(shù)：

令集合，且，定義集合C的支撐函數(shù)為，對于任意，是的線性函

數(shù)，所以是一些列線性函數(shù)的逐點(diǎn)上確界函數(shù)，因此是凸函數(shù)；

(4)到集合中最遠(yuǎn)點(diǎn)的距離：

令集合，定義點(diǎn)x與集合中最遠(yuǎn)點(diǎn)的距離(范數(shù))為；

(5)以權(quán)為變量的最小二乘費(fèi)用函數(shù)：

令，，，在加權(quán)最小二乘問題中，我們對所有的極小化目標(biāo)函數(shù)，

允許權(quán)為負(fù)；定義最優(yōu)加權(quán)最小二乘費(fèi)用函數(shù)為是凹函數(shù)；

(6)對稱矩陣的最大特征值：

定義函數(shù)，其定義域?yàn)?，它是凸函?shù),；

(7)矩陣范數(shù)：

考慮函數(shù)，其定義域?yàn)?，其中表示譜范數(shù)或者最大奇異值，f可以

表示為

,是凸函數(shù)；

矩陣誘導(dǎo)范數(shù)：

假設(shè)分別是和上的范數(shù)，定義矩陣的誘導(dǎo)范數(shù)為

；其中是的對偶范數(shù)；()

擴(kuò)展到無限個凸函數(shù)的逐點(diǎn)上確界：

如果對于任意，函數(shù)關(guān)于X都是凸的，則函數(shù)關(guān)于X也是凸的，此

時g的定義域?yàn)椋?

技巧：建立函數(shù)凸性的一個方法：

將其表示為一族仿射函數(shù)的逐點(diǎn)上確界；幾乎所有的凸函數(shù)都可

以表示成一族仿射函數(shù)的逐點(diǎn)上確界；

如果函數(shù)是凸函數(shù)，其定義域?yàn)椋覀冇蟹律洌?/p>

2.4、復(fù)合：

函數(shù)以及，定義復(fù)合函數(shù)為，

標(biāo)量復(fù)合：

如果下列性質(zhì)成立：

如果h是凸函數(shù)目非減，g是凸函數(shù)，則f是凸函數(shù)；

如果h是凸函數(shù)目非增，g是凹函數(shù)，則f是凸函數(shù)；

如果h是凹函數(shù)且非減，g是凹函數(shù),則f是凹函數(shù)；

如果h是凹函數(shù)目非減，g是凸函數(shù)，則f是凹函數(shù)；

簡單復(fù)合結(jié)論：

如果g是凸函數(shù)，則是凸函數(shù)；

如果g是凹函數(shù)且大于零，則是凹函數(shù)；

如果g是凹函數(shù)目大于零，則是凸函數(shù)；

如果g是凸函數(shù)且不小于零，，則是凸函數(shù)；

如果g是凸函數(shù)，則在上是凸函數(shù)；

矢量復(fù)合：

如果，設(shè)，，，其中，；下列性質(zhì)成立：

如果h是凸函數(shù)且在每維分量上h()非減，是凸函數(shù)，則f是凸

函數(shù)；

如果h是凸函數(shù)目在每維分量上h()非增，是凹函數(shù)，則f是凸

函數(shù)；

如果h是凹函數(shù)目在每維分量上h()非減,是凹函數(shù)，則f是凹

函數(shù)；

2.5、最小化：

如果函數(shù)f關(guān)于是凸函數(shù)，集合C是非空凸集，定義函數(shù)，

若存在某個x使得（這意味著對所有x,）,則函數(shù)g關(guān)于x是凸

函數(shù)；

點(diǎn)到某一集合的距離函數(shù)是凸的：采用范數(shù)，某點(diǎn)x到集合的距

離定義為，

因?yàn)殛P(guān)于是凸的，若集合S是凸集，則該距離函數(shù)是x的凸函數(shù)；

2.6、透視函數(shù)：

給定函數(shù)，則f的透視函數(shù)，定義為定義域?yàn)?/p>

，如果f是凸的，那么g也是凸的；

Euclid范數(shù)的平方函數(shù)的透視函數(shù)是凸的：上的凸函數(shù)的透視函

數(shù)，當(dāng)時，它關(guān)于是凸函數(shù)；

負(fù)對象函數(shù)的透視函數(shù)是凸的：上的凸函數(shù)的透視函數(shù)，在上是

凸函數(shù)，它關(guān)于是凸函數(shù)；函數(shù)g稱為關(guān)于t和x的相對嫡；當(dāng)x=l

時，g即為負(fù)嫡函數(shù)。

兩個向量的相對熔是凸函數(shù)：，關(guān)于是凸函數(shù)；

向量間的散度是凸函數(shù)：，，僅當(dāng)u二v時，散度為0；

----------------------------------------------------------3.共輾函數(shù)

設(shè)函數(shù)，定義函數(shù)為，，此函數(shù)稱為函數(shù)的共版函數(shù)；3.1、常見

函數(shù)的共輾函數(shù)

仿射函數(shù)的共柜函數(shù)：，當(dāng)且僅當(dāng)，即為常數(shù)時，有界，因此共

輾函數(shù)的定

義域?yàn)閱吸c(diǎn)集，且；

負(fù)對數(shù)函數(shù)的共版函數(shù)：，定義域?yàn)?，函?shù)僅在時有上界，故共

蛹

函數(shù)為，定義域?yàn)椋?/p>

指數(shù)函數(shù)的共犯函數(shù)"函數(shù)在時無界，在時，有上界，在時，；

因此；

負(fù)燧函數(shù)的共犯函數(shù)：，定義域，函數(shù)關(guān)于x在上有上界，因此共輾

函數(shù)；

3.2、共輾函數(shù)性質(zhì)：

Fenchel不等式：對于任意x和y,如下不等式成立;

Young不等式：當(dāng)f可微時，F(xiàn)enchel不搴稱為Young不等式;

共犯的共匏即為原函數(shù)：如果f是凸函數(shù)且是閉的（epif是閉集）；

Fenchel共姬:可微函數(shù)f的共姬函數(shù)稱為f的Legendre變換，

其中；獨(dú)立函數(shù)的和的共拆函數(shù)是各個凸函數(shù)的共軻函數(shù)的和；

4擬凸

函數(shù)

函數(shù)稱為擬凸函數(shù)（或者單峰函數(shù)），如果其定義域及所有下水

平集都是凸集。擬凸函數(shù)可能是凹函數(shù)如對數(shù)函數(shù)，擬凹函數(shù)也可能

是凸函數(shù)，擬凸函數(shù)、擬凹函數(shù)可能不連續(xù)；4.1、擬線性函數(shù)：既是

擬凸函數(shù)又是擬凹函數(shù)；其定義域及所有下水平集都是凸集；4.2、R

上的例子：

對數(shù)函數(shù)、上取整函數(shù)擬線性函數(shù)；

線性分式函數(shù)：，其定義域?yàn)?，是擬凸函數(shù)，也是擬凹函數(shù)，因

此是擬線性函數(shù)；

距離比函數(shù)：設(shè)，定義，即，到a點(diǎn)的歐氏距離和到b點(diǎn)的歐氏

距離之比；在時，下水平集為凸集；

4.3、基本性質(zhì)：

擬凸函數(shù)的Jensen不等式：函數(shù)f是擬凸函數(shù)的充要條件是，

domf是凸集，且對于任意及，有，即線段中任意一點(diǎn)的函數(shù)值不超

過其端點(diǎn)函數(shù)值中最大的那個；

f在直線上的性質(zhì)：函數(shù)f是擬凸的充要條件是它在和其定義域相

交的任意直線上是擬凸函數(shù)；這樣可以通過考察函數(shù)在R上的擬凸性

來驗(yàn)證原函數(shù)的擬凸性；

4.4、可微擬凸函數(shù)：

一階條件：設(shè)函數(shù)可微，則函數(shù)f是擬凸的充要條件是，domf是

凸集，且對于任意，有

幾何意義，當(dāng)時，它是在點(diǎn)X處定義了水平集的一個支撐超平面；

注意對于擬凸函數(shù)，當(dāng)時，點(diǎn)X有可能不是f的全局極小點(diǎn)；

二階條件：假設(shè)函數(shù)f二次可微，如果函數(shù)f是擬凸函數(shù)，則對任

意以及任意有

/

幾何意義，對于定義在R上的擬凸函數(shù)，條件簡化為，表示在斜

率為零的點(diǎn)，二階導(dǎo)數(shù)是非負(fù)的。對于定義在上的擬凸函數(shù)，條件等

價(jià)于在滿足的點(diǎn)處正定，在其它點(diǎn)處在n-1維子空間上正定；

4.5、保擬凸運(yùn)算：

非負(fù)加權(quán)最大：擬凸函數(shù)的非負(fù)加權(quán)最大定義為，其中，是擬凸

函數(shù)。

逐點(diǎn)上確界：，其中，固定任意y,是關(guān)于x是擬凸函數(shù)。

復(fù)合：如果函數(shù)是擬凸函數(shù)，且函數(shù)是非減的，則復(fù)合函數(shù)是擬

凸函數(shù)；

如果f是擬凸函數(shù)，則是擬凸函數(shù)，

且函數(shù)在集合上是擬凸函數(shù)；最小化：如果函數(shù)是x和y的聯(lián)合

擬凸函數(shù)，且C是凸集，則函數(shù)是擬凸函數(shù)；

4.6、擬凸函數(shù)下水平集的凸函數(shù)不等式表示：

選擇一族凸函數(shù)表示凸函數(shù)的編號，這些函數(shù)滿足，，即擬凸函

數(shù)f的

t-下水平集是凸函數(shù)的0-下水平集。

這要求對于任意，函數(shù)必須滿足:當(dāng)時，，為了滿足這個條件，要

求對于任意x,是t的非增函數(shù)，即當(dāng)時，；

例如，當(dāng)函數(shù)f的下水平集是閉集時，可以選取

凸凹函數(shù)之比：設(shè)p是凸函數(shù)，q是凹函數(shù)，在凸集C上，p非

負(fù)，q為正，那么集合C上的函數(shù)，是擬凸函數(shù)，其t-下水平集可以

表示為凸函數(shù)不等式；

5.對數(shù)

凸函數(shù)-對數(shù)凹函數(shù)

定義一：如果對所有的有且是凹（凸）函數(shù)，稱函數(shù)對數(shù)凹

（凸）；

定義二：函數(shù)，其定義域是凸集，且對于任意有，函數(shù)是對數(shù)凹

的，當(dāng)且僅當(dāng)對

任意，，有；

5.1、一些簡單的對數(shù)凹（凸）函數(shù)：

仿射函數(shù)：在上是對數(shù)凹函數(shù)；

黑函數(shù)：在上當(dāng)時是對數(shù)凸函數(shù)，當(dāng)時是對數(shù)凹函數(shù)；

指數(shù)函數(shù)：既是對數(shù)凸函數(shù)又是對數(shù)凹函數(shù)；

高斯概率密度函數(shù)的累積分布函數(shù)：是對數(shù)凹函數(shù)；

Gamma函數(shù)：，當(dāng)時是對數(shù)凸函數(shù)；

行列式：在上是對數(shù)凹函數(shù)；

行列式與跡之比：在上是對數(shù)凹函數(shù)；

一些概率密度函數(shù)：，其中，；

，其中；

,其中C是凸集，表示集合C的體積（Lebesgue測度）;

5.2、相關(guān)性質(zhì):

（1）二次可微的對數(shù)凸（凹）函數(shù)：

設(shè)函數(shù)f二次可微，其中domf是凸集，則有，

函數(shù)f是對數(shù)凸函數(shù)當(dāng)且僅當(dāng)對任意，下式成立：；

函數(shù)f是對數(shù)凹函數(shù)當(dāng)且僅當(dāng)對任意，下式成立：；

（2）乘積，和，以及積分運(yùn)算：

對數(shù)凸性以及凹性對乘積以及正的伸縮運(yùn)算時封閉的；

對數(shù)凸函數(shù)的和仍是對數(shù)凸函數(shù)，但對數(shù)凹函數(shù)的和不一定；

如果對于任意，是x的對數(shù)凸函數(shù)，則函數(shù)是對數(shù)凸函數(shù)；相關(guān)

例子如下：

非負(fù)函數(shù)的Laplace變換：設(shè)函數(shù)對所有x滿足，函數(shù)p的

Laplace變換:

在上是對數(shù)凸函數(shù)此時定義域domP為；

矩生成函數(shù)：設(shè)P是概率密度函數(shù)，即滿足，函數(shù)，

則一其中隨機(jī)向量V具有概率密度函數(shù)p;

累積量生成函數(shù)：凸函數(shù)稱為函數(shù)P的累積量生成函數(shù)；

(3)對數(shù)凹函數(shù)的積分：

在一些特殊情況下，對數(shù)凹的性質(zhì)在積分后仍然保留：如果函數(shù)

是對數(shù)凹函數(shù)，則在上是x的對數(shù)凹函數(shù);據(jù)此，得出一些結(jié)論：

對數(shù)凹的概率密度分布函數(shù)的邊際分布仍然是對數(shù)凹的；

對數(shù)凹的性質(zhì)對卷積運(yùn)算時封閉的，即如果函數(shù)f和g在上是對數(shù)

凹的，則它們的卷積

仍是對數(shù)凹的；據(jù)此可以得出以下結(jié)論：設(shè)是凸集，是上的隨機(jī)

向量，設(shè)其具有對

數(shù)凹的概率密度函數(shù)p,則函數(shù)是x的對數(shù)凹函數(shù)；

-----------------------------------------------------------------------------------6廣義

凸性

以廣義不等式來考慮廣義的單調(diào)性和凸性

6.1、廣義函數(shù)(關(guān)于廣義不等式的)單調(diào)性：

設(shè)是一個正常錐(指的是定義域)，其相應(yīng)的廣義不等式為，

稱函數(shù)，K-非減，如果下式成立：；

稱函數(shù)，K-增，如果下式成立：；

向量單調(diào)函數(shù)：在上非減，當(dāng)且僅當(dāng)對任意x,y下式成立；

矩陣單調(diào)函數(shù)：在上非減，如果在半正定錐內(nèi)函數(shù)是單調(diào)的；

矩陣函數(shù)tr(WX):其中，當(dāng)時，函數(shù)是矩陣非減的;當(dāng)時是矩陣

增的;當(dāng)

時，函數(shù)是矩陣非增的;當(dāng)時是矩陣減的；

函數(shù):在上矩陣減；

函數(shù):在上矩陣增，在上矩陣非減；

單調(diào)性的梯度條件：

可微函數(shù)f,其定義域?yàn)橥辜荎-非減的，當(dāng)且僅當(dāng)對任意有,

注意是對偶不等式；

6.2、廣義函數(shù)（關(guān)于廣義不等式的）凸性：

設(shè)是一個正常錐，其相應(yīng)的廣義不等式為，（K是像集）

稱函數(shù)，K-凸，如果對于任意x,y,以及有

相關(guān)性質(zhì)：

1）當(dāng)m=l時，即函數(shù)值為標(biāo)量，這種情況即是常見的凸以及嚴(yán)

格凸的定義；

2）注意K-凸針對的是值域；

3）函數(shù)是K-凸的,當(dāng)且僅當(dāng)它在定義域上的任意直線上是K-凸

的；

矩陣凸性：設(shè)函數(shù)f是矩陣值函數(shù)，即：，稱函數(shù)f關(guān)于矩陣不等

式是凸的，如果對任意x和y以及，有，這種凸性有時稱為矩陣凸性。

其等價(jià)定義：對任意向量z,標(biāo)量函數(shù)都是凸函數(shù);

一些列子：

函數(shù)：其中，是矩陣凸的；

函數(shù)：當(dāng)或時，函數(shù)在上是矩陣凸的；當(dāng)時，函數(shù)是矩陣凹的；

K■凸的對偶刻畫：

函數(shù)f是K-凸的，當(dāng)且僅當(dāng)對任意，實(shí)值函數(shù)是凸的；

函數(shù)f是嚴(yán)格K■凸的，當(dāng)且僅當(dāng)對任意非零向量，實(shí)值函數(shù)是嚴(yán)

格凸的；

可微函數(shù)的K-凸函數(shù)：

可微函數(shù)f是K-凸的，當(dāng)且僅當(dāng)其定義域是凸集，且對定義域內(nèi)

任意x,y有，其中是函數(shù)f在x處的導(dǎo)數(shù)或雅克比矩陣；

復(fù)合定理：函數(shù)復(fù)合保留的凸性很多結(jié)論都可以推廣到K■凸的情

形；

凸優(yōu)化問題

1、優(yōu)化問題：

1.1.基本概念

Minimize,subjectto,,,;

優(yōu)化變量：；

目標(biāo)函數(shù)：：；

不等式約束:;

等式約束:;

定義域：；

可行集（約束集）：可行點(diǎn)的集合，如果點(diǎn)X在定義域內(nèi)，稱X是

可行的，；

最優(yōu)值：

最優(yōu)點(diǎn)：如果是可行的并且；

最優(yōu)集：所有最優(yōu)點(diǎn)的集合；

最優(yōu)值是可達(dá)的：如果存在最優(yōu)值，且最優(yōu)點(diǎn)在定義域內(nèi)非無窮;

最優(yōu)值是不可達(dá)的：如果存在最優(yōu)值，但最優(yōu)點(diǎn)不在定義域內(nèi)；

問題無下界：如果最優(yōu)解在定義域內(nèi)但最優(yōu)值；

問題不可行：無可行解，令；

一次優(yōu)解：滿足的可行解，其中；

一次優(yōu)解集：-次優(yōu)解的集合；

局部最優(yōu)解：如果存在使得，稱可行解X為局部最優(yōu)解；這意味X

在可行集一個點(diǎn)的周圍極小化了；

不等式約束在X處起作用：如果X可行且，稱約束的第i個不等式

在X處起作用；

可行性問題：如果目標(biāo)函數(shù)恒等于0,那么其最優(yōu)解要么是零（如

果可行集非空），要么無窮大（如果可行集為空）；

find,

subjectto,,

*

//

L2、問題的標(biāo)準(zhǔn)形式：

Minimize,

subjectto,,

/I

在標(biāo)準(zhǔn)形式中，按照慣例設(shè)不等式和等式的右端為零，這一點(diǎn)總

可以通過對任何非零右端進(jìn)行減法得到；

1.3、問題的等價(jià)形式：

如果從一個問題的解，很容易得到另一個問題的解，并且反之亦

然，稱兩個問題是等價(jià)的；

變量變換：

設(shè)是一一映射，其象包含了問題的定義域D,即；

定義函數(shù)和為：，考慮關(guān)于z的問題：Minimize,

subjectto,,

/，

稱標(biāo)準(zhǔn)形式的問題和上面的問題通過變量變換所聯(lián)系；

目標(biāo)函數(shù)和約束函數(shù)的變換：

設(shè)：單增；滿足：當(dāng)且僅當(dāng)時；滿足：當(dāng)且僅當(dāng)時。

定義函數(shù)和為復(fù)合函數(shù);顯然問題：Minimize,

subjectto,,

//

松弛變量：

不等式約束中等價(jià)于存在一個滿足。利用這個變換，可以得到問

題：

Minimize,

subjectto,

//

*

//

這個問題有n+m個變量，m個不等式約束和m+p個等式約束。

新的變量稱為對應(yīng)原不等式約束

的松弛變量。

消除等式約束：

如果可以利用一些參數(shù)來顯示地參數(shù)化等式約束，的解，那么可

以從原問題中消除等式約束，那么可以得到等價(jià)的優(yōu)化問題：

Minimize,

subjectto,,

消除線性等式約束：

如果等式約束均是線性的，即，那么可以通過解線性方程組減少

變量；

引入等式約束：

可以在問題中引入等式約束和新的變量。如對于問題：

Minimize,

subjectto,,

//

引入新的變量和新的等式約束，從而構(gòu)造等吩問題：

Minimize,