統(tǒng)計機(jī)器學(xué)習(xí)-拉格朗日對偶性

將有原始問題轉(zhuǎn)化成對偶問題，通過求解對偶問題解決原始問題哲嘲。

原始問題

假設(shè) $f(x)$ ， $c_i(x)$ 媳禁， $h_j(x)$ 是定義在 $\textbf R^n$ 上的連續(xù)可微函數(shù)眠副，考慮約束最優(yōu)化問題
$\min_{x\in \textbf R^n}f(x)\\\tag1$

$\mathrm{s.t.}\ \ c_i(x)\leq0,\ \ i=1,2,\cdots,k\\\tag2$

$h_j(x)=0,\ \ j=1,2,\cdots,l\tag3$

稱此約束最優(yōu)化問題為原始最優(yōu)化問題或原始問題。

如果只是極小化(1)是比較容易的竣稽，但是加上約束就不太好處理囱怕，于是首先引入廣義拉格朗日函數(shù)
$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\tag4$
$\alpha_i$ 和 $\beta_j$ 是拉格朗日乘子，規(guī)定 $\alpha_i\geq0$ 毫别。定義函數(shù)
$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta)\\ =\max_{\alpha,\beta:\alpha_i\geq0}\bigg (f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\bigg )\tag5$
這是一個關(guān)于 $x$ 的函數(shù)娃弓。首先把 $x$ 看做一個常量，再此基礎(chǔ)上確定使(4)最大的 $\alpha_i$ 和 $\beta_j$ 岛宦，然后帶入(5)就成為了一個關(guān)于 $x$ 的函數(shù)台丛。

如果滿足了約束，很容易得到 $\theta_P(x)=f(x)$ 砾肺。因為第二項中 $\alpha_i\geq0$ 挽霉，且條件 $c_i(x)\leq0$ ，所以乘積 $\alpha_ic_i(x)\leq0$ 变汪，取最大則等于0侠坎，第三項滿足條件時為0，所以 $\theta_P(x)=f(x)$ 裙盾。

如果不滿足條件实胸，則會得到
$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\geq0}\bigg (f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\bigg )=+\infty\tag6$
因為如果 $c_i(x)\gt0$ ，則可以使 $\alpha_i=+\infty$ 番官。同理童芹，如果 $h_j(x)\neq0$ ，也可以找到 $\beta_j$ 使 $\beta_jh_j(x)=+\infty$ 鲤拿。

所以(5)可以改寫成
$\theta_P(x)=\begin{cases}f(x),\ x滿足原始問題約束\\ +\infty,\ 其他 \end{cases}\tag7$
于是原始問題就等于極小化問題
$\min_{x}\theta_P(x)=\min_x\max_{\alpha,\beta:\alpha_i\geq0}L(x,\alpha,\beta)\tag8$
稱為廣義拉格朗日函數(shù)的極大極小問題假褪。定義原始問題的最優(yōu)值
$p^*=\min_x\theta_P(x)\tag9$

對偶問題

定義
$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)\tag{10}$
類似的，這是一個關(guān)于 $\alpha$ 和 $\beta$ 的函數(shù)近顷。首先把 $\alpha$ 和 $\beta$ 看做一個常量生音，再此基礎(chǔ)上確定使(10)最大的 $x$ 宁否，然后帶入(10)就成為了一個關(guān)于 $\alpha$ 和 $\beta$ 的函數(shù)。

對公式(10)極大化缀遍，即
$\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geq0}\min_xL(x,\alpha,\beta)\\ =\max_{\alpha,\beta:\alpha_i\geq0}\min_x\bigg (f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\bigg )\tag{11}$
稱為廣義拉格朗日函數(shù)的極大極小問題慕匠。(11)等價于約束最優(yōu)化問題
$\max_{\alpha,\beta}\theta_D(\alpha,\beta)=\max_{\alpha,\beta}\min_xL(x,\alpha,\beta)\tag{12}$

$\mathrm{s.t.}\ \ \alpha_i\geq0,\ i=1,2,\cdots,k\tag{13}$

定義對偶問題的最優(yōu)值
$d^*=\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)\tag{14}$

原始問題和對偶問題的關(guān)系

定理1

若原始問題和對偶問題都有最優(yōu)值，則
$d^*\leq p^*\tag{15}$
證明略域醇。即當(dāng)原始問題和對偶問題都有最優(yōu)值時台谊，原始問題的最優(yōu)值大于等于對偶問題的最優(yōu)值。

推論1

設(shè) $x^*$ 和 $\alpha^*$ 譬挚， $\beta^*$ 分別是原始問題(1)-(3)和對偶問題(12)-(13)的可行解锅铅，并且 $d^*= p^*$ ，則 $x^*$ 和 $\alpha^*$ 减宣， $\beta^*$ 分別是原始問題和對偶問題的最優(yōu)解盐须。

證明略。即兩者都是最優(yōu)解時漆腌， $d^*= p^*$ 贼邓。

于是存在某些條件下可以用解對偶問題代替解原始問題，且 $d^*= p^*$

定理2

對于原始問題(1)-(3)和對偶問題(12)-(13)闷尿。假設(shè)函數(shù) $f(x)$ 和 $c_i(x)$ 是凸函數(shù)塑径， $h_j(x)$ 是仿射函數(shù)；并且假設(shè)不等式約束 $c_i(x)$ 是嚴(yán)格可行的填具，即存在 $x$ 晓勇，對所有 $i$ 有 $c_i(x)\lt0$ ，則存在 $x^*$ 灌旧， $\alpha^*$ ， $\beta^*$ 绰筛，使 $x^*$ 是原始問題的解枢泰， $\alpha^*$ ， $\beta^*$ 是對偶問題的解铝噩，并且
$d^*= p^*=L(x^*,\alpha^*,\beta^*)\tag{16}$

定理3

對于原始問題(1)-(3)和對偶問題(12)-(13)衡蚂。假設(shè)函數(shù) $f(x)$ 和 $c_i(x)$ 是凸函數(shù)， $h_j(x)$ 是仿射函數(shù)骏庸；并且假設(shè)不等式約束 $c_i(x)$ 是嚴(yán)格可行的毛甲，則 $x^*$ 和 $\alpha^*$ ， $\beta^*$ 分別是原始問題和對偶問題的解充分必要條件是 $x^*$ 具被， $\alpha^*$ 玻募， $\beta^*$ 滿足Karush Kuhn Tucker(KKT)條件：
$\nabla_xL(x^*,\alpha^*,\beta^*)=0\tag{17}$