拉格朗日对偶性

拉格朗日对偶性

在机器学习中,我们经常会遇到给定某些约束条件求解某个函数最大值或最小值的情况,称之为约束最优化,通常的做法是利用拉格朗日对偶性将原始问题转化为对偶问题,通过解对偶问题进而得到原始问题的解. 在机器学习的很多方法中都有用到此方法,如最大熵模型和SVM.

原始问题

我们假设f(x),ci(x),h(x)f(x),c_i(x),h_(x)f(x),ci​(x),h(​x)是定义在RnR^nRn上的连续可微函数,考虑如下约束最优化问题:

对于最优化问题我们通常转化为求min min⁡x∈Rn f(x)s.t. ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l \begin{aligned} \min_{x\in R^n}\ \ \ \ &f(x)\\ s.t.\ \ \ \ &c_i(x)\leq 0,\ \ \ i=1,2,\dots,k\\ &h_j(x) = 0,\ \ j=1,2,\dots, l \end{aligned} x∈Rnmin​ s.t. ​f(x)ci​(x)≤0, i=1,2,…,khj​(x)=0, j=1,2,…,l​ 我们称这个约束最优化问题为原始问题.

根据高等数学的相关知识可知,对于约束最优化的最常用解法是采用拉格朗日乘数法,将其转化为无约束的函数进而求其最值.

因此我们引入广义拉格朗日函数(generalized Lagrange function): L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x) L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k\alpha_ic_i(x) + \sum_{j=1}^l \beta_jh_j(x)L(x,α,β)=f(x)+i=1∑k​αi​ci​(x)+j=1∑l​βj​hj​(x)

其中,αi,βj\alpha_i,\beta_jαi​,βj​是拉格朗日乘子,αi≥0\alpha_i \geq 0αi​≥0,我们有如下关于xxx的函数: (1.1)θP(x)=max⁡α,β:αi≥0 L(x,α,β)\theta_P(x) = \max_{\alpha,\beta:\alpha_i\geq 0}\ L(x, \alpha, \beta)\tag{1.1}θP​(x)=α,β:αi​≥0max​ L(x,α,β)(1.1) 下标PPP表示原始问题.

假设给定某个xxx,若xxx违反原始问题的约束条件,即存在某个iii使得ci(w)>0c_i(w)>0ci​(w)>0或者存在某个jjj使得hj(x)≠0h_j(x)\neq 0hj​(x)̸​=0,那么有

θP(x)=max⁡α,β:αi≥0[f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)]=+∞ \theta_P(x) = \max_{\alpha,\beta:\alpha_i\geq 0} \Big[f(x) + \sum_{i=1}^k\alpha_ic_i(x) + \sum_{j=1}^l \beta_jh_j(x)\Big] = + \infty θP​(x)=α,β:αi​≥0max​[f(x)+i=1∑k​αi​ci​(x)+j=1∑l​βj​hj​(x)]=+∞

若某个iii使得约束ci(x)>0c_i(x)>0ci​(x)>0,则令αi→+∞\alpha_i\rightarrow + \inftyαi​→+∞,若存在某个hj(x)=0h_j(x)=0hj​(x)=0,则令βjh(x)→+∞\beta_jh_(x)\rightarrow + \inftyβj​h(​x)→+∞.

我们可以这样理解,拉格朗日函数相当于构造了一个含参函数,在满足约束条件的情况下,这个函数的值总是小于等于目标函数f(x)f(x)f(x). 而我们此时选取合适的参数α、β\alpha、\betaα、β令该函数最大可使等号成立,即令L(x,α,β)=f(x)L(x,\alpha,\beta) = f(x)L(x,α,β)=f(x);若不满足约束条件,则总存在α、β\alpha、\betaα、β使得该函数趋向于+∞+\infty+∞.

这里的max⁡\maxmax就是选取参数α、β\alpha、\betaα、β的过程.

