拉格朗日对偶性

整理自统计机器学习附录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 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

6- 深度学习之神经网络核心原理与算法-学习率

1032
来自专栏企鹅号快讯

常用的像素操作算法:Resize、Flip、Rotate

Resize 图像缩放是把原图像按照目标尺寸放大或者缩小,是图像处理的一种。 图像缩放有多种算法。最为简单的是最临近插值算法,它是根据原图像和目标图像的尺寸,计...

42610
来自专栏marsggbo

论文笔记系列-Simple And Efficient Architecture Search For Neural Networks

本文提出了一种新方法,可以基于简单的爬山过程自动搜索性能良好的CNN架构,该算法运算符应用网络态射,然后通过余弦退火进行短期优化运行。

1131
来自专栏深度学习那些事儿

利用pytorch实现神经网络风格迁移Neural Transfer

载入图像输入大小无要求,最终会被剪裁到相同大小,这是因为神经网络设计了一个特定的输入大小,因此内容图像和风格图像必须大小一致。

3222
来自专栏ATYUN订阅号

一文教你实现skip-gram模型,训练并可视化词向量

在本教程中,我将展示如何在Tensorflow中实现一个Word2Vec(Word2Vec是从大量文本语料中以无监督的方式学习语义知识的一种模型,它被大量地用在...

4894
来自专栏州的先生

使用机器学习模型快速进行图像分类识别

1583
来自专栏瓜大三哥

竞争型神经网络续1

1.竞争神经网络函数 1.1创建函数 1.1.1 newc函数 newc函数用于创建一个竞争层,这是一个旧版本的函数,现在用competlayer函数代替。函数...

37010
来自专栏Ldpe2G的个人博客

Mxnet 实现图片快速风格化

论文链接:Perceptual Losses for Real-Time Style Transfer and Super-Resolution

1657
来自专栏PPV课数据科学社区

Tensorflow入门-白话mnist手写数字识别

文章目录 mnist数据集 简介 图片和标签 One-hot编码(独热编码) 神经网络的重要概念 输入(x)输出(y)、标签(label) 损失函数(loss ...

47810
来自专栏计算机视觉战队

在单机上快速、精确的100000类别的检测

今天带来的这篇推送,估计您有读过或试验过,但是为了让更多的科研学者知道这么“牛”的内容知识,接下来就开始说说今天的主题——1000000类的快速精确检测。 注:...

2906

扫码关注云+社区