一. 最優(yōu)化問題求解

1. 等式約束的極值求法

$\begin{gather*} \underset{t}{min} f(t) \; s.t.\; h_i(t)=0,i=1,\cdots,p \end{gather*}$
目標(biāo)函數(shù): $f(t)$ , 引入Lagrange算子: $L(t,\beta) = f(t) + \sum_{i=1}^n\beta_ih_i(t)$

2. 不等式約束的極值求法

$\begin{gather*} \underset{t}{min}f(t) \; s.t. &g_i(t) \le 0, i=1,\cdots,p \\ &h_j(t) = 0, j=1, \cdots, q \end{gather*}$
目標(biāo)函數(shù): $f(t)$
約束條件:

$g_i(t) \le 0, i=1, \cdots, p$
$h_j(t) \le 0, j=1, \cdots, q$
很多情況, 不等式約束條件可引入新變量轉(zhuǎn)化為等式約束條件, 故上述問題可簡化為:
$\underset{t}{min}f(t)\;s.t.\; g_i(t) = 0, i=1, \cdots, n$

3. 最優(yōu)化問題分類

根據(jù)約束條件和目標(biāo)函數(shù)的類型分為3類:

線性規(guī)劃: 目標(biāo)函數(shù)和約束條件都為變量的線性函數(shù)

二次規(guī)劃: 目標(biāo)函數(shù)為變量的二次函數(shù), 約束條件為線性函數(shù)

非線性規(guī)劃: 目標(biāo)函數(shù)或者約束條件是非線性函數(shù)

4. KKT條件廣義定義

KKT條件指在滿足某些規(guī)則條件下, 非線性規(guī)劃問題能有最優(yōu)解的充要條件, 是廣義拉格朗日乘數(shù)的重要成果
一般優(yōu)化問題(含等式和不等式約束約束):
$\begin{gather*} \underset{t}{min}f(t) \; s.t. &g_i(t) \le 0, i=1,\cdots,p \\ &h_j(t) = 0, j=1, \cdots, q \end{gather*}$
引入Lagrange算子 $\alpha, \beta$ :
$L(t, \alpha, \beta) = f(t) + \sum_{i=1}^p\alpha_i g_i(t) + \sum_{j=1}^q\beta_j h_j(t)$

可將 $\alpha和\beta$ 分別看做兩個(gè)約束 $g_i(t) \le 0和g_j(t) \ 0$ 的限制條件

KKT條件指上述問題的最優(yōu)點(diǎn) $x^*$ 必須滿足:
(1) 約束條件滿足: $g_i(x^*) \le0, h_i(x^*)=0$
(2) $\nabla L(t,\alpha,\beta)|_{t=x^*} = \nabla f(x^*) + \sum_{i=1}^p\alpha_i\nabla g_i(x^*) + \sum_{j=1}^q \beta_j \nabla h_j(x^*) = 0$
即,
最優(yōu)點(diǎn) $x^*$ 處, $\nabla f$ 必須是 $\nabla g_i$ 和 $\nabla h_j$ 的線性組合
引入拉格朗日算子可以求出極值的原因:

由于 $f(t)$ 的 $dt$ 變化方向受其他不等式的約束, 且在極值 $x^*$ 處， $f(t$ )的梯度 $\nabla f(x^*)$ 與 $\nabla g(x^*)$ , $\nabla h(x^*)$ 之間存在線性關(guān)系, 故引入拉格朗日算子可以求出極值

(3) $\beta_j \ne 0$ 且 $\alpha_i \ge 0,\; \alpha_i g_i(x^*) = 0$

不等式 $g_i(t)\le0$ 的限制條件有方向性, 故 $\alpha_i \ge 0$ , 等式 $h_j(t)=0$ 的限制條件無方向性, 故 $\beta_j$ 無符號(hào)限制

5 為什么SVM用Lagrange duality來解決最大化間隔問題?

不等式約束一直是優(yōu)化問題中的難題，求解對偶問題可以將支持向量機(jī)原問題約束中的不等式約束轉(zhuǎn)化為等式約束；

