Lagrangian Duality

拉格朗日函数

考虑如下带约束的优化问题： 我们可以将其等价转换为无约束优化问题： 其中， 与 定义为：

直观上，如果 ，那么 ，因此为了最小化目标函数，必须有 ；同理，如果 ，那么 ，因此为了最小化目标函数，必须有 . 故二者等价。

然而， 和 都有不可导点，这让我们难以求解问题。为此，一个常见的技巧就是用方便优化的函数代替它们。

例如，我们可以用如下的 logarithm barrier function 代替 ： 也可以用如下的 penalty function 代替 ​： 还可以用 ReLU 代替 ： 甚至可以用线性函数代替 ： 上面四种函数都是 的下界，如下靠左四图所示：

这里我们特别考虑线性函数情形。对 也用线性函数做类似的代替，如上最右图所示： 那么，用 和 代替 和 ，则优化目标变成： 这就是拉格朗日函数，其中 和 称作拉格朗日乘子。

从推导过程可以看出，对于任意合法的解 ，拉格朗日函数都是原优化目标 的下界：

拉格朗日对偶函数

拉格朗日对偶函数定义为拉格朗日函数的下确界： 于是对于合法的解 ，拉格朗日对偶函数 、拉格朗日函数 和原优化目标 有关系： 注意对偶函数 是 的函数，原函数 是 的函数，二者通过拉格朗日函数 作为桥梁相连接。

由于对偶函数是原函数的下界，所以对偶函数的最大值小于等于原函数的最小值。如果二者正好相等（即具有强对偶性，见下一节），那么原问题就可以转化为如下的对偶问题： $$ 转化成对偶问题的好处在于——对偶函数一定是凹函数（即使原函数不是凸的或凹的），这是因为： $$ 括号内是关于 $$ 的仿射函数，而 $$ 是该仿射函数的逐点下确界，因而一定是凹函数。证明如下：为书写简便起见，记 $$，设 $$，则： $$ 因此 $$ 是凹函数。于是，对偶问题一定是一个凸优化问题，有时会比原问题更容易求解。

弱/强对偶性

尽管对偶问题有着非常好的性质（一定是凸优化问题），但是一般情况下我们只能保证其最优解小于等于原问题最优解，这就是弱对偶性。如果对偶问题最优解一定等于原问题最优解，那么称该问题具有强对偶性。

Slater 条件是强对偶性成立的充分非必要条件：设原问题是凸优化问题，即 $$ 均为凸函数且 $$ 为仿射函数，若存在 $$ 使得 $$ 成立，则强对偶性成立。其中 $$ 表示定义域的相对内部 (relative interior)，即定义域去除边界的所有点构成的集合。

注意 Slater 条件是充分非必要条件，因此满足 Slater 条件一定具有强对偶性，但不满足 Slater 条件也可能具有强对偶性。

几何视角与 KKT 条件

等式约束

考虑如下只有一个等式约束的优化问题： $$ 为方便可视化，假设 $$，作出 $$ 的等值面以及 $$ 代表的约束曲面，如下图所示：

首先注意到约束曲面上任一点 $$ 关于 $$ 的梯度 $$ 与约束曲面是正交的。为了说明这一点，考虑约束曲面上的一点 $$ 和也在约束曲面上的邻近的一点 $$. 在 $$ 处做泰勒展开： $$ 由于 $$ 都在约束曲面上，所以 $$，于是 $$. 当 $$ 时，有 $$. 由于 $$ 是平行于约束曲面的，所以 $$ 就是约束曲面的法向量方向，即与之正交。

现在我们想找到一个 $$ 使得 $$ 达到最小。这样的点一定满足 $$ 也与约束曲面正交，否则我们可以将其继续在约束曲面上沿梯度反方向移动，使得 $$ 更小。综上，$$ 与 $$ 平行，即存在一个 $$，使得： $$ 如果我们聪明地构造函数： $$ 那么 $$ 就是 $$ 的解。进一步地，令 $$ 就恰好得到了约束条件 $$. 因此，求解原问题就相当于在求解拉格朗日函数 $$ 的驻点。换句话说，$$ 为最优解的必要条件为： $$

