拉格朗日对偶性

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

相关文章

来自专栏TensorFlow从0到N

【译】TensorFlow实现Batch Normalization

原文:Implementing Batch Normalization in Tensorflow 来源:R2RT 译者注:本文基于一个最基础的全连接...

6876
来自专栏Ldpe2G的个人博客

Mxnet 实现图片快速风格化

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

1587
来自专栏PaddlePaddle

【结构化语义模型】深度结构化语义模型

导语 PaddlePaddle提供了丰富的运算单元,帮助大家以模块化的方式构建起千变万化的深度学习模型来解决不同的应用问题。这里,我们针对常见的机器学习任务,提...

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

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

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

2987
来自专栏ATYUN订阅号

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

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

4324
来自专栏企鹅号快讯

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

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

41410
来自专栏技术与生活

深度学习之卷积

今日休假,把卷积神经网络梳理下。先从一些基本概念入手,什么是卷积?为什么叫这么个名字? 搜索了一遍,网上有很多人已经表述的非常好了,这里用自己理解的语言重述下。

952
来自专栏YoungGy

机器翻译之Facebook的CNN与Google的Attention

传统的seq2seq facebook的cnn 结构 特点 position embedding 卷积的引入 GLU控制信息的流动 attention goog...

3389
来自专栏有趣的Python

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

1002
来自专栏深度学习自然语言处理

机器学习之多层感知机理论与实践

阅读大概需要10分钟 作者 Lefteris 翻译 bluepomelo 编辑 zenRRan 有修改 原文链接 http://blog.refu.co/?p=...

4164

扫码关注云+社区