喵喵爱编程

这个屌丝很懒，什么也没留下！

热门标签

对偶理论：基本概念札记_为什么要用对偶理论

作者：喵喵爱编程 | 2024-07-08 14:39:47

踩

为什么要用对偶理论

本文首次发表于知乎，欢迎关注作者。

1. 前言

在读论文或者学习机器学习理论时，常常看到对偶的身影。但因为对对偶问题的理解不够透彻，在看机器学习理论相关理论时也是懵懵懂懂。所以本文整理了对偶理论的基本概念，帮助理解记忆。本文主要描述：

优化问题的标准形式，即原问题的基本定义；
介绍 Lagragian 函数，Lagrage 对偶函数/对偶函数，Lagrage 对偶问题/对偶问题等基本概念；
介绍将原问题转化为对偶问题的方法。

优化问题的标准形式（原问题）

优化问题的形式有很多，如最大化一个目标函数，或者最小化一个目标函数，约束的不等号方向不同等。每一个形式的优化问题，都可以求出相应的对偶问题，但因为优化问题形式的不同，求解细节上，会有相应的不同，很难掌握。为了方便记忆，先定义标准优化问题（原问题），然后再介绍标准优化问题转化为对偶问题的过程。

理论上所有的优化问题，都可以转化为标准形式。优化问题的标准形式如式 2-1 所示：

由优化目标，不等式约束和等式约束三部分组成。式 2-1 有三个需要额外注意的地方：

$f_0(x)$ 是优化目标，期望可以最小化的量。它的形式无约束，可以是凸函数，也可以是非凸函数；
$f_i(x)$ 是优化问题的不等式约束，注意符号是 “≤” 且不等式右端为 0，共 m 个不等式约束，可以是线性不等式，也可以是非线性不等式；
$h_j$ 是优化问题的等式约束， 且“=”右端为 0，共有 p 个等式约束，可以是线性等式，也可以是非线性等式；

其中 $x \in R^n$ ，问题的定义域是优化目标与所有约束的交集 $D=\cap ^m_{i=1}dom f_i \cap f_0 \cap ^p_{j=1}h_j(x)$

求解优化问题是在定义域 D 中寻找到 $x^*$ 优化目标 $f_0(x)$ 达到最小值 $p^*$ 。

理论上我们遇到的所有的优化问题都可以化为式 2-1 这种标准形式。比如我们的优化目标要极大化 $max f_0(x)$ ，可以等效为极小化 $min -f_0(x)$ 。同理所有的不等式约束和等式约束经过化简变换后也可以转化为式 2-1 中形式。若某些优化问题，没有不等式约束，则标准形式中 $f_i(x)$ 的数量为 0；同理若优化问题中没有等式约束，则对应的标准形式中 $h_j(x)$ 的数量为 0；若优化问题中，既没有不等式约束也没有等式约束，则对应的标准形式是一个无约束的优化问题。另外根据 $f_0(x)$ ， $f_i(x)$ ， $h_j(x)$ 的形式不同，优化问题可以分为不同的种类，难易程度也会有很大的区别。本文我们主要讨论对偶理论，对优化问题的种类和难易不做过多的描述，只要知道任何形式的优化问题均可以转化为这种标准形式即可。我们通过一个简单案例看看如何将一般优化问题转化为标准形式：

例 1。将式 2-2 转为优化问题的标准形式：

转化为标准形式为：

2. Lagragian 函数

根据原问题（优化问题的标准形式），我们定义 Lagrangian 函数：

从下面 4 点理解 Lagrangian 函数：

3. Lagrage 对偶函数/对偶函数

有了 Lagrangian 函数，我们再引入 Lagrange 对偶函数如式 3-6：

Lagrange 对偶函数是 Lagrangian 函数关于 x 取最小值时的函数。Lagrange 对偶函数有以下 2 点性质：

针对性质 2，我们尝试简单证明：

证明。设原问题的最优解 $x^*$ ，最优解对应的最优值为 $p^*$ ，则有：

根据 Lagrange 对偶函数的定义，有：

又根据上文中，我们对 Lagrangian 函数讨论的第 4 点，有：

联立式 3-7，式 3-8，式 3-9 可推出：

即 $g(\lambda,\mu )$ 是原问题最优值的一个下界。

4. Lagrage 对偶问题/对偶问题

