優(yōu)化是機(jī)器學(xué)習(xí)中的關(guān)鍵步驟。在這個(gè)機(jī)器學(xué)習(xí)系列中，我們將簡(jiǎn)要介紹優(yōu)化問題，然后探討兩種特定的優(yōu)化方法，即拉格朗日乘子和對(duì)偶分解。這兩種方法在機(jī)器學(xué)習(xí)、強(qiáng)化學(xué)習(xí)和圖模型中非常流行。

優(yōu)化問題

優(yōu)化問題通常定義為：

優(yōu)化問題包含一個(gè)目標(biāo)函數(shù)和可選的不等式和等式約束。一般的優(yōu)化問題是NP難問題。但是，很多類別的凸優(yōu)化問題可以在多項(xiàng)式時(shí)間內(nèi)解決。當(dāng)我們將f(x?)和f(x?)相連形成下方的紅線時(shí)，如果f是一個(gè)凸函數(shù)，那么對(duì)于它們之間的點(diǎn)，紅線總是在f的上方，即 y? ≥ f(x?)。

一個(gè)凸優(yōu)化問題具有凸目標(biāo)函數(shù)和凸可行集的特征。可行集是滿足約束條件的x的集合。在凸集中，集合中兩個(gè)點(diǎn)之間的任何值也必須屬于凸集。

從另一個(gè)角度來看，在凸優(yōu)化問題中，f和l是凸函數(shù)，

并且等式約束是仿射函數(shù)，其一般形式為：

順帶一提，仿射函數(shù)是凸函數(shù)，這一點(diǎn)我們后面會(huì)用到。

在機(jī)器學(xué)習(xí)中，線性回歸的目標(biāo)函數(shù)通常表示為最小二乘誤差。最小二乘優(yōu)化問題已經(jīng)得到廣泛研究。有許多數(shù)值方法可以對(duì)它們進(jìn)行求解，除非達(dá)到了某些可擴(kuò)展性限制，否則它們可以通過解析方法（正規(guī)方程）解決。這在優(yōu)化問題中是相對(duì)容易解決的問題。

否則，如果機(jī)器學(xué)習(xí)問題可以表示為線性規(guī)劃問題，我們可以應(yīng)用線性規(guī)劃。這也已經(jīng)得到了廣泛的研究。線性規(guī)劃中x的可行集是一個(gè)多面體。

在我們上面的例子中，虛線是目標(biāo)函數(shù)的等高線。最優(yōu)解x*將是其中一個(gè)頂點(diǎn)。

一般來說，如果問題是凸優(yōu)化問題，我們可以通過數(shù)值方法來解決。一個(gè)函數(shù)是凸函數(shù)，如果它的二階導(dǎo)數(shù)對(duì)于所有x都是正的。

在機(jī)器學(xué)習(xí)中，我們經(jīng)常將問題轉(zhuǎn)換、近似或放寬為這些更簡(jiǎn)單的優(yōu)化模型之一。

拉格朗日乘子

讓我們專注于尋找一個(gè)一般優(yōu)化問題的解。考慮代價(jià)函數(shù)為f=x+y，等式約束為h: x2 + y2 = 25，如下圖所示的紅色圓圈。

為了滿足約束條件，我們沿著約束面法線的正交方向移動(dòng)，即垂直于?x h。為了降低代價(jià)，我們選擇沿著f的負(fù)梯度方向移動(dòng)。當(dāng)我們無法進(jìn)一步移動(dòng)以降低代價(jià)時(shí)，就達(dá)到了最優(yōu)點(diǎn)。這發(fā)生在?h與代價(jià)函數(shù)的梯度對(duì)齊時(shí)。

i.e.,

h(x) = 0也意味著-h(x) = 0。λ的符號(hào)取決于h的定義方式。因此，λ可以是正的、負(fù)的或零。

接下來，我們定義拉格朗日函數(shù)為：

如果我們分別對(duì)拉格朗日函數(shù)關(guān)于x和λ求導(dǎo)，并將它們?cè)O(shè)置為零，如下所示，我們就可以強(qiáng)制執(zhí)行前面描述的最優(yōu)點(diǎn)以及等式約束。

因此，通過找到關(guān)于x和λ的拉格朗日函數(shù)的最優(yōu)點(diǎn)，我們可以確定在強(qiáng)制執(zhí)行等式約束的情況下的最優(yōu)解。我們也可以在拉格朗日函數(shù)中有多個(gè)約束和不等式約束。優(yōu)化問題的形式將為：

拉格朗日函數(shù)的定義如下:

現(xiàn)在不等式約束要求最優(yōu)點(diǎn)在陰影區(qū)域內(nèi)（包括邊界）。當(dāng)解是最優(yōu)時(shí)，f和l的梯度將具有相同的方向，即α? ≥ 0。

讓我們?cè)賹?duì)不等式約束進(jìn)行另一個(gè)觀察。下面的左圖表示一個(gè)具有最優(yōu)解為該圓圈中心的代價(jià)函數(shù)f。

在中間的圖中，我們?yōu)閮?yōu)化問題添加了一個(gè)不等式約束。但是，這個(gè)約束是多余的，因?yàn)闊o約束最優(yōu)點(diǎn)已經(jīng)滿足這個(gè)約束條件。因此，α?可以簡(jiǎn)單地為零，表示它是多余的。

在右邊的圖中，無約束最優(yōu)解落在l的外面。我們必須增加代價(jià)（紅色圓圈）直到它與l相交。對(duì)應(yīng)的最低代價(jià)將使得約束l等于0。

因此，α? l?(x) 總是等于0。

例子

讓我們最大化f(x, y) = x + y，滿足x2 + y2 = 32。

拉格朗日函數(shù)為：

為了解決這個(gè)優(yōu)化問題，我們需要分別對(duì)