【机器学习】拉格朗日对偶性

拉格朗日对偶性

在求解最优化问题中，拉格朗日乘数法（Lagrange Multiplier）和 KKT（Karush Kuhn Tucker，三个人名）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘数法，在有不等约束时使用 KKT 条件。

1. 无约束的优化问题

假设目标函数为 f ( x ) f(x) f(x) 。形如

min ⁡ f ( x ) \min f(x) minf(x)

的优化问题称为无约束的优化问题，无约束条件是最简单的优化问题。解决方法通常为，令函数 f ( x ) f(x) f(x) 对变量 x x x 的偏导等于零获得计算极值点，将极值点代回函数验证极值点是否为最小值点。若无解析解，可采用梯度下降法或牛顿迭代方法逼近极小值点。

2. 等式约束的优化问题

假设等式约束条件（函数集合）为 h ( x ) h(x) h(x) 。形如

min ⁡ f ( x ) s . t . h i ( x ) = 0 i = 1 , 2 , … , l \begin{matrix} &\min f(x)\\ s.t.& h_i(x)=0 & i=1,2,\dots,l \\ \end{matrix} s.t.minf(x)hi(x)=0i=1,2,…,l

的优化问题称为等式约束的优化问题。可以采用的解决方法为消元法和拉格朗日乘数法。消元法是通过将等式条件转换为多变量表示单变量的形式后代入目标函数 f ( x ) f(x) f(x) 中，将等式约束优化问题转化为无约束优化问题。

