拉格朗日对偶性

在约束最优化问题中，常常利用拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。

该方法应用在许多统计学习方法中，例如，最大熵模型与支持向量机。

9.1 原始问题

假设$f(x)$，$c_i(x)$，$h_j(x)$是定义在$R^n$上的连续可微函数。考虑约束最优化问题：

$$\min_{x \in R^n} f(x) \tag{9.1}$$ $$\mathrm{s.t.} c_i(x)\le 0，i=1,2,…,k \tag{9.2}$$ $$h_j(x)=0，j=1,2,…,l \tag{9.3}$$

称此约束最优化问题为原始最优化问题或原始问题。

首先，引进广义拉格朗日函数：

$$L(x,\alpha,\beta) = f(x)+\sum_{i=1}^k \alpha_i c_i(x)+\sum_{j=1}^l \beta_j h_j(x) \tag{9.4}$$

这里，$x=(x^{(1)},x^{(2)},...,x^{(n)})^\top \in R^n,\alpha_i,\beta_i$是拉格朗日乘子，$\alpha_i \ge 0$。考虑x的函数:

$$\theta_p(x) = \max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta) \tag{9.5}$$

这里，下标P表示原始问题。

假设给定某个x。如果x违反原始问题的约束条件，即存在某个i使得$c_i(x)>0$或者存在某个j使得$h_j(x)\ne0$，那么就有：

$$\theta_p(x) = \max_{\alpha,\beta:\alpha_i\ge0} \left[f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\right] = +\infty \tag{9.6}$$

由于某个i使得$c_i(x)>0$，它会使得$\alpha_i \rightarrow +\infty$，同样的若存在某个j使得$h_j(x)\ne0$，它会使得$\beta_j \rightarrow +\infty$，而将其他的$\alpha_i$，$\beta_j$均取为0。

相反地，如果x满足约束条件式(9.2)和式(9.3)，则由式(9.5)和式(9.4)可知，$\theta_p(x)=f(x)$。因此，

$$\theta_p(x) = \left\{\begin{aligned} f(x) , \ & x satisfy the constraints \\ +\infty, \ & others \end{aligned}\right. \tag{9.7}$$

所有如果考虑极小化问题:

$$\min_x \theta_p(x) = \min_x \max_{\alpha,\beta:\alpha_i\ge0} L(x,\alpha,\beta) \tag{9.8}$$

它是与原始最优化问题(9.1)~(9.3)等价的。

问题$\min_x \max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)$称为广义拉格朗日函数的极大极小问题。

定义原始问题的最优解:

$$p^* = \min_x \theta_p(x) \tag{9.9}$$

9.2 对偶问题

定义

$$\theta_D(\alpha,\beta) = \min_x L(x, \alpha, \beta) \tag{9.10}$$

再考虑极大化$\theta_D(\alpha, \beta)=\min_x L(x, \alpha, \beta)$，即

$$\max_{\alpha,\beta:\alpha_i\ge0} \theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i\ge0} \min_x L(x,\alpha,\beta) \tag{9.11}$$

将广义拉格朗日函数的极大极小问题表示为约束最优化问题：

$$\max_{\alpha,\beta}\theta_D(\alpha,\beta) = \max_{\alpha,\beta}\min_x L(x, \alpha, \beta) \tag{9.12}$$ $$\mathrm{s.t.} \alpha_i \ge 0，i=1,2,…,k \tag{9.13}$$

称为原始问题的对偶问题。

定义对偶问题的最优解:

$$d^* = \max_{\alpha,\beta:\alpha_i \ge0} \theta_D(\alpha, \beta) \ (9.14)$$

9.3 原始问题和对偶问题的关系

下面讨论原始问题和对偶问题的关系。

定理9.1 若原始问题和对偶问题都有最优值，则

$$d^* = \max_{\alpha,\beta:\alpha_i\ge0} \min_x L(x,\alpha,\beta) \le \min_x \max_{\alpha,\beta:\alpha_i\ge0} L(x,\alpha,\beta) = p^* \tag{9.15}$$

证明 由式(9.12)和式(9.5)，对任意的$\alpha$，$\beta$和x，有

$$\theta_D(\alpha,\beta) = \min_x L(x,\alpha,\beta) \le L(x,\alpha,\beta) \le \max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta) = \theta_p(x) \tag{9.16}$$

即

$$\theta_D(\alpha,\beta) \le \theta_p(x) \tag{9.17}$$

由于原始问题和对偶问题均有最优值，所以，

$$\max_{\alpha,\beta:\alpha_i\ge0}\theta_D(\alpha,\beta) \le \min_x \theta_p(x) \tag{9.18}$$

即

$$d^* = \max_{\alpha,\beta:\alpha_i \ge 0} \min_x L(x,\alpha,\beta) \le \min_x \max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) = p^* \tag{9.19}$$

推论9.1 设$x^*$和$\alpha^*$，$\beta^*$分别是原始问题(9.1)~(9.3)和对偶问题(9.12)~(9.13)的可行解，并且$d^*=p^*$，则$x^*$和$\alpha^*$，$\beta^*$分别是原始问题和对偶问题的最优解。

在某些条件下，原始问题和对偶问题的最优解相等，$d^*=p^*$，这时对偶问题和原始问题等效。

定理9.2 考虑原始问题(9.1)~(9.3)和对偶问题(9.12)~(9.13)，假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的(即存在x，对所有i有$c_i(x)<0$，则存在$x^*$，$\alpha^*$,$\beta^*$，使$x^*$是原始问题的解，$\alpha^*$，$\beta^*$是对偶问题的解，并且

$$p^* = d^* = L(x^*,\alpha^*,\beta^*) \tag{9.20}$$

定理9.3 对原始问题(9.1)~(9.3)和对偶问题(9.12)~(9.13)，假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的，则$x^*$和$\alpha^*$，$\beta^*$分别是原始问题和对偶问题的解的充分必要条件是$x^*$，$\alpha^*$，$\beta^*$满足下面的KKT条件：

$$\nabla_x L(x^*,\alpha^*,\beta^*) = 0 \ (9.21)$$ $$\alpha_i^*c_i(x^*) = 0 , i=1,2,...,k \ (9.22)$$ $$c_i(x^*) \le 0 , i=1,2,...,k \ (9.23)$$ $$\alpha_i^* \ge 0 , i=1,2,...,k \ (9.24)$$ $$h_j(x^*) = 0 , j=1,2,...,l \ (9.25)$$

特别指出，式(9.24)称为KKT的对偶互补条件。由此条件可知：若$\alpha_i^* > 0$，则$c_i(x^*)=0$。