机器学习基础·拉格朗日乘数法

摘要

方法的目标问题，原始问题，对偶问题的描述及形式，相关理论及KKT条件。

正文

  1. 目标
    解决条件极值问题，条件含不等式约束及等式约束，拉格朗日乘数法将约束问题转换为无约束问题。

  2. 问题描述
    假设f(x),c_i(x),h_j(x)是定义在R^n上的连续可微函数。
    \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. 构造拉格朗日函数
    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. 原始问题和对偶问题的关系
    (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)是凸函数，h_j(x)是仿射函数；
    b. 不等式约束c_i(x)是严格可行的。

  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}

  • 备注:注意在使用拉格朗日乘数法时，约束条件的右端为=0，不等式约束是\le 0。
参考资料

[1] 李航.统计学习方法(第二版).清华大学出版社,2019.

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容