拉格朗日乘子法与对偶性

Reference

• 拉格朗日乘数
• 拉格朗日乘数法 —— 通俗理解
• 真正理解拉格朗日乘子法和 KKT 条件
• 支持向量机原理详解(二): 拉格朗日对偶函数，SVM的对偶问题
• 拉格朗日乘子法与对偶问题
• 拉格朗日乘子法与拉格朗日对偶性
• 约束优化&拉格朗日乘子法&拉格朗日对偶解法的关系
• 机器学习算法系列（二）：拉格朗日对偶性
• 对偶和KKT条件
• 凸优化（slater条件探讨）
• Slater与KKT条件
• Slater条件理解和证明

【概述】

拉格朗日乘子法（Lagrange Multipliers）是一种寻找多元函数在一组约束下的极值的方法，将含有 $d$ 个变量与 $k$ 个约束条件的最优化问题，转换为具有 $d+k$ 个变量的无约束最优化问题来求解

从数学意义上来讲，是通过引入拉格朗日乘子来建立极值条件，对 $d$ 个变量分别求偏导对应 $d$ 个方程，然后再加上 $k$ 个约束条件对应 $k$ 个拉格朗日乘子，从而构成了包含 $d+k$ 个变量的 $d+k$ 个方程的方程组问题，进一步就能根据求解方程组的方法来对最优化问题进行求解

【约束条件下的最优化问题】

等式约束

假设 $\mathbf{x}$ 为 $d$ 维向量，要寻找 $\mathbf{x}$ 的某个取值，使得目标函数 $f(\mathbf{x})$ 最小，且满足 $g(\mathbf{x})=0$ 的约束，即：

$$\begin{gather*} \mathbf{x^{*}} = &\arg \min_{\mathbf{x}} f(\mathbf{x}) \\ s.t. & g(\mathbf{x}^{*})=0 \end{gather*}$$

从几何的角度来看，该问题的目标，是在由方程 $g(\mathbf{x})=0$ 确定的 $d-1$ 维曲面上，寻找使目标函数 $f(\mathbf{x})$ 最小化的点，此时，可得到以下两条结论：

1. 对于约束曲面上的任意点 $\mathbf{x}$，该点的梯度 $\triangledown g(\mathbf{x})$ 与约束曲面正交
2. 在最优点 $\mathbf{x}^{*}$，目标函数在该点的梯度 $\triangledown f(\mathbf{x}^{*})$ 与约束曲面正交

如下图，图中用蓝线画出了目标函数 $f(x,y)$ 的一系列的等值面，用绿线画出了表示约束条件 $g(x,y)$ 的约束曲面

直观上来看，最优解 $\mathbf{x}^*$ 一定位于约束曲面上某处与等值面相切的位置，否则，一定会沿着约束曲面移动到目标函数更小的等值面上，即 $\triangledown f(\mathbf{x})$ 和 $\triangledown g(\mathbf{x})$ 的方向必定相同或相反，故有：

$$\triangledown f(\mathbf{x}^*)+\lambda\triangledown g(\mathbf{x}^*)=0$$

其中，$\lambda$ 被称为拉格朗日乘子

接着，定义拉格朗日函数：

$$L(\mathbf{x},\lambda)=f(\mathbf{x})+\lambda g(\mathbf{x})$$

不难发现，$L(\mathbf{x},\lambda)$ 的极值条件刚好就是最优解 $\mathbf{x}^*$ 满足以下两个条件：

