凸性在優化算法的設計中起著至關重要的作用。這主要是因為在這種情況下分析和測試算法要容易得多。換句話說，如果算法即使在凸設置中也表現不佳，通常我們不應該希望在其他情況下看到很好的結果。此外，盡管深度學習中的優化問題通常是非凸的，但它們通常在局部最小值附近表現出凸問題的某些性質。這可能會導致令人興奮的新優化變體，例如 ( Izmailov et al. , 2018 )。

%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l

%matplotlib inline
from mpl_toolkits import mplot3d
from mxnet import np, npx
from d2l import mxnet as d2l

npx.set_np()

%matplotlib inline
import numpy as np
import tensorflow as tf
from mpl_toolkits import mplot3d
from d2l import tensorflow as d2l

12.2.1。定義

在凸分析之前，我們需要定義凸集和凸函數。它們導致了通常應用于機器學習的數學工具。

12.2.1.1。凸集

集合是凸性的基礎。簡單的說，一套X 在向量空間中是凸的，如果對于任何a,b∈X 連接的線段a和b也在 X. 用數學術語來說，這意味著對于所有 λ∈[0,1]我們有

(12.2.1)λa+(1?λ)b∈Xwhenevera,b∈X.

這聽起來有點抽象。考慮圖 12.2.1。第一組不是凸的，因為存在不包含在其中的線段。其他兩組沒有這樣的問題。

圖 12.2.1第一組是非凸的，另外兩組是凸的。

定義本身并不是特別有用，除非您可以對它們做些什么。在這種情況下，我們可以查看如圖 12.2.2所示的交叉點。假使，假設X和 Y是凸集。然后 X∩Y也是凸的。要看到這一點，請考慮任何a,b∈X∩Y. 自從 X和Y是凸的，連接的線段a和b都包含在 X和Y. 鑒于此，它們還需要包含在X∩Y，從而證明了我們的定理。

圖 12.2.2兩個凸集的交集是凸的。

我們可以毫不費力地加強這個結果：給定凸集 Xi, 他們的交集∩iXi 是凸的。要看到相反的情況不成立，請考慮兩個不相交的集合X∩Y=?. 現在挑 a∈X和b∈Y. 圖 12.2.3中的線段連接a和b 需要包含一些既不在X也不在 Y, 因為我們假設 X∩Y=?. 因此線段不在X∪Y要么，從而證明通常凸集的并集不一定是凸的。

圖 12.2.3兩個凸集的并集不一定是凸集。

通常，深度學習中的問題是在凸集上定義的。例如，Rd, 的集合d維實數向量，是一個凸集（畢竟，在任何兩點之間的線Rd留在Rd). 在某些情況下，我們使用有界長度的變量，例如半徑為 r定義為 {x|x∈Rdand‖x‖≤r}.

12.2.1.2。凸函數

現在我們有了凸集，我們可以引入凸函數 f. 給定一個凸集X, 一個函數 f:X→R是凸的，如果對所有 x,x′∈X對于所有人λ∈[0,1]我們有

(12.2.2)λf(x)+(1?λ)f(x′)≥f(λx+(1?λ)x′).

為了說明這一點，讓我們繪制一些函數并檢查哪些函數滿足要求。下面我們定義了幾個函數，包括凸函數和非凸函數。

f = lambda x: 0.5 * x**2 # Convex
g = lambda x: torch.cos(np.pi * x) # Nonconvex
h = lambda x: torch.exp(0.5 * x) # Convex

x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
  d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

f = lambda x: 0.5 * x**2 # Convex
g = lambda x: np.cos(np.pi * x) # Nonconvex
h = lambda x: np.exp(0.5 * x) # Convex

