对偶及其原理

对偶性（Duality）

这个词我想大家都不陌生。如果我没记错的话，第一次遇见这个词是在小学语文课本中学的：天对地，雨对风，大陆对长空。这也被叫做对仗。但是今天要讲的对偶，不仅是一个数学概念，更可谓是哲学概念。之前的一篇文章：时域和频域就是它一个方面的反映。时域和频域更像是对对偶性的具体化，而对偶性只是一种思想。与对偶同时存在的一种思想叫做对称。之前写过的一篇文章镜像及其本质详细的解释了如何理解现实世界的不对称性以及不对称性的根源。对偶与对称在不同领域有不同的理解，在我看来，对偶是指在一个逻辑上的对称，而对称却是更加现实的。这种文字游戏我也得不到什么结论，我希望可以通过以下一些例子帮助大家得到结论。但是我需要说一句，这些例子都比较数学，只在最后上升到逻辑层面。

顺便提一句，duality这个词我是在金融数学的risk theory里面第一次见到，当时被我翻译为二元性，导致我一直没理解这个词。但是这个词本身被译作二元性确实是很合适的：比如一个函数$f(x,y)$可以看做$f_y(x)$, 也可以看做$f_x(y)$就是二元性的表现，它和对偶在本意上是相通的，但是我私以为对偶这个词更能体现这种关系。

对偶空间

在一个$n$维的线性空间$S$中，我们可以找一个线性映射$f: S_\to \mathbb R$. 由于是线性映射，我们由Riesz表示定理可以得到
$f(x) = \left< y_f, x\right>.$
其中$y_f\in S$是依赖$f$ 的一个点。这里的内积定义是自然的，来自欧式空间。Riesz表示定理将线性空间$S$以及定义在其上的线性函数联系了起来，这个关联是一一的！因此我们能做如下操作：对于$S$中的一个基$e_1, e_2,\dots, e_n$, 我们可以找到$f_i \in L(S)$, 其中$L(S)$即为定义在$S$上的线性函数的collection, 使得$f_i(x) = \left< e_i, x\right>$ for all $i = 1,2,\dots, n$. 现在，这个空间$L(S)$上任何的映射$f$都可以被表示为$f_i$的线性组合。这一个点同样来自Riesz representation theorem, 应该是不言自明的。

现在我们发现，哦，原来$L(S)$也是一个线性空间，而且是n维的，它和$S$是同构的呀。现在我们称$L(S)$为$S$的对偶空间，称呼$f_1,f_2,\dots,f_n$为$L(S)$的基，$e_1, e_2,\dots, e_n$为$L(S)$的对偶基。

作为对偶的记号，我们记$L(S) = S^*$. 其实很多时候，我们需要提高自己的认识视角，因此我们也常用$\left< f, x\right>$表示$f(x)$，因为函数作用本身就是一个内积的结构，只不过这个内积现在看来并不是对称。现在我们尝试理解$x$对$f$的作用，也就是说$x: L(S) \to \mathbb R$ such that $x(f) = f(x)$ for any $f\in L(S)$. 然后我们发现，哦，原来$L(S)^* = S$，也就是说我们的原空间$S$本就是$L(S)$的对偶空间呀。

这告诉我们$S^{**} = S$. 概括来说就是空间$S$是自反的（对偶两次得到自身）。这种自反性和对称的自反性类似：对称两次可以得到自己。注意，并不是所有空间都是自反的，但足够好的空间都具有自反性。

注意到，我们中间提到$S \simeq L(S)$: 两者是同构的。这其实是不常见的，比如$(l_p)^* = l_q$, where $1/p +1/q = 1$, 中$l_p$和$l_q$就不是同构的. 但是$(l_p)^{**} = l_p$仍然是成立的（p不能是1或$\infty$）.

优化问题的对偶性

对优化问题不太熟悉的小伙伴可以参考我之前写过一篇LP的文章，这一节就建立在线性优化问题的基础之上。

对于LP:
$\max c_1x_1+\dots+c_nx_n = c^Tx$
subject to $Ax\leq b$.

我们可以构造如下对偶问题：先在我们把原问题的限制变为优化的目标函数，原先的目标函数变为限制，我们得到
$\min b_1y_1 + \dots + b_ny_n = b^Ty$
subject to $A^Ty \geq c$
仔细看，这两个优化问题除了符号相反，结构几乎一样。我们称其互为对偶优化问题，简称对偶问题。如果其中一个问题足够好（有可行解，也就是可行集非空；且有最优解，最优解不在无穷远处），那么通过强对偶定理我们可以得到：另一个问题自动也有最优解，且两个最优解重合。这其实是相当有趣的。