$$\left\{\begin{array}{rl} \frac{\partial L}{\partial \mathbf{x}} &=& \triangledown f+\lambda\triangledown g=0\\ \frac{\partial L}{\partial \lambda} &=& g(x)=0 \end{array}\right.$$

此时，原等式的约束最优化问题，就转化为对拉格朗日函数 $L(\mathbf{x},\lambda)$ 的无约束优化问题

不等式约束

进一步，考虑不等式约束 $h(\mathbf{x})\leq 0$，有：

$$\begin{gather*} \mathbf{x}^{*}=& \arg \min_{\mathbf{x}} f(\mathbf{x}) \\ s.t. & h(\mathbf{x}^{*})\leq 0 \end{gather*}$$

如下图，图中的阴影部分代表不等式约束 $h(\mathbf{x})$ 的可行域

可根据目标函数 $f(\mathbf{x})$ 的最优解 $\mathbf{x}^{*}$ 是否在可行域内将这类不等式约束优化问题分为两类：

• $h(\mathbf{x})<0$：最优解 $\mathbf{x}^{*}$ 在可行域内，此时不等式约束不起作用，只需求解 $f(\mathbf{x})$ 的极值即可
• $h(\mathbf{x})=0$：最优解 $\mathbf{x}^{*}$ 在可行域边界上，此时不等式约束退化为等式约束

构造不等式约束下的拉格朗日函数：

$$L(\mathbf{x},\mu)=f(\mathbf{x})+\mu h(\mathbf{x})$$

对于 $h(\mathbf{x})<0$ 的情况，等价于令 $\mu=0$ 然后求 $L(\mathbf{x},\mu)$ 的极值，即：

$$\left\{\begin{align*} \frac{\partial L}{\partial \mathbf{x}} &= \triangledown f=0 \\ u &= 0 \\ h(\mathbf{x}) &< 0 \end{align*}\right.$$

对于 $h(\mathbf{x})=0$ 的情况，若要在边界上取极小值，等值面 $f(\mathbf{x})$ 的梯度必定是指向 $h(\mathbf{x})<0$ 的区域内，而 $h(\mathbf{x})$ 的梯度 $\triangledown h$ 显然向外，故 $\triangledown{f}$ 与 $\triangledown{h}$ 的方向相反，且有 $\mu>0$，则：

$$\left\{\begin{align*} \frac{\partial L}{\partial \mathbf{x}} &= \triangledown f+\mu \triangledown h =0 \\ \mu &> 0\\ h(\mathbf{x}) &=0 \end{align*}\right.$$

联立上述两种情况，可得到不等式约束的一般形式，称为 KKT（Karush-Kuhn-Tucker）条件

$$\left\{\begin{align*} \frac{\partial L}{\partial \mathbf{x}} &= \triangledown f+\mu \triangledown h =0 \\ \mu &\geq 0\\ h(\mathbf{x}) &\leq 0 \\ \mu h(\mathbf{x}) &=0 \end{align*}\right.$$

【拉格朗日对偶性】

主问题

将上述的等式约束与不等式约束进行推广，考虑具有 $n$ 个等式约束和 $m$ 个不等式约束，且可行域 $\mathbb{D}\subset \mathbb{R}^{d}$ 非空的优化问题：

$$\begin{gather*} \mathbf{x}^{*} = & \arg \min_{\mathbf{x}} f(\mathbf{x}) &\\ s.t. & g_i(\mathbf{x}^{*})=0,& i=1,2,...,n\\ & h_j(\mathbf{x}^{*})\leq0,& j=1,2,...,m \end{gather*}$$

原始问题

在主问题的基础上，引入拉格朗日乘子：

$$\begin{matrix} \boldsymbol{\lambda}=(\lambda_1,\lambda_2,...,\lambda_n)^T\\ \boldsymbol{\mu}=(\mu_1,\mu_2,...,\mu_m)^T \end{matrix}$$

此时，即可构造出广义拉格朗日函数（Generalized Lagrange Function）：

$$L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})=f(\mathbf{x})+\sum_{i=1}^n\lambda_ig_i(\mathbf{x})+\sum_{j=1}^m\mu_jh_j(\mathbf{x})$$

则其 KKT 条件为：

$$\left\{\begin{align*} \frac{\partial L}{\partial \mathbf{x}} &= \triangledown f+\sum\limits_{i=1}^n \lambda_i\triangledown g_i+ \sum\limits_{j=1}^m \mu_j \triangledown h_j =0 \\ \frac{\partial L}{\partial \lambda_i} &=g_i(\mathbf{x})=0 \\ \lambda_i &\neq 0\\ \mu_j &\geq 0\\ h_j(\mathbf{x}) &\leq 0 \\ \mu_j h_j(\mathbf{x}) &=0 \end{align*}\right.$$

这就是 KKT 条件下求极值的必要条件，即最优化问题的原始问题（Primal Problem）

其中，第一个条件是取极值的必要条件，第二个条件是原等式约束条件，第三个条件是等式约束的系数约束，第四个条件是不等式约束的系数约束，第五个条件是原不等式约束条件，第六个条件是互补松弛条件

对于互补松弛条件来说，其直观解释如下：要求 $L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})$ 的最小值，那么一定是三个项同时取最小值的情况，而第三项取最小值时，就是其等于 $0$ 的情况

但由于该原始问题不一定是凸优化问题，为此，引入了其对偶问题（Dual Problem）来辅助求解

对偶问题

设拉格朗日函数的对偶函数 $\Gamma:\mathbb{R}^{m}\times \mathbb{R}^{n}\mapsto \mathbb{R}$ 定义为：

$$\begin{align*} \Gamma(\boldsymbol{\lambda},\boldsymbol{\mu}) &= \inf_{\mathbf{x} \in \mathbb{D}} L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}) \\ &= \inf_{\mathbf{x} \in \mathbb{D}} \Big( f(\mathbf{x}) + \sum_{i=1}^n \lambda_i g_i (\mathbf{x}) + \sum_{j=1}^m \mu_j h_j(\mathbf{x}) \Big) \end{align*}$$

