拉格朗日函數(shù)及其對偶性

前言：機(jī)器學(xué)習(xí)這個吧，隨便動動就能碰到我數(shù)學(xué)天花板。來吧，我們開始吧

拉格朗日函數(shù)主要用來求解在約束條件下的最優(yōu)化問題，

一切從原始問題開始

假設(shè) f(x), c_i(x), h_j(x) 是定義在 R^n 上的連續(xù)可微函數(shù)，考慮最優(yōu)化問題

min
f(x)
s.t.
c_i(x) \leq 0, i = 1, 2, ..., k
h_j(x) = 0, j = 1, 2, ..., l

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

引入廣義拉格朗日函數(shù)

L(x, \alpha, \beta) = f(x) + \sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)

這里，x=(x^{(1)},x^{(1)},...,x^{(1)})^T \in R^n,\alpha_i, \beta_j是拉格朗日乘子，\alpha_i \geq 0.考慮 x 的函數(shù)：
\theta_p(x) = max L(x, \alpha, \beta)

這里，下標(biāo) p 表示原始問題。

假設(shè)給定某個 x ,如果 x 違反原始問題的約束條件

  • 假設(shè)有一個 i 使得 c_i(x) \geq 0 那么只要 \alpha_i \rightarrow +\infty其余參數(shù)為 0
  • 或者假設(shè)有某個 j 使 h_j(x) \neq 0，則可令\beta_j \rightarrow +\infty使\beta_jh_j(x) \rightarrow +\infty
    都可以得到
    \theta_p(x)=max[f(x) + \sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)]=+\infty

所以當(dāng)都滿足約束條件時，max L(x, \alpha, \beta) 可以得到所有的 \alpha 都為 0。另一項(xiàng)恒為 0。此時

\theta_p(x) = max L(x, \alpha, \beta)=f(x)

再最小化

min\theta_p(x) = minf(x)

與原始問題相同。

定義原始問題的最優(yōu)值
p^* = min\theta_p(x)
又叫做廣義拉格朗日函數(shù)的極小極大問題。

對偶問題

定義
\theta_D(\alpha, \beta)=minL(x, \alpha, \beta)

之前的原始問題，第一步是把 \alpha， \beta當(dāng)做常數(shù)，求\theta_p(x)?，F(xiàn)在的對偶問題，第一步是把 x 當(dāng)做常數(shù)求\theta_D(\alpha, \beta)

在考慮極大化
max\theta_D(\alpha, \beta)=maxminL(x, \alpha, \beta)

這又叫做，廣義拉格朗日函數(shù)的極大極小問題

定義最優(yōu)值

d^* = max\theta_D(\alpha, \beta)

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

這才是關(guān)鍵！??！如果求解不一樣，那對偶函數(shù)有什么用！

在最大熵模型中，正是因?yàn)閷ε紗栴}和原始問題的解一樣，才能互相轉(zhuǎn)換。

現(xiàn)在來探討這個對偶問題和原始問題的解一樣的條件

詳見這篇文章

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 本章涉及到的知識點(diǎn)清單：1、決策面方程2、函數(shù)間隔和幾何間隔3、不等式約束條件4、SVM最優(yōu)化模型的數(shù)學(xué)描述（凸二...
    PrivateEye_zzy閱讀 13,601評論 3贊 10
  • 其實(shí)我之前看過這個地方，但是當(dāng)時感觸不深(或者說根本沒看懂,也可能是忘了)，所以重新推導(dǎo)一下?！段鞴蠒?、《統(tǒng)計(jì)...
    mmmwhy閱讀 5,783評論 0贊 3
  • 01 SVM - 概述 自變量無約束的求極值方法 - 梯度下降法 10 回歸算法 - 梯度下降在線性回歸中的應(yīng)用1...
    白爾摩斯閱讀 4,891評論 0贊 26
  • LeetCode 202. Happy Number Description Write an algorithm...
    ruicore閱讀 195評論 0贊 0
  • 你應(yīng)該知道的 沒有你在身邊 我有多么無聊 孤獨(dú)和失落 前面的路充滿了未知 但我不能不往前走 關(guān)于你 我不能表達(dá)太多...
    onlyoneHeZ閱讀 299評論 0贊 6

友情鏈接更多精彩內(nèi)容