目錄

1.凸優(yōu)化到底是什么？

1.1 基本概念

1.2 凸優(yōu)化和非凸優(yōu)化

2、集合概念

2.1 仿射集、仿射包、仿射組合

2.2 凸集、凸包、凸組合

2.3 錐、凸錐

3.凸函數(shù)與非凸函數(shù)

4.總結(jié)

---

1.凸優(yōu)化到底是什么？

1.1 基本概念

凸優(yōu)化就是優(yōu)化問題的一個(gè)特例，我們所知道的優(yōu)化問題就是在一定的限制條件下求得目標(biāo)函數(shù)最優(yōu)值，可以是最大值也可以是最小值，那么在經(jīng)濟(jì)學(xué)上面就是在有限的資源下面尋求資源的最大利用效益。

那么，優(yōu)化問題按照不同的分類可以得到很多中細(xì)分類，比如線性規(guī)劃與非線性規(guī)劃等等。

凸優(yōu)化就是優(yōu)化問題的一個(gè)特例，其固有的形式如下：

很多非凸問題也可以通過某種形式轉(zhuǎn)化成凸優(yōu)化問題來(lái)求解其近似解（一般在找不到原問題的解或求解原問題所需的時(shí)間復(fù)雜度太大的情形下使用）。這是解決一類問題的一種技巧，在深度學(xué)習(xí)的一些模型中經(jīng)常用到。這是一種逼近的思想。

1.2 凸優(yōu)化和非凸優(yōu)化

在最小化（最大化）的優(yōu)化要求下，目標(biāo)函數(shù)是凸函數(shù)且約束條件所形成的可行域集合是一個(gè)凸集的優(yōu)化方法，因此凸優(yōu)化的判定條件有兩個(gè)

• 函數(shù)定義域是凸集
• 目標(biāo)函數(shù)是凸函數(shù)

2、集合概念

2.1 仿射集、仿射包、仿射組合

?（1）仿射集（Affine set）

仿射集（Affine set）是包含過兩個(gè)不同的點(diǎn)的直線的所有點(diǎn)。（“所有點(diǎn)”的集合）

?比如，我們舉一個(gè)小例子：

（2）仿射組合(affine combination)

?仿射集包含了集合內(nèi)點(diǎn)的所有仿射組合。

（3）仿射包(affine hull)

?（4）仿射集合的子集

2.2 凸集、凸包、凸組合

（1）凸集

凸集是包含兩個(gè)不同點(diǎn)之間的直線的所有點(diǎn)。（“所有點(diǎn)”的集合）

所有仿射集都是凸的，因?yàn)樗现腥我獠煌c(diǎn)的所有直線。

都是對(duì)集合本身性質(zhì)的描述，但是有所不同，否則就擁有一樣的名字了，不同點(diǎn)就在于數(shù)值的取值范圍：仿射集對(duì)集合的要求包括了凸集對(duì)集合的要求，因此可以說(shuō)仿射集比凸集要求更高，不僅要滿足凸集的定義（在區(qū)間[0,1]之間），還要滿足 在區(qū)間[0,1]之外）。

①仿射集的概念：一個(gè)集合是仿射集，當(dāng)且僅當(dāng)集合中經(jīng)過任意兩點(diǎn)的直線（而不是線段）上的點(diǎn)仍在集合中。

②凸集的概念：一個(gè)集合是凸集當(dāng)且僅當(dāng)該集合中任意兩點(diǎn)的連線上的所有點(diǎn)（即線段）仍然屬于該集合。

• 判定條件上，凸集比仿射集更弱，只對(duì)系數(shù)大于0的線性組合作出要求。換句話說(shuō)，判定集合是凸集的判定條件是判定集合是仿射集的判定條件的子集。
• 從具體的點(diǎn)集來(lái)說(shuō)，是仿射集的一定是凸集，反之不然。換句話說(shuō)，所有仿射集的集合是所有凸集的集合的子集。
• 從點(diǎn)集的包的角度來(lái)說(shuō)，一個(gè)點(diǎn)集的凸包是這個(gè)點(diǎn)集的仿射包的子集。