即 θP(x)={f(x),x满足原始问题约束+∞,其他 \theta_P(x) = \begin{cases} f(x),&x满足原始问题约束\\ +\infty, &其他 \end{cases} θP​(x)={f(x),+∞,​x满足原始问题约束其他​

至此,我们用一个无约束的函数替代了原来的约束项,接下来我们进一步考虑求解目标函数f(x)f(x)f(x)的最小化.

根据之前的理解,我们很容易得出,求解f(x)f(x)f(x)的最小化等价于求解θP(x)\theta_P(x)θP​(x)最小化: (1.2)min⁡xθP(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β) \min_x \theta_P(x) = \min_x \max_{\alpha,\beta:\alpha_i\geq 0}L(x,\alpha,\beta)\tag{1.2} xmin​θP​(x)=xmin​α,β:αi​≥0max​L(x,α,β)(1.2)

我们将 (1.3)min⁡xmax⁡α,β:αi≥0L(x,α,β)\min_x \max_{\alpha,\beta:\alpha_i\geq 0}L(x,\alpha,\beta)\tag{1.3}xmin​α,β:αi​≥0max​L(x,α,β)(1.3) 称为广义拉格朗日函数的极小极大问题. 我们定义原始问题的最优值 (1.4)p∗=min⁡xθP(x)p^* = \min_x\theta_P(x)\tag{1.4}p∗=xmin​θP​(x)(1.4) 称为原始问题的值.

对偶问题

定义α、β\alpha、\betaα、β的函数: (2.1)θD(α,β)=min⁡xL(x,α,β)\theta_D(\alpha,\beta) = \min_xL(x, \alpha,\beta)\tag{2.1}θD​(α,β)=xmin​L(x,α,β)(2.1) 再考虑极大化θD(α,β)\theta_D(\alpha, \beta)θD​(α,β),即 (2.2)max⁡α,β:αi≥0θD(α,β)=max⁡α,β:αi≥0min⁡xL(x,α,β) \max_{\alpha,\beta:\alpha_i\geq 0}\theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i\geq 0} \min_x L(x,\alpha,\beta)\tag{2.2} α,β:αi​≥0max​θD​(α,β)=α,β:αi​≥0max​xmin​L(x,α,β)(2.2) 我们将 (2.4)max⁡α,β:αi≥0min⁡xL(x,α,β) \max_{\alpha,\beta:\alpha_i\geq 0} \min_x L(x,\alpha,\beta)\tag{2.4} α,β:αi​≥0max​xmin​L(x,α,β)(2.4) 称为广义拉格朗日函数的极大极小问题.

将广义拉格朗日函数的极大极小问题表示为约束最优化问题: (2.5)max⁡α,βθD(α,β)=max⁡α,βmin⁡xL(x,α,β)s.t. αi≥0, i=1,2…,k \begin{aligned} &\max_{\alpha,\beta}\theta_D(\alpha,\beta) = \max_{\alpha,\beta} \min_x L(x,\alpha,\beta)\tag{2.5}\\ &s.t.\ \ \ \ \alpha_i\geq0,\ \ \ i=1,2\dots,k \end{aligned} ​α,βmax​θD​(α,β)=α,βmax​xmin​L(x,α,β)s.t. αi​≥0, i=1,2…,k​(2.5) 称为原始问题的对偶问题.

原始问题如下: min⁡xθP(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β) \min_x \theta_P(x) = \min_x \max_{\alpha,\beta:\alpha_i\geq 0}L(x,\alpha,\beta) xmin​θP​(x)=xmin​α,β:αi​≥0max​L(x,α,β)

定义对偶问题的最优值: (2.6)d∗=max⁡α,β:αi≥0θD(α,β)d^* = \max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)\tag{2.6}d∗=α,β:αi​≥0max​θD​(α,β)(2.6)

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

(1)若原始问题和对偶问题都有最优值, 对于式(1.1)(2.1)(1.1)(2.1)(1.1)(2.1),对于任意α、β、x\alpha、\beta、xα、β、x,我们有 θD(α,β)=min⁡xL(x,α,β)≤L(x,α,β)≤max⁡α,β:αi≥0 L(x,α,β)=θP(x) \theta_D(\alpha,\beta) = \min_xL(x, \alpha,\beta)\leq L(x,\alpha,\beta)\leq \max_{\alpha,\beta:\alpha_i\geq 0}\ L(x, \alpha, \beta) =\theta_P(x) θD​(α,β)=xmin​L(x,α,β)≤L(x,α,β)≤α,β:αi​≥0max​ L(x,α,β)=θP​(x) 即 θD(α,β)≤θP(x)\theta_D(\alpha,\beta)\leq \theta_P(x)θD​(α,β)≤θP​(x) 且原始问题和对偶问题都有最优值,所以 max⁡α,β:αi≥0θD(α,β)≤min⁡xθP(x)\max_{\alpha,\beta:\alpha_i\geq 0}\theta_D(\alpha,\beta)\leq \min_x\theta_P(x)α,β:αi​≥0max​θD​(α,β)≤xmin​θP​(x) 即 d∗=max⁡α,β:αi≥0θD(α,β)≤min⁡xθP(x)=p∗ d^* = \max_{\alpha,\beta:\alpha_i\geq 0}\theta_D(\alpha,\beta)\leq \min_x\theta_P(x) = p^* d∗=α,β:αi​≥0max​θD​(α,β)≤xmin​θP​(x)=p∗ 对偶问题的最优值应当小于等于原始问题的最优值.