x, segment = np.arange(-2, 2, 0.01), np.array([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
  d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

f = lambda x: 0.5 * x**2 # Convex
g = lambda x: tf.cos(np.pi * x) # Nonconvex
h = lambda x: tf.exp(0.5 * x) # Convex

x, segment = tf.range(-2, 2, 0.01), tf.constant([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
  d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

正如預期的那樣，余弦函數是非凸的，而拋物線和指數函數是。請注意，要求 X是一個凸集是使條件有意義所必需的。否則結果 f(λx+(1?λ)x′)可能沒有明確定義。

12.2.1.3。詹森不等式

給定一個凸函數f，最有用的數學工具之一是詹森不等式。它相當于凸性定義的概括：

(12.2.3)∑iαif(xi)≥f(∑iαixi)andEX[f(X)]≥f(EX[X]),

在哪里αi是非負實數使得 ∑iαi=1和X是一個隨機變量。換句話說，凸函數的期望不亞于期望的凸函數，后者通常是更簡單的表達式。為了證明第一個不等式，我們一次重復將凸性的定義應用于總和中的一項。

Jensen 不等式的一個常見應用是用一個更簡單的表達式來約束一個更復雜的表達式。例如，它的應用可以關于部分觀察到的隨機變量的對數似然。也就是說，我們使用

(12.2.4)EY～P(Y)[?log?P(X∣Y)]≥?log?P(X),

自從∫P(Y)P(X∣Y)dY=P(X). 這可以用于變分法。這里Y通常是未觀察到的隨機變量，P(Y)是對它可能如何分布的最佳猜測，并且P(X)是分布Y整合出來。例如，在聚類Y可能是集群標簽和 P(X∣Y)是應用集群標簽時的生成模型。

12.2.2。特性

凸函數有許多有用的性質。我們在下面描述了一些常用的。

12.2.2.1。局部最小值是全局最小值

首先，凸函數的局部最小值也是全局最小值。我們可以用反證法證明如下。

考慮一個凸函數f定義在凸集上 X. 假設x?∈X是局部最小值：存在一個小的正值p這樣對于 x∈X滿足 0<|x?x?|≤p我們有f(x?)

假設局部最小值x?不是全局最小值f： 那里存在x′∈X為了哪個 f(x′)

然而，根據凸函數的定義，我們有

(12.2.5)f(λx?+(1?λ)x′)≤λf(x?)+(1?λ)f(x′)<λf(x?)+(1?λ)f(x?)=f(x?),

這與我們的聲明相矛盾x?是局部最小值。因此，不存在x′∈X為了哪個f(x′)

例如，凸函數f(x)=(x?1)2有一個局部最小值x=1，這也是全局最小值。

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

凸函數的局部最小值也是全局最小值這一事實非常方便。這意味著如果我們最小化功能，我們就不會“卡住”。但是請注意，這并不意味著不能有一個以上的全局最小值，或者甚至可能存在一個。例如，函數f(x)=max(|x|?1,0) 在區間內達到最小值[?1,1]. 相反，函數f(x)=exp?(x)沒有達到最小值 R： 為了x→?∞它漸近于 0, 但沒有x為了哪個f(x)=0.

12.2.2.2。下面的凸函數集是凸的

我們可以通過下面的一組凸函數方便地定義凸集。具體來說，給定一個凸函數f定義在凸集上X, 任何以下集合

(12.2.6)Sb=def{x|x∈Xandf(x)≤b}

是凸的。

讓我們快速證明這一點。回想一下，對于任何 x,x′∈Sb我們需要證明 λx+(1?λ)x′∈Sb只要 λ∈[0,1]. 自從f(x)≤b和 f(x′)≤b, 根據凸性的定義我們有

(12.2.7)f(λx+(1?λ)x′)≤λf(x)+(1?λ)f(x′)≤b.

12.2.2.3。凸性和二階導數

每當函數的二階導數 f:Rn→R存在很容易檢查是否f是凸的。我們需要做的就是檢查 Hessian 是否f是半正定的： ?2f?0，即表示Hessian矩陣 ?2f經過H, x?Hx≥0對全部 x∈Rn. 例如，函數 f(x)=12‖x‖2是凸的，因為 ?2f=1，即它的 Hessian 矩陣是一個單位矩陣。

形式上，一個二次可微分的一維函數 f:R→R是凸的當且僅當它的二階導數f″≥0. 對于任何二次可微的多維函數 f:Rn→R, 它是凸的當且僅當它是 Hessian 矩陣?2f?0.

首先，我們需要證明一維情況。看到的凸性f暗示f″≥0我們使用這樣的事實

(12.2.8)12f(x+?)+12f(x??)≥f(x+?2+x??2)=f(x).

由于二階導數由有限差分的極限給出，因此

(12.2.9)f″(x)=lim?→0f(x+?)+f(x??)?2f(x)?2≥0.

看到那個f″≥0暗示f是凸的，我們使用這個事實f″≥0暗示f′是單調非遞減函數。讓a

(12.2.10)f′(α)=f(x)?f(a)x?aandf′(β)=f(b)?f(x)b?x.

通過單調性f′(β)≥f′(α)， 因此

(12.2.11)x?ab?af(b)+b?xb?af(a)≥f(x).

自從x=(1?λ)a+λb， 我們有

(12.2.12)λf(b)+(1?λ)f(a)≥f((1?λ)a+λb),

從而證明凸性。

其次，在證明多維情況之前我們需要一個引理： f:Rn→R是凸的當且僅當對所有x,y∈Rn

(12.2.13)g(z)=deff(zx+(1?z)y)wherez∈[0,1]

是凸的。

為了證明凸性f暗示g是凸的，我們可以證明對于所有a,b,λ∈[0,1]（因此 0≤λa+(1?λ)b≤1)

(12.2.14)g(λa+(1?λ)b)=f((λa+(1?λ)b)x+(1?λa?(1?λ)b)y)=f(λ(ax+(1?a)y)+(1?λ)(bx+(1?b)y))≤λf(ax+(1?a)y)+(1?λ)f(bx+(1?b)y)=λg(a)+(1?λ)g(b).

為了證明相反的情況，我們可以證明對于所有 λ∈[0,1]

(12.2.15)f(λx+(1?λ)y)=g(λ?1+(1?λ)?0)≤λg(1)+(1?λ)g(0)=λf(x)+(1?λ)f(y).

最后，利用上面的引理和一維情況的結果，多維情況可以證明如下。多維函數 f:Rn→R是凸的當且僅當對所有x,y∈Rn g(z)=deff(zx+(1?z)y)， 在哪里z∈[0,1], 是凸的。根據一維情況，這成立當且僅當 g″=(x?y)?H(x?y)≥0 (H=def?2f） 對全部 x,y∈Rn，相當于 H?0根據半正定矩陣的定義。

12.2.3。約束條件

凸優化的一個很好的特性是它允許我們有效地處理約束。也就是說，它允許我們解決 以下形式的約束優化問題：

(12.2.16)minimizexf(x)subject toci(x)≤0for alli∈{1,…,n},

在哪里f是目標和功能ci是約束函數。看看這確實考慮了以下情況 c1(x)=‖x‖2?1. 在這種情況下，參數x被限制在單位球內。如果第二個約束是 c2(x)=v?x+b，那么這對應于所有x躺在半空間上。同時滿足這兩個約束相當于選擇球的一部分。

12.2.3.1。拉格朗日量

通常，解決約束優化問題很困難。解決這個問題的一種方法來自物理學，具有相當簡單的直覺。想象一個盒子里的球。球將滾動到最低的位置，重力將與盒子側面可以施加在球上的力平衡。簡而言之，目標函數（即重力）的梯度將被約束函數的梯度所抵消（由于墻壁“推回”，球需要留在盒子內）。請注意，某些約束可能未激活：球未接觸的墻壁將無法對球施加任何力。

跳過拉格朗日量的推導 L，上述推理可以通過以下鞍點優化問題來表達：

(12.2.17)L(x,α1,…,αn)=f(x)+∑i=1nαici(x)whereαi≥0.

這里的變量αi(i=1,…,n) 是所謂的拉格朗日乘數，可確保正確執行約束。它們被選擇得足夠大以確保 ci(x)≤0對全部i. 例如，對于任何 x在哪里ci(x)<0自然地，我們最終會選擇αi=0. 此外，這是一個想要最大化的鞍點優化問題 L關于所有αi并同時將其最小化x. 有大量的文獻解釋了如何達到這個功能 L(x,α1,…,αn). 為了我們的目的，知道鞍點就足夠了L是原始約束優化問題得到最優解的地方。

12.2.3.2。處罰

至少近似滿足約束優化問題的一種方法 是采用拉格朗日量L. 而不是滿足ci(x)≤0我們只需添加 αici(x)到目標函數f(x). 這確保了約束不會被嚴重違反。

事實上，我們一直在使用這個技巧。考慮第 3.7 節中的權重衰減。在其中我們添加 λ2‖w‖2到目標函數以確保w不會長得太大。從約束優化的角度我們可以看出，這將確保‖w‖2?r2≤0對于一些半徑r. 調整值λ允許我們改變大小 w.

通常，添加懲罰項是確保近似約束滿足的好方法。在實踐中，這比完全滿意更穩健。此外，對于非凸問題，許多使精確方法在凸情況下如此有吸引力的屬性（例如，最優性）不再成立。

12.2.3.3。預測

滿足約束的另一種策略是預測。同樣，我們以前遇到過它們，例如，在9.5 節中處理梯度裁剪時。在那里我們確保梯度的長度為θ通過

(12.2.18)g←g?min(1,θ/‖g‖).

這原來是一個投影g到半徑球上θ. 更一般地，凸集上的投影 X定義為

(12.2.19)ProjX(x)=argminx′∈X?‖x?x′‖,

這是最近的點X到x.

圖 12.2.4凸投影。

投影的數學定義聽起來有點抽象。 圖 12.2.4解釋得更清楚一些。其中有兩個凸集，一個圓和一個菱形。兩組（黃色）內的點在投影期間保持不變。兩個集合外的點（黑色）被投影到集合內最接近原始點（黑色）的點（紅色）。而對于?2球這會使方向保持不變，一般情況下不必如此，正如在菱形的情況下所看到的那樣。

凸投影的用途之一是計算稀疏權重向量。在這種情況下，我們將權重向量投影到?1球，這是圖 12.2.4 中菱形情況的一般化版本 。

12.2.4。概括

在深度學習的背景下，凸函數的主要目的是激發優化算法并幫助我們詳細理解它們。下面我們將看到梯度下降和隨機梯度下降是如何相應推導出來的。

凸集的交集是凸的。工會不是。

凸函數的期望不亞于期望的凸函數（詹森不等式）。

當且僅當它的 Hessian（二階導數矩陣）是半正定的時，二次可微函數是凸函數。

可以通過拉格朗日添加凸約束。在實踐中，我們可以簡單地將它們與對目標函數的懲罰相加。

投影映射到凸集中最接近原始點的點。

12.2.5。練習

假設我們要通過在集合內的點之間繪制所有線并檢查是否包含這些線來驗證集合的凸性。

證明僅檢查邊界上的點就足夠了。

證明僅檢查集合的頂點就足夠了。

表示為 Bp[r]=def{x|x∈Rdand‖x‖p≤r} 半徑球r使用p-規范。證明 Bp[r]對所有人都是凸的p≥1.

給定凸函數f和g， 顯示 max(f,g)也是凸的 證明 min(f,g)不是凸的。

證明softmax函數的歸一化是凸的。更具體地證明的凸性 f(x)=log?∑iexp?(xi).

證明線性子空間，即 X={x|Wx=b}, 是凸集。

證明在線性子空間的情況下 b=0投影 ProjX可以寫成 Mx對于一些矩陣M.

表明對于二次可微凸函數f我們可以寫 f(x+?)=f(x)+?f′(x)+12?2f″(x+ξ) 對于一些ξ∈[0,?].

給定一個凸集X和兩個向量 x和y，證明投影永遠不會增加距離，即 ‖x?y‖≥‖ProjX(x)?ProjX(y)‖.

Discussions