这背后的原理其实并不复杂，一言以蔽之，就是拉格朗日乘数法。有些人可能忘得差不多了，如果你不记得，可以回溯一下它的定义，我在这里简单回顾一下：

我们想优化目标函数$f(x)$ over $x\in \mathcal X$, under constraint $g(x) = 0$. One may optimize $f(x) + \lambda g(x)$ over $x\in \mathcal X$. 然后我们得到的优化问题的解总会包含原问题的解。本质上，我们想在$g(x) = 0$这个可行集上找最优解，实际上在找$f(x) = d$这簇等高线的最高的点，但是仅仅在可行集上，我们是看不到等高线的；整体地想，$f(x) = d$ 的等高线在最优解处（如果有）应该会平行（这个需要一点思考），所以，他们的梯度是平行的！唯一的差异在于模长不同，这里的$\lambda$就是处理这个模长不同的问题。既然梯度平行（平行是相互的），我们完全可以换过来思考，毕竟我们要找的是在可行集$g(x) = 0$上两个等高线（$g(x) =c$与$f(x) = d$）平行的地方，如果我们知道这个点$x^*$处$f(x^*) = d^*$, 那么，我们完全可以这样做：optimize $g(x)$ subject to $f(x) = d^*$. 如此我们仍然会达到同一个点$x^*$。

拉格朗日乘数法的思想还是很有价值的，这里“乘的数”其实就是两个gradients的倍数关系。它也告诉我们，优化的目标函数和限制其实没有本质区别，是可以相互替换的。

也许你了解，lasso就有很多等价形式，such as constrained version and unconstrained version. 但是这里的等价，其实挺vague的，我想三两句话说不清楚，感兴趣的话可以私聊我。之前写过的一篇Basis Pursuit就介绍过其中的思想，但不深刻，感兴趣也可以再浏览一遍。

回到线性优化问题，其实这一对对偶问题就完全可以通过拉格朗日乘数法联系起来，具体过程我就不详细写了，感兴趣的可以参看这篇文章详细了解。

此外，自反性在这里也是有的（如果问题有最优解的话）。一个LP的对偶的对偶还是它本身。（实际上这个说法不严谨，这就像空间的自反性一样，结构太差的空间就回不到自己了）

除此之外，minimax问题也由冯 诺依曼的minimax定理表明，极大化极小值和极小化极大值在一定条件下是等价的，这算是strongly duality的推广。我们得到结论：极小化极大值与极大化极小值两个问题是对偶的！如果你去了解这背后的博弈故事背景，你应该会觉得很有趣（你甚至会惊奇，为什么会有这样的结果）。我自己总结的一句话：完全信息博弈的最高境界就是minimax。

傅里叶变换的对偶性

针对傅里叶变化，我就不说太多了，毕竟在时域和频域聊了很多了。这个对偶性，有一点这样的味道：你中有我，我中有你。时域和频域不仅是两个观点，两个视角，更是一个事物的两个方面。如果你了解一些阴阳五行的理论（这里我要说一下，我是纯属学术好奇，我不懂国学、道学，但我感兴趣哲学，因此我了解了一些），阴阳两极就是事物对立统一的两个方面，他们相生相合（阴中有阳，阳中有阴，阴阳转化，物极必反），没有边界。我觉得傅里叶变换就好比阴和阳相生的渠道，这和粒子的波粒二象性也有很好的对应。（有机会我会写一篇相关的介绍，取其精华）

总结

对于对偶，我们还是体会到了一些味道。它有时可以是理解上的转化（空间的对偶、LP的对偶），可以是观点的彻底转化（傅里叶变换），或者是互补共生的两方面的同时存在带给我们的感受（波粒二象性、时域和频域）。这确实是难以言表的，但是我们还是总结出了它与对称的不同：对称的事物往往是相克的，它们更加偏向于其中一个的繁荣，另一个的衰败；而对偶则更包容，由于其中的任何一方都可以若隐若现，两者必须被加起来才能组成一个事物，任何一方的完全消失会导致另一方的彻底消失。

当然，这些理解也不够全面，不一定能应用到各个地方。如果你也有自己的看法，我非常期待能与你交流相关观点。今天本来还想聊共轭和对偶的关系，但现在看来我的理解还不够深刻，以后有了认识我会继续写下去。

Ref:

https://www.zhihu.com/question/38464481
https://zhuanlan.zhihu.com/p/36621652
https://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0
https://en.wikipedia.org/wiki/Duality_(optimization)