其具体含义是：对于给定的 $\boldsymbol{\lambda}$ 和 $\boldsymbol{\mu}$，在可行域 $\mathbb{D}$ 内变动 $\mathbf{x}$，函数 $L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})$ 取值的下界即为 $\Gamma$ 的值

可以发现，如果将 $\boldsymbol{\lambda}$、$\boldsymbol{\mu}$ 当做变量，即 $\boldsymbol{\lambda}$、$\boldsymbol{\mu}$ 不受 KKT 条件的约束，并将 $\mathbf{x}$ 当做参数，那么，无论在可行域 $\mathbb{D}$ 内如何变动 $\mathbf{x}$，$\Gamma(\boldsymbol{\lambda},\boldsymbol{\mu})$ 都是一个仿射函数（最高次数为 $1$ 的多项式函数）

此时，对偶函数是一族关于 $(\boldsymbol{\lambda},\boldsymbol{\mu})$ 的仿射函数的逐点下确界，即使原始问题不是凸的，对偶函数也是凹函数，这样一来，对偶问题就都是凸优化问题

如下图，右侧的红线为逐点取最小值得到的函数图形

下面证明在什么新的约束条件下，对偶函数能够给出主问题最优值的下确界

对于原始问题可行域 $\mathbb{D}$ ，若 $\tilde{\mathbf{x}}\in \mathbb{D}$，则对任意 $\boldsymbol{\mu}\succeq 0$ 和 $\boldsymbol{\lambda}$，结合原始问题的约束条件 $g_i(\tilde{\mathbf{x}})=0$ 和 $h_j(\tilde{\mathbf{x}})\leq 0$，有：

$$\sum_{i=1}^n\lambda_ig_i(\mathbf{x})+\sum_{j=1}^m\mu_jh_j(\mathbf{x})\leq 0$$

进而对拉格朗日对偶函数 $\Gamma(\boldsymbol{\lambda},\boldsymbol{\mu})$ 有：

$$\begin{align*} \Gamma(\boldsymbol{\lambda},\boldsymbol{\mu}) &= \inf_{\mathbf{x}\in \mathbb{D}} L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}) \\ &\leq L(\tilde{\mathbf{x}},\boldsymbol{\lambda},\boldsymbol{\mu}) \\ &\leq f(\tilde{\mathbf{x}}) \end{align*}$$

