|
在教本科生优化课的时候，对偶理论是最不好讲的。形式上能推导，但为什么要这样做，有点讲不清道不明，属于典型的 “知其然而不知其所以然”，到最后就是记住了些定义、公式和定理。 翻了好些书，知乎、Quora、 math stack exchange 也查了，没见到哪讨论 “其所以然”。现在我就来讲讲自己对“其所以然”的思考，给中文知识库增加一些实质性的东西。囿于自身水平，行文不求深刻，但求易懂。 知其然什么是对偶 (duality) ？从数学上来讲，这不是个良定的问题，因为对偶有很多种。线性拓扑空间 有它的对偶空间 , 凸集有对偶表示，拓扑上有Poincare对偶，代数里有Koszul 对偶，函数有对偶，优化问题有对偶问题。 我们限制在优化问题的对偶这个范围内来回答这个问题。 从形式上来讲，对偶问题就是变量替换，把原始问题用新的变量表示成另外一种形式。在对偶形式下，原问题能够得到更好的解决。 通俗地讲，就是换个角度看问题，然后就豁然开朗。 天底下没有免费的午餐。问题本质性的困难还是在，只是换了个角度，能看到原来看不到的一些结构，也能用上更多的工具。 拉格朗日力学和哈密顿力学举个非常经典的例子（经典是可以也必须背下来的）。大家都知道牛顿第二定律 ，包罗万象，上知天文下知地理，刚出道就一统力学江湖。但为什么有这个定律呢？能否从更根本的原理 (first principle) 出发推导出来呢? 知其然更要知其所以然。接着就有了费马的 least action principle (最小作用原理)，拉格朗日把它写成一个优化问题。 引入 Lagrangian，最简单的例子是动能和势能之差，最小化 Lagrangian 得到的方程就是牛顿第二定律。这种推导力学方程的方式称之为拉格朗日力学。其中关键是写出 Lagrangian，主要工具是变分。 物体的运动轨迹是空间的一条曲线 . 时间 时的位置是 , 那么速度就是 , 加速度是二阶导数 . 记物体的质量为 . 那么动能是 , 势能是 的函数 . 简单的势能例子是 . Lagrangian . Least action principle 是说物体的轨迹是下面最小化问题的解 这里 是所有满足边界条件的曲线 组成的集合。边界条件可以是起始的位置 and , 也可以是初始位置和初始速度。对此优化问题求变分，就得到了牛顿第二定律 . 这个优化问题的对偶问题是什么呢？ 用一个变量替换，称之为 Lagendre （勒让德）变换。Lagrangian 变成了 Hamiltonian。原来的变量是（位置，速度），变换之后的变量是 （位置，动量）。当质量是常数的时候，速度和动量就差一个常数，但两者是完全不同的变量，是互为对偶的变量。 原来的 Euler-Lagrange 方程变成了 Hamilton system. 原来的 least action，变成了 preserving Hamiltonian。拉格朗日力学经过勒让德变换就变成了哈密尔顿力学。 把Lagrangian看做是速度 的函数（暂时忽略其他变量）. 对应的勒让德变化是 我们来求解上面的最大化问题。通过求解一阶方程 得到 , 物理意义就是动量。因为 对 是凸的二次函数，这个 就是上面这个最大化化问题的解. 代入就得到了 这里还做了一个平凡的变量替换 . 得到的新的函数 称为 Hamiltonian. 如果Lagrangian 是动能和势能的差，对应的 Hamiltonian 就是总能量: 动能和势能的和。Least action principle 就变成了 conservation of total energy. 然后考虑另外一个泛函 最小化问题变成了鞍点问题 对其求变分，对应的 first order system 称之为 Hamilton system 很强大，也很神秘。 勒让德变换为什么要做勒让德变换呢？是怎么发现这个变换的呢？在这个变换中还牵涉到一个最大化问题，这使得勒让德变换不是线性的。重复一遍：勒让德变换是非线性的。 在以先贤命名的变换里，还有一个变换比勒让德变换更厉害，更强大，更普适，那就是傅里叶变换。 傅里叶变换最开始的物理意义是把信号用各种频率的正弦余弦 (sin, cos) 波来表示。数学上，傅里叶变换就是函数在另外一组正交基下的展开。函数还是同一个函数，只是换了一组基来表示，所以函数的 Frouier transform （如果能做傅里叶变换的话） 能够忠实地刻画原函数。有些性质，傅里叶变换之后，在频率空间下看得更清楚。比如函数光滑性，就可以用傅里叶系数幂次的求和性来刻画。 更为方便的是：傅里叶变换是线性的。 而勒让德变换不是线性的，这不光增加了理解的难度也增加了使用的难度。 但和傅里叶变换一样强大的是：勒让德变换也能刻画原函数，但是，得加上一个限制条件：限制在凸函数的集合。 勒让德变换也称为Legendre-Fenchel 变换，又叫 conjugate 或者 dual，就是凸函数的对偶函数。给定一个凸函数 , 定义其对偶 这一节使用勒让德变换，是为了和傅里叶变换在修辞上对偶。 简言之：可以把凸函数的勒让德变换类比于 Schwartz 函数的傅里叶变换。 勒让德变换不是线性的原因是使用的代数系统不一样。傅里叶变换使用的我们通常的 (+，x) 代数，勒让德变换使用的是 (max, +) 代数。在这个代数里，加法定义为 max，乘法定义为 +。 凸函数在 (max, +) 代数结构下是封闭的。 拿两个凸函数 , 很容易找到例子 不是凸的，而 是凸的。对一个实数 , 不一定还是凸的，但 总是凸的。这样对更一般的线性组合 也是凸的。 问题 勒让德变换是否在 (max, +) 代数下是线性的？即是否有 ，更熟悉的写法：是否 ? 讲了半天，还是书上都讲了的东西。不着急，我们先 “知其然”。接下来从方法论上来探讨对偶的 “其所以然”。 |
|
|