现在我们知道 Lagrange 对偶函数是原问题最优值 $p^*$ 的一个下界，一个自然的想法是希望这个下界越紧越好，理想情况是式 3-10 中取得等号的时候，所以我们需要不断的调节 λ，µ 来最大化 $g(\lambda,\mu )$ ，于是便得到 Lagrange 对偶问题（也叫对偶问题）：

设对偶问题的最优解为 $d^*$ ，根据对偶函数定义可知：

又因为 $g(\lambda,\mu ) \leqslant p^*$ ，即 $g(\lambda,\mu )$ 可取到的所有值，包括 $g(\lambda,\mu )$ 的最大值 $d^*$ ，均小于 $p^*$ ，所以：

这时，我们将原问题和对偶问题最优值的差定义为对偶间隙（duality gap），如下：

当 $d^*\leqslant p^*$ 时，称原问题和对偶问题是弱对偶（weak duality）关系，当 $d^* = p^*$ 则称原问题和对偶问题是强对偶（strong duality）关系。概念上强对偶是弱对偶的一个特例。

因为对偶函数 $g(\lambda,\mu )$ 是凹函数，且对偶问题的可行域是一个凸集，易知对偶问题是凸问题。凸问题是比较容易求解的一类问题。

5. 总结

本文主要介绍了对偶理论的基本概念和由原问题求对偶问题的方法，如下图。

首先将一般优化问题化简为标准优化问题；
引入拉格朗日乘子 (λ,µ) 求解出 Lagrangian 函数；
对 Lagrangian 函数关于 x 求最小，得到 Lagrange 对偶函数，也叫对偶函数；
对 Lagrange 对偶函数关于 λ，µ 求最大，得到 Lagrange 对偶问题，也称作对偶问题；

总结下对偶理论的理解：

为什么要将原问题化简为对偶问题？答：通过章节 5 末尾的讨论，我们知道：无论原问题难度如何，对偶问题都是凸问题，凸问题是一类比较容易求解问题，当原问题是一个特别难的问题时，化简为对偶问题，相对容易求解；
任何一个原问题，转化为对偶问题后，都会变得容易求解么？答：不是的。由章节 3 中性质 2，我们知道：转化为对偶问题后，引入的拉格朗日乘子 (λ,µ) 数量是所有约束个数的总和，当原问题中变量个数，远小于约束个数时，就不要转化为对偶问题求解了。比如原问题中只有 5 个变量，但有 100 万个约束，这时候，原问题对应的对偶问题会有 100 万个对偶变量，相对比，还是优化只有 5 个变量的原问题更容易；
当原问题中变量的数量和约束个数在同一量级时，既然任何原问题转化为对偶问题后，都会变为凸问题，且容易求解，是不是意味着原问题容易求解？答：不完全是。我们只能说对偶问题是凸问题，对偶问题相对容易求解。我们要知道对偶问题的解只是原问题的一个下界。只有当对偶间隙为 0（强对偶）时，对偶问题的最优值才和原问题的最优值相等，即 $d^* = p^*$ 。对偶间隙不为 0 时，求得对偶问题的最优值是原问题最优值的一个下界。当证明不了强对偶存在时，往往用这种方法求原问题的一个下界，用于理论分析；
如何判断对偶间隙是否为 0（即强对偶），以及如何求解原问题和对偶问题？答：对于原问题是凸问题，slater 条件可以判断什么情况下存在强对偶；当原问题非凸时，需要单独分析。当已知强对偶（ $d^* = p^*$ ）存在的情况下，KKT 条件成立，可以借助 KKT 条件求解。以后会单独介绍 slater 条件和 KKT 相关内容。这里只为加深原问题和对偶问题之间关系的理解。

6. 参考资料

[1]. 中科大-凸优化-凌青

https://www.bilibili.com/video/av40

7. 团队介绍

「三翼鸟数字化技术平台-场景设计交互平台」主要负责设计工具的研发，包括营销设计工具、家电VR设计和展示、水电暖通前置设计能力，研发并沉淀素材库，构建家居家装素材库，集成户型库、全品类产品库、设计方案库、生产工艺模型，打造基于户型和风格的AI设计能力，快速生成算量和报价；同时研发了门店设计师中心和项目中心，包括设计师管理能力和项目经理管理能力。实现了场景全生命周期管理，同时为水，空气，厨房等产业提供商机管理工具，从而实现了以场景贯穿的B端C端全流程系统。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/799048

对偶理论：基本概念札记_为什么 要用 对偶理论