拉格朗日函数及其对偶性

前言：机器学习这个吧，随便动动就能碰到我数学天花板。来吧，我们开始吧

拉格朗日函数主要用来求解在约束条件下的最优化问题，

一切从原始问题开始

假设 f(x), c_i(x), h_j(x) 是定义在 R^n 上的连续可微函数，考虑最优化问题

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

称此约束最优化问题为原始最优化问题。

引入广义拉格朗日函数

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 的函数：
\theta_p(x) = max L(x, \alpha, \beta)

这里，下标 p 表示原始问题。

假设给定某个 x ,如果 x 违反原始问题的约束条件

  • 假设有一个 i 使得 c_i(x) \geq 0 那么只要 \alpha_i \rightarrow +\infty其余参数为 0
  • 或者假设有某个 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

所以当都满足约束条件时，max L(x, \alpha, \beta) 可以得到所有的 \alpha 都为 0。另一项恒为 0。此时

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

再最小化

min\theta_p(x) = minf(x)

与原始问题相同。

定义原始问题的最优值
p^* = min\theta_p(x)
又叫做广义拉格朗日函数的极小极大问题。

对偶问题

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

之前的原始问题，第一步是把 \alpha， \beta当做常数，求\theta_p(x)。现在的对偶问题，第一步是把 x 当做常数求\theta_D(\alpha, \beta)

在考虑极大化
max\theta_D(\alpha, \beta)=maxminL(x, \alpha, \beta)

这又叫做，广义拉格朗日函数的极大极小问题

定义最优值

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

原始问题和对偶问题的关系

这才是关键！！！如果求解不一样，那对偶函数有什么用！

在最大熵模型中，正是因为对偶问题和原始问题的解一样，才能互相转换。

现在来探讨这个对偶问题和原始问题的解一样的条件

详见这篇文章

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

推荐阅读更多精彩内容

  • SVM算法原理
    本章涉及到的知识点清单：1、决策面方程2、函数间隔和几何间隔3、不等式约束条件4、SVM最优化模型的数学描述（凸二...
    PrivateEye_zzy阅读 14,553评论 3赞 10
  • SVM(1) 之 拉格朗日乘子法和KKT条件
    其实我之前看过这个地方，但是当时感触不深(或者说根本没看懂,也可能是忘了)，所以重新推导一下。《西瓜书》 、《统计...
    mmmwhy阅读 10,923评论 0赞 3
  • 02 SVM - 拉格朗日乘子法
    01 SVM - 概述 自变量无约束的求极值方法 - 梯度下降法 10 回归算法 - 梯度下降在线性回归中的应用1...
    白尔摩斯阅读 10,114评论 0赞 26
  • 2019-01-21
    LeetCode 202. Happy Number Description Write an algorithm...
    ruicore阅读 1,248评论 0赞 0
  • 独行者
    你应该知道的 没有你在身边 我有多么无聊 孤独和失落 前面的路充满了未知 但我不能不往前走 关于你 我不能表达太多...
    onlyoneHeZ阅读 1,911评论 0赞 6