支持向量機(jī)中用到了高維映射，但是映射函數(shù)的具體形式幾乎完全不可確定，而求解對偶問題之后，可以使用核函數(shù)來解決這個(gè)問題。

并不一定要用拉格朗日對偶。要注意用拉格朗日對偶并沒有改變最優(yōu)解，而是改變了算法復(fù)雜度：
在原問題下，求解算法的復(fù)雜度與樣本維度（等于權(quán)值w的維度）有關(guān)；
而在對偶問題下，求解算法的復(fù)雜度與樣本數(shù)量（等于拉格朗日算子a的數(shù)量）有關(guān)。

因此，

如果你是做線性分類，且樣本維度低于樣本數(shù)量的話，在原問題下求解就好了，Liblinear之類的線性SVM默認(rèn)都是這樣做的；
如果你是做非線性分類，那就會(huì)涉及到升維（比如使用高斯核做核函數(shù)，其實(shí)是將樣本升到無窮維），升維后的樣本維度往往會(huì)遠(yuǎn)大于樣本數(shù)量，此時(shí)顯然在對偶問題下求解會(huì)更好。
這樣：

就可以由求特征向量w轉(zhuǎn)化為求比例系數(shù)a，
就可以導(dǎo)出含有內(nèi)積形式的目標(biāo)函數(shù)，
就可以實(shí)現(xiàn)對內(nèi)積后的gram矩陣使用核函數(shù)，以達(dá)到非線性分類的目的。

支持向量機(jī)實(shí)現(xiàn)非線性的方法的數(shù)學(xué)本質(zhì)是升維，升維升到無窮維則無法表達(dá)w, 所以還是使用拉格朗日對偶方法更好一點(diǎn)。準(zhǔn)確的說，可以用一些優(yōu)化算法直接求最小間距，但是，升維的時(shí)候核要是正定的，且升維可數(shù)，而且不是很大的時(shí)候可以用。

二. 拉格朗日對偶和KKT

1. 帶約束的優(yōu)化問題

任意一個(gè)帶約束的優(yōu)化均可寫成:
$\begin{gather*} \underset{x}{min}{f_0(x)}\;s.t. &f_i(x) \le 0, i= 1,\cdots,m \\ &h_i(x)=0,i=1,\cdots,p \end{gather*}$

對于任意 $f_i(x) \le 0$ 均有 $h_i(x)=0$ .
一個(gè) $maxf(x)$ 問題可以轉(zhuǎn)化為 $1-maxf(x)$
假定 $f_0,f_1,\cdots,f_m$ 為凸函數(shù), $h_1,h_2,\cdots,h_p$ 是仿射函數(shù)(形如 $Ax+b$ ),則上述問題為凸優(yōu)化問題, 凸優(yōu)化問題極值唯一

2. primal problem

將上述帶約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題, 定義拉格朗日(Lagrangian)函數(shù)如下:
$L(x,\lambda,v) = f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^pv_ih_i(x)$

最大化Lagrangian, 令
$z(x) = \underset{\lambda \ge 0,v}{max}L(x,\lambda,v)$

z(x)滿足原始約束條件的x, 其值等于 $f_0(x)$ :
滿足初始約束, 則 $h_i(x)=0$ , 拉格朗日函數(shù)第三項(xiàng)被消去:
$L(x,\lambda,v)=f_0(x) + \sum_{i=1}^m\lambda_if_i(x)$
又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clambda_if_i(x)%5Cle0" alt="\lambda_if_i(x)\le0" mathimg="1">, 所以 $L(x,\lambda,v)$ 的最大值在 $f_0(x)$ 處取得.

所以原始帶約束優(yōu)化問題等價(jià)于以下無約束優(yōu)化問題:
$\begin{gather*} min{f_0(x)}\;s.t. &f_i(x) \le 0, i= 1,\cdots,m \\ &h_i(x)=0,i=1,\cdots,p \end{gather*}$
等價(jià)于:
$\underset{x}{min}z(x) = \underset{x}{min} \;\underset{\lambda \ge0,v}{max}L(x,\lambda,v)$
上述問題稱為primal problem
總結(jié):