在某些条件下,会出现两者的最优值相等d∗=p∗d^* = p^*d∗=p∗,此时我们就可以用对偶问题替代原始问题,而此时的x∗,α∗、β∗x^*,\alpha^*、\beta^*x∗,α∗、β∗分别是原始问题和对偶问题的最优解.

(2)我们给出如下

定理(充分条件)

对于原始问题 min⁡x∈Rn f(x)s.t. ci(x)≤0, i=1,2,…,khj(x)=0, j=1,2,…,l \begin{aligned} \min_{x\in R^n}\ \ \ \ &amp;f(x)\\ s.t.\ \ \ \ &amp;c_i(x)\leq 0,\ \ \ i=1,2,\dots,k\\ &amp;h_j(x) = 0,\ \ j=1,2,\dots, l \end{aligned} x∈Rnmin​ s.t. ​f(x)ci​(x)≤0, i=1,2,…,khj​(x)=0, j=1,2,…,l​ 和对偶问题 max⁡α,βθD(α,β)=max⁡α,βmin⁡xL(x,α,β)s.t. αi≥0, i=1,2…,k \begin{aligned} &amp;\max_{\alpha,\beta}\theta_D(\alpha,\beta) = \max_{\alpha,\beta} \min_x L(x,\alpha,\beta)\\ &amp;s.t.\ \ \ \ \alpha_i\geq0,\ \ \ i=1,2\dots,k \end{aligned} ​α,βmax​θD​(α,β)=α,βmax​xmin​L(x,α,β)s.t. αi​≥0, i=1,2…,k​ 假设f(x)、ci(x)f(x)、c_i(x)f(x)、ci​(x)是凸函数,hj(x)h_j(x)hj​(x)是仿射函数,并且假设不等式约束ci(x)c_i(x)ci​(x)是严格可行的,即存在xxx,使得所有的ci(x)&lt;0c_i(x)&lt;0ci​(x)<0,

则存在x∗,α∗,β∗x^*,\alpha^*,\beta^*x∗,α∗,β∗使得x∗x^*x∗是原始问题的解,α∗,β∗\alpha^*,\beta^*α∗,β∗是对偶问题的解,且 p∗=d∗=L(x∗,α∗,β∗)p^*=d^* = L(x^*,\alpha^*,\beta^*)p∗=d∗=L(x∗,α∗,β∗)

KKT

如上给出的是求解的充分条件,通常情况下,我们求解问题时,只需要满足假设,即可通过该方法将原始问题转化为对偶问题求解.

对于给定假设,x∗,α∗、β∗x^*,\alpha^*、\beta^*x∗,α∗、β∗分别是原始问题和对偶问题的解的必要条件是,x∗,α∗,β∗x^*,\alpha^*,\beta^*x∗,α∗,β∗满足 Karush-Kuhn-Tucker(KKT) 条件: ΔxL(x∗,α∗,β∗)=0ΔαL(x∗,α∗,β∗)=0ΔβL(x∗,α∗,β∗)=0αi∗ci(x∗)=0,i=1,2,…,kci(x∗)≤0,i=1,2,…,kαi≥0,i=1,2,…,khj(x∗)=0,i=1,2,…,l \Delta_xL(x^*,\alpha^*,\beta^*) = 0\\ \Delta_{\alpha}L(x^*,\alpha^*,\beta^*) = 0\\ \Delta_{\beta}L(x^*,\alpha^*,\beta^*) = 0\\ \alpha_i^*c_i(x^*) = 0, i=1,2,\dots,k\\ c_i(x^*) \leq 0, i=1,2,\dots,k\\ \alpha_i \geq 0, i=1,2,\dots,k\\ h_j(x^*) = 0, i=1,2,\dots,l\\ Δx​L(x∗,α∗,β∗)=0Δα​L(x∗,α∗,β∗)=0Δβ​L(x∗,α∗,β∗)=0αi∗​ci​(x∗)=0,i=1,2,…,kci​(x∗)≤0,i=1,2,…,kαi​≥0,i=1,2,…,khj​(x∗)=0,i=1,2,…,l 其中αi∗ci(x∗)=0\alpha_i^*c_i(x^*) = 0αi∗​ci​(x∗)=0称为KKt的对偶互补体哦阿健,由此条件可知:若α∗&gt;0\alpha^* &gt; 0α∗>0,则ci(x∗)=0c_i(x^*) = 0ci​(x∗)=0.

