拉格朗日对偶性

整理自统计机器学习附录C。

目录:

  • 原始问题
  • 对偶问题
  • 原始问题与对偶问题的关系

1、原始问题

$\underset{x \in R^n} {min} \quad f(x)$

$s.t. \quad c_i(x) \leq 0,\quad i=1,2,...,k  $

$\ \qquad h_i(x)=0,\quad i=1,2,...,l$

引入拉格朗日函数:$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_i \quad \alpha_i \geq 0$

考虑x的函数:$\theta_p(x)=\underset{x}{max} \ L(x,\alpha,\beta)$

若x违反原始问题的约束,即$c_i(x)>0,h_j(x)!=0$,则$\theta_p(x)=+\infty$;相反,若x满足约束,则$\theta_p(x)=f(x)$;

故,原始问题等价于:$\underset{x}{min} \ \theta_p(x) = \underset{x}{min} \ \underset{\alpha,\beta:\alpha_i \geq 0}{max} \ L(x,\alpha,\beta)$

这个称为广义拉格朗日问题的极小极大问题。

至此,原始问题就可以表示为另一种形式,即广义拉格朗日问题的极小极大问题,这样做也是把一个约束优化问题转变成了无约束优化问题。

定义:$p^*=min \ \theta_p(x)$,为原始问题的最优值。

2、对偶问题

定义:$\theta_D(\alpha,\beta)=\underset{x}{min} \ L(x,\alpha,\beta) $

考虑极大化$\theta_D(\alpha,\beta)=\underset{x}{min} \ L(x,\alpha,\beta) $,即:

$\underset{\alpha,\beta:\alpha_i \geq 0}{max} \theta_D(\alpha,\beta)=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \ min \ L(x,\alpha,\beta) $

称之为广义拉格朗日问题的极大极小问题。

则:

$\underset{\alpha,\beta:\alpha_i \geq 0}{max} \quad \theta_D(\alpha,\beta)=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \ min \ L(x,\alpha,\beta) $

$s.t.\quad \alpha_i \geq 0,\ i=1,2,...,k$

称为原始问题的对偶问题,(把max和min互换即可)。

定义$\quad d^*=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \theta_D(\alpha,\beta)\quad$ 是对偶问题的最优值。

3、原始问题与对偶问题的关系

定理C.1 :  若原始问题和对偶问题都有最优值,则:

$d^*=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \ min \ L(x,\alpha,\beta) \leq \underset{x}{min} \ \underset{\alpha,\beta:\alpha_i \geq 0}{max} \ L(x,\alpha,\beta) = p^* $

这个很显然: $\theta_D(\alpha,\beta)=\underset{x}{min} \ L(x,\alpha,\beta) \leq \theta_p(x)=\underset{x}{max} \ L(x,\alpha,\beta)$,故

$\underset{x}{max} \ \theta_D(\alpha,\beta) \leq \underset{x}{min}  \ \theta_p(x)$,得证。

以上称之为弱对偶性(weak duality),$p^*-d^*$称为对偶间隙(duality gap)。

推论C.1 : 设$x^*$和$\alpha^*,\beta^*$分别为原始问题和对偶问题的可行解,且$d^*=p^*$,则$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的最优解。

以上称之为强对偶性(strong duality),

定理C.2:考虑对偶问题和原始问题,假设f(x),$c_i(x)$皆为凸函数,$h_j(x)$为仿射函数,且假设$c_i(x)$严格可行,则存在$\alpha^*,\beta^*,x^*$,使$x^*$是原始问题的解,$\alpha^*,\beta^*$是对偶问题的解,且$p^*=d^*=L(x^*,\alpha^*,\beta^*)$.

定理C.3:同C.2的假设,则$\alpha^*,\beta^*,x^*$是解的充分必要条件是,满足KKT条件:

$\bigtriangledown_x L(x^*,\alpha^*,\beta^*)=0     \qquad 最优条件$

$\bigtriangledown_\alpha L(x^*,\alpha^*,\beta^*)=0$

$\bigtriangledown_\beta L(x^*,\alpha^*,\beta^*)=0$

$\alpha_ic_i(x)=0  \qquad  互补条件$

$c_i(x)=0,\alpha_i \geq 0,,i=1,2...,k \qquad 约束条件$

$h_j(x)=0,j=1,2,...,l  \qquad 约束条件$

以上。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

在 TensorFlow 里构建神经网络来可视化高维数据

在诸如自然语言处理、推荐系统构建等深度学习研究的许多方面,词汇嵌入和高维数据无处不在。谷歌最近开源了 embedding project 项目,此项目是一个交...

913
来自专栏AI研习社

Kaggle Titanic 生存预测比赛超完整笔记(上)

一直想在Kaggle上参加一次比赛,奈何被各种事情所拖累。为了熟悉一下比赛的流程和对数据建模有个较为直观的认识,断断续续用一段时间做了Kaggle上的入门比赛:...

6953
来自专栏YoungGy

LinearAlgebra_1

方程组的几何解释 linear equation row picture column picture 矩阵计算的两种方法 some questions 需要思...

23910
来自专栏数值分析与有限元编程

三角形面积坐标

(一)三角形面积坐标的定义 三角形中任一点P与其三个角点相连形成三个子三角形,如图1所示 ? 需要注意的是,这里引用的面积坐标,只限于用在一个三角形单元之内,在...

3745
来自专栏WD学习记录

机器学习 学习笔记(2)拉格朗日乘子法 拉格朗日对偶性

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法,通过引入拉格朗日乘子,可将有d个变量与k个约束条件的最优化问题转化为具有d+k个变量的无约束优化问题的...

761
来自专栏云时之间

帮助阿姨学数学(线性代数篇)

前言 第一次接触线性代数是在大一的第一学期,学完以后分数不低,但是在结束考试后我就有点心虚,在这一段时间因为有个阿姨来问我线性代数,又温习了一遍,心里边变得更心...

36613
来自专栏YoungGy

LinearAlgebra_3

矩阵空间秩一矩阵小世界图 矩阵空间 秩一矩阵 小世界图 图和网络 零空间 左零空间 行空间 欧拉公式 工业用公式 正交向量和子空间 向量正交 子空间正交 矩阵的...

2189
来自专栏用户画像

FTRL

版权声明:本文为博主-姜兴琪原创文章,未经博主允许不得转载。 https://blog.csdn.net/jxq0816/article/d...

1013
来自专栏YoungGy

LinearAlgebra_4

投影矩阵和最小二乘 二维空间 多维空间 正交矩阵和Gram-Schmidt正交化 回顾 正交基 正交矩阵 如何变成正交矩阵 行列式与其性质 行列式公式和代数余子...

2065
来自专栏YoungGy

LinearAlgebra_2

列空间和零空间 回顾 主题 例子 AXb 求解AX0 回顾 主题 AX0求解的总体思路 例子 形式化的求解 AXb 什么时候有解 有解的话求解 特解 求出通解 ...

2159

扫码关注云+社区