一個(gè)帶約束的優(yōu)化問題均可用 $minf_0(x)$ 表示

用拉格朗日函數(shù)將帶約束優(yōu)化轉(zhuǎn)為無約束優(yōu)化問題

初始約束條件總可寫成 $f_i(x)\le0$ 的形式, 且拉格朗日算子 $\lambda_i\ge0$ , 所以 $maxL(x,\lambda,v)$ 可去掉約束條件:
去約束:
$f_0(x)\;\cdots s.t. \; f_i(x)\ge0 ,\;h_i(x)=0 \cong \underset{\lambda\ge0,v}{max}L(x,\lambda,v)$
最優(yōu)化:
$\underset{x}{min}f_0(x) \cong \underset{x}{min} \; \underset{\lambda\ge0,v}{max}L(x,\lambda,v)$

3. dual problem

dual problem 只是將primal proble調(diào)換了min和max位置:
$\underset{\lambda \ge0,v}{max} \;\underset{x}{min}L(x,\lambda,v)$
注意上式和 $\underset{x}{min} \;\underset{\lambda \ge0,v}{max}L(x,\lambda,v)$ 并不等價(jià).
令:
$g(\lambda,v) = \underset{x}{min}L(x,\lambda,v)$
上式中 $g(\lambda,v)$ 為拉格朗日對偶函數(shù)(Lagrange dual function), $g(\lambda,v)$ 是primal function的一個(gè)下界.
即, 若將primal proble的最小值記為 $p^*$ , 則對于所有的 $\lambda \ge 0和v$ , 有:
$g(\lambda,v) \le p^*$
證明:
對所有滿足約束條件的x, 總有:
$\sum_{i=1}^m\lambda_i f_i(x) + \sum_{i=1}^pv_ih_i(x) \le 0$
因此
$L(x,\lambda,v) = f_0(x)+\sum_{i=1}^m\lambda_i f_i(x) + \sum_{i=1}^pv_ih_i(x) \le f_0(x)$
假設(shè) $L(x,\lambda,v)$ 在 $x^*$ 處取得極值, 則
$minf_0(x) = f_0(x^*)$
代入上式:
$L(x^*,\lambda,v) = f_0(x^*)+\sum_{i=1}^m\lambda_i f_i(x^*) + \sum_{i=1}^pv_ih_i(x^*) \le f_0(x^*) = p^*$
于是
$g(\lambda,v) = \underset{x}{min}L(x,\lambda,v) \le L(x^*,\lambda,v) \le f_0(x^*) = p*$
這樣, $g(\lambda,v)$ 的上界是 $p^*$ ,于是:
$\underset{\lambda \ge0,v}{max}g(\lambda,v)$
是primal problem的最大下界!
記dual problem 的最優(yōu)值為 $d^*$ , 得到:
$d^* \le p^*$
該性質(zhì)稱為weak duality, 對所有的優(yōu)化問題都成立.
此外,
$p^*-d^*$ 稱為duality gap.

基于weak duality的重要結(jié)論:

無論 primal problem 是什么形式，dual problem 總是一個(gè) convex optimization 的問題——它的極值是唯一的（如果存在的話）. 對于那些難以求解的 primal problem （甚至可以是 NP 問題），我們可以通過找出它的 dual problem ，通過優(yōu)化這個(gè) dual problem 來得到原始問題的一個(gè)下界估計(jì)。

當(dāng)
$d^* = p^*$ 成立時(shí),稱為strong duality.

strong duality 成立的情況下，我們可以通過求解 dual problem 來優(yōu)化 primal problem, 例如SVM 的時(shí)候我們直接假定了 strong duality 的成立.

4. KKT條件

4.1 slater條件

嚴(yán)格滿足約束條件的點(diǎn)x, 指 $f_i(x)\le0$ 嚴(yán)格到 $f_i(x)<0$ , 即存在x滿足:
$f_i(x) <0\;i=1,\cdots,m\\ h_i(x)=0\;i=1,\cdots,p$

4.2 strong duality

原始問題是convex且滿足slater條件,則strong duality成立: $d^*=p^*$
特例: 對某些非convex optimization,strong duality也成立