参考资料

李航《统计学习方法》

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

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • 远程办公经验为0,如何将日常工作平滑过度到线上?

    我是一名创业者,我的公司(深圳市友浩达科技有限公司)在2018年8月8日开始运营,现在还属于微型公司。这个春节假期,我一直十分关注疫情动向,也非常关心其对公司带来的影响。

    TVP官方团队
    TAPD 敏捷项目管理腾讯乐享企业邮箱企业编程算法
  • 数据中台,概念炒作还是另有奇效? | TVP思享

    作者简介:史凯,花名凯哥,腾讯云最具价值专家TVP,ThoughtWorks数据智能业务总经理。投身于企业数字化转型工作近20年。2000年初,在IBM 研发企业级中间件,接着加入埃森哲,为大型企业提供信息化架构规划,设计,ERP,云平台,数据仓库构建等技术咨询实施服务,随后在EMC负责企业应用转型业务,为企业提供云迁移,应用现代化服务。现在专注于企业智能化转型领域,是数据驱动的数字化转型的行业布道者,数据中台的推广者,精益数据创新体系的创始人,2019年荣获全球Data IQ 100人的数据赋能者称号,创业邦卓越生态聚合赋能官TOP 5。2019年度数字化转型专家奖。打造了行业第一个数据创新的数字化转型卡牌和工作坊。创建了精益数据创新方法论体系构建数据驱动的智能企业,并在多个企业验证成功,正在向国内外推广。

    TVP官方团队
    大数据数据分析企业
  • 扩展 Kubernetes 之 CRI

    使用 cri-containerd 的调用流程更为简洁, 省去了上面的调用流程的 1,2 两步

    王磊-AI基础
    Kubernetes
  • 扩展 Kubernetes 之 Kubectl Plugin

    kubectl 功能非常强大, 常见的命令使用方式可以参考 kubectl --help,或者这篇文章

    王磊-AI基础
    Kubernetes
  • 多种登录方式定量性能测试方案

    最近接到到一个测试任务,某服务提供了两种登录方式:1、账号密码登录;2、手机号+验证码登录。要对这两种登录按照一定的比例进行压测。

    八音弦
    测试服务 WeTest
  • 线程安全类在性能测试中应用

    首先验证接口参数签名是否正确,然后加锁去判断订单信息和状态,处理用户增添VIP时间事务,成功之后释放锁。锁是针对用户和订单的分布式锁,使用方案是用的redis。

    八音弦
    安全编程算法
  • 使用CDN(jsdelivr) 优化博客访问速度

    PS: 此篇文章适用于 使用 Github pages 或者 coding pages 的朋友,其他博客也类似.

    IFONLY@CUIT
    CDNGitGitHub开源
  • 扩展 Kubernetes 之 CNI

    Network Configuration 是 CNI 输入参数中最重要当部分, 可以存储在磁盘上

    王磊-AI基础
    Kubernetes
  • 聚焦【技术应变力】云加社区沙龙online重磅上线!

    云加社区结合特殊时期热点,挑选备受关注的音视频流量暴增、线下业务快速转线上、紧急上线防疫IoT应用等话题,邀请众多业界专家,为大家提供连续十一天的干货分享。从视野、预判、应对等多角度,帮助大家全面提升「技术应变力」!

    腾小云
  • 京东购物小程序购物车性能优化实践

    它是小程序开发工具内置的一个可视化监控工具,能够在 OS 级别上实时记录系统资源的使用情况。

    WecTeam
    渲染JavaScripthttps网络安全缓存

扫码关注云+社区

领取腾讯云代金券