?（2）凸組合（構(gòu)建凸集合的具體模型）

?（3）凸包（構(gòu)建凸集合的方法）(convex hull)

（4）仿射包（affine hull）、凸包（convex hull）

?這兩個(gè)概念是對(duì)已有集合生成新的集合的方法，定義如下：

對(duì)于空間中的兩點(diǎn)，其仿射集是過這兩點(diǎn)的直線，其凸集是連接兩點(diǎn)的線段，線段應(yīng)該是直線的子集。所以這里描述的直線和線段應(yīng)該分別是這兩點(diǎn)組成的集合的仿射包和凸包。因此有：

?注意：從集合的角度來(lái)看和從包的角度來(lái)看是不一樣的。

2.3 錐、凸錐

(1)錐

?(2) 凸錐

即集合C如果既是凸集也是錐，那么這樣的集合就叫凸錐，凸錐也一定包含原點(diǎn)。?

（3）錐組合

?（4）錐包(cone hull)

3.凸函數(shù)與非凸函數(shù)

通常將函數(shù)分為凸函數(shù)和非凸函數(shù)。凸函數(shù)的幾何意義在于，定義域中任意兩點(diǎn)連線組成的線段都在這兩點(diǎn)的函數(shù)曲線（面）上方。凸函數(shù)是有且只有全局最優(yōu)解的，而非凸函數(shù)可能有多個(gè)局部最優(yōu)解。

因此，當(dāng)很多模型不是凸函數(shù)時(shí)，我們往往嘗試絞盡腦汁去將其變換為凸函數(shù)和擬凸函數(shù)。

3.1 強(qiáng)凸函數(shù)

強(qiáng)凸函數(shù)有三種定義：

3.2 嚴(yán)格凸函數(shù)

3.3 擬凸函數(shù)

?

3.4 凸函數(shù)判定方法：（非常重要）

3.4.1 凸函數(shù)判定條件

（1）一階充要條件（不常用）

（2）二階充要條件（常用）

3.4.2 凸優(yōu)化判定條件

判定一個(gè)優(yōu)化是不是凸優(yōu)化，有下面的凸優(yōu)化判定條件：

??? ①對(duì)于一元函數(shù)f(x)，首先必須定義域是凸集，其次通過其二階導(dǎo)數(shù)f′′(x) 的符號(hào)來(lái)判斷。如果函數(shù)的二階導(dǎo)數(shù)總是非負(fù)，即f′′(x)≥0 ，則f(x)是凸函數(shù)。
??? ②對(duì)于多元函數(shù)f(X)，首先必須定義域是凸集，其次通過其Hessian矩陣（Hessian矩陣是由多元函數(shù)的二階導(dǎo)數(shù)組成的方陣）的正定性來(lái)判斷。如果Hessian矩陣是半正定矩陣，則是f(X)凸函數(shù)。

4.總結(jié)

總結(jié)來(lái)看：

• 凸函數(shù)判定中首先要保證定義域?yàn)橥辜?#xff0c;且保證目標(biāo)函數(shù)為凸函數(shù)；關(guān)鍵在于判定凸函數(shù)。
• 一般的凸優(yōu)化函數(shù)形式是min f(x）的形式，那么這時(shí)取得的局部極小點(diǎn)就是全局最小點(diǎn)；有時(shí)候凸優(yōu)化（convex）的函數(shù)形式為maxf(x）的形式，此時(shí)可以將其轉(zhuǎn)換為minf(x）的形式，那么原來(lái)的形式只要是凹函數(shù)（concave）即可求得局部極大值即全局最大值；
• 無(wú)約束優(yōu)化問題，如果是一個(gè)凸優(yōu)化問題，那么極值點(diǎn)就是全局最大或者最小點(diǎn)；

總結(jié)

以上是生活随笔為你收集整理的优化问题---凸优化基本概念的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。