機器學(xué)習(xí)基礎(chǔ)·拉格朗日乘數(shù)法

摘要

方法的目標(biāo)問題，原始問題，對偶問題的描述及形式，相關(guān)理論及KKT條件。

正文

  1. 目標(biāo)
    解決條件極值問題，條件含不等式約束及等式約束，拉格朗日乘數(shù)法將約束問題轉(zhuǎn)換為無約束問題。

  2. 問題描述
    假設(shè)f(x),c_i(x),h_j(x)是定義在R^n上的連續(xù)可微函數(shù)。
    \begin{align} \min_{x\in R^n}\ \ &f(x)\\ s.t.\ \ &c_i(x)\leq0,i=1,2,...,k\\ &h_j(x)=0,j=1,2,...,l \end{align}

  3. 構(gòu)造拉格朗日函數(shù)
    L(x,\alpha ,\beta )=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x),\alpha_i \geq0

  4. 原始問題的等價表示
    \min_x\theta_p(x)=\min_x\max_{\alpha ,\beta :\alpha_i\geq 0 } L(x,\alpha,\beta)

  5. 對偶問題
    \max_x\theta_D(\alpha,\beta)=\max_{\alpha,\beta :\alpha_i\geq 0}\min_x L(x,\alpha,\beta )

  6. 原始問題和對偶問題的關(guān)系
    (1) d^*=\max_{\alpha,\beta :\alpha_i\geq 0}\min_x L(x,\alpha,\beta )\leq \min_x\max_{\alpha ,\beta :\alpha_i\geq 0 } L(x,\alpha,\beta)=p^*
    (2) d^*=p^*的條件
    a. f(x),c_i(x)是凸函數(shù)，h_j(x)是仿射函數(shù)；
    b. 不等式約束c_i(x)是嚴(yán)格可行的。

  7. KKT條件

\begin {align} &\nabla _x L(x^*,\alpha ^*,\beta ^*)=0\\ &\alpha_i^*c_i(x^*)=0,i=1,2,...,k\\ &c_i(x^*) \leq 0,i=1,2,...,k\\ &\alpha _i^* \geq 0,i=1,2,...,k\\ &h_j(x^*)=9,j=1,2,...,l \end {align}

  • 備注:注意在使用拉格朗日乘數(shù)法時，約束條件的右端為=0，不等式約束是\le 0。
參考資料

[1] 李航.統(tǒng)計學(xué)習(xí)方法(第二版).清華大學(xué)出版社,2019.

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

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

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