拉格朗日乘数法更具有普适性，泛化性。定义拉格朗日函数 L ( x , λ ) L(x, \lambda) L(x,λ)
L ( x , λ ) = f ( x ) + ∑ i = 1 l λ i h i ( x ) L(x, \lambda) = f(x)+\sum_{i=1}^l\lambda_ih_i(x) L(x,λ)=f(x)+i=1∑lλihi(x)
其中， λ = { λ 1 , λ 2 , … , λ l } \lambda=\{\lambda_1,\lambda_2,\dots,\lambda_l\} λ={λ1,λ2,…,λl} 为拉格朗日乘子。分别令函数 L L L 对 x x x 和 λ \lambda λ 的偏导等于零，联立求解获得极值点
{ ∇ x L = 0 ∇ λ 1 L = 0 ∇ λ 2 L = 0 ⋮ ∇ λ l L = 0 \left\{ \begin{array}{ll} \nabla _xL = 0\\ \nabla _{\lambda_1} L=0 \\ \nabla _{\lambda_2} L=0 \\ \space\space\space\space\space\space\space\space\space\vdots\\ \nabla _{\lambda_l} L=0 \\ \end{array} \right. ⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧∇xL=0∇λ1L=0∇λ2L=0 ⋮∇λlL=0
简记为
{ ∇ x L = 0 ∇ λ L = 0 \left\{ \begin{array}{ll} \nabla _xL = 0\\ \nabla _{\lambda} L=0 \end{array} \right. {∇xL=0∇λL=0
将方程组的解代回拉格朗日函数检验。

3. 不等式约束的优化问题

假设不等式约束条件（函数集合）为 g ( x ) g(x) g(x) 。形如
min ⁡ f ( x ) s . t . g i ( x ) ≤ 0 i = 1 , 2 , … , k h j ( x ) = 0 j = 1 , 2 , … , l (1) \begin{matrix} &\min f(x)\\ s.t.& g_i(x)\le 0 &i=1,2,\dots,k \\ &h_j(x)=0 & j=1,2,\dots,l \\ \end{matrix} \tag{1} s.t.minf(x)gi(x)≤0hj(x)=0i=1,2,…,kj=1,2,…,l(1)
的优化问题称为不等式约束的优化问题，我们认为式 ( 1 ) (1) (1) 为约束最优化问题的一般形式。

定义广义拉格朗日函数（generalized Lagrange function）
L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i g i ( x ) + ∑ j = 1 l β j h j ( x ) (2) L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k\alpha_i g_i(x) + \sum_{j=1}^l\beta_jh_j(x)\tag{2} L(x,α,β)=f(x)+i=1∑kαigi(x)+j=1∑lβjhj(x)(2)
其中，不等式约束系数 α = { α 1 , α 2 , … , α k } \alpha=\{\alpha_1,\alpha_2,\dots,\alpha_k\} α={α1,α2,…,αk} 和等式约束系数 β = { β 1 , β 2 , … , β l } \beta = \{\beta_1,\beta_2,\dots,\beta_l\} β={β1,β2,…,βl} 为拉格朗日乘子，且 α i ≥ 0 \alpha_i\ge 0 αi≥0 。

4. 凸优化问题

4.1. 凸集

对于集合 D D D，若对于 D D D 中任意两点 x 1 x_1 x1 和 x 2 x_2 x2 满足：
λ x 1 + ( 1 − λ ) x 2 ∈ D \lambda x_1+(1-\lambda)x_2\in D λx1+(1−λ)x2∈D
其中， λ ∈ ( 0 , 1 ) \lambda \in (0,1) λ∈(0,1) 。直观理解如图 1 1 1 所示。

【机器学习】拉格朗日对偶性-LMLPHP

图 1 凸集与非凸集

4.2. 凸函数

对于凸集 D D D 中的任意两点 x 1 x_1 x1 和 x 2 x_2 x2 满足：
f ( λ x 1 + ( 1 − λ ) x 2 ) ≤ λ f ( x 1 ) + ( 1 − λ ) f ( x 2 ) f\big(\lambda x_1 + (1-\lambda)x_2\big)\le \lambda f(x_1) + (1-\lambda)f(x_2) f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)
则函数 f ( x ) f(x) f(x) 为凸集 D D D 上的凸函数（convex function）。如果满足：
f ( λ x 1 + ( 1 − λ ) x 2 ) < λ f ( x 1 ) + ( 1 − λ ) f ( x 2 ) f\big(\lambda x_1 + (1-\lambda)x_2\big)\lt \lambda f(x_1) + (1-\lambda)f(x_2) f(λx1+(1−λ)x2)<λf(x1)+(1−λ)f(x2)
则函数 f ( x ) f(x) f(x) 为凸集 D D D 上的严格凸函数。

4.3. 凸优化

如果约束最优化问题的目标函数 f ( x ) f(x) f(x) 和不等式约束函数 g i ( x ) g_i(x) gi(x) 都是 R p \mathbb R^p Rp 上的连续可微的凸函数，约束函数 h j ( x ) h_j(x) hj(x) 是 R p \mathbb R^p Rp 上的仿射函数，那么该约束最优化问题为凸优化问题（convex optimization problem）。

尽管凸优化的条件比较苛刻，但仍然在机器学习领域有十分广泛的应用。这主要得益于凸优化的优良性质：

凸优化问题的局部最优解就是全局最优解，但是可能存在多个最优解；
很多非凸问题可以等价或近似转化为凸优化问题（比如拉格朗日对偶）；
凸优化问题的研究较为成熟，求解方法也较为成熟。

4.4. 凸二次规划

特别地，当凸优化问题的目标函数 f ( x ) f(x) f(x) 是二次函数且不等式约束函数 g i ( x ) g_i(x) gi(x) 是仿射函数时，该凸最优化问题为凸二次规划问题（convex quadratic programming）。

二次规划（Quadratic Programming，QP）是一类典型的优化问题，包括凸二次优化和非凸二次优化。在此类问题中，目标函数是变量的二次函数，而约束条件是变量的线性不等式。

假定变量个数为 d d d，约束条件的个数为 m m m，则标准的二次规划问题形如
min ⁡ x 1 2 x T Q x + c T x s . t . A x ≤ b \min_x \frac{1}{2} x^TQx + c^Tx \\ s.t.\space\space\space\space Ax\le b xmin21xTQx+cTxs.t. Ax≤b
其中 x x x 为 d d d 维向量， Q ∈ R d × d Q∈ \mathbb R^{d\times d} Q∈Rd×d 为实对称矩阵， A ∈ R m × d A ∈ \mathbb R^{m\times d} A∈Rm×d 为实矩阵， b ∈ R m b ∈ \mathbb R^m b∈Rm 和 c ∈ R d c ∈\mathbb R^d c∈Rd 为实向量， A x ≤ b Ax≤b Ax≤b 的每一行对应一个约束。

若 Q Q Q 为半正定矩阵，则目标函数是凸函数，相应的二次规划是凸二次优化问题；此时若约束条件 A x ≤ b Ax≤b Ax≤b 定义的可行域不为空，且目标函数在此可行域有下界，则该问题将有全局最小值。若 Q Q Q 为正定矩阵，则该问题有唯一的全局最小值。若 Q Q Q 为非正定矩阵，则目标函数是有多个平稳点和局部极小点的 NP 难问题。

常用的二次规划解法有椭球法（elipsoid method）、内点法（interior point）、增广拉格朗日法（augmentcd Lagrangian）、梯度投影法（gradicnt projection）等。若 Q Q Q 为正定矩阵，则相应的二次规划问题可由椭球法在多项式时间内求解。

5. 几何意义

考虑到一般优化问题的几何意义包括非常多的情形，也就对应非常多的图像，不方便介绍且不便于理解，所以下面仅讨论三种约束情况下凸优化问题的几何意义。

5.1. 无约束优化

假设 x ∗ x^* x∗ 表示目标函数 f ( x ) f(x) f(x) 的最优解，我们通过等高线图表示一种最简单的目标函数，类似于 f ( x 1 , x 2 ) = ( x 1 − c ) 2 a 2 + ( x 2 − d ) 2 b 2 f(x_1,x_2)=\frac{(x_1-c)^2}{a^2}+\frac{(x_2-d)^2}{b^2} f(x1,x2)=a2(x1−c)2+b2(x2−d)2 的形式，其中 a a a， b b b，$c ，，，d$ 为常数。等高线图如图 2 2 2 所示。

【机器学习】拉格朗日对偶性-LMLPHP

图 2 无约束优化问题等高线图

其中， C 1 > C 2 > C 3 > C 4 C_1>C_2>C_3>C_4 C1>C2>C3>C4 且均为常数。可见，由于没有约束条件，目标函数的最值点为问题的最优解。

5.2. 等式约束优化

当只有一个等式约束条件 h 1 ( x ) = 0 h_1(x)=0 h1(x)=0 时，根据拉格朗日乘数法，对拉格朗日函数 L ( x , λ 1 ) = f ( x ) + λ 1 h 1 ( x ) L(x,\lambda_1)=f(x)+\lambda_1h_1(x) L(x,λ1)=f(x)+λ1h1(x) 的变量 x x x 计算偏导得
∇ x L = ∇ x f + λ 1 ∇ x h 1 \nabla_x L = \nabla_x f + \lambda_1 \nabla_x h_1 ∇xL=∇xf+λ1∇xh1
令偏导等于零，得
∇ x f = − λ 1 ∇ x h 1 \nabla_x f = - \lambda_1 \nabla_x h_1 ∇xf=−λ1∇xh1
我们知道，梯度是一个向量，在某一点的梯度方向，就是过该点的等高线切线的法线方向。观察上式，目标函数的梯度与约束条件的梯度共线，且大小成 λ 1 \lambda_1 λ1 倍。故，在单一等式约束下，拉格朗日乘子 λ \lambda λ 的几何意义为在最优解处两个函数的梯度大小成 λ \lambda λ 倍。因为并未要求等式约束的拉格朗日乘子必须大于 0 0 0，所以最优解处两个函数的梯度可能同向，也可能反向。如图 3 3 3 左子图所示。

当有两个约束条件时，计算拉格朗日函数的偏导，并令导数等于零得
∇ x f = − λ 1 ∇ x h 1 − λ 2 ∇ x h 2 \nabla_x f = - \lambda_1 \nabla_x h_1-\lambda_2\nabla_xh_2 ∇xf=−λ1∇xh1−λ2∇xh2
可见，在最优解处目标函数的梯度为两个约束条件梯度的线性组合，组合系数为拉格朗日乘子。如图 3 3 3 中间子图所示。另外注意，最优解位于满足线性组合处需要以该位置满足全部约束条件为前提。可以理解为，约束条件规定了目标函数的可行域，最优解只能在可行域中进行选取，这正是约束优化问题的几何意义，即在约束条件规定的可行域内确定最小化目标函数的解。

上面提到两个约束条件对应的几何意义为线性组合，那么三个及三个以上约束条件对应的几何意义也为线性组合。依然要保证最优解是在可行域内进行搜索，所以如果多个约束条件之间不存在交集，即可行域为空，显然对应无解，如图 3 3 3 右子图所示。当然，如果三个约束条件对应的直线存在交集，那么存在最优解。

【机器学习】拉格朗日对偶性-LMLPHP

图 3 单一等式约束(左)、两个等式约束(中)和三个等式约束(右，无解)

5.3. 不等式约束优化

相对于等式约束而言，不等式约束对应可行域从一条直线变为一个区域。

当只有一个不等式约束条件 g 1 ( x ) = 0 g_1(x)=0 g1(x)=0 时，能取到极值点的位置存在两种情形：

当可行域囊括目标函数的极小值点时，该约束不起作用，即优化问题的最优解为目标函数的极小值点；
当可行域未囊括目标函数的极小值点时，该约束的作用与等式约束条件一致，即优化问题的最优解一定位于可行域边界与目标函数等高线的切点处。

以上两种情形分别对应图 4 4 4 中的 a a a 和 b b b 子图。

观察广义拉格朗日函数 L ( x , α , β ) L(x,\alpha,\beta) L(x,α,β) 要求 g 1 ( x ) g_1(x) g1(x) 的拉格朗日乘子 α 1 ≥ 0 \alpha_1\ge 0 α1≥0。当 α 1 = 0 \alpha_1=0 α1=0 时表示不等式约束不起作用，与之相乘的不等式条件项为零；当 α 1 ≠ 0 \alpha_1\ne0 α1=0 时表示不等式约束起作用，作用与等式约束一致。另外，与等式优化不同的是，不等式优化不允许 α i < 0 \alpha_i<0 αi<0。在不等式约束的拉格朗日乘子 α ≠ 0 \alpha \ne 0 α=0 的前提下（对应 b b b 子图），可行域内部为 g 1 ( x ) ≤ 0 g_1(x)\le 0 g1(x)≤0，外部为 g 1 ( x ) > 0 g_1(x)>0 g1(x)>0，显然约束函数 g 1 ( x ) g_1(x) g1(x) 在可行域边界与目标函数等高线切点处的梯度由区域内指向区域外，目标函数在切点处的梯度由区域外指向区域内，两个梯度方向必然相反。对拉格朗日函数求导并零导数为零可知 ∇ x f = − α 1 ∇ x g 1 \nabla_xf = -\alpha_1\nabla_xg_1 ∇xf=−α1∇xg1，为保证确定的最优解处两个函数梯度相反，需要限制 α 1 > 0 \alpha_1>0 α1>0。

当有多个不等式约束条件时，无非就是在每个不等式约束条件的可行域交集中确定最优解，如图 4 4 4 中的 c c c 子图所示。如果某个约束的可行域囊括了目标函数的极小值点，那么该约束将不起作用，最优解依赖于其他约束。

当既有不等式约束，又有等式约束时，可行域仍然取全部约束的可行域交集，如图 4 4 4 中的 d d d 子图所示。

【机器学习】拉格朗日对偶性-LMLPHP

图 4 单一不等式约束覆盖目标函数极值点(a)、单一不等式约束未覆盖目标函数极值点(b)、两个不等式约束(c)和两个不等式约束与一个等式约束(d)

6. 原始问题

在得到对偶问题前，我们习惯上将带约束的原始问题式 ( 1 ) (1) (1) 转换为等价的无约束的原始问题式 ( 3 ) (3) (3)，二者都称为原始问题（primal problem）。
min ⁡ x max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) (3) \min_x \max_{\alpha,\beta;\alpha_i\ge 0}L(x, \alpha, \beta)\tag{3} xminα,β;αi≥0maxL(x,α,β)(3)
其中 L ( x , α , β ) L(x,\alpha, \beta) L(x,α,β) 为广义拉格朗日函数式 ( 2 ) (2) (2)。式 ( 3 ) (3) (3) 为无约束的原始问题，“无约束”是指相比于式 ( 1 ) (1) (1)，尽管式 ( 3 ) (3) (3) 对拉格朗日乘子 α \alpha α 进行限制，但不再对目标函数变量 x x x 进行约束，故称“无约束”。另外，由于式 ( 1 ) (1) (1) 与式 ( 3 ) (3) (3) 在结果上一致，只是对问题采用了不同的数学方式表达而已，所以认为二者是等价的。

下面来证明二者是等价的，即结果一致。令
θ P ( x ) = max ⁡ a , β ; α i ≥ 0 L ( x , α , β ) \theta_P(x) = \max_{a,\beta;\alpha_i\ge0}L(x, \alpha, \beta) θP(x)=a,β;αi≥0maxL(x,α,β)
对于满足全部约束条件 g i ( x ) ≤ 0 g_i(x)\le0 gi(x)≤0 和 h j ( x ) = 0 h_j(x)=0 hj(x)=0 的 x x x 而言，即 x x x 在可行域内，
θ P ( x ) = f ( x ) \theta_P(x)=f(x) θP(x)=f(x)
这个很容易验证，因为满足约束条件的 x x x 一定满足 h j ( x ) = 0 h_j(x)=0 hj(x)=0，广义拉格朗日函数式 ( 2 ) (2) (2) 中的等式约束项被消除； x x x 也一定满足 g i ( x ) ≤ 0 g_i(x)\le 0 gi(x)≤0，又因为拉格朗日乘子 α i ≥ 0 \alpha_i\ge 0 αi≥0，所以 α i g i ( x ) ≤ 0 \alpha_ig_i(x)\le 0 αigi(x)≤0，故 L ( x , α , β ) L(x,\alpha,\beta) L(x,α,β) 以 α \alpha α 和 β \beta β 为变量， x x x 为常数时的最大值只能在 α i g i ( x ) = 0 \alpha_ig_i(x)=0 αigi(x)=0 时取到，式 ( 2 ) (2) (2) 中的不等式约束项也被消除，只剩目标函数项，即 θ P ( x ) = f ( x ) \theta_P(x)=f(x) θP(x)=f(x)。

讨论当 x x x 不满足原始问题约束条件时的 θ P ( x ) \theta_P(x) θP(x)，即 x x x 不在可行域内。假设给定某个 x x x，如果 x x x 违反原始问题的约束条件，即存在某个 i i i 使得 g i ( x ) > 0 g_i(x) \gt 0 gi(x)>0 或者存在某个 j j j 使得 h j ( x ) ≠ 0 h_j(x)\ne 0 hj(x)=0，那么就有
θ P ( x ) = + ∞ \theta_P(x)=+∞ θP(x)=+∞
因为若某个 i i i 使约束 g i ( x ) > 0 g_i(x) > 0 gi(x)>0，则可令 α i → + ∞ \alpha_i →+∞ αi→+∞；若某个 j j j 使 h j ( x ) ≠ 0 h_j(x)\ne 0 hj(x)=0 ，则可令 β j \beta_j βj 使 β j h j ( x ) → + ∞ \beta_jh_j(x) →+∞ βjhj(x)→+∞，而将其余各 α i α_i αi 和 β j \beta_j βj 均取 0 0 0。

可以将两种情况整合，
θ P ( x ) = { f ( x ) x 满足约束条件 + ∞ 其他 \theta_P(x)=\left\{ \begin{matrix} f(x) & x满足约束条件\\ +∞ & 其他 \end{matrix} \right. θP(x)={f(x)+∞x满足约束条件其他
极小化 θ P ( x ) \theta_P(x) θP(x)
min ⁡ x θ P ( x ) = min ⁡ x max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) \min_x \theta_P(x) =\min_x \max_{\alpha,\beta;\alpha_i\ge 0}L(x, \alpha, \beta) xminθP(x)=xminα,β;αi≥0maxL(x,α,β)
可以理解为，当 x x x 不在可行域内时， θ P ( x ) \theta_P(x) θP(x) 取无穷大是没有意义的，对应无解；当 x x x 在可行域内时，最小化 θ P ( x ) \theta_P(x) θP(x) 就是最小化目标函数 f ( x ) f(x) f(x)，且此时 θ P ( x ) \theta_P(x) θP(x) 的最优解与 f ( x ) f(x) f(x) 的最优解相同。这样我们很自然地将式 ( 1 ) (1) (1) 转化为了式 ( 3 ) (3) (3) 。

7. 对偶问题

定义
θ D ( α , β ) = min ⁡ x L ( x , α , β ) \theta_D(\alpha,\beta) = \min_xL(x, \alpha,\beta) θD(α,β)=xminL(x,α,β)
极大化 θ D ( α , β ) \theta_D(\alpha, \beta) θD(α,β)
max ⁡ α , β ; α i ≥ 0 θ D ( α , β ) = max ⁡ α , β ; α i ≥ 0 min ⁡ x L ( x , α , β ) \max_{\alpha,\beta;\alpha_i\ge0}\theta_D(\alpha, \beta) = \max_{\alpha,\beta;\alpha_i\ge0}\min_xL(x, \alpha, \beta) α,β;αi≥0maxθD(α,β)=α,β;αi≥0maxxminL(x,α,β)
表示为约束最优化问题：
max ⁡ α , β θ D ( α , β ) = max ⁡ α , β min ⁡ x L ( x , α , β ) s . t . α i ≥ 0 , i = 1 , 2 , … , k (4) \max_{\alpha,\beta}\theta_D(\alpha, \beta) = \max_{\alpha,\beta}\min_xL(x, \alpha, \beta) \\ s.t. \space\space\space\space \alpha_i\ge 0,\space\space\space\space i=1,2,\dots,k\tag{4} α,βmaxθD(α,β)=α,βmaxxminL(x,α,β)s.t. αi≥0, i=1,2,…,k(4)
称为原始问题的对偶问题（dual problem）。与原始问题式 ( 3 ) (3) (3) 对比，二者仅交换了取最大值和取最小值符号的位置。

7.1. 弱对偶性

若原始问题和对偶问题均有可行解，那么原始问题对应的目标函数值恒不小于对偶问题对应的目标函数值，这就是弱对偶性（weak duality），即
θ D ( α , β ) ≤ θ P ( x ) \theta_D(\alpha,\beta)\le \theta_P(x) θD(α,β)≤θP(x)
假设原始问题和对偶问题的最优值分别为
p ∗ = min ⁡ x max ⁡ α , β ; α i ≥ 0 L ( x , α , β ) d ∗ = max ⁡ α , β ; α i ≥ 0 min ⁡ x L ( x , α , β ) p^*= \min_x \max_{\alpha,\beta;\alpha_i\ge 0}L(x, \alpha, \beta)\\ d^*=\max_{\alpha,\beta;\alpha_i\ge0}\min_xL(x, \alpha, \beta) p∗=xminα,β;αi≥0maxL(x,α,β)d∗=α,β;αi≥0maxxminL(x,α,β)
特别地，若原始问题和对偶问题均有一个确定的最优解，那么最优解对应的目标函数指恒满足原始问题最小值不小于对偶问题最大值，即
d ∗ ≤ p ∗ d^*\le p^* d∗≤p∗
证明如下。

易知
L ( x , α , β ) ≤ max ⁡ α , β L ( x , α , β ) min ⁡ x L ( x , α , β ) ≤ L ( x , α , β ) L(x, \alpha, \beta)\le \max_{\alpha, \beta}L(x,\alpha, \beta) \\ \min_x L(x,\alpha, \beta) \le L(x, \alpha, \beta) L(x,α,β)≤α,βmaxL(x,α,β)xminL(x,α,β)≤L(x,α,β)
所以
θ D ( α , β ) = min ⁡ x L ( x , α , β ) ≤ L ( x , α , β ) ≤ max ⁡ α , β L ( x , α , β ) = θ P ( x ) (5) \theta_D(\alpha, \beta) = \min_x L(x,\alpha, \beta) \le L(x, \alpha, \beta)\le \max_{\alpha, \beta}L(x,\alpha, \beta) = \theta_P(x)\tag{5} θD(α,β)=xminL(x,α,β)≤L(x,α,β)≤α,βmaxL(x,α,β)=θP(x)(5)
对于一般情形下的弱对偶性已经证明完毕了，但是直接理解式 ( 5 ) (5) (5) 还是比较困难的，在这里我们通过一个非常简单的例子来理解。不妨将式 ( 5 ) (5) (5) 重新写为更简洁、更本质的形式
G ( y ) = min ⁡ x L ( x , y ) ≤ L ( x , y ) ≤ max ⁡ y L ( x , y ) = H ( x ) G(y) = \min_x L(x, y) \le L(x, y)\le \max_y L(x,y) = H(x) G(y)=xminL(x,y)≤L(x,y)≤ymaxL(x,y)=H(x)
G ( y ) G(y) G(y) 的几何意义为 L ( x , y ) L(x,y) L(x,y) 在空间直角坐标系中沿 x x x 轴方向投影，以投影后区域的下边界为函数；类似地， H ( x ) H(x) H(x) 的几何意义为 L ( x , y ) L(x,y) L(x,y) 在空间直角坐标系中沿 y y y 轴方向投影，以投影后区域的下边界为函数。对于 x ∈ [ − 1 , 4 ] x\in[-1,4] x∈[−1,4]， y ∈ [ − 5 , 2 ] y\in [-5,2] y∈[−5,2] 的部分马鞍面 L ( x , y ) = x 2 − y 2 / 3 L(x,y)=x^2-y^2/3 L(x,y)=x2−y2/3 如图 5 5 5 所示，分别沿 x x x 轴和 y y y 轴投影得到的 G ( y ) G(y) G(y) 和 H ( x ) H(x) H(x) 如图 6 6 6 所示。

【机器学习】拉格朗日对偶性-LMLPHP

图 5 部分马鞍面

【机器学习】拉格朗日对偶性-LMLPHP

图 6 沿 x 轴投影(左)和沿 y 轴投影(右)

可见， G ( y ) G(y) G(y) 为 L ( x , y ) L(x,y) L(x,y) 的一个下界，而 H ( x ) H(x) H(x) 为 L ( x , y ) L(x,y) L(x,y) 的一个上界，所以必然存在 G ( y ) ≤ H ( x ) G(y)\le H(x) G(y)≤H(x)。对应到式 ( 5 ) (5) (5) 中， θ D ( α , β ) \theta_D(\alpha, \beta) θD(α,β) 为 L ( x , α , β ) L(x,\alpha, \beta) L(x,α,β) 的下界， θ P ( x ) \theta_P(x) θP(x) 为 L ( x , α , β ) L(x,\alpha,\beta) L(x,α,β) 的上界。

要想证明 d ∗ ≤ p ∗ d^*\le p^* d∗≤p∗，则需要基于式 ( 5 ) (5) (5) 继续推导。分别取最大下界和最小上界，二者依然满足不等关系
d ∗ = max ⁡ α , β θ D ( α , β ) ≤ min ⁡ x θ P ( x ) = p ∗ d^*=\max_{\alpha,\beta}\theta_D(\alpha, \beta)\le \min_x \theta_P(x)=p^* d∗=α,βmaxθD(α,β)≤xminθP(x)=p∗
这里依然可以通过图 6 6 6 来理解，观察图可知， G ( y ) G(y) G(y) 的最大值显然不大于 H ( x ) H(x) H(x) 的最小值，即下界最大值依然不大于上界最小值。

另外，可以通过“宁做鸡头不做凤尾”的俗语来记忆，“鸡”不如“凤”，分别对应下界和上界，亦取最小值和取最大值，可以理解为全部的鸡都是不如凤的，“头”和“尾”分别对应取最大值和取最小值，即在上、下界内选最小和最大，在鸡中无论怎么选都不可能比凤好，其语言表达就是“鸡头不如凤尾”。

7.2. 强对偶性

若原始问题（对偶问题）有一个确定的最优解，那么对偶问题（原始问题）也有一个确定的最优解，而且这两个最优解所对应的目标函数值相等，这就是强对偶性（strong duality），即
d ∗ = p ∗ d^*=p^* d∗=p∗
p ∗ − d ∗ p^*-d^* p∗−d∗ 称为对偶间隙（duality gap），当对偶间隙为 0 0 0 时，认为具有强对偶性。

任何优化问题都具有弱对偶性，但是不一定具有强对偶性。只有当某些规范性条件（constraint qualification）成立时，优化问题才具有强对偶性。

常见的规范性条件有：

Slater’s condition：对于一个凸优化问题，如果存在一个点满足全部约束，且对于不等式约束都严格成立，即不存在不等号取等的情况，那么问题具有强对偶性。
Linearity constraint qualification：简称 LCQ。对于一个优化问题，如果约束条件均为线性，那么问题具有强对偶性。

这里仅列举了常见的两个条件，所以满足一些其他条件也可能推出问题具有强对偶性。

7.3. KKT 条件

KKT 条件（Karush–Kuhn–Tucker condition）被定义为一个方程组

g i ( x ) ≤ 0 ( 6 ~ 1 ) h j ( x ) = 0 ( 6 ~ 2 ) ∇ x L ( x , α , β ) = 0 ( 6 ~ 3 ) α i ≥ 0 ( 6 ~ 4 ) α i g i ( x ) = 0 ( 6 ~ 5 ) \begin{aligned} g_i(x)&\le 0 &\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space&&&&{(6\text{\textasciitilde}1)} \\ h_j(x)&=0 &&&&& {(6\text{\textasciitilde}2)} \\\\ \nabla_x L(x,\alpha, \beta) &=0 &&&&&{(6\text{\textasciitilde}3)} \\ \alpha_i&\ge 0 &&&&&{(6\text{\textasciitilde}4)} \\ \\ \alpha_ig_i(x)&=0&&&&&{(6\text{\textasciitilde}5)} \end{aligned} gi(x)hj(x)∇xL(x,α,β)αiαigi(x)≤0=0=0≥0=0 (6~1)(6~2)(6~3)(6~4)(6~5)

其中， ( 6 ~ 1 ) ∼ ( 6 ~ 2 ) (6\text{\textasciitilde}1)\sim(6\text{\textasciitilde}2) (6~1)∼(6~2) 称为原问题可行条件， ( 6 ~ 3 ) ∼ ( 6 ~ 4 ) (6\text{\textasciitilde}3)\sim(6\text{\textasciitilde}4) (6~3)∼(6~4) 称为对偶可行条件， ( 6 ~ 5 ) (6\text{\textasciitilde}5) (6~5) 称为互补松弛条件。

我们虽然知道了问题具有强对偶性的前提，但是依然无法计算出最优解，而 KKT 条件的这一组方程就提供了求解方法。下面的讨论均以“原问题和对偶问题都有最优解”为前提。

两条关于 KKT 条件和强对偶性关系的基本定理：

任何具有强对偶性的问题的最优解均满足 KKT 条件。
在某些规范性条件成立的前提下，满足 KKT 条件的点才是问题的最优解；进一步，此时才能说明满足 KKT 条件可以推导出问题具有强对偶性，亦二者可以互相推导。

简而言之，任何情况下，强对偶性都可以推出 KKT 条件，但是只有在某些条件成立的前提下，KKT 条件才可以推出强对偶性，此时二者等价。我们只要保证规范性条件成立，就可以利用 KKT 条件计算最优解。

KKT 条件中五个式子 ( 6 ~ 1 ) ∼ ( 6 ~ 5 ) (6\text{\textasciitilde}1)\sim(6\text{\textasciitilde}5) (6~1)∼(6~5) 的推导。

假设 x ∗ x^* x∗ 为原始问题的极小值点， α ∗ \alpha^* α∗ 和 β ∗ \beta^* β∗ 为对偶问题的极大值点，对应的极值分别为 p ∗ p^* p∗ 和 d ∗ d^* d∗ 。根据强对偶性 d ∗ = p ∗ d^*=p^* d∗=p∗ 可以得到
f ( x ∗ ) = θ D ( α ∗ , β ∗ ) = min ⁡ x ( f ( x ) + ∑ i = 1 k α i ∗ g i ( x ) + ∑ j = 1 l β j ∗ h j ( x ) ) ≤ f ( x ∗ ) + ∑ i = 1 k α i ∗ g i ( x ∗ ) + ∑ j = 1 l β j ∗ h j ( x ∗ ) ≤ f ( x ∗ ) \begin{aligned} f(x^*) &=\theta_D(\alpha^*,\beta^*) \\ &=\min_x \Big( f(x) + \sum_{i=1}^k\alpha_i^* g_i(x) + \sum_{j=1}^l\beta_j^*h_j(x)\Big) \\ &\le f(x^*) + \sum_{i=1}^k\alpha_i^* g_i(x^*) + \sum_{j=1}^l\beta_j^* h_j(x^*)\\ &\le f(x^*) \end{aligned} f(x∗)=θD(α∗,β∗)=xmin(f(x)+i=1∑kαi∗gi(x)+j=1∑lβj∗hj(x))≤f(x∗)+i=1∑kαi∗gi(x∗)+j=1∑lβj∗hj(x∗)≤f(x∗)
显然上式中的不等号需要全部取等。观察第一个不等号处变为
min ⁡ x ( f ( x ) + ∑ i = 1 k α i ∗ g i ( x ) + ∑ j = 1 l β j ∗ h j ( x ) ) = f ( x ∗ ) + ∑ i = 1 k α i ∗ g i ( x ∗ ) + ∑ j = 1 l β j ∗ h j ( x ∗ ) \min_x \Big( f(x) + \sum_{i=1}^k\alpha_i^* g_i(x) + \sum_{j=1}^l\beta_j^*h_j(x)\Big) = f(x^*) + \sum_{i=1}^k\alpha_i^* g_i(x^*) + \sum_{j=1}^l\beta_j^* h_j(x^*) xmin(f(x)+i=1∑kαi∗gi(x)+j=1∑lβj∗hj(x))=f(x∗)+i=1∑kαi∗gi(x∗)+j=1∑lβj∗hj(x∗)
可见， x ∗ x^* x∗ 是 L ( x , α ∗ , β ∗ ) L(x,\alpha^*,\beta^*) L(x,α∗,β∗) 的一个极值点，故 L ( x , α ∗ , β ∗ ) L(x,\alpha^*,\beta^*) L(x,α∗,β∗) 在 x ∗ x^* x∗ 处的梯度为零，即
∇ x f ( x ∗ ) + ∑ i = 1 k α i ∗ ∇ x g i ( x ∗ ) + ∑ j = 1 l β j ∗ ∇ x h j ( x ∗ ) = 0 \nabla_x f(x^*) + \sum_{i=1}^k\alpha_i^* \nabla_x g_i(x^*) + \sum_{j=1}^l\beta_j^* \nabla_xh_j(x^*)=0 ∇xf(x∗)+i=1∑kαi∗∇xgi(x∗)+j=1∑lβj∗∇xhj(x∗)=0
这与式 ( 6 ~ 3 ) (6\text{\textasciitilde}3) (6~3) 一致。

观察第二个不等号处变为
f ( x ∗ ) + ∑ i = 1 k α i ∗ g i ( x ∗ ) + ∑ j = 1 l β j ∗ h j ( x ∗ ) = f ( x ∗ ) ∑ i = 1 k α i ∗ g i ( x ∗ ) + ∑ j = 1 l β j ∗ h j ( x ∗ ) = 0 \begin{aligned} f(x^*) + \sum_{i=1}^k\alpha_i^* g_i(x^*) + \sum_{j=1}^l\beta_j^* h_j(x^*) &= f(x^*) \\ \sum_{i=1}^k\alpha_i^* g_i(x^*) + \sum_{j=1}^l\beta_j^* h_j(x^*) &=0 \end{aligned} f(x∗)+i=1∑kαi∗gi(x∗)+j=1∑lβj∗hj(x∗)i=1∑kαi∗gi(x∗)+j=1∑lβj∗hj(x∗)=f(x∗)=0
因为 x ∗ x^* x∗ 一定在可行域内，所以等式约束条件对应的项 ∑ j = 1 l β j ∗ h j ( x ∗ ) = 0 \sum_{j=1}^l\beta_j^* h_j(x^*)=0 ∑j=1lβj∗hj(x∗)=0，故 ∑ i = 1 k α i ∗ g i ( x ∗ ) = 0 \sum_{i=1}^k\alpha_i^* g_i(x^*) =0 ∑i=1kαi∗gi(x∗)=0。又因为 α i g i ( x ) ≤ 0 \alpha_ig_i(x)\le 0 αigi(x)≤0，所以
α i ∗ g i ( x ∗ ) = 0 , i = 1 , 2 , … , k \alpha_i^*g_i(x^*)=0,\space\space\space\space\space\space\space\space\space i=1,2,\dots,k αi∗gi(x∗)=0, i=1,2,…,k
这与互补松弛条件式 ( 6 ~ 5 ) (6\text{\textasciitilde}5) (6~5) 一致。其他 KKT 条件， ( 6 ~ 1 ) (6\text{\textasciitilde}1) (6~1)、 ( 6 ~ 2 ) (6\text{\textasciitilde}2) (6~2) 和 ( 6 ~ 4 ) (6\text{\textasciitilde}4) (6~4) 均为显而易见的条件，联立这些条件得到完整 KKT 条件。

特别指出，由互补松弛条件式 ( 6 ~ 5 ) (6\text{\textasciitilde}5) (6~5) 可知，若 α i ∗ > 0 \alpha_i^*>0 αi∗>0，则 g i ( x ∗ ) = 0 g_i(x^*)=0 gi(x∗)=0；若 g i ( x ∗ ) < 0 g_i(x^*)<0 gi(x∗)<0，则 α i ∗ = 0 \alpha_i^*=0 αi∗=0。