4.3 SVM中的strong duality

SVM是一種convex optimization, SVM中通過QP(quadratic programming凸二次規(guī)劃)求解, QP是凸優(yōu)化問題的特殊情況
slater條件在SVM中等價(jià)于存在超平面能將數(shù)據(jù)分隔開來

4.4 strong duality成立時(shí)的性質(zhì)

回顧primal problem和dual problem
primal problem: $\underset{x}{min}\;\underset{\lambda \ge 0,v}{max}L(x,\lambda,v)$
dual problem: $\underset{\lambda \ge 0,v}{max}\;\underset{x}{min}L(x,\lambda,v)$
dual problem極值 $d^*$ 在 $(\lambda^*,v^*)$ 處取得, primal problem極值 $p^*$ 在 $x^*$ 處取得
strong duality成立, 則 $d^*=p^*$ , duality gap為0
$f_0(x^*)\le f_0(x^*)$ 成立:
$\begin{align*} f_0(x^*) &=g(\lambda^*,v^*) \\ &=\underset{x}{min} \left( f_0(x)+\sum_{i=1}^m\lambda_i^*f_i(x)+\sum_{i=1}^pv_i^*h_i(x) \right) \\ &\le f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)+\sum_{i=1}^pv_i^*h_i(x^*) \\ &\le f_0(x^*) \end{align*}$
由
$f_0(x^*) \le f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^pv_ih_i(x)$
得:
$f_0(x^*) \le L(x^*,\lambda^*,v^*)$
所以 $x^*$ 是 $L(x,\lambda^*,v^*)$ 的一個(gè)極值點(diǎn), 所以:
$\nabla f_0(x^*) + \sum_{i=1}^m\lambda_i^*\nabla f_i(x^*) + \sum_{i=1}^pv_i^*\nabla h_i(x^*)=0 \;(條件1)$
又由
$f_0(x^*) \le f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)+\sum_{i=1}^pv_i^*h_i(x^*)$
得:
$\lambda_i^*f_i(x^*) \le 0$
故極值點(diǎn) $x^*$ 處:
$\lambda_i^*f_i(x^*)=0,\;i=1,\cdots,m\;(條件2)$
條件(1)(2)合起來稱為complementary slackness.

4.5 complementary slacknes條件分析

條件(2)中若 $\lambda_i^*>0$ 必有 $f_i(x^*)=0$ , 反之, 若 $f_i(x^*)<0$ 可得 $\lambda_i^*=0$ , 此條件在SVM中用來證明非支持向量 $f_i(x^*)<0$ 對應(yīng)的系數(shù) $\alpha_i$

4.6 引入KKT條件

complementary slacknes加上其他約束條件即為KKT條件:
$\begin{align*} \nabla f_0(x^*) + \sum_{i=1}^m\lambda_i^*\nabla f_i(x^*) + \sum_{i=1}^pv_i^*\nabla h_i(x^*)&=0 &(條件1) \\ \lambda_i^*f_i(x^*)&=0,\; i=1,\cdots,m&(條件2) \\ f_i(x^*) &\le 0,\; i=1,\cdots,m&(條件3) \\ \lambda_i^* &\ge0,\;i=1,\cdots,m&(條件4) \\ h_i(x^*) &= 0,\; i=1,\cdots,p&(條件5) \end{align*}$

任何滿足strong duality的問題都滿足KKT條件
primal problem是convex optimization problem是, KKT升級為充要條件, 通過KKT條件可求得$$, $(\lambda^*,v^*)$ 分別是primal problem和dual problem的極值點(diǎn),且strong duality成立

總結(jié)

通過dual problem可求primal problem的解:

只有weak duality成立時(shí), 至少可得到一個(gè)(primal problem的)下界
strong duality成立,則直接求解dual problem
dual problem可能比primal problem更易求解
dual problem可能有一些優(yōu)良的結(jié)構(gòu)(SVM通過dual problem將問題轉(zhuǎn)化為內(nèi)積以使用kernel trick)
迭代求解中, 會(huì)同事求解dual和primal problem, 通過duality gap來early stopping

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一文理解拉格朗日對偶和KKT條件