不等约束

接下来考虑具有不等约束的优化问题： $$ 此时可行域不再是一个约束曲面，而是曲面所包围的一个区域。仍然构造拉格朗日函数： $$ 分两种情形讨论：

1. 最优解落在约束区域内，即 $$，如下右图所示。此时约束条件并没有发挥作用，问题退化为无约束情形。因此若 $$ 是最优解，则满足 $$，对应拉格朗日乘子 $$；
2. 最优解落在约束区域边界上，即 $$，如下左图所示。此时回到了等式约束下的优化问题，可以通过解拉格朗日函数的驻点求解。但是为了让 $$ 最小，$$ 必须朝向区域 $$ 的内部，否则沿着梯度反方向移动就可以在 $$ 区域内找到更小的 $$. 由于 $$，所以此时 $$.

上述两种情形可以通过 $$ 统一起来。所以综上所述，$$ 是最优解的必要条件为： $$

KKT 条件

将上述结果推广到多个等式和不等式约束的情况下，考虑一般性的优化问题及其对偶问题： $$ 构造拉格朗日函数： $$ 假设强对偶性成立，则 $$ 是原问题和对偶问题的最优解的必要条件为： $$ 上述条件统称作 KKT (Karush-Kuhn-Tucker) 条件。

上文从几何视角直观地展现了 KKT 条件的意义，但不是严谨证明。下面给出互补松弛性条件的证明： $$ 注意第一个等号需要强对偶性的支持。上式中的小于等于都只能取等，易知： $$ 又由于 $$，所以只能是 $$，即互补松弛性条件成立。

例子：线性规划

本节中，两个向量比大小指各分量同时比大小。例如，设 $$，则 $$ 指的是 $$ 对 $$ 均成立。

Case 1

考虑如下线性规划问题（松弛型）： $$ 引入拉格朗日乘子 $$，构造拉格朗日函数： $$ 则拉格朗日对偶函数为： $$ 因此对偶问题为： $$ 注意到，由于 $$，所以如果存在某个 $$ 使得 $$ 成立，那么上述优化问题一定不会走 $$ 那个分支，此时问题等价于： $$ 由于优化目标并不包含 $$，因此可以去掉。另外为了对称起见，用 $$ 代替 $$，则得到原问题与对偶问题： $$

Case 2

考虑如下线性规划问题（标准型）： $$

与 Case 1 相比改动了一个符号，对应新增条件 $$，其余不变，因此略过中间步骤，直接写出对偶问题： $$ 仍然暂不考虑 $$ 情形，那么问题等价于： $$ 去掉 $$ 并用 $$ 代替 $$，得到： $$

Case 3

考虑如下线性规划问题（标准型）： $$ 符号的改变对应对偶变量（拉格朗日乘子）符号的改变，其余部分完全相同，因此直接写出结论： $$

线性规划对偶的性质

1. 对偶的对偶就是原问题：根据上述三种 cases 容易验证。
2. 弱对偶性成立：对偶问题的可行解是原问题的可行解的下界。
3. 强对偶性成立：对偶问题的最优解等于原问题的最优解。
4. 互补松弛性成为充要条件：设 $$ 分别是原问题和对偶问题的可行解，则 $$ 是最优解当且仅当 $$.

参考资料

1. Dongbo Bu. CS711008Z Algorithm Design and Analysis. Lecture 9. Algorithm design technique: Linear programming and duality. https://deltadbu.github.io/UCAS_algorithm_course/Lectures/Lec9.pdf ↩︎
2. Bishop, Christopher. Pattern recognition and machine learning. Springer google schola 2 (2006): 5-43. ↩︎