拉格朗日对偶性

在约束最优化问题中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解。该方法应用在许多统计学习方法中,例如,最大熵模型与支持向量机。这里简要叙述拉格朗日对偶性的主要概念和结果。

1. 原始问题

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

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

首先,引进广义拉格朗日函数(generalized Lagrange function)

这里,$x=(x^(1),x^(2),…x^(n))^T \in R^n$,$\alpha_i, \beta_j$ 是拉格朗日乘子, $\alpha_i \ge 0$,考虑 $x$ 的函数:

这里,下标 $P$ 表示原始问题

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

因为若某个 $i$ 使约束 $c(w) \gt 0$,则可令 $\alpha_i \to + \infty$,若某个 $j$ 使 $h_j(w) \neq 0$,则可令 $\beta$ 使 $\beta_j h_j(x) \to \infty$,而将其余各 $\alpha_i, \beta_j$ 均取为 $0$ 。

相反的,如果 $x$ 满足约束条件式 $c_i(x) \le 0$ 和式 $h_j(x) = 0$ ,则可知 $\theta_P(x) = f(x)$(少的两项一个是非正的,一个是0,要取最大值的话当然得令两者都为0)。因此,

所以如果考虑极小化问题



它($\min _ {x}\theta_P$) 是与原始最优化问题($\min f(x)$)是等价的,即它们有相同的解。问题 $\min _ { x } \max _ { \alpha , \beta : x _ { i } \geq 0 } L ( x , \alpha , \beta )$ 称为广义拉格朗日函数的极小极大问题。为了方便,定义原始问题的最优值

称为原始问题$\min f(x)$的值在约束下的最小值。

2. 对偶问题

定义

再考虑极大化 $\theta _ { D } ( \alpha , \beta ) = \min _ { x } L ( x , \alpha , \beta )$,即

问题 $\max _ { \alpha , \beta \cdot x _ { i } \geq 0 } \min _ { x } L ( x , \alpha , \beta )$ 称为广义拉格朗日函数的极大极小问题

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

称为原始问题的对偶问题。定义对偶问题的最优值

称为对偶问题的值。

3. 原始问题和对偶问题的关系

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

定理 C.1

若原始问题和对偶问题都有最优值,则

(通俗讲就是最小化后最大化,小于等于最大化后最小化)

证明

若原始问题和对偶问题都有最优值,则

推论 C.2

设 $x^\ast,\alpha^\ast,\beta^\ast$ 分别是原始问题、对偶问题的可行解,并且$d ^ { \ast } = p ^ { \ast }$,则 $x^\ast,\alpha^\ast,\beta^\ast$分别是原始问题和对偶问题的最优解。

在某些条件下,原始问题和对偶问题的最优值相等,$d ^ { } = p ^ { }$。这时可以用解对偶问题替代解原始问题。下面以定理的形式叙述有关的重要结论而不予证明。

定理 C.2

考虑原始问题

(等价于)

和对偶问题

假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数,$h_j(x)$ 是仿射函数,并且假设不等式约束 $c_i(x)$ 是严格可行的,即存在 $x$,对所有 $c_i(x) < 0$

存在 $x^\ast,\alpha^\ast,\beta^\ast$ 是原始问题解,并且

仿射函数是特殊的凸函数。既是凸函数,又是凹函数的函数称为仿射函数。它必定是线性函数与常数之和在有限维空间上,仿射函数就是一次函数。 仿射函数的重要性在于局部凸空间(包括赋范线性空间、有限维空间)上的下半连续凸函数一定是连续仿射函数族的上包络.

仿射函数就是一个线性函数,其输入是 n 维向量,参数 A 可以是常数,也可以是 mn 的矩阵,b 可以是常数,也可以是 m 维的列向量,输出是一个 m 维的列向量。*在几何上,仿射函数是一个线性空间到另一个线性空间的变换。

定理 C.3(KTT 条件)

对原始问题

(等价于)

和对偶问题

假设函数 $f(x)$ 和 $c_i(x)$ 是凸函数,$h_j(x)$ 是仿射函数,并且假设不等式约束 $c_i(x)$ 是严格可行的,则 $x^\ast,\alpha^\ast,\beta^\ast$ 分别是原始问题和对偶问题的解的充分必要条件是 $x^\ast,\alpha^\ast,\beta^\ast$ 满足下面的 Karush-Kuhn-Tucker (KKT)条件:

特别之处,式 $\alpha _ { i } ^ { } c _ { i } \left( x ^ { } \right) = 0$ 称为 KKT 的对偶互补条件。由此条件可知:若 $\alpha_i^ > 0$,则 $c_i(x^) = 0$。