也就是说，原始问题的最小值大于等于对偶问题的最大值

若主问题的最优解为 $\mathbf{x}^{*}=\mathbf{p}^{*}$，则对任意的 $\boldsymbol{\mu}\succeq 0$ 和 $\boldsymbol{\lambda}$ 都有：

$$\Gamma(\boldsymbol{\lambda},\boldsymbol{\mu})\leq \mathbf{p}^*$$

也就是说，当满足 $\boldsymbol{\mu}\succeq 0$ 时，对偶函数给出了主问题最优值的下界，于是，可以利用这个对偶函数 $\Gamma$ 的最大值去逼近主问题中的最优解 $\mathbf{p}^{*}$

显然，对偶函数 $\Gamma$ 的最大值是趋近于 $\mathbf{p}^{*}$ 的值，由此引出了一个最优化问题：

$$\begin{gather*} (\boldsymbol{\lambda}^{*},\boldsymbol{\mu}^{*}) = & \arg \max_{\boldsymbol{\lambda},\boldsymbol{\mu}} \Gamma(\boldsymbol{\lambda},\boldsymbol{\mu}) \\ s.t. & \boldsymbol{\mu}\succeq 0 \end{gather*}$$

这就是原始问题的对偶问题，其中 $\boldsymbol{\lambda}$ 和 $\boldsymbol{\mu}$ 被称为对偶变量（Dual Variable）

将原始问题转换为对偶问题后，可以发现，约束条件变少了，只剩下 $m$ 个不等式约束，这无疑极大的简化了计算，且对偶问题一定是凸优化问题

---

关于如何获得对偶函数表达式：

1. 令 $\frac{\partial L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})}{\partial \mathbf{x}}=0$，以得到 $\mathbf{x}$ 关于 $\boldsymbol{\lambda}$、$\boldsymbol{\mu}$ 的表达式
2. 将 $\mathbf{x}$ 关于 $\boldsymbol{\lambda}$、$\boldsymbol{\mu}$ 的表达式带回 $L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})$，即可得到对偶函数的表达式

弱对偶性与最优对偶间隙

设拉格朗日对偶问题的最优解为 $d^{*}$，则有：

$$d^*\leq p^*$$

即使原始问题不是凸优化问题，这个不等式仍然成立，该性质即被称为弱对偶性（Weak Duality）

可以发现，有：

• 若 $p^{*}=-\infty$，则：$d^{*}=-\infty$
• 若 $d^{*}=+\infty$，则：$p^{*}=+\infty$

同时，对于主问题的最优解 $p^{*}$ 与获得了凸优化属性的对偶问题的最优解 $d^{*}$ 的非负差值 $p^{*}-d^{*}$，被称为最优对偶间隙（Duality Gap），其说明了原始解和对偶解对应的目标函数值的差距，差距越小说明最优解的上界和下界越小，也就是说越来越靠近最优解

强对偶性与 Slater 条件

设拉格朗日对偶问题的最优解为 $d^{*}$，若有：

$$d^*= p^*$$

则称强对偶性（Strong Duality）成立

在强对偶性成立的情况下，将拉格朗日函数分别对原变量和对偶变量求导，再令导数为 $0$，即可得到原变量和对偶变量的数值关系

对于一般的优化问题来说，强对偶性一般不成立，但若原始问题是凸优化问题，且 Slater 条件成立，即：存在一点 $\mathbf{x} \in \mathbb{D}$ 使得不等式约束 $h(\mathbf{x})\leq0$ 严格成立，那么强对偶性成立

简单来说，如果原始问题是凸优化问题，且至少存在绝对一个绝对可行点（一个可以让所有不等式约束都不取等号的可行点），那么就具有强对偶性

需要补充的是，Slater 条件是强对偶性成立的充分条件，KKT 条件是强对偶性成立的必要条件